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