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

author shellac Mon, 22 Mar 2021 18:12:50 +0000
comparison
equal 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
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)
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: