Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tree_isomorphism.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 """ | |
2 An algorithm for finding if two undirected trees are isomorphic, | |
3 and if so returns an isomorphism between the two sets of nodes. | |
4 | |
5 This algorithm uses a routine to tell if two rooted trees (trees with a | |
6 specified root node) are isomorphic, which may be independently useful. | |
7 | |
8 This implements an algorithm from: | |
9 The Design and Analysis of Computer Algorithms | |
10 by Aho, Hopcroft, and Ullman | |
11 Addison-Wesley Publishing 1974 | |
12 Example 3.2 pp. 84-86. | |
13 | |
14 A more understandable version of this algorithm is described in: | |
15 Homework Assignment 5 | |
16 McGill University SOCS 308-250B, Winter 2002 | |
17 by Matthew Suderman | |
18 http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf | |
19 """ | |
20 | |
21 import networkx as nx | |
22 from networkx.utils.decorators import not_implemented_for | |
23 | |
24 __all__ = ["rooted_tree_isomorphism", "tree_isomorphism"] | |
25 | |
26 | |
27 def root_trees(t1, root1, t2, root2): | |
28 """ Create a single digraph dT of free trees t1 and t2 | |
29 # with roots root1 and root2 respectively | |
30 # rename the nodes with consecutive integers | |
31 # so that all nodes get a unique name between both trees | |
32 | |
33 # our new "fake" root node is 0 | |
34 # t1 is numbers from 1 ... n | |
35 # t2 is numbered from n+1 to 2n | |
36 """ | |
37 | |
38 dT = nx.DiGraph() | |
39 | |
40 newroot1 = 1 # left root will be 1 | |
41 newroot2 = nx.number_of_nodes(t1) + 1 # right will be n+1 | |
42 | |
43 # may be overlap in node names here so need separate maps | |
44 # given the old name, what is the new | |
45 namemap1 = {root1: newroot1} | |
46 namemap2 = {root2: newroot2} | |
47 | |
48 # add an edge from our new root to root1 and root2 | |
49 dT.add_edge(0, namemap1[root1]) | |
50 dT.add_edge(0, namemap2[root2]) | |
51 | |
52 for i, (v1, v2) in enumerate(nx.bfs_edges(t1, root1)): | |
53 namemap1[v2] = i + namemap1[root1] + 1 | |
54 dT.add_edge(namemap1[v1], namemap1[v2]) | |
55 | |
56 for i, (v1, v2) in enumerate(nx.bfs_edges(t2, root2)): | |
57 namemap2[v2] = i + namemap2[root2] + 1 | |
58 dT.add_edge(namemap2[v1], namemap2[v2]) | |
59 | |
60 # now we really want the inverse of namemap1 and namemap2 | |
61 # giving the old name given the new | |
62 # since the values of namemap1 and namemap2 are unique | |
63 # there won't be collisions | |
64 namemap = {} | |
65 for old, new in namemap1.items(): | |
66 namemap[new] = old | |
67 for old, new in namemap2.items(): | |
68 namemap[new] = old | |
69 | |
70 return (dT, namemap, newroot1, newroot2) | |
71 | |
72 | |
73 # figure out the level of each node, with 0 at root | |
74 def assign_levels(G, root): | |
75 level = {} | |
76 level[root] = 0 | |
77 for (v1, v2) in nx.bfs_edges(G, root): | |
78 level[v2] = level[v1] + 1 | |
79 | |
80 return level | |
81 | |
82 | |
83 # now group the nodes at each level | |
84 def group_by_levels(levels): | |
85 L = {} | |
86 for (n, lev) in levels.items(): | |
87 if lev not in L: | |
88 L[lev] = [] | |
89 L[lev].append(n) | |
90 | |
91 return L | |
92 | |
93 | |
94 # now lets get the isomorphism by walking the ordered_children | |
95 def generate_isomorphism(v, w, M, ordered_children): | |
96 # make sure tree1 comes first | |
97 assert v < w | |
98 M.append((v, w)) | |
99 for i, (x, y) in enumerate(zip(ordered_children[v], ordered_children[w])): | |
100 generate_isomorphism(x, y, M, ordered_children) | |
101 | |
102 | |
103 def rooted_tree_isomorphism(t1, root1, t2, root2): | |
104 """ | |
105 Given two rooted trees `t1` and `t2`, | |
106 with roots `root1` and `root2` respectivly | |
107 this routine will determine if they are isomorphic. | |
108 | |
109 These trees may be either directed or undirected, | |
110 but if they are directed, all edges should flow from the root. | |
111 | |
112 It returns the isomorphism, a mapping of the nodes of `t1` onto the nodes | |
113 of `t2`, such that two trees are then identical. | |
114 | |
115 Note that two trees may have more than one isomorphism, and this | |
116 routine just returns one valid mapping. | |
117 | |
118 Parameters | |
119 ---------- | |
120 `t1` : NetworkX graph | |
121 One of the trees being compared | |
122 | |
123 `root1` : a node of `t1` which is the root of the tree | |
124 | |
125 `t2` : undirected NetworkX graph | |
126 The other tree being compared | |
127 | |
128 `root2` : a node of `t2` which is the root of the tree | |
129 | |
130 This is a subroutine used to implement `tree_isomorphism`, but will | |
131 be somewhat faster if you already have rooted trees. | |
132 | |
133 Returns | |
134 ------- | |
135 isomorphism : list | |
136 A list of pairs in which the left element is a node in `t1` | |
137 and the right element is a node in `t2`. The pairs are in | |
138 arbitrary order. If the nodes in one tree is mapped to the names in | |
139 the other, then trees will be identical. Note that an isomorphism | |
140 will not necessarily be unique. | |
141 | |
142 If `t1` and `t2` are not isomorphic, then it returns the empty list. | |
143 """ | |
144 | |
145 assert nx.is_tree(t1) | |
146 assert nx.is_tree(t2) | |
147 | |
148 # get the rooted tree formed by combining them | |
149 # with unique names | |
150 (dT, namemap, newroot1, newroot2) = root_trees(t1, root1, t2, root2) | |
151 | |
152 # compute the distance from the root, with 0 for our | |
153 levels = assign_levels(dT, 0) | |
154 | |
155 # height | |
156 h = max(levels.values()) | |
157 | |
158 # collect nodes into a dict by level | |
159 L = group_by_levels(levels) | |
160 | |
161 # each node has a label, initially set to 0 | |
162 label = {v: 0 for v in dT} | |
163 # and also ordered_labels and ordered_children | |
164 # which will store ordered tuples | |
165 ordered_labels = {v: () for v in dT} | |
166 ordered_children = {v: () for v in dT} | |
167 | |
168 # nothing to do on last level so start on h-1 | |
169 # also nothing to do for our fake level 0, so skip that | |
170 for i in range(h - 1, 0, -1): | |
171 # update the ordered_labels and ordered_childen | |
172 # for any children | |
173 for v in L[i]: | |
174 # nothing to do if no children | |
175 if dT.out_degree(v) > 0: | |
176 # get all the pairs of labels and nodes of children | |
177 # and sort by labels | |
178 s = sorted([(label[u], u) for u in dT.successors(v)]) | |
179 | |
180 # invert to give a list of two tuples | |
181 # the sorted labels, and the corresponding children | |
182 ordered_labels[v], ordered_children[v] = list(zip(*s)) | |
183 | |
184 # now collect and sort the sorted ordered_labels | |
185 # for all nodes in L[i], carrying along the node | |
186 forlabel = sorted([(ordered_labels[v], v) for v in L[i]]) | |
187 | |
188 # now assign labels to these nodes, according to the sorted order | |
189 # starting from 0, where idential ordered_labels get the same label | |
190 current = 0 | |
191 for i, (ol, v) in enumerate(forlabel): | |
192 # advance to next label if not 0, and different from previous | |
193 if (i != 0) and (ol != forlabel[i - 1][0]): | |
194 current += 1 | |
195 label[v] = current | |
196 | |
197 # they are isomorphic if the labels of newroot1 and newroot2 are 0 | |
198 isomorphism = [] | |
199 if label[newroot1] == 0 and label[newroot2] == 0: | |
200 generate_isomorphism(newroot1, newroot2, isomorphism, ordered_children) | |
201 | |
202 # get the mapping back in terms of the old names | |
203 # return in sorted order for neatness | |
204 isomorphism = [(namemap[u], namemap[v]) for (u, v) in isomorphism] | |
205 | |
206 return isomorphism | |
207 | |
208 | |
209 @not_implemented_for("directed", "multigraph") | |
210 def tree_isomorphism(t1, t2): | |
211 """ | |
212 Given two undirected (or free) trees `t1` and `t2`, | |
213 this routine will determine if they are isomorphic. | |
214 It returns the isomorphism, a mapping of the nodes of `t1` onto the nodes | |
215 of `t2`, such that two trees are then identical. | |
216 | |
217 Note that two trees may have more than one isomorphism, and this | |
218 routine just returns one valid mapping. | |
219 | |
220 Parameters | |
221 ---------- | |
222 t1 : undirected NetworkX graph | |
223 One of the trees being compared | |
224 | |
225 t2 : undirected NetworkX graph | |
226 The other tree being compared | |
227 | |
228 Returns | |
229 ------- | |
230 isomorphism : list | |
231 A list of pairs in which the left element is a node in `t1` | |
232 and the right element is a node in `t2`. The pairs are in | |
233 arbitrary order. If the nodes in one tree is mapped to the names in | |
234 the other, then trees will be identical. Note that an isomorphism | |
235 will not necessarily be unique. | |
236 | |
237 If `t1` and `t2` are not isomorphic, then it returns the empty list. | |
238 | |
239 Notes | |
240 ----- | |
241 This runs in O(n*log(n)) time for trees with n nodes. | |
242 """ | |
243 | |
244 assert nx.is_tree(t1) | |
245 assert nx.is_tree(t2) | |
246 | |
247 # To be isomrophic, t1 and t2 must have the same number of nodes. | |
248 if nx.number_of_nodes(t1) != nx.number_of_nodes(t2): | |
249 return [] | |
250 | |
251 # Another shortcut is that the sorted degree sequences need to be the same. | |
252 degree_sequence1 = sorted([d for (n, d) in t1.degree()]) | |
253 degree_sequence2 = sorted([d for (n, d) in t2.degree()]) | |
254 | |
255 if degree_sequence1 != degree_sequence2: | |
256 return [] | |
257 | |
258 # A tree can have either 1 or 2 centers. | |
259 # If the number doesn't match then t1 and t2 are not isomorphic. | |
260 center1 = nx.center(t1) | |
261 center2 = nx.center(t2) | |
262 | |
263 if len(center1) != len(center2): | |
264 return [] | |
265 | |
266 # If there is only 1 center in each, then use it. | |
267 if len(center1) == 1: | |
268 return rooted_tree_isomorphism(t1, center1[0], t2, center2[0]) | |
269 | |
270 # If there both have 2 centers, then try the first for t1 | |
271 # with the first for t2. | |
272 attemps = rooted_tree_isomorphism(t1, center1[0], t2, center2[0]) | |
273 | |
274 # If that worked we're done. | |
275 if len(attemps) > 0: | |
276 return attemps | |
277 | |
278 # Otherwise, try center1[0] with the center2[1], and see if that works | |
279 return rooted_tree_isomorphism(t1, center1[0], t2, center2[1]) |