Compressed sparse graph routines (scipy.sparse.csgraph)#
Fast graph algorithms based on sparse matrix representations.
Contents#
| Analyze the connected components of a sparse graph |
| Return the Laplacian of a directed graph. |
| Perform a shortest-path graph search on a positive directed or undirected graph. |
| Dijkstra algorithm using priority queue |
| Compute the shortest path lengths using the Floyd-Warshall algorithm |
| Compute the shortest path lengths using the Bellman-Ford algorithm. |
| Compute the shortest path lengths using Johnson's algorithm. |
| Yen's K-Shortest Paths algorithm on a directed or undirected graph. |
| Return a breadth-first ordering starting with specified node. |
| Return a depth-first ordering starting with specified node. |
| Return the tree generated by a breadth-first search |
| Return a tree generated by a depth-first search. |
| Return a minimum spanning tree of an undirected graph |
| Returns the permutation array that orders a sparse CSR or CSC matrix in Reverse-Cuthill McKee ordering. |
| Maximize the flow between two vertices in a graph. |
| Returns a matching of a bipartite graph whose cardinality is at least that of any given matching of the graph. |
| Returns the minimum weight full matching of a bipartite graph. |
| Compute the structural rank of a graph (matrix) with a given sparsity pattern. |
|
| Construct distance matrix from a predecessor matrix |
| Construct a CSR-format sparse graph from a dense matrix. |
| Construct a CSR-format graph from a masked array. |
| Construct a masked array graph representation from a dense matrix. |
| Convert a sparse graph representation to a dense representation |
| Convert a sparse graph representation to a masked array representation |
| Construct a tree from a graph and a predecessor list. |
Graph Representations#
This module uses graphs which are stored in a matrix format. Agraph with N nodes can be represented by an (N x N) adjacency matrix G.If there is a connection from node i to node j, then G[i, j] = w, wherew is the weight of the connection. For nodes i and j which arenot connected, the value depends on the representation:
for dense array representations, non-edges are represented byG[i, j] = 0, infinity, or NaN.
for dense masked representations (of type np.ma.MaskedArray), non-edgesare represented by masked values. This can be useful when graphs withzero-weight edges are desired.
for sparse array representations, non-edges are represented bynon-entries in the matrix. This sort of sparse representation alsoallows for edges with zero weights.
As a concrete example, imagine that you would like to represent the followingundirected graph:
G(0)/ \12/ \(2)(1)
This graph has three nodes, where node 0 and 1 are connected by an edge ofweight 2, and nodes 0 and 2 are connected by an edge of weight 1.We can construct the dense, masked, and sparse representations as follows,keeping in mind that an undirected graph is represented by a symmetric matrix:
>>>importnumpyasnp>>>G_dense=np.array([[0,2,1],...[2,0,0],...[1,0,0]])>>>G_masked=np.ma.masked_values(G_dense,0)>>>fromscipy.sparseimportcsr_array>>>G_sparse=csr_array(G_dense)
This becomes more difficult when zero edges are significant. For example,consider the situation when we slightly modify the above graph:
G2(0)/ \02/ \(2)(1)
This is identical to the previous graph, except nodes 0 and 2 are connectedby an edge of zero weight. In this case, the dense representation aboveleads to ambiguities: how can non-edges be represented if zero is a meaningfulvalue? In this case, either a masked or sparse representation must be usedto eliminate the ambiguity:
>>>importnumpyasnp>>>G2_data=np.array([[np.inf,2,0],...[2,np.inf,np.inf],...[0,np.inf,np.inf]])>>>G2_masked=np.ma.masked_invalid(G2_data)>>>fromscipy.sparse.csgraphimportcsgraph_from_dense>>># G2_sparse = csr_array(G2_data) would give the wrong result>>>G2_sparse=csgraph_from_dense(G2_data,null_value=np.inf)>>>G2_sparse.dataarray([ 2., 0., 2., 0.])
Here we have used a utility routine from the csgraph submodule in order toconvert the dense representation to a sparse representation which can beunderstood by the algorithms in submodule. By viewing the data array, wecan see that the zero values are explicitly encoded in the graph.
Directed vs. undirected#
Matrices may represent either directed or undirected graphs. This isspecified throughout the csgraph module by a boolean keyword. Graphs areassumed to be directed by default. In a directed graph, traversal from nodei to node j can be accomplished over the edge G[i, j], but not the edgeG[j, i]. Consider the following dense graph:
>>>importnumpyasnp>>>G_dense=np.array([[0,1,0],...[2,0,3],...[0,4,0]])
Whendirected=True we get the graph:
---1-->---3-->(0)(1)(2)<--2---<--4---
In a non-directed graph, traversal from node i to node j can beaccomplished over either G[i, j] or G[j, i]. If both edges are not null,and the two have unequal weights, then the smaller of the two is used.
So for the same graph, whendirected=False we get the graph:
(0)--1--(1)--3--(2)
Note that a symmetric matrix will represent an undirected graph, regardlessof whether the ‘directed’ keyword is set to True or False. In this case,usingdirected=True generally leads to more efficient computation.
The routines in this module accept as input either scipy.sparse representations(csr, csc, or lil format), masked representations, or dense representationswith non-edges indicated by zeros, infinities, and NaN entries.