pyamg.graph#

Algorithms related to graphs.

Functions

_choice(p)

Random selection based on a distribution.

_elimination_penalty(A, m, d, dist_all, ...)

Calculate elimination penalty.

_rebalance(G, c, m, d, dist_all, num_clusters)

Rebalance clusters.

_split_improvement(m, d, dist_all, num_clusters)

Calculate split improvement.

asgraph(G)

Return (square) array as sparse.

balanced_lloyd_cluster(G, centers[, ...])

Perform Lloyd clustering on graph with weighted edges.

bellman_ford(G, centers[, method, tiebreaking])

Bellman-Ford iteration.

breadth_first_search(G, seed)

Breadth First search of a graph.

connected_components(G)

Compute the connected components of a graph.

kmeanspp_seed(G, nseeds)

K-means++ seed.

lloyd_cluster(G, centers[, maxiter])

Perform Lloyd clustering on graph with weighted edges.

maximal_independent_set(G[, algo, k])

Compute a maximal independent vertex set for a graph.

metis_partition(G[, nparts, seed])

Perform partitioning of graph with weighted edges using METIS.

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._choice(p)[source]#

Random selection based on a distribution.

Parameters:
parray

Probabilities [0,1], with sum(p) == 1.

Notes

For efficiency, there are no checks.

pyamg.graph._elimination_penalty(A, m, d, dist_all, num_clusters)[source]#

Calculate elimination penalty.

see _rebalance()

pyamg.graph._rebalance(G, c, m, d, dist_all, num_clusters)[source]#

Rebalance clusters.

Parameters:
Gsparray

Sparse graph.

carray

List of centers.

marray

Cluster membership.

darray

Distance to cluster center.

dist_allarray

Node-to-node distance for every node in each cluster.

num_clustersint

Number of clusters (= number centers).

pyamg.graph._split_improvement(m, d, dist_all, num_clusters)[source]#

Calculate split improvement.

see _rebalance()

pyamg.graph.asgraph(G)[source]#

Return (square) array as sparse.

Parameters:
Gsparray

Sparse matrix.

Returns:
csr_array or csc_array

Converted array.

pyamg.graph.balanced_lloyd_cluster(G, centers, maxiter=5, rebalance_iters=5, tiebreaking=True)[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.

centersint array

If centers is an integer, then its value determines the number of clusters. Otherwise, centers is an array of unique integers between 0 and n-1 that will be used as the initial centers for clustering.

maxiterint

Number of bellman_ford_balanced->center_nodes iterations to run within the clustering.

rebalance_itersint

Number of post-Lloyd rebalancing iterations to run.

tiebreakingbool, default True

Flag for triggering tiebreaking.

Returns:
clustersint array

id of each cluster of points

centersint array

index of each center

Notes

  • If G has complex values, abs(G) is used instead.

  • Only positive edge weights may be used

  • This version computes improved cluster centers with Floyd-Warshall and also uses a balanced version of Bellman-Ford to try and find nearly-equal-sized clusters.

  • Repeated calls to bellman_ford_balanced() in the rebalance loop can result in different centers. This is due to the tie-breaker based on aggregate size in bellman_ford_balanced(). Alternatively, the graph can be seeded with a small random number to make the edge lengths (and distances) unique.

pyamg.graph.bellman_ford(G, centers, method='standard', tiebreaking=True)[source]#

Bellman-Ford iteration.

Parameters:
Gsparray

Directed graph with positive weights.

centerslist

Starting centers or source nodes.

methodstr

  • ‘standard’: base implementation of Bellman-Ford.

  • ‘balanced’: a balanced version of Bellman-Ford.

tiebreakingbool

Tie break flag if method='balanced'.

Returns:
array

Distance of each point to the nearest center.

array

Index of the nearest center.

array

Predecessors in the array.

See also

pyamg.amg_core.bellman_ford
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_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:
ndarray

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.kmeanspp_seed(G, nseeds)[source]#

K-means++ seed.

Parameters:
Gsparray

Sparse graph on which to seed.

nseedsint

Number of seeds.

Notes

This is a reference algorithms, at O(n^3).

TODO - needs testing

pyamg.graph.lloyd_cluster(G, centers, maxiter=5)[source]#

Perform Lloyd clustering on graph with weighted edges.

Parameters:
Gcsr_array, csc_array

A sparse matrix of size (n,n) where each nonzero entry G[i,j] is the distance between nodes i and j.

centersint array

If centers is an integer, then its value determines the number of clusters. Otherwise, centers is an array of unique integers between 0 and n-1 that will be used as the initial centers for clustering.

maxiterint

Maximum number of iterations.

Returns:
int array

Id of each cluster of points.

int array

Index of each seed.

Notes

If G has complex values, abs(G) is used instead.

Only positive edge weights may be used

pyamg.graph.maximal_independent_set(G, algo='serial', k=None)[source]#

Compute a maximal independent vertex set for a graph.

Parameters:
Gsparray

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:
array

  • 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.metis_partition(G, nparts=5, seed=None)[source]#

Perform partitioning of graph with weighted edges using METIS.

Parameters:
Gsparray

A sparse n x n matrix where each nonzero entry G[i,j] is the distance between nodes i and j. G[i,j] is required to be integer.

npartsint

Number of parts in the resulting partition.

seedint

Random seed for METIS.

Returns:
array

Array of n x 1 indices from 0 … nparts-1.

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

Find a pseudo peripheral node.

Parameters:
Asparray

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:
Asparray

Sparse matrix.

Returns:
sparray

Permuted matrix with reordering.

See also

pseudo_peripheral_node

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:
Gsparray

Symmetric matrix, preferably in sparse CSR or CSC format The nonzeros of G represent the edges of an undirected graph.

methodstr

Algorithm used to compute the vertex coloring:

  • ‘MIS’ - Maximal Independent Set

  • ‘JP’ - Jones-Plassmann (parallel)

  • ‘LDF’ - Largest-Degree-First (parallel)

Returns:
array

An array of vertex colors (integers beginning at 0).

Notes

Diagonal entries in the G (self loops) will be ignored.