graph.py

G1 = { 1: [2, 5],
       2: [1, 3],
       5: [4] }
G2 = { 1: [2, 4],
       2: [3, 4],
       3: [5],
       5: [2, 6] }
G3 = { 1: [2, 5],
       2: [3],
       5: [4] }

def count_vertices(G):
    return len(set(G.keys()).union(e for es in G.values() for e in es))

def count_edges(G):
    return len([e for es in G.values() for e in es])

def topological_sort(G):
    sorted_graph = []
    unsorted_graph = dict(G.items())
    while unsorted_graph:
        acyclic = False
        for (node, edges) in list(unsorted_graph.items()):
            for edge in edges:
                if edge in unsorted_graph:
                    break
            else:
                acyclic = True
                del unsorted_graph[node]
                sorted_graph.append((node, edges))
        if not acyclic:
            return None
    return sorted_graph

def iscyclic(G):
    return topological_sort(G) is None

def test_count_vertices():
    assert count_vertices(G1) == 5
    assert count_vertices(G2) == 6
    assert count_vertices(G3) == 5

def test_count_edges():
    assert count_edges(G1) == 5
    assert count_edges(G2) == 7
    assert count_edges(G3) == 4

def test_iscyclic():
    assert iscyclic(G1) == True
    assert iscyclic(G2) == True
    assert iscyclic(G3) == False