Task 1.sagews

G = DiGraph()
G.add_edges((
('A', 'D'), ('A', 'C'), ('N', 'A'), ('A', 'G'), ('D', 'B'), ('B', 'K'),
('K', 'D'), ('C', 'D'), ('C', 'E'), ('E', 'N'), ('N', 'G'), ('E', 'F'),
('E', 'H'), ('H', 'G'), ('F', 'I'), ('J', 'I'), ('M', 'F'), ('M', 'L'), ('L', 'M')))
E = G.edges()
V = G.vertices()

def find_sccs(V, E):
    V = set(V)
    found = set()
    finished = dict()
    reverse = False

    def dfs(u, t):
        found.add(u)
        for a, b, w in E:
            if reverse:
                a, b = b, a
            if a == u and b not in found:
                t = dfs(b, t+1)
        finished[u] = t + 1
        return finished[u]

    # Calculate the finishing times
    t = 0
    while len(V) > len(found):
        t = dfs((V - found).pop(), t+1)

    # Find the SCCs
    sccs = []
    reverse = True
    found = set()
    original_finished = finished.copy()
    while len(V) > len(found):
        # Find the vertex with the highest finishing time from the set of unvisited vertices
        next_u = max((original_finished[u], u) for u in (V - found))[1]
        prev_found = found.copy()
        dfs(next_u, 0)
        sccs.append(found - prev_found)

    sccs = sorted(sccs, key=lambda scc: (-len(scc), max(scc)))
    node_to_scc = dict()
    for i, scc in enumerate(sccs):
        for u in scc:
            node_to_scc[u] = i

    scc_edges = [set() for i in range(len(sccs))]
    for a, b, w in E:
        if node_to_scc[a] != node_to_scc[b]:
            scc_edges[node_to_scc[a]].add(node_to_scc[b])

    return sccs, node_to_scc, scc_edges, original_finished


sccs, node_to_scc, scc_edges, finish_times = find_sccs(V, E)
# Calculate the topological ordering of the SCC graph
topo_sort = sorted(range(1, len(sccs) + 1), key=lambda i: -finish_times[iter(sccs[i-1]).next()])
︠6bf44038-fc3e-40b1-8c6a-074d5157b6bdi︠
print "SCCs:", map(list, sccs)
print "SCC graph edges:", map(list, scc_edges)
print "Topological ordering of SCC graph:", topo_sort

SCCs: [['A', 'C', 'E', 'N'], ['K', 'B', 'D'], ['M', 'L'], ['F'], ['G'], ['H'], ['I'], ['J']] SCC graph edges: [[1, 3, 4, 5], [], [3], [6], [], [4], [], [6]] Topological ordering of SCC graph: [3, 8, 1, 6, 5, 4, 7, 2]

H = G.plot(partition = sccs)
H.show(figsize=8)
H.save('T1_SCCs.pdf')

scc_G = DiGraph({i: list(edges) for i, edges in enumerate(scc_edges)})
scc_G.relabel(topo_sort)
H = scc_G.plot(partition = [[u] for u in topo_sort], vertex_size=600)
H.show(figsize=4)
H.save('T1_toposort.pdf')