Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
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"""
21from collections import defaultdict
23import networkx as nx
24from networkx.utils.decorators import not_implemented_for
26__all__ = ["rooted_tree_isomorphism", "tree_isomorphism"]
29@nx._dispatchable(graphs={"t1": 0, "t2": 2}, returns_graph=True)
30def root_trees(t1, root1, t2, root2):
31 """Create a single digraph dT of free trees t1 and t2
32 # with roots root1 and root2 respectively
33 # rename the nodes with consecutive integers
34 # so that all nodes get a unique name between both trees
36 # our new "fake" root node is 0
37 # t1 is numbers from 1 ... n
38 # t2 is numbered from n+1 to 2n
39 """
41 dT = nx.DiGraph()
43 newroot1 = 1 # left root will be 1
44 newroot2 = nx.number_of_nodes(t1) + 1 # right will be n+1
46 # may be overlap in node names here so need separate maps
47 # given the old name, what is the new
48 namemap1 = {root1: newroot1}
49 namemap2 = {root2: newroot2}
51 # add an edge from our new root to root1 and root2
52 dT.add_edge(0, namemap1[root1])
53 dT.add_edge(0, namemap2[root2])
55 for i, (v1, v2) in enumerate(nx.bfs_edges(t1, root1)):
56 namemap1[v2] = i + namemap1[root1] + 1
57 dT.add_edge(namemap1[v1], namemap1[v2])
59 for i, (v1, v2) in enumerate(nx.bfs_edges(t2, root2)):
60 namemap2[v2] = i + namemap2[root2] + 1
61 dT.add_edge(namemap2[v1], namemap2[v2])
63 # now we really want the inverse of namemap1 and namemap2
64 # giving the old name given the new
65 # since the values of namemap1 and namemap2 are unique
66 # there won't be collisions
67 namemap = {}
68 for old, new in namemap1.items():
69 namemap[new] = old
70 for old, new in namemap2.items():
71 namemap[new] = old
73 return (dT, namemap, newroot1, newroot2)
76@nx._dispatchable(graphs={"t1": 0, "t2": 2})
77def rooted_tree_isomorphism(t1, root1, t2, root2):
78 """
79 Return an isomorphic mapping between rooted trees `t1` and `t2` with roots
80 `root1` and `root2`, respectively.
82 These trees may be either directed or undirected,
83 but if they are directed, all edges should flow from the root.
85 It returns the isomorphism, a mapping of the nodes of `t1` onto the nodes
86 of `t2`, such that two trees are then identical.
88 Note that two trees may have more than one isomorphism, and this
89 routine just returns one valid mapping.
90 This is a subroutine used to implement `tree_isomorphism`, but will
91 be somewhat faster if you already have rooted trees.
93 Parameters
94 ----------
95 t1 : NetworkX graph
96 One of the trees being compared
98 root1 : node
99 A node of `t1` which is the root of the tree
101 t2 : NetworkX graph
102 The other tree being compared
104 root2 : node
105 a node of `t2` which is the root of the tree
107 Returns
108 -------
109 isomorphism : list
110 A list of pairs in which the left element is a node in `t1`
111 and the right element is a node in `t2`. The pairs are in
112 arbitrary order. If the nodes in one tree is mapped to the names in
113 the other, then trees will be identical. Note that an isomorphism
114 will not necessarily be unique.
116 If `t1` and `t2` are not isomorphic, then it returns the empty list.
118 Raises
119 ------
120 NetworkXError
121 If either `t1` or `t2` is not a tree
122 """
124 if not nx.is_tree(t1):
125 raise nx.NetworkXError("t1 is not a tree")
126 if not nx.is_tree(t2):
127 raise nx.NetworkXError("t2 is not a tree")
129 # get the rooted tree formed by combining them
130 # with unique names
131 (dT, namemap, newroot1, newroot2) = root_trees(t1, root1, t2, root2)
133 # Group nodes by their distance from the root
134 L = defaultdict(list)
135 for n, dist in nx.shortest_path_length(dT, source=0).items():
136 L[dist].append(n)
138 # height
139 h = max(L)
141 # each node has a label, initially set to 0
142 label = {v: 0 for v in dT}
143 # and also ordered_labels and ordered_children
144 # which will store ordered tuples
145 ordered_labels = {v: () for v in dT}
146 ordered_children = {v: () for v in dT}
148 # nothing to do on last level so start on h-1
149 # also nothing to do for our fake level 0, so skip that
150 for i in range(h - 1, 0, -1):
151 # update the ordered_labels and ordered_children
152 # for any children
153 for v in L[i]:
154 # nothing to do if no children
155 if dT.out_degree(v) > 0:
156 # get all the pairs of labels and nodes of children and sort by labels
157 # reverse=True to preserve DFS order, see gh-7945
158 s = sorted(((label[u], u) for u in dT.successors(v)), reverse=True)
160 # invert to give a list of two tuples
161 # the sorted labels, and the corresponding children
162 ordered_labels[v], ordered_children[v] = list(zip(*s))
164 # now collect and sort the sorted ordered_labels
165 # for all nodes in L[i], carrying along the node
166 forlabel = sorted((ordered_labels[v], v) for v in L[i])
168 # now assign labels to these nodes, according to the sorted order
169 # starting from 0, where identical ordered_labels get the same label
170 current = 0
171 for i, (ol, v) in enumerate(forlabel):
172 # advance to next label if not 0, and different from previous
173 if (i != 0) and (ol != forlabel[i - 1][0]):
174 current += 1
175 label[v] = current
177 # they are isomorphic if the labels of newroot1 and newroot2 are 0
178 isomorphism = []
179 if label[newroot1] == 0 and label[newroot2] == 0:
180 # now lets get the isomorphism by walking the ordered_children
181 stack = [(newroot1, newroot2)]
182 while stack:
183 curr_v, curr_w = stack.pop()
184 isomorphism.append((curr_v, curr_w))
185 stack.extend(zip(ordered_children[curr_v], ordered_children[curr_w]))
187 # get the mapping back in terms of the old names
188 # return in sorted order for neatness
189 isomorphism = [(namemap[u], namemap[v]) for (u, v) in isomorphism]
191 return isomorphism
194@not_implemented_for("directed")
195@not_implemented_for("multigraph")
196@nx._dispatchable(graphs={"t1": 0, "t2": 1})
197def tree_isomorphism(t1, t2):
198 """
199 Return an isomorphic mapping between two trees `t1` and `t2`.
201 If `t1` and `t2` are not isomorphic, an empty list is returned.
202 Note that two trees may have more than one isomorphism, and this routine just
203 returns one valid mapping.
205 Parameters
206 ----------
207 t1 : undirected NetworkX graph
208 One of the trees being compared
210 t2 : undirected NetworkX graph
211 The other tree being compared
213 Returns
214 -------
215 isomorphism : list
216 A list of pairs in which the left element is a node in `t1`
217 and the right element is a node in `t2`. The pairs are in
218 arbitrary order. If the nodes in one tree is mapped to the names in
219 the other, then trees will be identical. Note that an isomorphism
220 will not necessarily be unique.
222 If `t1` and `t2` are not isomorphic, then it returns the empty list.
224 Raises
225 ------
226 NetworkXError
227 If either `t1` or `t2` is not a tree
229 Notes
230 -----
231 This runs in ``O(n*log(n))`` time for trees with ``n`` nodes.
232 """
233 if not nx.is_tree(t1):
234 raise nx.NetworkXError("t1 is not a tree")
235 if not nx.is_tree(t2):
236 raise nx.NetworkXError("t2 is not a tree")
238 # To be isomorphic, t1 and t2 must have the same number of nodes and sorted
239 # degree sequences
240 if not nx.faster_could_be_isomorphic(t1, t2):
241 return []
243 # A tree can have either 1 or 2 centers.
244 # If the number doesn't match then t1 and t2 are not isomorphic.
245 center1 = nx.center(t1)
246 center2 = nx.center(t2)
248 if len(center1) != len(center2):
249 return []
251 # If there is only 1 center in each, then use it.
252 if len(center1) == 1:
253 return rooted_tree_isomorphism(t1, center1[0], t2, center2[0])
255 # If there both have 2 centers, then try the first for t1
256 # with the first for t2.
257 attempts = rooted_tree_isomorphism(t1, center1[0], t2, center2[0])
259 # If that worked we're done.
260 if len(attempts) > 0:
261 return attempts
263 # Otherwise, try center1[0] with the center2[1], and see if that works
264 return rooted_tree_isomorphism(t1, center1[0], t2, center2[1])