Skip to content
Snippets Groups Projects
Select Git revision
  • 2194946825b3c71a4d097846f5b9aea6dc9b23f9
  • master default protected
2 results

find_duplicates_test.cpp

Blame
    • tests.py 2.22 KiB
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60 
    

    

    

    """Helper to run tests.

>>> from .all import *
>>> from sage.all import *

>>> g2g = lambda gadget: gadget.eval(UnderlayingGraph)
>>> assert graphs.CompleteGraph(4).is_isomorphic(g2g(Necklace.graph(1)))
>>> assert graphs.PetersenGraph().is_isomorphic(g2g(Petersen))
>>> assert all( \
      g2g(CyclicLadder().graph(i)).is_isomorphic(g2g(GeneralizedPetersen(1).graph(i))) \
    for i in range(3, 20) )
>>> cdc_count = lambda gadget: gadget.eval(CircuitDoubleCover)
>>> cdc_count(Petersen)
52
>>> cdc_count(GeneralizedPetersen(2).graph(5))
52
>>> cdc_count(FlowerSnark.graph(3))
104
>>> all( cdc_count(Necklace.graph(i)) == 2 * 4**(i-1) for i in range(1, 100) )
True


>>> Necklace.stabilize(CircuitDoubleCover)
Loop 1 done - 1 boundaries (0 new)
{'variables': [((1, 2), (1, 2), None)], 'step_matrix': [4], 'initial_vector': [2], \
'finalize': [1], 'simplified': ([1], [4], [2]), 'formula': 1/2*4^k, 'formula_if': k - 1 >= 0}

>>> f = CyclicLadder().stabilize(CircuitDoubleCover, start_at=1)['formula']; f
Loop 1 done - 6 boundaries (6 new)
Loop 2 done - 13 boundaries (6 new)
Loop 3 done - 15 boundaries (2 new)
Loop 4 done - 15 boundaries (0 new)
1/2*(-1)^k*(k - 1) + 1/6*4^(k - 1) + 3*2^(k - 1) + 1/3*(-2)^(k - 2) - 5/2*k - 3/2
>>> assert all( f(k=k) == cdc_count(CyclicLadder().graph(k)) for k in range(3, 10) )

>>> f = CyclicLadder(crossed=True).stabilize(CircuitDoubleCover, start_at=3)['formula']; f
Loop 1 done - 12 boundaries (4 new)
Loop 2 done - 14 boundaries (0 new)
-1/2*(-1)^k*k + 1/6*4^(k - 1) + 3*2^(k - 1) + 1/3*(-2)^(k - 2) - 5/2*k
>>> assert all( f(k=k) == cdc_count(CyclicLadder(True).graph(k)) for k in range(3, 10) )

>>> sun_cdc = lambda n: sum( b.value for b in sun(n).eval_gadget(CircuitDoubleCover) )
>>> all( sun_cdc(n) == 2**n - 2*n for n in range(3, 10) )
True

>>> d = [ list(range(5)), list(range(5, 10)) ]
>>> graph_to_gadget(graphs.PetersenGraph(), d).eval(GroupFlow(Integers(3), False))
729
>>> graph_to_gadget(graphs.PetersenGraph(), d).eval(GroupFlow(Integers(4), True))
0
>>> graph_to_gadget(graphs.PetersenGraph(), d).eval(GroupFlow(Integers(5), True))
240


>>> [ GeneralizedPetersen(1).graph(i).eval(CircuitDoubleCover) for i in range(3, 16) ]
[4, 26, 72, 258, 842, 3118, 11620, 45290, 177630, 705510, 2807768, 11210722, 44785618]

"""