Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/chains.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """Functions for finding chains in a graph.""" | |
2 | |
3 import networkx as nx | |
4 from networkx.utils import not_implemented_for | |
5 | |
6 | |
7 @not_implemented_for("directed") | |
8 @not_implemented_for("multigraph") | |
9 def chain_decomposition(G, root=None): | |
10 """Returns the chain decomposition of a graph. | |
11 | |
12 The *chain decomposition* of a graph with respect a depth-first | |
13 search tree is a set of cycles or paths derived from the set of | |
14 fundamental cycles of the tree in the following manner. Consider | |
15 each fundamental cycle with respect to the given tree, represented | |
16 as a list of edges beginning with the nontree edge oriented away | |
17 from the root of the tree. For each fundamental cycle, if it | |
18 overlaps with any previous fundamental cycle, just take the initial | |
19 non-overlapping segment, which is a path instead of a cycle. Each | |
20 cycle or path is called a *chain*. For more information, see [1]_. | |
21 | |
22 Parameters | |
23 ---------- | |
24 G : undirected graph | |
25 | |
26 root : node (optional) | |
27 A node in the graph `G`. If specified, only the chain | |
28 decomposition for the connected component containing this node | |
29 will be returned. This node indicates the root of the depth-first | |
30 search tree. | |
31 | |
32 Yields | |
33 ------ | |
34 chain : list | |
35 A list of edges representing a chain. There is no guarantee on | |
36 the orientation of the edges in each chain (for example, if a | |
37 chain includes the edge joining nodes 1 and 2, the chain may | |
38 include either (1, 2) or (2, 1)). | |
39 | |
40 Raises | |
41 ------ | |
42 NodeNotFound | |
43 If `root` is not in the graph `G`. | |
44 | |
45 Notes | |
46 ----- | |
47 The worst-case running time of this implementation is linear in the | |
48 number of nodes and number of edges [1]_. | |
49 | |
50 References | |
51 ---------- | |
52 .. [1] Jens M. Schmidt (2013). "A simple test on 2-vertex- | |
53 and 2-edge-connectivity." *Information Processing Letters*, | |
54 113, 241–244. Elsevier. <https://doi.org/10.1016/j.ipl.2013.01.016> | |
55 | |
56 """ | |
57 | |
58 def _dfs_cycle_forest(G, root=None): | |
59 """Builds a directed graph composed of cycles from the given graph. | |
60 | |
61 `G` is an undirected simple graph. `root` is a node in the graph | |
62 from which the depth-first search is started. | |
63 | |
64 This function returns both the depth-first search cycle graph | |
65 (as a :class:`~networkx.DiGraph`) and the list of nodes in | |
66 depth-first preorder. The depth-first search cycle graph is a | |
67 directed graph whose edges are the edges of `G` oriented toward | |
68 the root if the edge is a tree edge and away from the root if | |
69 the edge is a non-tree edge. If `root` is not specified, this | |
70 performs a depth-first search on each connected component of `G` | |
71 and returns a directed forest instead. | |
72 | |
73 If `root` is not in the graph, this raises :exc:`KeyError`. | |
74 | |
75 """ | |
76 # Create a directed graph from the depth-first search tree with | |
77 # root node `root` in which tree edges are directed toward the | |
78 # root and nontree edges are directed away from the root. For | |
79 # each node with an incident nontree edge, this creates a | |
80 # directed cycle starting with the nontree edge and returning to | |
81 # that node. | |
82 # | |
83 # The `parent` node attribute stores the parent of each node in | |
84 # the DFS tree. The `nontree` edge attribute indicates whether | |
85 # the edge is a tree edge or a nontree edge. | |
86 # | |
87 # We also store the order of the nodes found in the depth-first | |
88 # search in the `nodes` list. | |
89 H = nx.DiGraph() | |
90 nodes = [] | |
91 for u, v, d in nx.dfs_labeled_edges(G, source=root): | |
92 if d == "forward": | |
93 # `dfs_labeled_edges()` yields (root, root, 'forward') | |
94 # if it is beginning the search on a new connected | |
95 # component. | |
96 if u == v: | |
97 H.add_node(v, parent=None) | |
98 nodes.append(v) | |
99 else: | |
100 H.add_node(v, parent=u) | |
101 H.add_edge(v, u, nontree=False) | |
102 nodes.append(v) | |
103 # `dfs_labeled_edges` considers nontree edges in both | |
104 # orientations, so we need to not add the edge if it its | |
105 # other orientation has been added. | |
106 elif d == "nontree" and v not in H[u]: | |
107 H.add_edge(v, u, nontree=True) | |
108 else: | |
109 # Do nothing on 'reverse' edges; we only care about | |
110 # forward and nontree edges. | |
111 pass | |
112 return H, nodes | |
113 | |
114 def _build_chain(G, u, v, visited): | |
115 """Generate the chain starting from the given nontree edge. | |
116 | |
117 `G` is a DFS cycle graph as constructed by | |
118 :func:`_dfs_cycle_graph`. The edge (`u`, `v`) is a nontree edge | |
119 that begins a chain. `visited` is a set representing the nodes | |
120 in `G` that have already been visited. | |
121 | |
122 This function yields the edges in an initial segment of the | |
123 fundamental cycle of `G` starting with the nontree edge (`u`, | |
124 `v`) that includes all the edges up until the first node that | |
125 appears in `visited`. The tree edges are given by the 'parent' | |
126 node attribute. The `visited` set is updated to add each node in | |
127 an edge yielded by this function. | |
128 | |
129 """ | |
130 while v not in visited: | |
131 yield u, v | |
132 visited.add(v) | |
133 u, v = v, G.nodes[v]["parent"] | |
134 yield u, v | |
135 | |
136 # Create a directed version of H that has the DFS edges directed | |
137 # toward the root and the nontree edges directed away from the root | |
138 # (in each connected component). | |
139 H, nodes = _dfs_cycle_forest(G, root) | |
140 | |
141 # Visit the nodes again in DFS order. For each node, and for each | |
142 # nontree edge leaving that node, compute the fundamental cycle for | |
143 # that nontree edge starting with that edge. If the fundamental | |
144 # cycle overlaps with any visited nodes, just take the prefix of the | |
145 # cycle up to the point of visited nodes. | |
146 # | |
147 # We repeat this process for each connected component (implicitly, | |
148 # since `nodes` already has a list of the nodes grouped by connected | |
149 # component). | |
150 visited = set() | |
151 for u in nodes: | |
152 visited.add(u) | |
153 # For each nontree edge going out of node u... | |
154 edges = ((u, v) for u, v, d in H.out_edges(u, data="nontree") if d) | |
155 for u, v in edges: | |
156 # Create the cycle or cycle prefix starting with the | |
157 # nontree edge. | |
158 chain = list(_build_chain(H, u, v, visited)) | |
159 yield chain |