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