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