Mercurial > repos > guerler > springsuite

comparison planemo/lib/python3.7/site-packages/networkx/algorithms/bridges.py @ 1:56ad4e20f292 draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"planemo upload commit 6eee67778febed82ddd413c3ca40b3183a3898f1"
author guerler
date Fri, 31 Jul 2020 00:32:28 -0400
parents
children
comparison
equal deleted inserted replaced
0:d30785e31577 1:56ad4e20f292
1 # -*- coding: utf-8 -*-
2 # bridges.py - bridge-finding algorithms
3 #
4 # Copyright 2004-2019 NetworkX developers.
5 #
6 # This file is part of NetworkX.
7 #
8 # NetworkX is distributed under a BSD license; see LICENSE.txt for more
9 # information.
10 """Bridge-finding algorithms."""
11 from itertools import chain
12
13 import networkx as nx
14 from networkx.utils import not_implemented_for
15
16 __all__ = ['bridges', 'has_bridges', 'local_bridges']
17
18
19 @not_implemented_for('multigraph')
20 @not_implemented_for('directed')
21 def bridges(G, root=None):
22 """Generate all bridges in a graph.
23
24 A *bridge* in a graph is an edge whose removal causes the number of
25 connected components of the graph to increase. Equivalently, a bridge is an
26 edge that does not belong to any cycle.
27
28 Parameters
29 ----------
30 G : undirected graph
31
32 root : node (optional)
33 A node in the graph `G`. If specified, only the bridges in the
34 connected component containing this node will be returned.
35
36 Yields
37 ------
38 e : edge
39 An edge in the graph whose removal disconnects the graph (or
40 causes the number of connected components to increase).
41
42 Raises
43 ------
44 NodeNotFound
45 If `root` is not in the graph `G`.
46
47 Examples
48 --------
49 The barbell graph with parameter zero has a single bridge:
50
51 >>> G = nx.barbell_graph(10, 0)
52 >>> list(nx.bridges(G))
53 [(9, 10)]
54
55 Notes
56 -----
57 This is an implementation of the algorithm described in _[1]. An edge is a
58 bridge if and only if it is not contained in any chain. Chains are found
59 using the :func:`networkx.chain_decomposition` function.
60
61 Ignoring polylogarithmic factors, the worst-case time complexity is the
62 same as the :func:`networkx.chain_decomposition` function,
63 $O(m + n)$, where $n$ is the number of nodes in the graph and $m$ is
64 the number of edges.
65
66 References
67 ----------
68 .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29#Bridge-Finding_with_Chain_Decompositions
69 """
70 chains = nx.chain_decomposition(G, root=root)
71 chain_edges = set(chain.from_iterable(chains))
72 for u, v in G.edges():
73 if (u, v) not in chain_edges and (v, u) not in chain_edges:
74 yield u, v
75
76
77 @not_implemented_for('multigraph')
78 @not_implemented_for('directed')
79 def has_bridges(G, root=None):
80 """Decide whether a graph has any bridges.
81
82 A *bridge* in a graph is an edge whose removal causes the number of
83 connected components of the graph to increase.
84
85 Parameters
86 ----------
87 G : undirected graph
88
89 root : node (optional)
90 A node in the graph `G`. If specified, only the bridges in the
91 connected component containing this node will be considered.
92
93 Returns
94 -------
95 bool
96 Whether the graph (or the connected component containing `root`)
97 has any bridges.
98
99 Raises
100 ------
101 NodeNotFound
102 If `root` is not in the graph `G`.
103
104 Examples
105 --------
106 The barbell graph with parameter zero has a single bridge::
107
108 >>> G = nx.barbell_graph(10, 0)
109 >>> nx.has_bridges(G)
110 True
111
112 On the other hand, the cycle graph has no bridges::
113
114 >>> G = nx.cycle_graph(5)
115 >>> nx.has_bridges(G)
116 False
117
118 Notes
119 -----
120 This implementation uses the :func:`networkx.bridges` function, so
121 it shares its worst-case time complexity, $O(m + n)$, ignoring
122 polylogarithmic factors, where $n$ is the number of nodes in the
123 graph and $m$ is the number of edges.
124
125 """
126 try:
127 next(bridges(G))
128 except StopIteration:
129 return False
130 else:
131 return True
132
133
134 @not_implemented_for('multigraph')
135 @not_implemented_for('directed')
136 def local_bridges(G, with_span=True, weight=None):
137 """Iterate over local bridges of `G` optionally computing the span
138
139 A *local bridge* is an edge whose endpoints have no common neighbors.
140 That is, the edge is not part of a triangle in the graph.
141
142 The *span* of a *local bridge* is the shortest path length between
143 the endpoints if the local bridge is removed.
144
145 Parameters
146 ----------
147 G : undirected graph
148
149 with_span : bool
150 If True, yield a 3-tuple `(u, v, span)`
151
152 weight : function, string or None (default: None)
153 If function, used to compute edge weights for the span.
154 If string, the edge data attribute used in calculating span.
155 If None, all edges have weight 1.
156
157 Yields
158 ------
159 e : edge
160 The local bridges as an edge 2-tuple of nodes `(u, v)` or
161 as a 3-tuple `(u, v, span)` when `with_span is True`.
162
163 Examples
164 --------
165 A cycle graph has every edge a local bridge with span N-1.
166
167 >>> G = nx.cycle_graph(9)
168 >>> (0, 8, 8) in set(nx.local_bridges(G))
169 True
170 """
171 if with_span is not True:
172 for u, v in G.edges:
173 if not (set(G[u]) & set(G[v])):
174 yield u, v
175 else:
176 wt = nx.weighted._weight_function(G, weight)
177 for u, v in G.edges:
178 if not (set(G[u]) & set(G[v])):
179 enodes = {u, v}
180
181 def hide_edge(n, nbr, d):
182 if n not in enodes or nbr not in enodes:
183 return wt(n, nbr, d)
184 return None
185
186 try:
187 span = nx.shortest_path_length(G, u, v, weight=hide_edge)
188 yield u, v, span
189 except nx.NetworkXNoPath:
190 yield u, v, float('inf')