Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/chains.py: 18%

1"""Functions for finding chains in a graph.""" 

2 

3import networkx as nx 

4from networkx.utils import not_implemented_for 

5 

6__all__ = ["chain_decomposition"] 

7 

8 

9@not_implemented_for("directed") 

10@not_implemented_for("multigraph") 

11@nx._dispatch 

12def chain_decomposition(G, root=None): 

13 """Returns the chain decomposition of a graph. 

14 

15 The *chain decomposition* of a graph with respect a depth-first 

16 search tree is a set of cycles or paths derived from the set of 

17 fundamental cycles of the tree in the following manner. Consider 

18 each fundamental cycle with respect to the given tree, represented 

19 as a list of edges beginning with the nontree edge oriented away 

20 from the root of the tree. For each fundamental cycle, if it 

21 overlaps with any previous fundamental cycle, just take the initial 

22 non-overlapping segment, which is a path instead of a cycle. Each 

23 cycle or path is called a *chain*. For more information, see [1]_. 

24 

25 Parameters 

26 ---------- 

27 G : undirected graph 

28 

29 root : node (optional) 

30 A node in the graph `G`. If specified, only the chain 

31 decomposition for the connected component containing this node 

32 will be returned. This node indicates the root of the depth-first 

33 search tree. 

34 

35 Yields 

36 ------ 

37 chain : list 

38 A list of edges representing a chain. There is no guarantee on 

39 the orientation of the edges in each chain (for example, if a 

40 chain includes the edge joining nodes 1 and 2, the chain may 

41 include either (1, 2) or (2, 1)). 

42 

43 Raises 

44 ------ 

45 NodeNotFound 

46 If `root` is not in the graph `G`. 

47 

48 Examples 

49 -------- 

50 >>> G = nx.Graph([(0, 1), (1, 4), (3, 4), (3, 5), (4, 5)]) 

51 >>> list(nx.chain_decomposition(G)) 

52 [[(4, 5), (5, 3), (3, 4)]] 

53 

54 Notes 

55 ----- 

56 The worst-case running time of this implementation is linear in the 

57 number of nodes and number of edges [1]_. 

58 

59 References 

60 ---------- 

61 .. [1] Jens M. Schmidt (2013). "A simple test on 2-vertex- 

62 and 2-edge-connectivity." *Information Processing Letters*, 

63 113, 241–244. Elsevier. <https://doi.org/10.1016/j.ipl.2013.01.016> 

64 

65 """ 

66 

67 def _dfs_cycle_forest(G, root=None): 

68 """Builds a directed graph composed of cycles from the given graph. 

69 

70 `G` is an undirected simple graph. `root` is a node in the graph 

71 from which the depth-first search is started. 

72 

73 This function returns both the depth-first search cycle graph 

74 (as a :class:`~networkx.DiGraph`) and the list of nodes in 

75 depth-first preorder. The depth-first search cycle graph is a 

76 directed graph whose edges are the edges of `G` oriented toward 

77 the root if the edge is a tree edge and away from the root if 

78 the edge is a non-tree edge. If `root` is not specified, this 

79 performs a depth-first search on each connected component of `G` 

80 and returns a directed forest instead. 

81 

82 If `root` is not in the graph, this raises :exc:`KeyError`. 

83 

84 """ 

85 # Create a directed graph from the depth-first search tree with 

86 # root node `root` in which tree edges are directed toward the 

87 # root and nontree edges are directed away from the root. For 

88 # each node with an incident nontree edge, this creates a 

89 # directed cycle starting with the nontree edge and returning to 

90 # that node. 

91 # 

92 # The `parent` node attribute stores the parent of each node in 

93 # the DFS tree. The `nontree` edge attribute indicates whether 

94 # the edge is a tree edge or a nontree edge. 

95 # 

96 # We also store the order of the nodes found in the depth-first 

97 # search in the `nodes` list. 

98 H = nx.DiGraph() 

99 nodes = [] 

100 for u, v, d in nx.dfs_labeled_edges(G, source=root): 

101 if d == "forward": 

102 # `dfs_labeled_edges()` yields (root, root, 'forward') 

103 # if it is beginning the search on a new connected 

104 # component. 

105 if u == v: 

106 H.add_node(v, parent=None) 

107 nodes.append(v) 

108 else: 

109 H.add_node(v, parent=u) 

110 H.add_edge(v, u, nontree=False) 

111 nodes.append(v) 

112 # `dfs_labeled_edges` considers nontree edges in both 

113 # orientations, so we need to not add the edge if it its 

114 # other orientation has been added. 

115 elif d == "nontree" and v not in H[u]: 

116 H.add_edge(v, u, nontree=True) 

117 else: 

118 # Do nothing on 'reverse' edges; we only care about 

119 # forward and nontree edges. 

120 pass 

121 return H, nodes 

122 

123 def _build_chain(G, u, v, visited): 

124 """Generate the chain starting from the given nontree edge. 

125 

126 `G` is a DFS cycle graph as constructed by 

127 :func:`_dfs_cycle_graph`. The edge (`u`, `v`) is a nontree edge 

128 that begins a chain. `visited` is a set representing the nodes 

129 in `G` that have already been visited. 

130 

131 This function yields the edges in an initial segment of the 

132 fundamental cycle of `G` starting with the nontree edge (`u`, 

133 `v`) that includes all the edges up until the first node that 

134 appears in `visited`. The tree edges are given by the 'parent' 

135 node attribute. The `visited` set is updated to add each node in 

136 an edge yielded by this function. 

137 

138 """ 

139 while v not in visited: 

140 yield u, v 

141 visited.add(v) 

142 u, v = v, G.nodes[v]["parent"] 

143 yield u, v 

144 

145 # Check if the root is in the graph G. If not, raise NodeNotFound 

146 if root is not None and root not in G: 

147 raise nx.NodeNotFound(f"Root node {root} is not in graph") 

148 

149 # Create a directed version of H that has the DFS edges directed 

150 # toward the root and the nontree edges directed away from the root 

151 # (in each connected component). 

152 H, nodes = _dfs_cycle_forest(G, root) 

153 

154 # Visit the nodes again in DFS order. For each node, and for each 

155 # nontree edge leaving that node, compute the fundamental cycle for 

156 # that nontree edge starting with that edge. If the fundamental 

157 # cycle overlaps with any visited nodes, just take the prefix of the 

158 # cycle up to the point of visited nodes. 

159 # 

160 # We repeat this process for each connected component (implicitly, 

161 # since `nodes` already has a list of the nodes grouped by connected 

162 # component). 

163 visited = set() 

164 for u in nodes: 

165 visited.add(u) 

166 # For each nontree edge going out of node u... 

167 edges = ((u, v) for u, v, d in H.out_edges(u, data="nontree") if d) 

168 for u, v in edges: 

169 # Create the cycle or cycle prefix starting with the 

170 # nontree edge. 

171 chain = list(_build_chain(H, u, v, visited)) 

172 yield chain