diff env/lib/python3.9/site-packages/networkx/algorithms/isomorphism/tests/test_tree_isomorphism.py @ 0:4f3585e2f14b draft default tip

"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"

--- /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)