import unittest from altgraph import GraphError from altgraph.Graph import Graph class TestGraph(unittest.TestCase): def test_nodes(self): graph = Graph() self.assertEqual(graph.node_list(), []) o1 = object() o1b = object() o2 = object() graph.add_node(1, o1) graph.add_node(1, o1b) graph.add_node(2, o2) graph.add_node(3) self.assertRaises(TypeError, graph.add_node, []) self.assertTrue(graph.node_data(1) is o1) self.assertTrue(graph.node_data(2) is o2) self.assertTrue(graph.node_data(3) is None) self.assertTrue(1 in graph) self.assertTrue(2 in graph) self.assertTrue(3 in graph) self.assertEqual(graph.number_of_nodes(), 3) self.assertEqual(graph.number_of_hidden_nodes(), 0) self.assertEqual(graph.hidden_node_list(), []) self.assertEqual(list(sorted(graph)), [1, 2, 3]) graph.hide_node(1) graph.hide_node(2) graph.hide_node(3) self.assertEqual(graph.number_of_nodes(), 0) self.assertEqual(graph.number_of_hidden_nodes(), 3) self.assertEqual(list(sorted(graph.hidden_node_list())), [1, 2, 3]) self.assertFalse(1 in graph) self.assertFalse(2 in graph) self.assertFalse(3 in graph) graph.add_node(1) self.assertFalse(1 in graph) graph.restore_node(1) self.assertTrue(1 in graph) self.assertFalse(2 in graph) self.assertFalse(3 in graph) graph.restore_all_nodes() self.assertTrue(1 in graph) self.assertTrue(2 in graph) self.assertTrue(3 in graph) self.assertEqual(list(sorted(graph.node_list())), [1, 2, 3]) v = graph.describe_node(1) self.assertEqual(v, (1, o1, [], [])) def test_edges(self): graph = Graph() graph.add_node(1) graph.add_node(2) graph.add_node(3) graph.add_node(4) graph.add_node(5) self.assertTrue(isinstance(graph.edge_list(), list)) graph.add_edge(1, 2) graph.add_edge(4, 5, "a") self.assertRaises(GraphError, graph.add_edge, "a", "b", create_nodes=False) self.assertEqual(graph.number_of_hidden_edges(), 0) self.assertEqual(graph.number_of_edges(), 2) self.assertEqual(graph.hidden_edge_list(), []) e = graph.edge_by_node(1, 2) self.assertTrue(isinstance(e, int)) graph.hide_edge(e) self.assertEqual(graph.number_of_hidden_edges(), 1) self.assertEqual(graph.number_of_edges(), 1) self.assertEqual(graph.hidden_edge_list(), [e]) e2 = graph.edge_by_node(1, 2) self.assertTrue(e2 is None) graph.restore_edge(e) e2 = graph.edge_by_node(1, 2) self.assertEqual(e, e2) self.assertEqual(graph.number_of_hidden_edges(), 0) self.assertEqual(graph.number_of_edges(), 2) e1 = graph.edge_by_node(1, 2) e2 = graph.edge_by_node(4, 5) graph.hide_edge(e1) graph.hide_edge(e2) self.assertEqual(graph.number_of_edges(), 0) graph.restore_all_edges() self.assertEqual(graph.number_of_edges(), 2) self.assertEqual(graph.edge_by_id(e1), (1, 2)) self.assertRaises(GraphError, graph.edge_by_id, (e1 + 1) * (e2 + 1) + 1) self.assertEqual(list(sorted(graph.edge_list())), [e1, e2]) self.assertEqual(graph.describe_edge(e1), (e1, 1, 1, 2)) self.assertEqual(graph.describe_edge(e2), (e2, "a", 4, 5)) self.assertEqual(graph.edge_data(e1), 1) self.assertEqual(graph.edge_data(e2), "a") self.assertEqual(graph.head(e2), 4) self.assertEqual(graph.tail(e2), 5) graph.add_edge(1, 3) graph.add_edge(1, 5) graph.add_edge(4, 1) self.assertEqual(list(sorted(graph.out_nbrs(1))), [2, 3, 5]) self.assertEqual(list(sorted(graph.inc_nbrs(1))), [4]) self.assertEqual(list(sorted(graph.inc_nbrs(5))), [1, 4]) self.assertEqual(list(sorted(graph.all_nbrs(1))), [2, 3, 4, 5]) graph.add_edge(5, 1) self.assertEqual(list(sorted(graph.all_nbrs(5))), [1, 4]) self.assertEqual(graph.out_degree(1), 3) self.assertEqual(graph.inc_degree(2), 1) self.assertEqual(graph.inc_degree(5), 2) self.assertEqual(graph.all_degree(5), 3) v = graph.out_edges(4) self.assertTrue(isinstance(v, list)) self.assertEqual(graph.edge_by_id(v[0]), (4, 5)) v = graph.out_edges(1) for e in v: self.assertEqual(graph.edge_by_id(e)[0], 1) v = graph.inc_edges(1) self.assertTrue(isinstance(v, list)) self.assertEqual(graph.edge_by_id(v[0]), (4, 1)) v = graph.inc_edges(5) for e in v: self.assertEqual(graph.edge_by_id(e)[1], 5) v = graph.all_edges(5) for e in v: self.assertTrue(graph.edge_by_id(e)[1] == 5 or graph.edge_by_id(e)[0] == 5) e1 = graph.edge_by_node(1, 2) self.assertTrue(isinstance(e1, int)) graph.hide_node(1) self.assertRaises(GraphError, graph.edge_by_node, 1, 2) graph.restore_node(1) e2 = graph.edge_by_node(1, 2) self.assertEqual(e1, e2) self.assertRaises(GraphError, graph.hide_edge, "foo") self.assertRaises(GraphError, graph.hide_node, "foo") self.assertRaises(GraphError, graph.inc_edges, "foo") self.assertEqual(repr(graph), "") def test_toposort(self): graph = Graph() graph.add_node(1) graph.add_node(2) graph.add_node(3) graph.add_node(4) graph.add_node(5) graph.add_edge(1, 2) graph.add_edge(1, 3) graph.add_edge(2, 4) graph.add_edge(3, 5) ok, result = graph.forw_topo_sort() self.assertTrue(ok) for idx in range(1, 6): self.assertTrue(idx in result) self.assertTrue(result.index(1) < result.index(2)) self.assertTrue(result.index(1) < result.index(3)) self.assertTrue(result.index(2) < result.index(4)) self.assertTrue(result.index(3) < result.index(5)) ok, result = graph.back_topo_sort() self.assertTrue(ok) for idx in range(1, 6): self.assertTrue(idx in result) self.assertTrue(result.index(2) < result.index(1)) self.assertTrue(result.index(3) < result.index(1)) self.assertTrue(result.index(4) < result.index(2)) self.assertTrue(result.index(5) < result.index(3)) # Same graph as before, but with edges # reversed, which means we should get # the same results as before if using # back_topo_sort rather than forw_topo_sort # (and v.v.) graph = Graph() graph.add_node(1) graph.add_node(2) graph.add_node(3) graph.add_node(4) graph.add_node(5) graph.add_edge(2, 1) graph.add_edge(3, 1) graph.add_edge(4, 2) graph.add_edge(5, 3) ok, result = graph.back_topo_sort() self.assertTrue(ok) for idx in range(1, 6): self.assertTrue(idx in result) self.assertTrue(result.index(1) < result.index(2)) self.assertTrue(result.index(1) < result.index(3)) self.assertTrue(result.index(2) < result.index(4)) self.assertTrue(result.index(3) < result.index(5)) ok, result = graph.forw_topo_sort() self.assertTrue(ok) for idx in range(1, 6): self.assertTrue(idx in result) self.assertTrue(result.index(2) < result.index(1)) self.assertTrue(result.index(3) < result.index(1)) self.assertTrue(result.index(4) < result.index(2)) self.assertTrue(result.index(5) < result.index(3)) # Create a cycle graph.add_edge(1, 5) ok, result = graph.forw_topo_sort() self.assertFalse(ok) ok, result = graph.back_topo_sort() self.assertFalse(ok) def test_bfs_subgraph(self): graph = Graph() graph.add_edge(1, 2) graph.add_edge(1, 4) graph.add_edge(2, 4) graph.add_edge(4, 8) graph.add_edge(4, 9) graph.add_edge(4, 10) graph.add_edge(8, 10) subgraph = graph.forw_bfs_subgraph(10) self.assertTrue(isinstance(subgraph, Graph)) self.assertEqual(subgraph.number_of_nodes(), 1) self.assertTrue(10 in subgraph) self.assertEqual(subgraph.number_of_edges(), 0) subgraph = graph.forw_bfs_subgraph(4) self.assertTrue(isinstance(subgraph, Graph)) self.assertEqual(subgraph.number_of_nodes(), 4) self.assertTrue(4 in subgraph) self.assertTrue(8 in subgraph) self.assertTrue(9 in subgraph) self.assertTrue(10 in subgraph) self.assertEqual(subgraph.number_of_edges(), 4) e = subgraph.edge_by_node(4, 8) e = subgraph.edge_by_node(4, 9) e = subgraph.edge_by_node(4, 10) e = subgraph.edge_by_node(8, 10) # same graph as before, but switch around # edges. This results in the same test results # but now for back_bfs_subgraph rather than # forw_bfs_subgraph graph = Graph() graph.add_edge(2, 1) graph.add_edge(4, 1) graph.add_edge(4, 2) graph.add_edge(8, 4) graph.add_edge(9, 4) graph.add_edge(10, 4) graph.add_edge(10, 8) subgraph = graph.back_bfs_subgraph(10) self.assertTrue(isinstance(subgraph, Graph)) self.assertEqual(subgraph.number_of_nodes(), 1) self.assertTrue(10 in subgraph) self.assertEqual(subgraph.number_of_edges(), 0) subgraph = graph.back_bfs_subgraph(4) self.assertTrue(isinstance(subgraph, Graph)) self.assertEqual(subgraph.number_of_nodes(), 4) self.assertTrue(4 in subgraph) self.assertTrue(8 in subgraph) self.assertTrue(9 in subgraph) self.assertTrue(10 in subgraph) self.assertEqual(subgraph.number_of_edges(), 4) e = subgraph.edge_by_node(4, 8) e = subgraph.edge_by_node(4, 9) e = subgraph.edge_by_node(4, 10) e = subgraph.edge_by_node(8, 10) def test_bfs_subgraph_does_not_reverse_egde_direction(self): graph = Graph() graph.add_node("A") graph.add_node("B") graph.add_node("C") graph.add_edge("A", "B") graph.add_edge("B", "C") whole_graph = graph.forw_topo_sort() subgraph_backward = graph.back_bfs_subgraph("C") subgraph_backward = subgraph_backward.forw_topo_sort() self.assertEqual(whole_graph, subgraph_backward) subgraph_forward = graph.forw_bfs_subgraph("A") subgraph_forward = subgraph_forward.forw_topo_sort() self.assertEqual(whole_graph, subgraph_forward) def test_iterdfs(self): graph = Graph() graph.add_edge("1", "1.1") graph.add_edge("1", "1.2") graph.add_edge("1", "1.3") graph.add_edge("1.1", "1.1.1") graph.add_edge("1.1", "1.1.2") graph.add_edge("1.2", "1.2.1") graph.add_edge("1.2", "1.2.2") graph.add_edge("1.2.2", "1.2.2.1") graph.add_edge("1.2.2", "1.2.2.2") graph.add_edge("1.2.2", "1.2.2.3") result = list(graph.iterdfs("1")) self.assertEqual( result, [ "1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1", "1.1", "1.1.2", "1.1.1", ], ) result = list(graph.iterdfs("1", "1.2.1")) self.assertEqual( result, ["1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1"], ) result = graph.forw_dfs("1") self.assertEqual( result, [ "1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1", "1.1", "1.1.2", "1.1.1", ], ) result = graph.forw_dfs("1", "1.2.1") self.assertEqual( result, ["1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1"], ) graph = Graph() graph.add_edge("1.1", "1") graph.add_edge("1.2", "1") graph.add_edge("1.3", "1") graph.add_edge("1.1.1", "1.1") graph.add_edge("1.1.2", "1.1") graph.add_edge("1.2.1", "1.2") graph.add_edge("1.2.2", "1.2") graph.add_edge("1.2.2.1", "1.2.2") graph.add_edge("1.2.2.2", "1.2.2") graph.add_edge("1.2.2.3", "1.2.2") result = list(graph.iterdfs("1", forward=False)) self.assertEqual( result, [ "1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1", "1.1", "1.1.2", "1.1.1", ], ) result = list(graph.iterdfs("1", "1.2.1", forward=False)) self.assertEqual( result, ["1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1"], ) result = graph.back_dfs("1") self.assertEqual( result, [ "1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1", "1.1", "1.1.2", "1.1.1", ], ) result = graph.back_dfs("1", "1.2.1") self.assertEqual( result, ["1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1"], ) # Introduce cyle: graph.add_edge("1", "1.2") result = list(graph.iterdfs("1", forward=False)) self.assertEqual( result, [ "1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1", "1.1", "1.1.2", "1.1.1", ], ) result = graph.back_dfs("1") self.assertEqual( result, [ "1", "1.3", "1.2", "1.2.2", "1.2.2.3", "1.2.2.2", "1.2.2.1", "1.2.1", "1.1", "1.1.2", "1.1.1", ], ) def test_iterdata(self): graph = Graph() graph.add_node("1", "I") graph.add_node("1.1", "I.I") graph.add_node("1.2", "I.II") graph.add_node("1.3", "I.III") graph.add_node("1.1.1", "I.I.I") graph.add_node("1.1.2", "I.I.II") graph.add_node("1.2.1", "I.II.I") graph.add_node("1.2.2", "I.II.II") graph.add_node("1.2.2.1", "I.II.II.I") graph.add_node("1.2.2.2", "I.II.II.II") graph.add_node("1.2.2.3", "I.II.II.III") graph.add_edge("1", "1.1") graph.add_edge("1", "1.2") graph.add_edge("1", "1.3") graph.add_edge("1.1", "1.1.1") graph.add_edge("1.1", "1.1.2") graph.add_edge("1.2", "1.2.1") graph.add_edge("1.2", "1.2.2") graph.add_edge("1.2.2", "1.2.2.1") graph.add_edge("1.2.2", "1.2.2.2") graph.add_edge("1.2.2", "1.2.2.3") result = list(graph.iterdata("1", forward=True)) self.assertEqual( result, [ "I", "I.III", "I.II", "I.II.II", "I.II.II.III", "I.II.II.II", "I.II.II.I", "I.II.I", "I.I", "I.I.II", "I.I.I", ], ) result = list(graph.iterdata("1", end="1.2.1", forward=True)) self.assertEqual( result, [ "I", "I.III", "I.II", "I.II.II", "I.II.II.III", "I.II.II.II", "I.II.II.I", "I.II.I", ], ) result = list(graph.iterdata("1", condition=lambda n: len(n) < 6, forward=True)) self.assertEqual(result, ["I", "I.III", "I.II", "I.I", "I.I.I"]) # And the revese option: graph = Graph() graph.add_node("1", "I") graph.add_node("1.1", "I.I") graph.add_node("1.2", "I.II") graph.add_node("1.3", "I.III") graph.add_node("1.1.1", "I.I.I") graph.add_node("1.1.2", "I.I.II") graph.add_node("1.2.1", "I.II.I") graph.add_node("1.2.2", "I.II.II") graph.add_node("1.2.2.1", "I.II.II.I") graph.add_node("1.2.2.2", "I.II.II.II") graph.add_node("1.2.2.3", "I.II.II.III") graph.add_edge("1.1", "1") graph.add_edge("1.2", "1") graph.add_edge("1.3", "1") graph.add_edge("1.1.1", "1.1") graph.add_edge("1.1.2", "1.1") graph.add_edge("1.2.1", "1.2") graph.add_edge("1.2.2", "1.2") graph.add_edge("1.2.2.1", "1.2.2") graph.add_edge("1.2.2.2", "1.2.2") graph.add_edge("1.2.2.3", "1.2.2") result = list(graph.iterdata("1", forward=False)) self.assertEqual( result, [ "I", "I.III", "I.II", "I.II.II", "I.II.II.III", "I.II.II.II", "I.II.II.I", "I.II.I", "I.I", "I.I.II", "I.I.I", ], ) result = list(graph.iterdata("1", end="1.2.1", forward=False)) self.assertEqual( result, [ "I", "I.III", "I.II", "I.II.II", "I.II.II.III", "I.II.II.II", "I.II.II.I", "I.II.I", ], ) result = list( graph.iterdata("1", condition=lambda n: len(n) < 6, forward=False) ) self.assertEqual(result, ["I", "I.III", "I.II", "I.I", "I.I.I"]) def test_bfs(self): graph = Graph() graph.add_edge("1", "1.1") graph.add_edge("1.1", "1.1.1") graph.add_edge("1.1", "1.1.2") graph.add_edge("1.1.2", "1.1.2.1") graph.add_edge("1.1.2", "1.1.2.2") graph.add_edge("1", "1.2") graph.add_edge("1", "1.3") graph.add_edge("1.2", "1.2.1") self.assertEqual( graph.forw_bfs("1"), ["1", "1.1", "1.2", "1.3", "1.1.1", "1.1.2", "1.2.1", "1.1.2.1", "1.1.2.2"], ) self.assertEqual( graph.forw_bfs("1", "1.1.1"), ["1", "1.1", "1.2", "1.3", "1.1.1"] ) # And the "reverse" graph graph = Graph() graph.add_edge("1.1", "1") graph.add_edge("1.1.1", "1.1") graph.add_edge("1.1.2", "1.1") graph.add_edge("1.1.2.1", "1.1.2") graph.add_edge("1.1.2.2", "1.1.2") graph.add_edge("1.2", "1") graph.add_edge("1.3", "1") graph.add_edge("1.2.1", "1.2") self.assertEqual( graph.back_bfs("1"), ["1", "1.1", "1.2", "1.3", "1.1.1", "1.1.2", "1.2.1", "1.1.2.1", "1.1.2.2"], ) self.assertEqual( graph.back_bfs("1", "1.1.1"), ["1", "1.1", "1.2", "1.3", "1.1.1"] ) # check cycle handling graph.add_edge("1", "1.2.1") self.assertEqual( graph.back_bfs("1"), ["1", "1.1", "1.2", "1.3", "1.1.1", "1.1.2", "1.2.1", "1.1.2.1", "1.1.2.2"], ) def test_connected(self): graph = Graph() graph.add_node(1) graph.add_node(2) graph.add_node(3) graph.add_node(4) self.assertFalse(graph.connected()) graph.add_edge(1, 2) graph.add_edge(3, 4) self.assertFalse(graph.connected()) graph.add_edge(2, 3) graph.add_edge(4, 1) self.assertTrue(graph.connected()) def test_edges_complex(self): g = Graph() g.add_edge(1, 2) e = g.edge_by_node(1, 2) g.hide_edge(e) g.hide_node(2) self.assertRaises(GraphError, g.restore_edge, e) g.restore_all_edges() self.assertRaises(GraphError, g.edge_by_id, e) def test_clust_coef(self): g = Graph() g.add_edge(1, 2) g.add_edge(1, 3) g.add_edge(1, 4) self.assertEqual(g.clust_coef(1), 0) g.add_edge(2, 5) g.add_edge(3, 5) g.add_edge(4, 5) self.assertEqual(g.clust_coef(1), 0) g.add_edge(2, 3) self.assertEqual(g.clust_coef(1), 1.0 / 6) g.add_edge(2, 4) self.assertEqual(g.clust_coef(1), 2.0 / 6) g.add_edge(4, 2) self.assertEqual(g.clust_coef(1), 3.0 / 6) g.add_edge(2, 3) g.add_edge(2, 4) g.add_edge(3, 4) g.add_edge(3, 2) g.add_edge(4, 2) g.add_edge(4, 3) self.assertEqual(g.clust_coef(1), 1) g.add_edge(1, 1) self.assertEqual(g.clust_coef(1), 1) g.add_edge(2, 2) self.assertEqual(g.clust_coef(1), 1) g.add_edge(99, 99) self.assertEqual(g.clust_coef(99), 0.0) def test_get_hops(self): graph = Graph() graph.add_edge(1, 2) graph.add_edge(1, 3) graph.add_edge(2, 4) graph.add_edge(4, 5) graph.add_edge(5, 7) graph.add_edge(7, 8) self.assertEqual( graph.get_hops(1), [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)] ) self.assertEqual(graph.get_hops(1, 5), [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3)]) graph.add_edge(5, 1) graph.add_edge(7, 1) graph.add_edge(7, 4) self.assertEqual( graph.get_hops(1), [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)] ) # And the reverse graph graph = Graph() graph.add_edge(2, 1) graph.add_edge(3, 1) graph.add_edge(4, 2) graph.add_edge(5, 4) graph.add_edge(7, 5) graph.add_edge(8, 7) self.assertEqual( graph.get_hops(1, forward=False), [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)], ) self.assertEqual( graph.get_hops(1, 5, forward=False), [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3)], ) graph.add_edge(1, 5) graph.add_edge(1, 7) graph.add_edge(4, 7) self.assertEqual( graph.get_hops(1, forward=False), [(1, 0), (2, 1), (3, 1), (4, 2), (5, 3), (7, 4), (8, 5)], ) def test_constructor(self): graph = Graph(iter([(1, 2), (2, 3, "a"), (1, 3), (3, 4)])) self.assertEqual(graph.number_of_nodes(), 4) self.assertEqual(graph.number_of_edges(), 4) try: graph.edge_by_node(1, 2) graph.edge_by_node(2, 3) graph.edge_by_node(1, 3) graph.edge_by_node(3, 4) except GraphError: self.fail("Incorrect graph") self.assertEqual(graph.edge_data(graph.edge_by_node(2, 3)), "a") self.assertRaises(GraphError, Graph, [(1, 2, 3, 4)]) if __name__ == "__main__": # pragma: no cover unittest.main()