-
-
Save rik0/2438870 to your computer and use it in GitHub Desktop.
Simple test for a Graph class
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import unittest | |
| from graph import Graph | |
| class TestGraph(unittest.TestCase): | |
| def test_init(self): | |
| # Graph(iterable: nodes, iterable of nodes couples: edges) | |
| graph = Graph() | |
| self.assertEqual(graph.number_of_nodes, 0) | |
| self.assertEqual(graph.number_of_edges, 0) | |
| self.assertEqual(list(graph.nodes), []) | |
| self.assertEqual(list(graph.edges), []) | |
| graph = Graph(range(5)) | |
| self.assertEqual(graph.number_of_nodes, 5) | |
| self.assertEqual(graph.number_of_edges, 0) | |
| self.assertEqual(sorted(graph.nodes), list(range(5))) | |
| self.assertEqual(list(graph.edges), []) | |
| graph = Graph(range(5), ((0,1), (3,2), (4,0))) | |
| self.assertEqual(graph.number_of_nodes, 5) | |
| self.assertEqual(graph.number_of_edges, 3) | |
| self.assertEqual(sorted(graph.nodes), list(range(5))) | |
| self.assertEqual(sorted(graph.edges), [(0, 1), (3, 2), (4, 0)]) | |
| graph = Graph([0,3,7], ((0,3), (7,3))) | |
| self.assertEqual(graph.number_of_nodes, 3) | |
| self.assertEqual(graph.number_of_edges, 2) | |
| self.assertEqual(sorted(graph.nodes), [0,3,7]) | |
| self.assertEqual(sorted(graph.edges), [(0,3), (7,3)]) | |
| def test_equals(self): | |
| # A == B <=> set(A.nodes) == set(B.nodes) and set(A.edges) == (B.edges) | |
| graph = Graph(range(7), ((1,2), (3,6), (4,5))) | |
| graph2 = Graph(range(7), ((1,2), (4,5), (3,6))) | |
| self.assertEqual(graph, graph2) | |
| self.assertNotEqual(graph, Graph(range(8), ((1,2), (3,6), (4,5)))) | |
| self.assertNotEqual(graph, Graph(range(7), ((1,2), (5,4)))) | |
| def test_contains(self): | |
| graph = Graph(range(4), ((0,1), (1,2))) | |
| # Graph contains the node? | |
| self.assertTrue(2 in graph) | |
| self.assertTrue(0 in graph) | |
| self.assertFalse(4 in graph) | |
| # Graph contains the edge? | |
| self.assertTrue((0,1) in graph) | |
| self.assertTrue((1,2) in graph) | |
| self.assertFalse((0,2) in graph) | |
| subgraph = Graph(range(2), ((0,1),)) | |
| # Graph contains subgraph? | |
| self.assertTrue(subgraph in graph) | |
| subgraph = Graph(range(2), ((1,0),)) | |
| self.assertFalse(subgraph in graph) | |
| path = [(0,1)] | |
| # Graph contains the path? (sequence of edges) | |
| self.assertTrue(path in graph) | |
| path = [(0,1), (1,3)] | |
| self.assertFalse(path in graph) | |
| def test_is_connected(self): | |
| self.assertTrue(Graph().is_connected()) | |
| self.assertTrue(Graph(range(1)).is_connected()) | |
| self.assertFalse(Graph(range(2), ((0,1),)).is_connected()) | |
| self.assertTrue(Graph(range(2),((0,1),(1,0))).is_connected()) | |
| # strongly=True -> takes into account orientation of edges | |
| # strongly=False returns True if the underneath, not oriented, graph | |
| # is connected. | |
| self.assertTrue(Graph(range(2), ((0,1),)).is_connected(strongly=False)) | |
| def test_induce(self): | |
| graph = Graph(range(10), ((0,1), (0,3), (0,9), (2,1), (2,5), (2,8), | |
| (3,4), (4,1), (4,3), (5,6), (5,9), (7,8))) | |
| # subgraph containing only the given subset of nodes | |
| # and removing all edges containg other nodes | |
| subgraph = graph.induce(nodes=(0,1,2,3)) | |
| self.assertEqual(subgraph, Graph(range(4), ((0,1), (0,3), (2,1)))) | |
| # Raises ValueError if a node which does not belong to the | |
| # graph is in the set of nodes. | |
| self.assertRaises(ValueError, graph.induce, (0,1,2,10)) | |
| subgraph = graph.induce(edges=((0,1), (0,9), (5,6), (7,8), (3,4))) | |
| self.assertEqual(subgraph, Graph(range(10), ((0,1), (0,9), (5,6), (7,8), (3,4)))) | |
| # Raises ValueError if an edge which does not belong to the | |
| # graph is in the set of edges. | |
| self.assertRaises(ValueError, graph.induce,((0,1), (4,5))) | |
| subgraph = graph.induce(nodes=(0,1,3,4,5,6,7,8,9), | |
| edges=((0,1), (0,9), (5,6), (7,8),(3,4))) | |
| self.assertEqual(subgraph, Graph([0,1,3,4,5,6,7,8,9], | |
| ((0,1),(0,9),(5,6),(7,8),(3,4)))) | |
| self.assertRaises(ValueError, graph.induce, (0,1,2), ((0,1),(0,3),(2,1),(5,9))) | |
| def test_add_edge(self): | |
| graph = Graph(range(4)) | |
| graph.add_edge((2,3)) | |
| self.assertEqual(graph, Graph(range(4), ((2,3),))) | |
| # Can't add an edge referring to a node which does not | |
| # belong to the graph. | |
| self.assertRaises(ValueError, graph.add_edge, (1,4)) | |
| def test_remove_edge(self): | |
| graph = Graph(range(4), ((0,1), (1,0), (2,1), (2,3))) | |
| graph.remove_edge((0,1)) | |
| self.assertEqual(graph, Graph(range(4), ((1,0), (2,1), (2,3)))) | |
| self.assertRaises(ValueError, graph.remove_edge,(1,2)) | |
| def test_add_node(self): | |
| graph = Graph(range(7), ((4,5), (5,7), (7,6), (7,5))) | |
| graph.add_node(10) | |
| self.assertEqual(graph, Graph(range(7) + [10], ((4,5),(5,7),(7,6),(7,5)))) | |
| # Raise an error if the node is already in the graph | |
| self.assertRaises(ValueError, graph.add_node, 6) | |
| def test_remove_node(self): | |
| graph = Graph(range(9), ((2,3), (2,6), (4,7), (5,8))) | |
| graph.remove_node(4) | |
| self.assertEqual(graph, Graph((0,1,2,3,5,6,7,8), ((2,3), (2,6), (5,8)))) | |
| # Raise an error if the node is not in the graph. | |
| self.assertRaises(ValueError, graph.remove_node, 10) | |
| def test_connected_components(self): | |
| graph = Graph(range(10), ((0,1), (0,2), (2,1), | |
| (0,3), (3,4), (3,5), (4,3), (4,5), (5,3), (5,4), | |
| (5,7), (8,9), (6,8))) | |
| # Return a sequence of strongly-connected components | |
| components = graph.connected_components() | |
| self.assertEqual(len(components), 1) | |
| self.assertEqual(components[0], | |
| Graph((3,4,5), ((3,4), (3,5), (4,3), (4,5), (5,3), (5,4)))) | |
| # Return a sequence of weakly-connected components | |
| components = graph.connected_components(strongly=False) | |
| self.assertEqual(len(components), 2) | |
| first_comp = Graph(range(6), ((0,1), (0,2), (2,1), (0,3), (3,4), (3,5), | |
| (4,3), (4,5), (5,3), (5,4))) | |
| second_comp = Graph((6,8,9), ((8,9), (6,8))) | |
| if components[0] == first_comp: | |
| self.assertEqual(components[1], second_comp) | |
| elif components[0] == second_comp: | |
| self.assertEqual(components[1], first_comp) | |
| else: | |
| self.fail('Bad components: %s' % components) | |
| def test_is_eulerian(self): | |
| graph = Graph(range(3), ((0,1), (1,0), (0,2), (2,0), (1,2), (2,1))) | |
| # Return True if the graph contains an eulerian-cycle | |
| self.assertTrue(graph.is_eulerian()) | |
| # Return True if the graph contains an eulerian-cycle, | |
| # without considering edge orientation. | |
| self.assertTrue(graph.is_eulerian(strongly=False)) | |
| graph = Graph(range(3), ((0,1), (1,2), (2,0))) | |
| self.assertFalse(graph.is_eulerian()) | |
| self.assertTrue(graph.is_eulerian(strongly=False)) | |
| graph = Graph(range(2), ((0,1),)) | |
| self.assertFalse(graph.is_eulerian()) | |
| self.assertFalse(graph.is_eulerian(strongly=False)) | |
| graph = Graph(range(2), ((0,1), (1,0))) | |
| self.assertTrue(graph.is_eulerian()) | |
| self.assertFalse(graph.is_eulerian(strongly=False)) | |
| def test_get_eulerian_cycle(self): | |
| graph = Graph(range(4), ((0,1), (1,3), (3,2), (2, 0))) | |
| cycle = graph.get_eulerian_cycle() | |
| self.assertEqual(list(cycle), [(0,1), (1,3), (3,2), (2,0)]) | |
| cycle = graph.get_eulerian_cycle(strongly=False) | |
| self.assertEqual(list(cycle), [(0,1), (1,3), (3,2), (2,0)]) | |
| graph = Graph(range(4), ((0,1), (1,3), (3,2), (0,2))) | |
| self.assertRaises(ValueError, graph.get_eulerian_cycle) | |
| cycle = graph.get_eulerian_cycle(strongly=False) | |
| self.assertTrue(list(cycle) in ([(0,1), (1,3), (3,2), (0,2)], | |
| [(0,2), (2,3), (1,3), (0,1)])) | |
| def test_get_eulerian_cycle2(self): | |
| graph = Graph(range(6), ((0,1), (0, 4), | |
| (1,2), (1,3), (1,5), | |
| (2,3), (2,5), (2,4), | |
| (3,4), (3,5), | |
| (4,5))) | |
| self.assertRaises(ValueError, graph.get_eulerian_cycle) | |
| cycle = graph.get_eulerian_cycle(strongly=False) | |
| # is made from all and only the 11 edges? | |
| self.assertEqual(len(cycle), 11) | |
| self.assertEqual(len(set(cycle)), 11) | |
| for edge in cycle: | |
| self.assertTrue(edge in graph) | |
| # if each edge is adjacent to the next and the last is adjacent | |
| # to the first, than the cycle is an eulerian one. | |
| for i,edge in enumerate(cycle[1:]): | |
| if not set(cycle[i]).intersection(edge): | |
| self.fail('Edges %s and %s are not adjacent.' % (cycle[i], edge)) | |
| self.assertTrue(set(cycle[0]).intersection(cycle[-1])) | |
| def test_get_eulerian_cycle3(self): | |
| graph = Graph(range(4), ((0,1), (1,0), (1,3), (3,2), (2,1))) | |
| cycle = graph.get_eulerian_cycle() | |
| self.assertEqual(cycle, [(0,1), (1,3), (3,2), (2,1), (1,0)]) | |
| self.assertRaises(ValueError, graph.get_eulerian_cycle, False) | |
| graph = Graph(range(5), ((0,1), (4,0), (2,1), (1,3), (1,4), (3,2))) | |
| cycle = graph.get_eulerian_cycle(strongly=False) | |
| self.assertEqual(len(cycle), 6) | |
| self.assertEqual(len(set(cycle)), 6) | |
| for edge in cycle: | |
| self.assertTrue(cycle in graph) | |
| for i,edge in enumerate(cycle[1:]): | |
| if not set(cycle[i]).intersection(edge): | |
| self.fail('Edges %s and %s are not adjacent.' % (cycle[i], edge)) | |
| self.assertTrue(set(cycle[0]).intersection(cycle[-1])) | |
| cycle = graph.get_eulerian_cycle() | |
| self.assertEqual(cycle, [(0,1), (1,3), (3,2), (2,1), (1,4), (4,0)]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment