Mercurial > repos > shellac > sam_consensus_v3
view 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 source
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)