Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/traversal/edgebfs.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 """ | |
2 ============================= | |
3 Breadth First Search on Edges | |
4 ============================= | |
5 | |
6 Algorithms for a breadth-first traversal of edges in a graph. | |
7 | |
8 """ | |
9 from collections import deque | |
10 import networkx as nx | |
11 | |
12 FORWARD = "forward" | |
13 REVERSE = "reverse" | |
14 | |
15 __all__ = ["edge_bfs"] | |
16 | |
17 | |
18 def edge_bfs(G, source=None, orientation=None): | |
19 """A directed, breadth-first-search of edges in `G`, beginning at `source`. | |
20 | |
21 Yield the edges of G in a breadth-first-search order continuing until | |
22 all edges are generated. | |
23 | |
24 Parameters | |
25 ---------- | |
26 G : graph | |
27 A directed/undirected graph/multigraph. | |
28 | |
29 source : node, list of nodes | |
30 The node from which the traversal begins. If None, then a source | |
31 is chosen arbitrarily and repeatedly until all edges from each node in | |
32 the graph are searched. | |
33 | |
34 orientation : None | 'original' | 'reverse' | 'ignore' (default: None) | |
35 For directed graphs and directed multigraphs, edge traversals need not | |
36 respect the original orientation of the edges. | |
37 When set to 'reverse' every edge is traversed in the reverse direction. | |
38 When set to 'ignore', every edge is treated as undirected. | |
39 When set to 'original', every edge is treated as directed. | |
40 In all three cases, the yielded edge tuples add a last entry to | |
41 indicate the direction in which that edge was traversed. | |
42 If orientation is None, the yielded edge has no direction indicated. | |
43 The direction is respected, but not reported. | |
44 | |
45 Yields | |
46 ------ | |
47 edge : directed edge | |
48 A directed edge indicating the path taken by the breadth-first-search. | |
49 For graphs, `edge` is of the form `(u, v)` where `u` and `v` | |
50 are the tail and head of the edge as determined by the traversal. | |
51 For multigraphs, `edge` is of the form `(u, v, key)`, where `key` is | |
52 the key of the edge. When the graph is directed, then `u` and `v` | |
53 are always in the order of the actual directed edge. | |
54 If orientation is not None then the edge tuple is extended to include | |
55 the direction of traversal ('forward' or 'reverse') on that edge. | |
56 | |
57 Examples | |
58 -------- | |
59 >>> nodes = [0, 1, 2, 3] | |
60 >>> edges = [(0, 1), (1, 0), (1, 0), (2, 0), (2, 1), (3, 1)] | |
61 | |
62 >>> list(nx.edge_bfs(nx.Graph(edges), nodes)) | |
63 [(0, 1), (0, 2), (1, 2), (1, 3)] | |
64 | |
65 >>> list(nx.edge_bfs(nx.DiGraph(edges), nodes)) | |
66 [(0, 1), (1, 0), (2, 0), (2, 1), (3, 1)] | |
67 | |
68 >>> list(nx.edge_bfs(nx.MultiGraph(edges), nodes)) | |
69 [(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (1, 2, 0), (1, 3, 0)] | |
70 | |
71 >>> list(nx.edge_bfs(nx.MultiDiGraph(edges), nodes)) | |
72 [(0, 1, 0), (1, 0, 0), (1, 0, 1), (2, 0, 0), (2, 1, 0), (3, 1, 0)] | |
73 | |
74 >>> list(nx.edge_bfs(nx.DiGraph(edges), nodes, orientation="ignore")) | |
75 [(0, 1, 'forward'), (1, 0, 'reverse'), (2, 0, 'reverse'), (2, 1, 'reverse'), (3, 1, 'reverse')] | |
76 | |
77 >>> list(nx.edge_bfs(nx.MultiDiGraph(edges), nodes, orientation="ignore")) | |
78 [(0, 1, 0, 'forward'), (1, 0, 0, 'reverse'), (1, 0, 1, 'reverse'), (2, 0, 0, 'reverse'), (2, 1, 0, 'reverse'), (3, 1, 0, 'reverse')] | |
79 | |
80 Notes | |
81 ----- | |
82 The goal of this function is to visit edges. It differs from the more | |
83 familiar breadth-first-search of nodes, as provided by | |
84 :func:`networkx.algorithms.traversal.breadth_first_search.bfs_edges`, in | |
85 that it does not stop once every node has been visited. In a directed graph | |
86 with edges [(0, 1), (1, 2), (2, 1)], the edge (2, 1) would not be visited | |
87 if not for the functionality provided by this function. | |
88 | |
89 The naming of this function is very similar to bfs_edges. The difference | |
90 is that 'edge_bfs' yields edges even if they extend back to an already | |
91 explored node while 'bfs_edges' yields the edges of the tree that results | |
92 from a breadth-first-search (BFS) so no edges are reported if they extend | |
93 to already explored nodes. That means 'edge_bfs' reports all edges while | |
94 'bfs_edges' only report those traversed by a node-based BFS. Yet another | |
95 description is that 'bfs_edges' reports the edges traversed during BFS | |
96 while 'edge_bfs' reports all edges in the order they are explored. | |
97 | |
98 See Also | |
99 -------- | |
100 bfs_edges | |
101 bfs_tree | |
102 edge_dfs | |
103 | |
104 """ | |
105 nodes = list(G.nbunch_iter(source)) | |
106 if not nodes: | |
107 return | |
108 | |
109 directed = G.is_directed() | |
110 kwds = {"data": False} | |
111 if G.is_multigraph() is True: | |
112 kwds["keys"] = True | |
113 | |
114 # set up edge lookup | |
115 if orientation is None: | |
116 | |
117 def edges_from(node): | |
118 return iter(G.edges(node, **kwds)) | |
119 | |
120 elif not directed or orientation == "original": | |
121 | |
122 def edges_from(node): | |
123 for e in G.edges(node, **kwds): | |
124 yield e + (FORWARD,) | |
125 | |
126 elif orientation == "reverse": | |
127 | |
128 def edges_from(node): | |
129 for e in G.in_edges(node, **kwds): | |
130 yield e + (REVERSE,) | |
131 | |
132 elif orientation == "ignore": | |
133 | |
134 def edges_from(node): | |
135 for e in G.edges(node, **kwds): | |
136 yield e + (FORWARD,) | |
137 for e in G.in_edges(node, **kwds): | |
138 yield e + (REVERSE,) | |
139 | |
140 else: | |
141 raise nx.NetworkXError("invalid orientation argument.") | |
142 | |
143 if directed: | |
144 neighbors = G.successors | |
145 | |
146 def edge_id(edge): | |
147 # remove direction indicator | |
148 return edge[:-1] if orientation is not None else edge | |
149 | |
150 else: | |
151 neighbors = G.neighbors | |
152 | |
153 def edge_id(edge): | |
154 return (frozenset(edge[:2]),) + edge[2:] | |
155 | |
156 check_reverse = directed and orientation in ("reverse", "ignore") | |
157 | |
158 # start BFS | |
159 visited_nodes = {n for n in nodes} | |
160 visited_edges = set() | |
161 queue = deque([(n, edges_from(n)) for n in nodes]) | |
162 while queue: | |
163 parent, children_edges = queue.popleft() | |
164 for edge in children_edges: | |
165 if check_reverse and edge[-1] == REVERSE: | |
166 child = edge[0] | |
167 else: | |
168 child = edge[1] | |
169 if child not in visited_nodes: | |
170 visited_nodes.add(child) | |
171 queue.append((child, edges_from(child))) | |
172 edgeid = edge_id(edge) | |
173 if edgeid not in visited_edges: | |
174 visited_edges.add(edgeid) | |
175 yield edge |