本文整理汇总了Python中networkx.utils.reverse_cuthill_mckee_ordering函数的典型用法代码示例。如果您正苦于以下问题:Python reverse_cuthill_mckee_ordering函数的具体用法?Python reverse_cuthill_mckee_ordering怎么用?Python reverse_cuthill_mckee_ordering使用的例子?那么恭喜您, 这里精选的函数代码示例或许可以为您提供帮助。
在下文中一共展示了reverse_cuthill_mckee_ordering函数的12个代码示例,这些例子默认根据受欢迎程度排序。您可以为喜欢或者感觉有用的代码点赞,您的评价将有助于我们的系统推荐出更棒的Python代码示例。
示例1: test_reverse_cuthill_mckee
def test_reverse_cuthill_mckee():
# example nxgraph from
# http://www.boost.org/doc/libs/1_37_0/libs/nxgraph/example/cuthill_mckee_ordering.cpp
G = nx.Graph([(0,3),(0,5),(1,2),(1,4),(1,6),(1,9),(2,3),
(2,4),(3,5),(3,8),(4,6),(5,6),(5,7),(6,7)])
rcm = list(reverse_cuthill_mckee_ordering(G,start=0))
assert_equal(rcm,[9, 1, 4, 6, 7, 2, 8, 5, 3, 0])
rcm = list(reverse_cuthill_mckee_ordering(G))
assert_equal(rcm,[0, 8, 5, 7, 3, 6, 4, 2, 1, 9])
开发者ID:NikitaVAP,项目名称:pycdb,代码行数:9,代码来源:test_rcm.py
示例2: test_rcm_alternate_heuristic
def test_rcm_alternate_heuristic():
# example from
G = nx.Graph([(0, 0),
(0, 4),
(1, 1),
(1, 2),
(1, 5),
(1, 7),
(2, 2),
(2, 4),
(3, 3),
(3, 6),
(4, 4),
(5, 5),
(5, 7),
(6, 6),
(7, 7)])
answers = [[6, 3, 5, 7, 1, 2, 4, 0], [6, 3, 7, 5, 1, 2, 4, 0],
[7, 5, 1, 2, 4, 0, 6, 3]]
def smallest_degree(G):
deg, node = min((d, n) for n, d in G.degree())
return node
rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree))
assert_true(rcm in answers)
开发者ID:AmesianX,项目名称:networkx,代码行数:26,代码来源:test_rcm.py
示例3: test_rcm_alternate_heuristic
def test_rcm_alternate_heuristic():
# example from
G = nx.Graph([(0, 0),
(0, 4),
(1, 1),
(1, 2),
(1, 5),
(1, 7),
(2, 2),
(2, 4),
(3, 3),
(3, 6),
(4, 4),
(5, 5),
(5, 7),
(6, 6),
(7, 7)])
answers = [[6, 3, 5, 7, 1, 2, 4, 0], [6, 3, 7, 5, 1, 2, 4, 0]]
def smallest_degree(G):
node, deg = min(G.degree().items(), key=lambda x: x[1])
return node
rcm = list(reverse_cuthill_mckee_ordering(G, heuristic=smallest_degree))
assert_true(rcm in answers)
开发者ID:666888,项目名称:networkx,代码行数:25,代码来源:test_rcm.py
示例4: test_reverse_cuthill_mckee
def test_reverse_cuthill_mckee():
# example graph from
# http://www.boost.org/doc/libs/1_37_0/libs/graph/example/cuthill_mckee_ordering.cpp
G = nx.Graph([(0, 3), (0, 5), (1, 2), (1, 4), (1, 6), (1, 9), (2, 3),
(2, 4), (3, 5), (3, 8), (4, 6), (5, 6), (5, 7), (6, 7)])
rcm = list(reverse_cuthill_mckee_ordering(G))
assert_true(rcm in [[0, 8, 5, 7, 3, 6, 2, 4, 1, 9],
[0, 8, 5, 7, 3, 6, 4, 2, 1, 9]])
开发者ID:AmesianX,项目名称:networkx,代码行数:8,代码来源:test_rcm.py
示例5: _rcm_estimate
def _rcm_estimate(G, nodelist):
"""Estimate the Fiedler vector using the reverse Cuthill-McKee ordering.
"""
G = G.subgraph(nodelist)
order = reverse_cuthill_mckee_ordering(G)
n = len(nodelist)
index = dict(zip(nodelist, range(n)))
x = ndarray(n, dtype=float)
for i, u in enumerate(order):
x[index[u]] = i
x -= (n - 1) / 2.
return x
开发者ID:4c656554,项目名称:networkx,代码行数:12,代码来源:algebraicconnectivity.py
示例6: edge_current_flow_betweenness_centrality
def edge_current_flow_betweenness_centrality(G, normalized=True,
weight='weight',
dtype=float, solver='full'):
"""Compute current-flow betweenness centrality for edges.
Current-flow betweenness centrality uses an electrical current
model for information spreading in contrast to betweenness
centrality which uses shortest paths.
Current-flow betweenness centrality is also known as
random-walk betweenness centrality [2]_.
Parameters
----------
G : graph
A NetworkX graph
normalized : bool, optional (default=True)
If True the betweenness values are normalized by 2/[(n-1)(n-2)] where
n is the number of nodes in G.
weight : string or None, optional (default='weight')
Key for edge data used as the edge weight.
If None, then use 1 as each edge weight.
dtype: data type (float)
Default data type for internal matrices.
Set to np.float32 for lower memory consumption.
solver: string (default='lu')
Type of linear solver to use for computing the flow matrix.
Options are "full" (uses most memory), "lu" (recommended), and
"cg" (uses least memory).
Returns
-------
nodes : dictionary
Dictionary of edge tuples with betweenness centrality as the value.
See Also
--------
betweenness_centrality
edge_betweenness_centrality
current_flow_betweenness_centrality
Notes
-----
Current-flow betweenness can be computed in `O(I(n-1)+mn \log n)`
time [1]_, where `I(n-1)` is the time needed to compute the
inverse Laplacian. For a full matrix this is `O(n^3)` but using
sparse methods you can achieve `O(nm{\sqrt k})` where `k` is the
Laplacian matrix condition number.
The space required is `O(nw) where `w` is the width of the sparse
Laplacian matrix. Worse case is `w=n` for `O(n^2)`.
If the edges have a 'weight' attribute they will be used as
weights in this algorithm. Unspecified weights are set to 1.
References
----------
.. [1] Centrality Measures Based on Current Flow.
Ulrik Brandes and Daniel Fleischer,
Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf
.. [2] A measure of betweenness centrality based on random walks,
M. E. J. Newman, Social Networks 27, 39-54 (2005).
"""
from networkx.utils import reverse_cuthill_mckee_ordering
try:
import numpy as np
except ImportError:
raise ImportError('current_flow_betweenness_centrality requires NumPy ',
'http://scipy.org/')
try:
import scipy
except ImportError:
raise ImportError('current_flow_betweenness_centrality requires SciPy ',
'http://scipy.org/')
if G.is_directed():
raise nx.NetworkXError('edge_current_flow_betweenness_centrality ',
'not defined for digraphs.')
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected.")
n = G.number_of_nodes()
ordering = list(reverse_cuthill_mckee_ordering(G))
# make a copy with integer labels according to rcm ordering
# this could be done without a copy if we really wanted to
H = nx.relabel_nodes(G,dict(zip(ordering,range(n))))
betweenness=(dict.fromkeys(H.edges(),0.0))
if normalized:
nb=(n-1.0)*(n-2.0) # normalization factor
else:
nb=2.0
for row,(e) in flow_matrix_row(H, weight=weight, dtype=dtype,
solver=solver):
pos=dict(zip(row.argsort()[::-1],range(1,n+1)))
for i in range(n):
#.........这里部分代码省略.........
开发者ID:666888,项目名称:networkx,代码行数:101,代码来源:current_flow_betweenness.py
示例7: approximate_current_flow_betweenness_centrality
def approximate_current_flow_betweenness_centrality(G, normalized=True,
weight='weight',
dtype=float, solver='full',
epsilon=0.5, kmax=10000):
r"""Compute the approximate current-flow betweenness centrality for nodes.
Approximates the current-flow betweenness centrality within absolute
error of epsilon with high probability [1]_.
Parameters
----------
G : graph
A NetworkX graph
normalized : bool, optional (default=True)
If True the betweenness values are normalized by 2/[(n-1)(n-2)] where
n is the number of nodes in G.
weight : string or None, optional (default='weight')
Key for edge data used as the edge weight.
If None, then use 1 as each edge weight.
dtype: data type (float)
Default data type for internal matrices.
Set to np.float32 for lower memory consumption.
solver: string (default='lu')
Type of linear solver to use for computing the flow matrix.
Options are "full" (uses most memory), "lu" (recommended), and
"cg" (uses least memory).
epsilon: float
Absolute error tolerance.
kmax: int
Maximum number of sample node pairs to use for approximation.
Returns
-------
nodes : dictionary
Dictionary of nodes with betweenness centrality as the value.
See Also
--------
current_flow_betweenness_centrality
Notes
-----
The running time is `O((1/\epsilon^2)m{\sqrt k} \log n)`
and the space required is `O(m)` for n nodes and m edges.
If the edges have a 'weight' attribute they will be used as
weights in this algorithm. Unspecified weights are set to 1.
References
----------
.. [1] Ulrik Brandes and Daniel Fleischer:
Centrality Measures Based on Current Flow.
Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf
"""
from networkx.utils import reverse_cuthill_mckee_ordering
try:
import numpy as np
except ImportError:
raise ImportError('current_flow_betweenness_centrality requires NumPy ',
'http://scipy.org/')
try:
from scipy import sparse
from scipy.sparse import linalg
except ImportError:
raise ImportError('current_flow_betweenness_centrality requires SciPy ',
'http://scipy.org/')
if G.is_directed():
raise nx.NetworkXError('current_flow_betweenness_centrality() ',
'not defined for digraphs.')
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected.")
solvername={"full" :FullInverseLaplacian,
"lu": SuperLUInverseLaplacian,
"cg": CGInverseLaplacian}
n = G.number_of_nodes()
ordering = list(reverse_cuthill_mckee_ordering(G))
# make a copy with integer labels according to rcm ordering
# this could be done without a copy if we really wanted to
H = nx.relabel_nodes(G,dict(zip(ordering,range(n))))
L = laplacian_sparse_matrix(H, nodelist=range(n), weight=weight,
dtype=dtype, format='csc')
C = solvername[solver](L, dtype=dtype) # initialize solver
betweenness = dict.fromkeys(H,0.0)
nb = (n-1.0)*(n-2.0) # normalization factor
cstar = n*(n-1)/nb
l = 1 # parameter in approximation, adjustable
k = l*int(np.ceil((cstar/epsilon)**2*np.log(n)))
if k > kmax:
raise nx.NetworkXError('Number random pairs k>kmax (%d>%d) '%(k,kmax),
'Increase kmax or epsilon')
cstar2k = cstar/(2*k)
#.........这里部分代码省略.........
开发者ID:666888,项目名称:networkx,代码行数:101,代码来源:current_flow_betweenness.py
示例8: current_flow_closeness_centrality
def current_flow_closeness_centrality(G, weight='weight',
dtype=float, solver='lu'):
"""Compute current-flow closeness centrality for nodes.
Current-flow closeness centrality is variant of closeness
centrality based on effective resistance between nodes in
a network. This metric is also known as information centrality.
Parameters
----------
G : graph
A NetworkX graph
dtype: data type (float)
Default data type for internal matrices.
Set to np.float32 for lower memory consumption.
solver: string (default='lu')
Type of linear solver to use for computing the flow matrix.
Options are "full" (uses most memory), "lu" (recommended), and
"cg" (uses least memory).
Returns
-------
nodes : dictionary
Dictionary of nodes with current flow closeness centrality as the value.
See Also
--------
closeness_centrality
Notes
-----
The algorithm is from Brandes [1]_.
See also [2]_ for the original definition of information centrality.
References
----------
.. [1] Ulrik Brandes and Daniel Fleischer,
Centrality Measures Based on Current Flow.
Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
http://www.inf.uni-konstanz.de/algo/publications/bf-cmbcf-05.pdf
.. [2] Karen Stephenson and Marvin Zelen:
Rethinking centrality: Methods and examples.
Social Networks 11(1):1-37, 1989.
http://dx.doi.org/10.1016/0378-8733(89)90016-6
"""
from networkx.utils import reverse_cuthill_mckee_ordering
import numpy as np
import scipy
if G.is_directed():
raise nx.NetworkXError(
"current_flow_closeness_centrality() not defined for digraphs.")
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected.")
solvername = {"full": FullInverseLaplacian,
"lu": SuperLUInverseLaplacian,
"cg": CGInverseLaplacian}
n = G.number_of_nodes()
ordering = list(reverse_cuthill_mckee_ordering(G))
# make a copy with integer labels according to rcm ordering
# this could be done without a copy if we really wanted to
H = nx.relabel_nodes(G, dict(zip(ordering, range(n))))
betweenness = dict.fromkeys(H, 0.0) # b[v]=0 for v in H
n = H.number_of_nodes()
L = laplacian_sparse_matrix(H, nodelist=range(n), weight=weight,
dtype=dtype, format='csc')
C2 = solvername[solver](L, width=1, dtype=dtype) # initialize solver
for v in H:
col = C2.get_row(v)
for w in H:
betweenness[v] += col[v]-2*col[w]
betweenness[w] += col[v]
for v in H:
betweenness[v] = 1.0 / (betweenness[v])
return dict((ordering[k], float(v)) for k, v in betweenness.items())
开发者ID:4c656554,项目名称:networkx,代码行数:81,代码来源:current_flow_closeness.py
示例9: current_flow_betweenness_centrality_subset
def current_flow_betweenness_centrality_subset(G, sources, targets,
normalized=True,
weight=None,
dtype=float, solver='lu'):
r"""Compute current-flow betweenness centrality for subsets of nodes.
Current-flow betweenness centrality uses an electrical current
model for information spreading in contrast to betweenness
centrality which uses shortest paths.
Current-flow betweenness centrality is also known as
random-walk betweenness centrality [2]_.
Parameters
----------
G : graph
A NetworkX graph
sources: list of nodes
Nodes to use as sources for current
targets: list of nodes
Nodes to use as sinks for current
normalized : bool, optional (default=True)
If True the betweenness values are normalized by b=b/(n-1)(n-2) where
n is the number of nodes in G.
weight : string or None, optional (default=None)
Key for edge data used as the edge weight.
If None, then use 1 as each edge weight.
dtype: data type (float)
Default data type for internal matrices.
Set to np.float32 for lower memory consumption.
solver: string (default='lu')
Type of linear solver to use for computing the flow matrix.
Options are "full" (uses most memory), "lu" (recommended), and
"cg" (uses least memory).
Returns
-------
nodes : dictionary
Dictionary of nodes with betweenness centrality as the value.
See Also
--------
approximate_current_flow_betweenness_centrality
betweenness_centrality
edge_betweenness_centrality
edge_current_flow_betweenness_centrality
Notes
-----
Current-flow betweenness can be computed in $O(I(n-1)+mn \log n)$
time [1]_, where $I(n-1)$ is the time needed to compute the
inverse Laplacian. For a full matrix this is $O(n^3)$ but using
sparse methods you can achieve $O(nm{\sqrt k})$ where $k$ is the
Laplacian matrix condition number.
The space required is $O(nw)$ where $w$ is the width of the sparse
Laplacian matrix. Worse case is $w=n$ for $O(n^2)$.
If the edges have a 'weight' attribute they will be used as
weights in this algorithm. Unspecified weights are set to 1.
References
----------
.. [1] Centrality Measures Based on Current Flow.
Ulrik Brandes and Daniel Fleischer,
Proc. 22nd Symp. Theoretical Aspects of Computer Science (STACS '05).
LNCS 3404, pp. 533-544. Springer-Verlag, 2005.
http://algo.uni-konstanz.de/publications/bf-cmbcf-05.pdf
.. [2] A measure of betweenness centrality based on random walks,
M. E. J. Newman, Social Networks 27, 39-54 (2005).
"""
from networkx.utils import reverse_cuthill_mckee_ordering
try:
import numpy as np
except ImportError:
raise ImportError('current_flow_betweenness_centrality requires NumPy ',
'http://scipy.org/')
try:
import scipy
except ImportError:
raise ImportError('current_flow_betweenness_centrality requires SciPy ',
'http://scipy.org/')
if not nx.is_connected(G):
raise nx.NetworkXError("Graph not connected.")
n = G.number_of_nodes()
ordering = list(reverse_cuthill_mckee_ordering(G))
# make a copy with integer labels according to rcm ordering
# this could be done without a copy if we really wanted to
mapping = dict(zip(ordering, range(n)))
H = nx.relabel_nodes(G, mapping)
betweenness = dict.fromkeys(H, 0.0) # b[v]=0 for v in H
for row, (s, t) in flow_matrix_row(H, weight=weight, dtype=dtype,
solver=solver):
#.........这里部分代码省略.........
开发者ID:ProgVal,项目名称:networkx,代码行数:101,代码来源:current_flow_betweenness_subset.py
示例10: Copyright
Cuthill-McKee ordering of matrices
The reverse Cuthill-McKee algorithm gives a sparse matrix ordering that
reduces the matrix bandwidth.
"""
# Copyright (C) 2011-2019 by
# Author: Aric Hagberg <[email protected]>
# BSD License
import networkx as nx
from networkx.utils import reverse_cuthill_mckee_ordering
import numpy as np
# build low-bandwidth numpy matrix
G = nx.grid_2d_graph(3, 3)
rcm = list(reverse_cuthill_mckee_ordering(G))
print("ordering", rcm)
print("unordered Laplacian matrix")
A = nx.laplacian_matrix(G)
x, y = np.nonzero(A)
#print("lower bandwidth:",(y-x).max())
#print("upper bandwidth:",(x-y).max())
print("bandwidth: %d" % ((y - x).max() + (x - y).max() + 1))
print(A)
B = nx.laplacian_matrix(G, nodelist=rcm)
print("low-bandwidth Laplacian matrix")
x, y = np.nonzero(B)
#print("lower bandwidth:",(y-x).max())
#print("upper bandwidth:",(x-y).max())
开发者ID:jg-you,项目名称:networkx,代码行数:31,代码来源:plot_rcm.py
示例11: rcm
def rcm(matrix):
"""Returns a reverse Cuthill-McKee reordering of the given matrix."""
G = nx.from_scipy_sparse_matrix(matrix)
rcm = reverse_cuthill_mckee_ordering(G)
return nx.to_scipy_sparse_matrix(G, nodelist=list(rcm), format='csr')
开发者ID:paul-g,项目名称:sparsegrind,代码行数:5,代码来源:reorder.py
示例12: rcm_min_degree
def rcm_min_degree(matrix):
"""Returns a reverse Cuthill-McKee reordering of the given matrix,
using the minimum degree heuristic."""
G = nx.from_scipy_sparse_matrix(matrix)
rcm = reverse_cuthill_mckee_ordering(G, heuristic=min_degree_heuristic)
return nx.to_scipy_sparse_matrix(G, nodelist=list(rcm), format='csr')
开发者ID:paul-g,项目名称:sparsegrind,代码行数:6,代码来源:reorder.py
注:本文中的networkx.utils.reverse_cuthill_mckee_ordering函数示例由纯净天空整理自Github/MSDocs等源码及文档管理平台,相关代码片段筛选自各路编程大神贡献的开源项目,源码版权归原作者所有,传播和使用请参考对应项目的License;未经允许,请勿转载。 |
请发表评论