| 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) |
| 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) |
| 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) |
| |
| |
| |
| 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_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./6) |
| g.add_edge(2, 4) |
| self.assertEqual(g.clust_coef(1), 2./6) |
| g.add_edge(4, 2) |
| self.assertEqual(g.clust_coef(1), 3./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) |
| |
| |
| 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() |