Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1r""" 

2Compressed sparse graph routines (:mod:`scipy.sparse.csgraph`) 

3============================================================== 

4 

5.. currentmodule:: scipy.sparse.csgraph 

6 

7Fast graph algorithms based on sparse matrix representations. 

8 

9Contents 

10-------- 

11 

12.. autosummary:: 

13 :toctree: generated/ 

14 

15 connected_components -- determine connected components of a graph 

16 laplacian -- compute the laplacian of a graph 

17 shortest_path -- compute the shortest path between points on a positive graph 

18 dijkstra -- use Dijkstra's algorithm for shortest path 

19 floyd_warshall -- use the Floyd-Warshall algorithm for shortest path 

20 bellman_ford -- use the Bellman-Ford algorithm for shortest path 

21 johnson -- use Johnson's algorithm for shortest path 

22 breadth_first_order -- compute a breadth-first order of nodes 

23 depth_first_order -- compute a depth-first order of nodes 

24 breadth_first_tree -- construct the breadth-first tree from a given node 

25 depth_first_tree -- construct a depth-first tree from a given node 

26 minimum_spanning_tree -- construct the minimum spanning tree of a graph 

27 reverse_cuthill_mckee -- compute permutation for reverse Cuthill-McKee ordering 

28 maximum_flow -- solve the maximum flow problem for a graph 

29 maximum_bipartite_matching -- compute a maximum matching of a bipartite graph 

30 structural_rank -- compute the structural rank of a graph 

31 NegativeCycleError 

32 

33.. autosummary:: 

34 :toctree: generated/ 

35 

36 construct_dist_matrix 

37 csgraph_from_dense 

38 csgraph_from_masked 

39 csgraph_masked_from_dense 

40 csgraph_to_dense 

41 csgraph_to_masked 

42 reconstruct_path 

43 

44Graph Representations 

45--------------------- 

46This module uses graphs which are stored in a matrix format. A 

47graph with N nodes can be represented by an (N x N) adjacency matrix G. 

48If there is a connection from node i to node j, then G[i, j] = w, where 

49w is the weight of the connection. For nodes i and j which are 

50not connected, the value depends on the representation: 

51 

52- for dense array representations, non-edges are represented by 

53 G[i, j] = 0, infinity, or NaN. 

54 

55- for dense masked representations (of type np.ma.MaskedArray), non-edges 

56 are represented by masked values. This can be useful when graphs with 

57 zero-weight edges are desired. 

58 

59- for sparse array representations, non-edges are represented by 

60 non-entries in the matrix. This sort of sparse representation also 

61 allows for edges with zero weights. 

62 

63As a concrete example, imagine that you would like to represent the following 

64undirected graph:: 

65 

66 G 

67 

68 (0) 

69 / \ 

70 1 2 

71 / \ 

72 (2) (1) 

73 

74This graph has three nodes, where node 0 and 1 are connected by an edge of 

75weight 2, and nodes 0 and 2 are connected by an edge of weight 1. 

76We can construct the dense, masked, and sparse representations as follows, 

77keeping in mind that an undirected graph is represented by a symmetric matrix:: 

78 

79 >>> G_dense = np.array([[0, 2, 1], 

80 ... [2, 0, 0], 

81 ... [1, 0, 0]]) 

82 >>> G_masked = np.ma.masked_values(G_dense, 0) 

83 >>> from scipy.sparse import csr_matrix 

84 >>> G_sparse = csr_matrix(G_dense) 

85 

86This becomes more difficult when zero edges are significant. For example, 

87consider the situation when we slightly modify the above graph:: 

88 

89 G2 

90 

91 (0) 

92 / \ 

93 0 2 

94 / \ 

95 (2) (1) 

96 

97This is identical to the previous graph, except nodes 0 and 2 are connected 

98by an edge of zero weight. In this case, the dense representation above 

99leads to ambiguities: how can non-edges be represented if zero is a meaningful 

100value? In this case, either a masked or sparse representation must be used 

101to eliminate the ambiguity:: 

102 

103 >>> G2_data = np.array([[np.inf, 2, 0 ], 

104 ... [2, np.inf, np.inf], 

105 ... [0, np.inf, np.inf]]) 

106 >>> G2_masked = np.ma.masked_invalid(G2_data) 

107 >>> from scipy.sparse.csgraph import csgraph_from_dense 

108 >>> # G2_sparse = csr_matrix(G2_data) would give the wrong result 

109 >>> G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf) 

110 >>> G2_sparse.data 

111 array([ 2., 0., 2., 0.]) 

112 

113Here we have used a utility routine from the csgraph submodule in order to 

114convert the dense representation to a sparse representation which can be 

115understood by the algorithms in submodule. By viewing the data array, we 

116can see that the zero values are explicitly encoded in the graph. 

117 

118Directed vs. undirected 

119^^^^^^^^^^^^^^^^^^^^^^^ 

120Matrices may represent either directed or undirected graphs. This is 

121specified throughout the csgraph module by a boolean keyword. Graphs are 

122assumed to be directed by default. In a directed graph, traversal from node 

123i to node j can be accomplished over the edge G[i, j], but not the edge 

124G[j, i]. Consider the following dense graph:: 

125 

126 >>> G_dense = np.array([[0, 1, 0], 

127 ... [2, 0, 3], 

128 ... [0, 4, 0]]) 

129 

130When ``directed=True`` we get the graph:: 

131 

132 ---1--> ---3--> 

133 (0) (1) (2) 

134 <--2--- <--4--- 

135 

136In a non-directed graph, traversal from node i to node j can be 

137accomplished over either G[i, j] or G[j, i]. If both edges are not null, 

138and the two have unequal weights, then the smaller of the two is used. 

139 

140So for the same graph, when ``directed=False`` we get the graph:: 

141 

142 (0)--1--(1)--2--(2) 

143 

144Note that a symmetric matrix will represent an undirected graph, regardless 

145of whether the 'directed' keyword is set to True or False. In this case, 

146using ``directed=True`` generally leads to more efficient computation. 

147 

148The routines in this module accept as input either scipy.sparse representations 

149(csr, csc, or lil format), masked representations, or dense representations 

150with non-edges indicated by zeros, infinities, and NaN entries. 

151""" 

