Skip to content

Instantly share code, notes, and snippets.

/test_graph.py

Created April 21, 2012 13:32
Show Gist options
  • Save anonymous/2437083 to your computer and use it in GitHub Desktop.
Save anonymous/2437083 to your computer and use it in GitHub Desktop.
Download ZIP
Simple test for a Graph class
Raw
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)])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment