Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/connectivity/disjoint_paths.py: 14%
83 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""Flow based node and edge disjoint paths."""
2import networkx as nx
4# Define the default maximum flow function to use for the underlying
5# maximum flow computations
6from networkx.algorithms.flow import (
7 edmonds_karp,
8 preflow_push,
9 shortest_augmenting_path,
10)
11from networkx.exception import NetworkXNoPath
13default_flow_func = edmonds_karp
14from itertools import filterfalse as _filterfalse
16# Functions to build auxiliary data structures.
17from .utils import build_auxiliary_edge_connectivity, build_auxiliary_node_connectivity
19__all__ = ["edge_disjoint_paths", "node_disjoint_paths"]
22@nx._dispatch(
23 graphs={"G": 0, "auxiliary?": 5, "residual?": 6},
24 preserve_edge_attrs={
25 "auxiliary": {"capacity": float("inf")},
26 "residual": {"capacity": float("inf")},
27 },
28 preserve_graph_attrs={"residual"},
29)
30def edge_disjoint_paths(
31 G, s, t, flow_func=None, cutoff=None, auxiliary=None, residual=None
32):
33 """Returns the edges disjoint paths between source and target.
35 Edge disjoint paths are paths that do not share any edge. The
36 number of edge disjoint paths between source and target is equal
37 to their edge connectivity.
39 Parameters
40 ----------
41 G : NetworkX graph
43 s : node
44 Source node for the flow.
46 t : node
47 Sink node for the flow.
49 flow_func : function
50 A function for computing the maximum flow among a pair of nodes.
51 The function has to accept at least three parameters: a Digraph,
52 a source node, and a target node. And return a residual network
53 that follows NetworkX conventions (see :meth:`maximum_flow` for
54 details). If flow_func is None, the default maximum flow function
55 (:meth:`edmonds_karp`) is used. The choice of the default function
56 may change from version to version and should not be relied on.
57 Default value: None.
59 cutoff : integer or None (default: None)
60 Maximum number of paths to yield. If specified, the maximum flow
61 algorithm will terminate when the flow value reaches or exceeds the
62 cutoff. This only works for flows that support the cutoff parameter
63 (most do) and is ignored otherwise.
65 auxiliary : NetworkX DiGraph
66 Auxiliary digraph to compute flow based edge connectivity. It has
67 to have a graph attribute called mapping with a dictionary mapping
68 node names in G and in the auxiliary digraph. If provided
69 it will be reused instead of recreated. Default value: None.
71 residual : NetworkX DiGraph
72 Residual network to compute maximum flow. If provided it will be
73 reused instead of recreated. Default value: None.
75 Returns
76 -------
77 paths : generator
78 A generator of edge independent paths.
80 Raises
81 ------
82 NetworkXNoPath
83 If there is no path between source and target.
85 NetworkXError
86 If source or target are not in the graph G.
88 See also
89 --------
90 :meth:`node_disjoint_paths`
91 :meth:`edge_connectivity`
92 :meth:`maximum_flow`
93 :meth:`edmonds_karp`
94 :meth:`preflow_push`
95 :meth:`shortest_augmenting_path`
97 Examples
98 --------
99 We use in this example the platonic icosahedral graph, which has node
100 edge connectivity 5, thus there are 5 edge disjoint paths between any
101 pair of nodes.
103 >>> G = nx.icosahedral_graph()
104 >>> len(list(nx.edge_disjoint_paths(G, 0, 6)))
105 5
108 If you need to compute edge disjoint paths on several pairs of
109 nodes in the same graph, it is recommended that you reuse the
110 data structures that NetworkX uses in the computation: the
111 auxiliary digraph for edge connectivity, and the residual
112 network for the underlying maximum flow computation.
114 Example of how to compute edge disjoint paths among all pairs of
115 nodes of the platonic icosahedral graph reusing the data
116 structures.
118 >>> import itertools
119 >>> # You also have to explicitly import the function for
120 >>> # building the auxiliary digraph from the connectivity package
121 >>> from networkx.algorithms.connectivity import build_auxiliary_edge_connectivity
122 >>> H = build_auxiliary_edge_connectivity(G)
123 >>> # And the function for building the residual network from the
124 >>> # flow package
125 >>> from networkx.algorithms.flow import build_residual_network
126 >>> # Note that the auxiliary digraph has an edge attribute named capacity
127 >>> R = build_residual_network(H, "capacity")
128 >>> result = {n: {} for n in G}
129 >>> # Reuse the auxiliary digraph and the residual network by passing them
130 >>> # as arguments
131 >>> for u, v in itertools.combinations(G, 2):
132 ... k = len(list(nx.edge_disjoint_paths(G, u, v, auxiliary=H, residual=R)))
133 ... result[u][v] = k
134 >>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))
135 True
137 You can also use alternative flow algorithms for computing edge disjoint
138 paths. For instance, in dense networks the algorithm
139 :meth:`shortest_augmenting_path` will usually perform better than
140 the default :meth:`edmonds_karp` which is faster for sparse
141 networks with highly skewed degree distributions. Alternative flow
142 functions have to be explicitly imported from the flow package.
144 >>> from networkx.algorithms.flow import shortest_augmenting_path
145 >>> len(list(nx.edge_disjoint_paths(G, 0, 6, flow_func=shortest_augmenting_path)))
146 5
148 Notes
149 -----
150 This is a flow based implementation of edge disjoint paths. We compute
151 the maximum flow between source and target on an auxiliary directed
152 network. The saturated edges in the residual network after running the
153 maximum flow algorithm correspond to edge disjoint paths between source
154 and target in the original network. This function handles both directed
155 and undirected graphs, and can use all flow algorithms from NetworkX flow
156 package.
158 """
159 if s not in G:
160 raise nx.NetworkXError(f"node {s} not in graph")
161 if t not in G:
162 raise nx.NetworkXError(f"node {t} not in graph")
164 if flow_func is None:
165 flow_func = default_flow_func
167 if auxiliary is None:
168 H = build_auxiliary_edge_connectivity(G)
169 else:
170 H = auxiliary
172 # Maximum possible edge disjoint paths
173 possible = min(H.out_degree(s), H.in_degree(t))
174 if not possible:
175 raise NetworkXNoPath
177 if cutoff is None:
178 cutoff = possible
179 else:
180 cutoff = min(cutoff, possible)
182 # Compute maximum flow between source and target. Flow functions in
183 # NetworkX return a residual network.
184 kwargs = {
185 "capacity": "capacity",
186 "residual": residual,
187 "cutoff": cutoff,
188 "value_only": True,
189 }
190 if flow_func is preflow_push:
191 del kwargs["cutoff"]
192 if flow_func is shortest_augmenting_path:
193 kwargs["two_phase"] = True
194 R = flow_func(H, s, t, **kwargs)
196 if R.graph["flow_value"] == 0:
197 raise NetworkXNoPath
199 # Saturated edges in the residual network form the edge disjoint paths
200 # between source and target
201 cutset = [
202 (u, v)
203 for u, v, d in R.edges(data=True)
204 if d["capacity"] == d["flow"] and d["flow"] > 0
205 ]
206 # This is equivalent of what flow.utils.build_flow_dict returns, but
207 # only for the nodes with saturated edges and without reporting 0 flows.
208 flow_dict = {n: {} for edge in cutset for n in edge}
209 for u, v in cutset:
210 flow_dict[u][v] = 1
212 # Rebuild the edge disjoint paths from the flow dictionary.
213 paths_found = 0
214 for v in list(flow_dict[s]):
215 if paths_found >= cutoff:
216 # preflow_push does not support cutoff: we have to
217 # keep track of the paths founds and stop at cutoff.
218 break
219 path = [s]
220 if v == t:
221 path.append(v)
222 yield path
223 continue
224 u = v
225 while u != t:
226 path.append(u)
227 try:
228 u, _ = flow_dict[u].popitem()
229 except KeyError:
230 break
231 else:
232 path.append(t)
233 yield path
234 paths_found += 1
237@nx._dispatch(
238 graphs={"G": 0, "auxiliary?": 5, "residual?": 6},
239 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
240 preserve_node_attrs={"auxiliary": {"id": None}},
241 preserve_graph_attrs={"auxiliary", "residual"},
242)
243def node_disjoint_paths(
244 G, s, t, flow_func=None, cutoff=None, auxiliary=None, residual=None
245):
246 r"""Computes node disjoint paths between source and target.
248 Node disjoint paths are paths that only share their first and last
249 nodes. The number of node independent paths between two nodes is
250 equal to their local node connectivity.
252 Parameters
253 ----------
254 G : NetworkX graph
256 s : node
257 Source node.
259 t : node
260 Target node.
262 flow_func : function
263 A function for computing the maximum flow among a pair of nodes.
264 The function has to accept at least three parameters: a Digraph,
265 a source node, and a target node. And return a residual network
266 that follows NetworkX conventions (see :meth:`maximum_flow` for
267 details). If flow_func is None, the default maximum flow function
268 (:meth:`edmonds_karp`) is used. See below for details. The choice
269 of the default function may change from version to version and
270 should not be relied on. Default value: None.
272 cutoff : integer or None (default: None)
273 Maximum number of paths to yield. If specified, the maximum flow
274 algorithm will terminate when the flow value reaches or exceeds the
275 cutoff. This only works for flows that support the cutoff parameter
276 (most do) and is ignored otherwise.
278 auxiliary : NetworkX DiGraph
279 Auxiliary digraph to compute flow based node connectivity. It has
280 to have a graph attribute called mapping with a dictionary mapping
281 node names in G and in the auxiliary digraph. If provided
282 it will be reused instead of recreated. Default value: None.
284 residual : NetworkX DiGraph
285 Residual network to compute maximum flow. If provided it will be
286 reused instead of recreated. Default value: None.
288 Returns
289 -------
290 paths : generator
291 Generator of node disjoint paths.
293 Raises
294 ------
295 NetworkXNoPath
296 If there is no path between source and target.
298 NetworkXError
299 If source or target are not in the graph G.
301 Examples
302 --------
303 We use in this example the platonic icosahedral graph, which has node
304 connectivity 5, thus there are 5 node disjoint paths between any pair
305 of non neighbor nodes.
307 >>> G = nx.icosahedral_graph()
308 >>> len(list(nx.node_disjoint_paths(G, 0, 6)))
309 5
311 If you need to compute node disjoint paths between several pairs of
312 nodes in the same graph, it is recommended that you reuse the
313 data structures that NetworkX uses in the computation: the
314 auxiliary digraph for node connectivity and node cuts, and the
315 residual network for the underlying maximum flow computation.
317 Example of how to compute node disjoint paths reusing the data
318 structures:
320 >>> # You also have to explicitly import the function for
321 >>> # building the auxiliary digraph from the connectivity package
322 >>> from networkx.algorithms.connectivity import build_auxiliary_node_connectivity
323 >>> H = build_auxiliary_node_connectivity(G)
324 >>> # And the function for building the residual network from the
325 >>> # flow package
326 >>> from networkx.algorithms.flow import build_residual_network
327 >>> # Note that the auxiliary digraph has an edge attribute named capacity
328 >>> R = build_residual_network(H, "capacity")
329 >>> # Reuse the auxiliary digraph and the residual network by passing them
330 >>> # as arguments
331 >>> len(list(nx.node_disjoint_paths(G, 0, 6, auxiliary=H, residual=R)))
332 5
334 You can also use alternative flow algorithms for computing node disjoint
335 paths. For instance, in dense networks the algorithm
336 :meth:`shortest_augmenting_path` will usually perform better than
337 the default :meth:`edmonds_karp` which is faster for sparse
338 networks with highly skewed degree distributions. Alternative flow
339 functions have to be explicitly imported from the flow package.
341 >>> from networkx.algorithms.flow import shortest_augmenting_path
342 >>> len(list(nx.node_disjoint_paths(G, 0, 6, flow_func=shortest_augmenting_path)))
343 5
345 Notes
346 -----
347 This is a flow based implementation of node disjoint paths. We compute
348 the maximum flow between source and target on an auxiliary directed
349 network. The saturated edges in the residual network after running the
350 maximum flow algorithm correspond to node disjoint paths between source
351 and target in the original network. This function handles both directed
352 and undirected graphs, and can use all flow algorithms from NetworkX flow
353 package.
355 See also
356 --------
357 :meth:`edge_disjoint_paths`
358 :meth:`node_connectivity`
359 :meth:`maximum_flow`
360 :meth:`edmonds_karp`
361 :meth:`preflow_push`
362 :meth:`shortest_augmenting_path`
364 """
365 if s not in G:
366 raise nx.NetworkXError(f"node {s} not in graph")
367 if t not in G:
368 raise nx.NetworkXError(f"node {t} not in graph")
370 if auxiliary is None:
371 H = build_auxiliary_node_connectivity(G)
372 else:
373 H = auxiliary
375 mapping = H.graph.get("mapping", None)
376 if mapping is None:
377 raise nx.NetworkXError("Invalid auxiliary digraph.")
379 # Maximum possible edge disjoint paths
380 possible = min(H.out_degree(f"{mapping[s]}B"), H.in_degree(f"{mapping[t]}A"))
381 if not possible:
382 raise NetworkXNoPath
384 if cutoff is None:
385 cutoff = possible
386 else:
387 cutoff = min(cutoff, possible)
389 kwargs = {
390 "flow_func": flow_func,
391 "residual": residual,
392 "auxiliary": H,
393 "cutoff": cutoff,
394 }
396 # The edge disjoint paths in the auxiliary digraph correspond to the node
397 # disjoint paths in the original graph.
398 paths_edges = edge_disjoint_paths(H, f"{mapping[s]}B", f"{mapping[t]}A", **kwargs)
399 for path in paths_edges:
400 # Each node in the original graph maps to two nodes in auxiliary graph
401 yield list(_unique_everseen(H.nodes[node]["id"] for node in path))
404def _unique_everseen(iterable):
405 # Adapted from https://docs.python.org/3/library/itertools.html examples
406 "List unique elements, preserving order. Remember all elements ever seen."
407 # unique_everseen('AAAABBBCCDAABBB') --> A B C D
408 seen = set()
409 seen_add = seen.add
410 for element in _filterfalse(seen.__contains__, iterable):
411 seen_add(element)
412 yield element