guohanghui/graph-theory

1from graph import Graph2from tests.test_graph import graph3x3, graph01, graph05, graph_cycle_6, graph_cycle_53 4 5def test_to_from_dict():6    d = {1: {2: 10, 3: 5},7         2: {4: 1, 3: 2},8         3: {2: 3, 4: 9, 5: 2},9         4: {5: 4},10         5: {1: 7, 4: 6},11         6: {}}12    g = Graph()13    g.from_dict(d)14    d2 = g.to_dict()15    assert d == d216 17 18def test_setitem():19    g = Graph()20    try:21        g[1][2] = 322        raise ValueError("Assignment is not permitted use g.add_edge instead.")23    except ValueError:24        pass25    g.add_node(1)26    try:27        g[1][2] = 328        raise ValueError29    except ValueError:30        pass31    g.add_edge(1, 2, 3)32    assert g.edges() == [(1, 2, 3)]33    link_1 = g.edge(1, 2)34    assert link_1 == 335    link_1 = g.edge(1, 2)36    assert link_1 == 337    link_1 = 4  # attempt setattr.38    assert g.edge(1, 2) != 4  # the edge is not an object.39    g.add_edge(1, 2, 4)40    assert g.edges() == [(1, 2, 4)]41 42    g = Graph()43    try:44        g[1] = {2: 3}45        raise ValueError46    except ValueError:47        pass48 49 50def test_add_node_attr():51    g = graph3x3()52    g.add_node(1, "this")53    assert set(g.nodes()) == set(range(1, 10))54    node_1 = g.node(1)55    assert node_1 == "this"56 57    d = {"This": 1, "That": 2}58    g.add_node(1, obj=d)59    assert g.node(1) == d60 61    rm = 562    g.del_node(rm)63    for n1, n2, d in g.edges():64        assert n1 != rm and n2 != rm65    g.del_node(rm)  # try again for a node that doesn't exist.66 67 68def test_add_edge_attr():69    g = Graph()70    try:71        g.add_edge(1, 2, {'a': 1, 'b': 2})72        raise Exception("Assignment of non-values is not supported.")73    except ValueError:74        pass75 76 77class MyCustomHashableNode():78    def __init__(self, name):79        self.name = name80 81    def __hash__(self):82        return hash(self.name)83 84    def __eq__(self, other):85        """ note that without __eq__ this wont work.86        https://stackoverflow.com/questions/9010222/why-can-a-python-dict-have-multiple-keys-with-the-same-hash?noredirect=1&lq=187        """88        return hash(self) == hash(other)89 90 91def test_node_types():92    for test in [93        [1, 2, 1, 3],94        ['A', 'B', 'A', 'C'],95        [MyCustomHashableNode(i) for i in ['A', 'B', 'A', 'C']],96    ]:97        a,b,c,d = test98        g = Graph()99        g.add_edge(a,b,10)100        g.add_edge(c,d,10)101        assert len(g.nodes()) == 3102 103 104def test_to_list():105    g1 = graph01()106    g1.add_node(44)107    g2 = Graph(from_list=g1.to_list())108    assert g1.edges() == g2.edges()109    assert g1.nodes() == g2.nodes()110 111 112def test_bidirectional_link():113    g = Graph()114    g.add_edge(node1=1, node2=2, value=4, bidirectional=True)115    assert g.edge(1, 2) == g.edge(2, 1)116 117 118def test_edges_with_node():119    g = graph3x3()120    edges = g.edges(from_node=5)121    assert set(edges) == {(5, 6, 1), (5, 8, 1)}122    assert g.edge(5, 6) == 1123    assert g.edge(5, 600) is None  # 600 doesn't exist.124 125 126def test_nodes_from_node():127    g = graph3x3()128    nodes = g.nodes(from_node=1)129    assert set(nodes) == {2, 4}130    nodes = g.nodes(to_node=9)131    assert set(nodes) == {6, 8}132    nodes = g.nodes()133    assert set(nodes) == set(range(1, 10))134 135    try:136        _ = g.nodes(in_degree=-1)137        assert False138    except ValueError:139        assert True140 141    nodes = g.nodes(in_degree=0)142    assert set(nodes) == {1}143    nodes = g.nodes(in_degree=1)144    assert set(nodes) == {2, 3, 4, 7}145    nodes = g.nodes(in_degree=2)146    assert set(nodes) == {5, 6, 8, 9}147    nodes = g.nodes(in_degree=3)148    assert nodes == []149 150    try:151        _ = g.nodes(out_degree=-1)152        assert False153    except ValueError:154        assert True155 156    nodes = g.nodes(out_degree=0)157    assert set(nodes) == {9}158 159    g.add_node(44)160    assert set(g.nodes(out_degree=0)) == {9, 44}161 162    nodes = g.nodes(out_degree=1)163    assert set(nodes) == {3, 6, 7, 8}164    nodes = g.nodes(out_degree=2)165    assert set(nodes) == {1, 2, 4, 5}166    nodes = g.nodes(out_degree=3)167    assert nodes == []168 169    try:170        _ = g.nodes(in_degree=1, out_degree=1)171        assert False172    except ValueError:173        assert True174 175 176def test01():177    """178    Asserts that the shortest_path is correct179    """180    g = graph01()181    dist, path = g.shortest_path(1, 4)182    assert [1, 3, 2, 4] == path, path183    assert 9 == dist, dist184 185 186def test02():187    """188    Assert that the dict loader works.189    """190    d = {1: {2: 10, 3: 5},191         2: {4: 1, 3: 2},192         3: {2: 3, 4: 9, 5: 2},193         4: {5: 4},194         5: {1: 7, 4: 6}}195    g = Graph(from_dict=d)196    assert 3 in g197    assert d[3][4] == g.edge(3, 4)198 199 200def test03():201    g = graph3x3()202    all_edges = g.edges()203    edges = g.edges(path=[1, 2, 3, 6, 9])204    for edge in edges:205        assert edge in all_edges, edge206 207 208def test_subgraph():209    g = graph3x3()210    g2 = g.subgraph_from_nodes([1, 2, 3, 4])211    d = {1: {2: 1, 4: 1},212         2: {3: 1},213         }214    assert g2.is_subgraph(g)215    for k, v in d.items():216        for k2, d2 in v.items():217            assert g.edge(k, k2) == g2.edge(k, k2)218 219    g3 = graph3x3()220    g3.add_edge(3, 100, 7)221    assert not g3.is_subgraph(g2)222 223 224def test_in_and_out_degree():225    g = graph3x3()226 227    in_degree = {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2, 7: 1, 8: 2, 9: 2}228    out_degree = {1: 2, 2: 2, 3: 1, 4: 2, 5: 2, 6: 1, 7: 1, 8: 1, 9: 0}229    for node in g.nodes():230        assert g.in_degree(node) == in_degree[node]231        assert g.out_degree(node) == out_degree[node]232 233def test_equals():234    g1 = Graph(from_list=[(1,2),(2,3)])235    g2 = g1.copy()236    assert g1 == g2237 238    g1.add_edge(3,1)239    g1.del_edge(3,1)240    assert g1 == g2241 242    assert g1.edges() == g2.edges()243    assert g1.nodes() == g2.nodes()244 245def test_equals_2():246    g1 = Graph(from_list=[(1,2),(2,3)])247    g2 = Graph(from_list=[(1,2),(2,3)])248    _ = g1.edge(3,1)  # simple getter.249    assert g1._edges == g2._edges250    assert g1 == g2251 252 253def test_copy_equals():254    g1 = Graph(from_list=[(1,2),(2,3)])255    g1.add_edge(3,1)256    g1.del_edge(3,1)257    g2 = g1.copy()258    assert g1 == g2259 260 261def test_copy_equals_2():262    g1 = Graph(from_list=[(1,2),(2,3)])263    g1.edge(3,1)264    g2 = g1.copy()265    assert g1 == g2266    assert g1._edges == g2._edges267    assert g1._edges is not g2._edges, "the two graphs must be independent"268    assert g1._edge_count == g2._edge_count269    270 271def test_copy():272    g = graph05()273    g2 = g.copy()274    assert set(g.edges()) == set(g2.edges())275    assert g == g2, "testing == operator failed"276    g2.add_node(1, "this")277 278    g3 = Graph(from_list=g.to_list())279    assert g2 != g3280    g2.add_node(1)281    assert g2 == g3282 283 284def test_errors():285    g = graph05()286    try:287        len(g)288        raise AssertionError289    except ValueError:290        assert True291 292    try:293        g.edges(from_node=1, to_node=1)294        raise AssertionError295    except ValueError:296        assert True297 298    try:299        g.edges(path=[1])300        raise AssertionError301    except ValueError:302        assert True303 304    try:305        g.edges(path="this")306        raise AssertionError307    except ValueError:308        assert True309 310    e = g.edges(from_node=77)311    assert e == []312 313 314def test_delitem():315    g = graph05()316 317    try:318        g.__delitem__(key=1)319        assert False320    except ValueError:321        assert True322 323    g.del_edge(node1=0, node2=1)324    g.del_edge(0, 1)  # idempotent.325 326    v = g.edge(0, 1)327    if v is not None:328        raise ValueError329    v = g.edge(0, 1, default=44)330    if v != 44:331        raise ValueError332 333 334def test_is_partite():335    g = graph_cycle_6()336    bol, partitions = g.is_partite(n=2)337    assert bol is True338 339    g = graph_cycle_5()340    bol, part = g.is_partite(n=2)341    assert bol is False342    bol, part = g.is_partite(n=5)343    assert bol is True344    assert len(part) == 5345 346 347def test_is_cyclic():348    g = graph_cycle_5()349    assert g.has_cycles()350 351 352def test_is_not_cyclic():353    g = graph3x3()354    assert not g.has_cycles()355 356 357def test_is_really_cyclic():358    g = Graph(from_list=[(1, 1, 1), (2, 2, 1)])  # two loops onto themselves.359    assert g.has_cycles()360 361 362def test_no_edge_connected():363    g = Graph()364    g.add_node(4)365    g.add_node(5)366    assert g.is_connected(4, 5) is False367 368 369def test_edge_connected():370    g = Graph()371    g.add_edge(4, 5)372    assert g.is_connected(4, 5) is True373 374 375def test_edge_not_connected():376    g = Graph()377    g.add_edge(3, 4)378    g.add_edge(5, 4)379    assert g.is_connected(3, 5) is False380 381 382def test_del_edge():383    the_sort = []384    g = Graph()385    g.add_edge(1, 2)386    g.add_edge(2, 3)387    zero_in = g.nodes(in_degree=0)388    while zero_in:389        for n in zero_in:390            the_sort.append(n)391            g.del_node(n)392        zero_in = g.nodes(in_degree=0)393    assert len(g.nodes()) == 0394    assert len(g._nodes) == 0395    assert len(g._edges) == 0396    assert len(g._reverse_edges) == 0397    assert len(g._in_degree) == 0398    assert len(g._out_degree) == 0399 400