Mercurial > repos > shellac > sam_consensus_v3
diff env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tests/test_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 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tests/test_tree_isomorphism.py Mon Mar 22 18:12:50 2021 +0000 @@ -0,0 +1,289 @@ +import networkx as nx +import random +import time +from networkx.classes.function import is_directed + +from networkx.algorithms.isomorphism.tree_isomorphism import ( + rooted_tree_isomorphism, + tree_isomorphism, +) + + +# have this work for graph +# given two trees (either the directed or undirected) +# transform t2 according to the isomorphism +# and confirm it is identical to t1 +# randomize the order of the edges when constructing +def check_isomorphism(t1, t2, isomorphism): + + # get the name of t1, given the name in t2 + mapping = {v2: v1 for (v1, v2) in isomorphism} + + # these should be the same + d1 = is_directed(t1) + d2 = is_directed(t2) + assert d1 == d2 + + edges_1 = [] + for (u, v) in t1.edges(): + if d1: + edges_1.append((u, v)) + else: + # if not directed, then need to + # put the edge in a consistent direction + if u < v: + edges_1.append((u, v)) + else: + edges_1.append((v, u)) + + edges_2 = [] + for (u, v) in t2.edges(): + # translate to names for t1 + u = mapping[u] + v = mapping[v] + if d2: + edges_2.append((u, v)) + else: + if u < v: + edges_2.append((u, v)) + else: + edges_2.append((v, u)) + + return sorted(edges_1) == sorted(edges_2) + + +def test_hardcoded(): + + print("hardcoded test") + + # define a test problem + edges_1 = [ + ("a", "b"), + ("a", "c"), + ("a", "d"), + ("b", "e"), + ("b", "f"), + ("e", "j"), + ("e", "k"), + ("c", "g"), + ("c", "h"), + ("g", "m"), + ("d", "i"), + ("f", "l"), + ] + + edges_2 = [ + ("v", "y"), + ("v", "z"), + ("u", "x"), + ("q", "u"), + ("q", "v"), + ("p", "t"), + ("n", "p"), + ("n", "q"), + ("n", "o"), + ("o", "r"), + ("o", "s"), + ("s", "w"), + ] + + # there are two possible correct isomorphisms + # it currently returns isomorphism1 + # but the second is also correct + isomorphism1 = [ + ("a", "n"), + ("b", "q"), + ("c", "o"), + ("d", "p"), + ("e", "v"), + ("f", "u"), + ("g", "s"), + ("h", "r"), + ("i", "t"), + ("j", "y"), + ("k", "z"), + ("l", "x"), + ("m", "w"), + ] + + # could swap y and z + isomorphism2 = [ + ("a", "n"), + ("b", "q"), + ("c", "o"), + ("d", "p"), + ("e", "v"), + ("f", "u"), + ("g", "s"), + ("h", "r"), + ("i", "t"), + ("j", "z"), + ("k", "y"), + ("l", "x"), + ("m", "w"), + ] + + t1 = nx.Graph() + t1.add_edges_from(edges_1) + root1 = "a" + + t2 = nx.Graph() + t2.add_edges_from(edges_2) + root2 = "n" + + isomorphism = sorted(rooted_tree_isomorphism(t1, root1, t2, root2)) + + # is correct by hand + assert (isomorphism == isomorphism1) or (isomorphism == isomorphism2) + + # check algorithmically + assert check_isomorphism(t1, t2, isomorphism) + + # try again as digraph + t1 = nx.DiGraph() + t1.add_edges_from(edges_1) + root1 = "a" + + t2 = nx.DiGraph() + t2.add_edges_from(edges_2) + root2 = "n" + + isomorphism = sorted(rooted_tree_isomorphism(t1, root1, t2, root2)) + + # is correct by hand + assert (isomorphism == isomorphism1) or (isomorphism == isomorphism2) + + # check algorithmically + assert check_isomorphism(t1, t2, isomorphism) + + +# randomly swap a tuple (a,b) +def random_swap(t): + (a, b) = t + if random.randint(0, 1) == 1: + return (a, b) + else: + return (b, a) + + +# given a tree t1, create a new tree t2 +# that is isomorphic to t1, with a known isomorphism +# and test that our algorithm found the right one +def positive_single_tree(t1): + + assert nx.is_tree(t1) + + nodes1 = [n for n in t1.nodes()] + # get a random permutation of this + nodes2 = nodes1.copy() + random.shuffle(nodes2) + + # this is one isomorphism, however they may be multiple + # so we don't necessarily get this one back + someisomorphism = [(u, v) for (u, v) in zip(nodes1, nodes2)] + + # map from old to new + map1to2 = {u: v for (u, v) in someisomorphism} + + # get the edges with the transformed names + edges2 = [random_swap((map1to2[u], map1to2[v])) for (u, v) in t1.edges()] + # randomly permute, to ensure we're not relying on edge order somehow + random.shuffle(edges2) + + # so t2 is isomorphic to t1 + t2 = nx.Graph() + t2.add_edges_from(edges2) + + # lets call our code to see if t1 and t2 are isomorphic + isomorphism = tree_isomorphism(t1, t2) + + # make sure we got a correct solution + # although not necessarily someisomorphism + assert len(isomorphism) > 0 + assert check_isomorphism(t1, t2, isomorphism) + + +# run positive_single_tree over all the +# non-isomorphic trees for k from 4 to maxk +# k = 4 is the first level that has more than 1 non-isomorphic tree +# k = 13 takes about 2.86 seconds to run on my laptop +# larger values run slow down significantly +# as the number of trees grows rapidly +def test_positive(maxk=14): + + print("positive test") + + for k in range(2, maxk + 1): + start_time = time.time() + trial = 0 + for t in nx.nonisomorphic_trees(k): + positive_single_tree(t) + trial += 1 + print(k, trial, time.time() - start_time) + + +# test the trivial case of a single node in each tree +# note that nonisomorphic_trees doesn't work for k = 1 +def test_trivial(): + + print("trivial test") + + # back to an undirected graph + t1 = nx.Graph() + t1.add_node("a") + root1 = "a" + + t2 = nx.Graph() + t2.add_node("n") + root2 = "n" + + isomorphism = rooted_tree_isomorphism(t1, root1, t2, root2) + + assert isomorphism == [("a", "n")] + + assert check_isomorphism(t1, t2, isomorphism) + + +# test another trivial case where the two graphs have +# different numbers of nodes +def test_trivial_2(): + + print("trivial test 2") + + edges_1 = [("a", "b"), ("a", "c")] + + edges_2 = [("v", "y")] + + t1 = nx.Graph() + t1.add_edges_from(edges_1) + + t2 = nx.Graph() + t2.add_edges_from(edges_2) + + isomorphism = tree_isomorphism(t1, t2) + + # they cannot be isomorphic, + # since they have different numbers of nodes + assert isomorphism == [] + + +# the function nonisomorphic_trees generates all the non-isomorphic +# trees of a given size. Take each pair of these and verify that +# they are not isomorphic +# k = 4 is the first level that has more than 1 non-isomorphic tree +# k = 11 takes about 4.76 seconds to run on my laptop +# larger values run slow down significantly +# as the number of trees grows rapidly +def test_negative(maxk=11): + + print("negative test") + + for k in range(4, maxk + 1): + test_trees = list(nx.nonisomorphic_trees(k)) + start_time = time.time() + trial = 0 + for i in range(len(test_trees) - 1): + for j in range(i + 1, len(test_trees)): + trial += 1 + assert tree_isomorphism(test_trees[i], test_trees[j]) == [] + print(k, trial, time.time() - start_time)