### annotate env/lib/python3.9/site-packages/networkx/algorithms/traversal/edgedfs.py @ 0:4f3585e2f14bdraftdefaulttip

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