Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.8/site-packages/scipy/sparse/csgraph/__init__.py: 100%
13 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-12-12 06:31 +0000
1r"""
2Compressed sparse graph routines (:mod:`scipy.sparse.csgraph`)
3==============================================================
5.. currentmodule:: scipy.sparse.csgraph
7Fast graph algorithms based on sparse matrix representations.
9Contents
10--------
12.. autosummary::
13 :toctree: generated/
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 min_weight_full_bipartite_matching - compute a minimum weight full matching of a bipartite graph
31 structural_rank -- compute the structural rank of a graph
32 NegativeCycleError
34.. autosummary::
35 :toctree: generated/
37 construct_dist_matrix
38 csgraph_from_dense
39 csgraph_from_masked
40 csgraph_masked_from_dense
41 csgraph_to_dense
42 csgraph_to_masked
43 reconstruct_path
45Graph Representations
46---------------------
47This module uses graphs which are stored in a matrix format. A
48graph with N nodes can be represented by an (N x N) adjacency matrix G.
49If there is a connection from node i to node j, then G[i, j] = w, where
50w is the weight of the connection. For nodes i and j which are
51not connected, the value depends on the representation:
53- for dense array representations, non-edges are represented by
54 G[i, j] = 0, infinity, or NaN.
56- for dense masked representations (of type np.ma.MaskedArray), non-edges
57 are represented by masked values. This can be useful when graphs with
58 zero-weight edges are desired.
60- for sparse array representations, non-edges are represented by
61 non-entries in the matrix. This sort of sparse representation also
62 allows for edges with zero weights.
64As a concrete example, imagine that you would like to represent the following
65undirected graph::
67 G
69 (0)
70 / \
71 1 2
72 / \
73 (2) (1)
75This graph has three nodes, where node 0 and 1 are connected by an edge of
76weight 2, and nodes 0 and 2 are connected by an edge of weight 1.
77We can construct the dense, masked, and sparse representations as follows,
78keeping in mind that an undirected graph is represented by a symmetric matrix::
80 >>> import numpy as np
81 >>> G_dense = np.array([[0, 2, 1],
82 ... [2, 0, 0],
83 ... [1, 0, 0]])
84 >>> G_masked = np.ma.masked_values(G_dense, 0)
85 >>> from scipy.sparse import csr_matrix
86 >>> G_sparse = csr_matrix(G_dense)
88This becomes more difficult when zero edges are significant. For example,
89consider the situation when we slightly modify the above graph::
91 G2
93 (0)
94 / \
95 0 2
96 / \
97 (2) (1)
99This is identical to the previous graph, except nodes 0 and 2 are connected
100by an edge of zero weight. In this case, the dense representation above
101leads to ambiguities: how can non-edges be represented if zero is a meaningful
102value? In this case, either a masked or sparse representation must be used
103to eliminate the ambiguity::
105 >>> import numpy as np
106 >>> G2_data = np.array([[np.inf, 2, 0 ],
107 ... [2, np.inf, np.inf],
108 ... [0, np.inf, np.inf]])
109 >>> G2_masked = np.ma.masked_invalid(G2_data)
110 >>> from scipy.sparse.csgraph import csgraph_from_dense
111 >>> # G2_sparse = csr_matrix(G2_data) would give the wrong result
112 >>> G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
113 >>> G2_sparse.data
114 array([ 2., 0., 2., 0.])
116Here we have used a utility routine from the csgraph submodule in order to
117convert the dense representation to a sparse representation which can be
118understood by the algorithms in submodule. By viewing the data array, we
119can see that the zero values are explicitly encoded in the graph.
121Directed vs. undirected
122^^^^^^^^^^^^^^^^^^^^^^^
123Matrices may represent either directed or undirected graphs. This is
124specified throughout the csgraph module by a boolean keyword. Graphs are
125assumed to be directed by default. In a directed graph, traversal from node
126i to node j can be accomplished over the edge G[i, j], but not the edge
127G[j, i]. Consider the following dense graph::
129 >>> import numpy as np
130 >>> G_dense = np.array([[0, 1, 0],
131 ... [2, 0, 3],
132 ... [0, 4, 0]])
134When ``directed=True`` we get the graph::
136 ---1--> ---3-->
137 (0) (1) (2)
138 <--2--- <--4---
140In a non-directed graph, traversal from node i to node j can be
141accomplished over either G[i, j] or G[j, i]. If both edges are not null,
142and the two have unequal weights, then the smaller of the two is used.
144So for the same graph, when ``directed=False`` we get the graph::
146 (0)--1--(1)--3--(2)
148Note that a symmetric matrix will represent an undirected graph, regardless
149of whether the 'directed' keyword is set to True or False. In this case,
150using ``directed=True`` generally leads to more efficient computation.
152The routines in this module accept as input either scipy.sparse representations
153(csr, csc, or lil format), masked representations, or dense representations
154with non-edges indicated by zeros, infinities, and NaN entries.
155"""
157__docformat__ = "restructuredtext en"
159__all__ = ['connected_components',
160 'laplacian',
161 'shortest_path',
162 'floyd_warshall',
163 'dijkstra',
164 'bellman_ford',
165 'johnson',
166 'breadth_first_order',
167 'depth_first_order',
168 'breadth_first_tree',
169 'depth_first_tree',
170 'minimum_spanning_tree',
171 'reverse_cuthill_mckee',
172 'maximum_flow',
173 'maximum_bipartite_matching',
174 'min_weight_full_bipartite_matching',
175 'structural_rank',
176 'construct_dist_matrix',
177 'reconstruct_path',
178 'csgraph_masked_from_dense',
179 'csgraph_from_dense',
180 'csgraph_from_masked',
181 'csgraph_to_dense',
182 'csgraph_to_masked',
183 'NegativeCycleError']
185from ._laplacian import laplacian
186from ._shortest_path import (
187 shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson,
188 NegativeCycleError
189)
190from ._traversal import (
191 breadth_first_order, depth_first_order, breadth_first_tree,
192 depth_first_tree, connected_components
193)
194from ._min_spanning_tree import minimum_spanning_tree
195from ._flow import maximum_flow
196from ._matching import (
197 maximum_bipartite_matching, min_weight_full_bipartite_matching
198)
199from ._reordering import reverse_cuthill_mckee, structural_rank
200from ._tools import (
201 construct_dist_matrix, reconstruct_path, csgraph_from_dense,
202 csgraph_to_dense, csgraph_masked_from_dense, csgraph_from_masked,
203 csgraph_to_masked
204)
206from scipy._lib._testutils import PytestTester
207test = PytestTester(__name__)
208del PytestTester