152 

153__docformat__ = "restructuredtext en" 

154 

155__all__ = ['connected_components', 

156 'laplacian', 

157 'shortest_path', 

158 'floyd_warshall', 

159 'dijkstra', 

160 'bellman_ford', 

161 'johnson', 

162 'breadth_first_order', 

163 'depth_first_order', 

164 'breadth_first_tree', 

165 'depth_first_tree', 

166 'minimum_spanning_tree', 

167 'reverse_cuthill_mckee', 

168 'maximum_flow', 

169 'maximum_bipartite_matching', 

170 'structural_rank', 

171 'construct_dist_matrix', 

172 'reconstruct_path', 

173 'csgraph_masked_from_dense', 

174 'csgraph_from_dense', 

175 'csgraph_from_masked', 

176 'csgraph_to_dense', 

177 'csgraph_to_masked', 

178 'NegativeCycleError'] 

179 

180from ._laplacian import laplacian 

181from ._shortest_path import shortest_path, floyd_warshall, dijkstra,\ 

182 bellman_ford, johnson, NegativeCycleError 

183from ._traversal import breadth_first_order, depth_first_order, \ 

184 breadth_first_tree, depth_first_tree, connected_components 

185from ._min_spanning_tree import minimum_spanning_tree 

186from ._flow import maximum_flow 

187from ._matching import maximum_bipartite_matching 

188from ._reordering import reverse_cuthill_mckee, structural_rank 

189from ._tools import construct_dist_matrix, reconstruct_path,\ 

190 csgraph_from_dense, csgraph_to_dense, csgraph_masked_from_dense,\ 

191 csgraph_from_masked, csgraph_to_masked 

192 

193from scipy._lib._testutils import PytestTester 

194test = PytestTester(__name__) 

195del PytestTester