pyamg.graph#
Algorithms related to graphs.
Functions
|
Return (square) matrix as sparse. |
|
Bellman-Ford iteration. |
|
Breadth First search of a graph. |
Compute the connected components of a graph. |
|
|
Perform Lloyd clustering on graph with weighted edges. |
|
Compute a maximal independent vertex set for a graph. |
Find a pseudo peripheral node. |
|
Symmetric Reverse Cutthill-McKee. |
|
|
Compute a vertex coloring of a graph. |
- pyamg.graph.bellman_ford(G, seeds)[source]#
Bellman-Ford iteration.
- Parameters:
- Gsparse matrix
Directed graph with positive weights.
- seedslist
Starting seeds
- Returns:
- distancesarray
Distance of each point to the nearest seed
- nearest_seedarray
Index of the nearest seed
See also
scipy.sparse.csgraph.bellman_ford
Notes
This should be viewed as the transpose of Bellman-Ford in scipy.sparse.csgraph. Here, bellman_ford is used to find the shortest path from any point to the seeds. In csgraph, bellman_ford is used to find “the shortest distance from point i to point j”. So csgraph.bellman_ford could be run for seed in seeds. Also note that test_graph.py tests against csgraph.bellman_ford(G.T).
- pyamg.graph.breadth_first_search(G, seed)[source]#
Breadth First search of a graph.
- Parameters:
- Gcsr_array, csc_array
A sparse NxN matrix where each nonzero entry G[i,j] is the distance between nodes i and j.
- seedint
Index of the seed location
- Returns:
- orderint array
Breadth first order
- levelint array
Final levels
Examples
0—2 | / | / 1—4—7—8—9 | /| / | / | / 3/ 6/ | | 5 >>> import numpy as np >>> import pyamg >>> import scipy.sparse as sparse >>> edges = np.array([[0,1],[0,2],[1,2],[1,3],[1,4],[3,4],[3,5], … [4,6], [4,7], [6,7], [7,8], [8,9]], dtype=np.int32) >>> N = np.max(edges.ravel())+1 >>> data = np.ones((edges.shape[0],)) >>> A = sparse.coo_array((data, (edges[:,0], edges[:,1])), shape=(N,N)) >>> c, l = pyamg.graph.breadth_first_search(A, 0) >>> print(l) [0 1 1 2 2 3 3 3 4 5] >>> print(c) [0 1 2 3 4 5 6 7 8 9]
- pyamg.graph.connected_components(G)[source]#
Compute the connected components of a graph.
The connected components of a graph G, which is represented by a symmetric sparse matrix, are labeled with the integers 0,1,..(K-1) where K is the number of components.
- Parameters:
- Gsymmetric matrix, preferably in sparse CSR or CSC format
The nonzeros of G represent the edges of an undirected graph.
- Returns:
- componentsndarray
An array of component labels for each vertex of the graph.
Notes
If the nonzero structure of G is not symmetric, then the result is undefined.
Examples
>>> from pyamg.graph import connected_components >>> print(connected_components( [[0,1,0],[1,0,1],[0,1,0]] )) [0 0 0] >>> print(connected_components( [[0,1,0],[1,0,0],[0,0,0]] )) [0 0 1] >>> print(connected_components( [[0,0,0],[0,0,0],[0,0,0]] )) [0 1 2] >>> print(connected_components( [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]] )) [0 0 1 1]
- pyamg.graph.lloyd_cluster(G, seeds, maxiter=10)[source]#
Perform Lloyd clustering on graph with weighted edges.
- Parameters:
- Gcsr_array, csc_array
A sparse NxN matrix where each nonzero entry G[i,j] is the distance between nodes i and j.
- seedsint array
If seeds is an integer, then its value determines the number of clusters. Otherwise, seeds is an array of unique integers between 0 and N-1 that will be used as the initial seeds for clustering.
- maxiterint
The maximum number of iterations to perform.
- Returns:
- distancesarray
final distances
- clustersint array
id of each cluster of points
- seedsint array
index of each seed
Notes
If G has complex values, abs(G) is used instead.
- pyamg.graph.maximal_independent_set(G, algo='serial', k=None)[source]#
Compute a maximal independent vertex set for a graph.
- Parameters:
- Gsparse matrix
Symmetric matrix, preferably in sparse CSR or CSC format The nonzeros of G represent the edges of an undirected graph.
- algo{‘serial’, ‘parallel’}
- Algorithm used to compute the MIS
serial : greedy serial algorithm
parallel : variant of Luby’s parallel MIS algorithm
- kint
Minimum separation between MIS vertices
- Returns:
- Sarray
S[i] = 1 if vertex i is in the MIS S[i] = 0 otherwise
Notes
Diagonal entries in the G (self loops) will be ignored.
Luby’s algorithm is significantly more expensive than the greedy serial algorithm.
- pyamg.graph.pseudo_peripheral_node(A)[source]#
Find a pseudo peripheral node.
- Parameters:
- Asparse matrix
Sparse matrix
- Returns:
- xint
Location of the node
- orderarray
BFS ordering
- levelarray
BFS levels
Notes
Algorithm in Saad
- pyamg.graph.symmetric_rcm(A)[source]#
Symmetric Reverse Cutthill-McKee.
- Parameters:
- Asparse matrix
Sparse matrix
- Returns:
- Bsparse matrix
Permuted matrix with reordering
See also
Notes
Get a pseudo-peripheral node, then call BFS
Examples
>>> from pyamg import gallery >>> from pyamg.graph import symmetric_rcm >>> n = 200 >>> density = 1.0/n >>> A = gallery.sprand(n, n, density, format='csr') >>> S = A + A.T >>> # try the visualizations >>> # import matplotlib.pyplot as plt >>> # plt.figure() >>> # plt.subplot(121) >>> # plt.spy(S,marker='.') >>> # plt.subplot(122) >>> # plt.spy(symmetric_rcm(S),marker='.')
- pyamg.graph.vertex_coloring(G, method='MIS')[source]#
Compute a vertex coloring of a graph.
- Parameters:
- Gsparse matrix
Symmetric matrix, preferably in sparse CSR or CSC format The nonzeros of G represent the edges of an undirected graph.
- methodstring
Algorithm used to compute the vertex coloring:
‘MIS’ - Maximal Independent Set
‘JP’ - Jones-Plassmann (parallel)
‘LDF’ - Largest-Degree-First (parallel)
- Returns:
- coloringarray
An array of vertex colors (integers beginning at 0)
Notes
Diagonal entries in the G (self loops) will be ignored.