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