Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/traversal/edgedfs.py: 10%

1""" 

2=========================== 

3Depth First Search on Edges 

4=========================== 

5 

6Algorithms for a depth-first traversal of edges in a graph. 

7 

8""" 

9import networkx as nx 

10 

11FORWARD = "forward" 

12REVERSE = "reverse" 

13 

14__all__ = ["edge_dfs"] 

15 

16 

17@nx._dispatch 

18def edge_dfs(G, source=None, orientation=None): 

19 """A directed, depth-first-search of edges in `G`, beginning at `source`. 

20 

21 Yield the edges of G in a depth-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 depth-first traversal. 

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, 1), (3, 1)] 

61 

62 >>> list(nx.edge_dfs(nx.Graph(edges), nodes)) 

63 [(0, 1), (1, 2), (1, 3)] 

64 

65 >>> list(nx.edge_dfs(nx.DiGraph(edges), nodes)) 

66 [(0, 1), (1, 0), (2, 1), (3, 1)] 

67 

68 >>> list(nx.edge_dfs(nx.MultiGraph(edges), nodes)) 

69 [(0, 1, 0), (1, 0, 1), (0, 1, 2), (1, 2, 0), (1, 3, 0)] 

70 

71 >>> list(nx.edge_dfs(nx.MultiDiGraph(edges), nodes)) 

72 [(0, 1, 0), (1, 0, 0), (1, 0, 1), (2, 1, 0), (3, 1, 0)] 

73 

74 >>> list(nx.edge_dfs(nx.DiGraph(edges), nodes, orientation="ignore")) 

75 [(0, 1, 'forward'), (1, 0, 'forward'), (2, 1, 'reverse'), (3, 1, 'reverse')] 

76 

77 >>> list(nx.edge_dfs(nx.MultiDiGraph(edges), nodes, orientation="ignore")) 

78 [(0, 1, 0, 'forward'), (1, 0, 0, 'forward'), (1, 0, 1, '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 depth-first traversal of nodes, as provided by 

84 :func:`~networkx.algorithms.traversal.depth_first_search.dfs_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 See Also 

90 -------- 

91 :func:`~networkx.algorithms.traversal.depth_first_search.dfs_edges` 

92 

93 """ 

94 nodes = list(G.nbunch_iter(source)) 

95 if not nodes: 

96 return 

97 

98 directed = G.is_directed() 

99 kwds = {"data": False} 

100 if G.is_multigraph() is True: 

101 kwds["keys"] = True 

102 

103 # set up edge lookup 

104 if orientation is None: 

105 

106 def edges_from(node): 

107 return iter(G.edges(node, **kwds)) 

108 

109 elif not directed or orientation == "original": 

110 

111 def edges_from(node): 

112 for e in G.edges(node, **kwds): 

113 yield e + (FORWARD,) 

114 

115 elif orientation == "reverse": 

116 

117 def edges_from(node): 

118 for e in G.in_edges(node, **kwds): 

119 yield e + (REVERSE,) 

120 

121 elif orientation == "ignore": 

122 

123 def edges_from(node): 

124 for e in G.edges(node, **kwds): 

125 yield e + (FORWARD,) 

126 for e in G.in_edges(node, **kwds): 

127 yield e + (REVERSE,) 

128 

129 else: 

130 raise nx.NetworkXError("invalid orientation argument.") 

131 

132 # set up formation of edge_id to easily look up if edge already returned 

133 if directed: 

134 

135 def edge_id(edge): 

136 # remove direction indicator 

137 return edge[:-1] if orientation is not None else edge 

138 

139 else: 

140 

141 def edge_id(edge): 

142 # single id for undirected requires frozenset on nodes 

143 return (frozenset(edge[:2]),) + edge[2:] 

144 

145 # Basic setup 

146 check_reverse = directed and orientation in ("reverse", "ignore") 

147 

148 visited_edges = set() 

149 visited_nodes = set() 

150 edges = {} 

151 

152 # start DFS 

153 for start_node in nodes: 

154 stack = [start_node] 

155 while stack: 

156 current_node = stack[-1] 

157 if current_node not in visited_nodes: 

158 edges[current_node] = edges_from(current_node) 

159 visited_nodes.add(current_node) 

160 

161 try: 

162 edge = next(edges[current_node]) 

163 except StopIteration: 

164 # No more edges from the current node. 

165 stack.pop() 

166 else: 

167 edgeid = edge_id(edge) 

168 if edgeid not in visited_edges: 

169 visited_edges.add(edgeid) 

170 # Mark the traversed "to" node as to-be-explored. 

171 if check_reverse and edge[-1] == REVERSE: 

172 stack.append(edge[0]) 

173 else: 

174 stack.append(edge[1]) 

175 yield edge