Simple test for a Graph class

test_graph.py

import unittest
import itertools as it

from graph import Graph


class TestGraph(unittest.TestCase):
    
    
    def test_init(self):
        
        parameters = (
            (((), ()), (0,0,[],[])),
            ((range(5), ()), (5,0,list(range(5)),[])),
            ((range(5), ((0,1),(3,2),(4,0))), (5,3,list(range(5)), [(0,1),(3,2),(4,0)])),
            (([0,3,7], ((0,3),(7,3))), (3,2,[0,3,7],[(0,3),(7,3)])),
            )
        
        for (nodes,edges),(num_nodes,num_edges,node_list,edge_list) in parameters:
            graph = Graph(nodes,edges)
            
            self.assertEqual(graph.number_of_nodes, num_nodes)
            self.assertEqual(graph.number_of_edges, num_edges)
            self.assertEqual(sorted(graph.nodes), sorted(node_list))
            self.assertEqual(sorted(graph.edges), sorted(edge_list))
    
    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)))
        
        parameters = (
            (2,0,4),
            ((0,1), (1,2), (0,2)),
            (Graph([0,1], ((0,1),)), Graph([0,1], ((1,2),)), Graph([0,1], ((1,0),))),
            ([(0,1)], [(0,1), (1,2)], [(0,1), (1,3)]),
            )
        
        for true_first, true_second, false in parameters:
            self.assertTrue(true_first in graph)
            self.assertTrue(true_second in graph)
            self.assertFalse(false in graph)
    
    def test_is_connected_true(self):
        parameters = (
            ((), (), True),
            (range(1), (), True),
            (range(1), (), False),
            (range(2), ((0,1), (1,0)), True),
            (range(2), ((0,1),), False),
            (range(4), ((0,1), (1,2), (2,3)), False),
            (range(4), ((0,1), (1,2), (0,3)), False),
            (range(3), ((0,1), (1,0), (1,2), (2,1), (2,3), (3,2)), True)
            )
        
        for nodes,edges,strongly in parameters:
            self.assertTrue(Graph(nodes,edges).is_connected(strongly))
    
    def test_is_connected_false(self):
        parameters = (
            (range(2), ((0,1),), True),
            (range(4), ((0,1), (1,2), (2,3)), True),
            (range(3), ((0,1), (1,0), (1,2), (2,1), (2,3)), True),
            (range(4), ((0,1), (1,2)), False),
            
            )
        
        for nodes, edges, strongly in parameters:
            self.assertFalse(Graph(nodes, edges).is_connected(strongly))
    
    def test_induce_nodes(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)))
        
        parameters = (
            ((0,1,2,3), Graph(range(4), ((0,1), (0,3), (2,1)))),
            ((0,1), Graph([0,1], ((0,1),))),
            ((1,2), Graph([1,2], ((2,1),))),
            ((3,4), Graph([3,4], ((3,4), (4,3)))),
            ((0,3,4,7), Graph([0,3,4,7], ((0,3), (3,4), (4,3)))),
            
            )
        
        for nodes, result in parameters:
            self.assertEqual(graph.induce(nodes), result)
    
    def test_induce_edges(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)))
        
        parameters = (
            (
                ((0,1), (0,9), (5,6), (7,8), (3,4)),
                Graph(range(10), ((0,1), (0,9), (5,6), (3,4)))
            ), (
                ((0,1), (0,3)),
                Graph(range(10), ((0,1), (0,3)))
            ), (
                (),
                Graph(range(10))
            )
            )
        
        for edges, result in parameters:
            self.assertEqual(graph.induce(edges=edges), result)
    
    def test_induce_nodes_and_edges(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)))
        
        parameters = (
            (range(4), ((0,3), (0,1), (2,1)), Graph(range(4), ((0,3), (0,1), (2,1)))),
            (range(6), ((3,4), (0,1), (2,5)), Graph(range(6), ((3,4), (0,1), (2,5)))),
            ([0,5,6,7], ((5,6),), Graph([0,5,6,7], ((5,6),))),
        
        for nodes, edges result in parameters:
            self.assertEqual(graph.induce(nodes, edges), result)
    
    def test_induce_raises_errors(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)))
        
        self.assertRaises(ValueError,
                          graph.induce, (0,1,2,10))
        
        self.assertRaises(ValueError,
                          graph.induce, ((0,1), (4,5)))
        
        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))
        
        for comb in it.combinations(range(4), 2):
            graph.add_edge(comb)
        
        self.assertEqual(graph,
                         Graph(range(4), it.combinations(range(4),2)))
        
        self.assertRaises(ValueError, graph.add_edge, (1,4))
        
        graph = Graph(range(5), ((0,1), (2,3), (1,0)))
        
        for comb in it.combinations(reversed(range(4)),2):
            graph.add_edge(comb)
        
        self.assertEqual(graph,
                        Graph(range(5), it.chain(((0,1),(2,3),(1,0)),
                                                 it.combinations(reversed(range(4),2)))))
        
        self.assertRaises(ValueError,
                          graph.add_edge, (2,3))
    
    def test_remove_edge(self):
        
        edges = [(0,1), (1,0), (2,1), (2,3)]
        graph = Graph(range(4), edges)
        
        for edge in edges[:]:
            graph.remove_edge(edge)
            edges.remove(edge)
            
            self.assertEqual(graph, Graph(range(4), edges))
        
        self.assertRaises(ValueError, graph.remove_edge,(1,2))
    
    def test_add_node(self):
        
        nodes = list(range(8))
        edges = ((4,5), (5,7), (7,6), (7,5))
        
        graph = Graph(nodes, edges)
        
        for node in [10, 12,13,-4,8,9]:
            graph.add_node(node)
            nodes.append(node)
            
            self.assertEqual(graph, Graph(nodes,edges))
        
        self.assertRaises(ValueError, graph.add_node, 6)
    
    def test_remove_node(self):
        nodes = list(range(9))
        edges = ((2,3), (2,6), (4,7), (5,8))
        graph = Graph(nodes,edges)
        
        for node in nodes[:]
            graph.remove_node(node)
            nodes.remove(node)
            
            self.assertEqual(graph, Graph(nodes, edges))
        
        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(7), ((0,1), (0,2), (2,1), (0,3), (3,4), (3,5),
                               (4,3), (4,5), (5,3), (5,4), (5,7)))
        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):
        parameters = (
            (range(3), ((0,1),(1,0),(0,2),(2,0),(1,2),(2,1)), True, True),
            (range(3), ((0,1), (1,2), (2,0)), False, True),
            (range(2), ((0,1),), False, False),
            (range(2), ((0,1), (1,0)), True, False),
            
            )
        
        for nodes, edges, strong_res, weak_res in parameters:
            self.assertEqual(Graph(nodes, edges).is_eulerian(), strong_res)
            self.assertEqual(Graph(nodes, edges).is_eulerian(strongly=False), weak_res)
    
    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)])