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