pyamg.graph#

Algorithms related to graphs.

Functions

`asgraph`(G)	Return (square) matrix as sparse.
`bellman_ford`(G, seeds)	Bellman-Ford iteration.
`breadth_first_search`(G, seed)	Breadth First search of a graph.
`connected_components`(G)	Compute the connected components of a graph.
`lloyd_cluster`(G, seeds[, maxiter])	Perform Lloyd clustering on graph with weighted edges.
`maximal_independent_set`(G[, algo, k])	Compute a maximal independent vertex set for a graph.
`pseudo_peripheral_node`(A)	Find a pseudo peripheral node.
`symmetric_rcm`(A)	Symmetric Reverse Cutthill-McKee.
`vertex_coloring`(G[, method])	Compute a vertex coloring of a graph.

pyamg.graph.asgraph(G)[source]#: Return (square) matrix as sparse.

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_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,..(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_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 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

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