pyamg.graph#
Algorithms related to graphs.
Functions

Return (square) matrix as sparse. 

BellmanFord 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 CutthillMcKee. 


Compute a vertex coloring of a graph. 
 pyamg.graph.bellman_ford(G, seeds)[source]#
BellmanFord 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 BellmanFord 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_matrix, csc_matrix
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]]) >>> N = np.max(edges.ravel())+1 >>> data = np.ones((edges.shape[0],)) >>> A = sparse.coo_matrix((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,..(K1) 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_matrix, csc_matrix
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 N1 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
 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 CutthillMcKee.
 Parameters:
 Asparse matrix
Sparse matrix
 Returns:
 Bsparse matrix
Permuted matrix with reordering
See also
Notes
Get a pseudoperipheral 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’  JonesPlassmann (parallel)
‘LDF’  LargestDegreeFirst (parallel)
 Returns:
 coloringarray
An array of vertex colors (integers beginning at 0)
Notes
Diagonal entries in the G (self loops) will be ignored.