# pyamg.graph#

Algorithms related to graphs.

Functions

 Return (square) matrix as sparse. `bellman_ford`(G, seeds) Bellman-Ford iteration. `breadth_first_search`(G, seed) Breadth First search of a graph. 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. Find a pseudo peripheral node. 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

`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).

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

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,)) >>> 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

Locaiton of the node

orderarray

BFS ordering

levelarray

BFS levels

Notes

pyamg.graph.symmetric_rcm(A)[source]#

Symmetric Reverse Cutthill-McKee.

Parameters:
Asparse matrix

Sparse matrix

Returns:
Bsparse matrix

Permuted matrix with reordering

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.