guohanghui/graph-theory

1from graph import Graph2from graph.hash_methods import graph_hash, flow_graph_hash, merkle_tree3 4 5def test_merkle_tree_1_block():6    data_blocks = [b"this"]7    g = merkle_tree(data_blocks)8    assert len(g.nodes()) == 19 10 11def test_merkle_tree_2_blocks():12    data_blocks = [b"this",13                   b"that"]14    g = merkle_tree(data_blocks)15    assert len(g.nodes()) == 316 17 18def test_merkle_tree_3_blocks():19    data_blocks = [b"this",20                   b"that",21                   b"them"]22    g = merkle_tree(data_blocks)23    assert len(g.nodes()) == 524 25 26def test_merkle_tree_4_blocks():27    data_blocks = [b"this",28                   b"that",29                   b"them",30                   b"they"]31    g = merkle_tree(data_blocks)32    assert len(g.nodes()) == 733 34 35def test_flow_graph_hash_01():36    """37    This example includes a loop to distinguish it from the common merkle tree.38 39    S-1         S-2             S-3                 S-440 (hash S1)   (hash S2)       (hash S3)           (hash S4)41     +          +   +            +42     |          |   +----------->+43     |          |                +<-------------+44     v          v                v              |45          I-1                    I-2            | (loop)46     (hash S1+S2+I1)         (hash S3 + I2)     |47     +          +                +              |48     |          |                +------------->+49     v          |                |50     E-1        +---> E-2 <------+51 (hash I1+E1)    (hash I1+I2+E2)52 53    """54    links = [55        ('s-1', 'i-1', 1),56        ('s-2', 'i-1', 1),57        ('i-1', 'e-1', 1),58        ('i-1', 'e-2', 1),59        ('s-3', 'i-2', 1),60        ('i-2', 'i-2', 1),61        ('i-2', 'e-2', 1),62    ]63    g = Graph(from_list=links)64    g.add_node('s-4')65    g2 = flow_graph_hash(g)66    assert len(g2.nodes()) == len(g.nodes())67 68 69def test_flow_graph_loop_01():70    links = [71        (1, 2, 1),72        (2, 3, 1),73        (3, 4, 1),74        (3, 2, 1)75    ]76    g = Graph(from_list=links)77    g2 = flow_graph_hash(g)78    assert len(g2.nodes()) == len(g.nodes())79 80 81def test_flow_graph_async_01():82    """83 84    (s1) --> (i2) --> (e4)85                      /86             (s3) -->/87    """88    links = [89        (1, 2, 1),90        (2, 4, 1),91        (3, 4, 1)92    ]93    g = Graph(from_list=links)94    g2 = flow_graph_hash(g)95    assert len(g2.nodes()) == len(g.nodes())96 97 98def test_graph_hash():99    """100    Simple test of the graph hash function.101    """102    links = [103        (1, 2, 1),104        (2, 3, 1),105        (3, 4, 1),106        (3, 2, 1)107    ]108    g = Graph(from_list=links)109    h = graph_hash(g)110    assert isinstance(h, int)111    assert sum((int(d) for d in str(h))) == 312112 113