Algorithm to determine a topological ordering of a DAG.

topological_order.py

import itertools
import re


def UniqueList(data):
    return list(set(data))


class Graph:
    def __init__(self, vertices, edges):
        self.vertices = UniqueList(vertices)
        self.edges = UniqueList(edges)

    def areAdjacent(self, u, v):
        for edge in self.edges:
            if edge == (u, v):
                return True
        return False

    def topological_order(self):
        stack = []

        visited = {}

        for v in self.vertices:
            visited[v] = False

        def order(graph, visited, stack, v):
            visited[v] = True

            for u in graph.vertices:
                if not graph.areAdjacent(v, u):
                    continue

                if not visited[u]:
                    order(graph, visited, stack, u)

            stack.append(v)

        for v in self.vertices:
            if not visited[v]:
                order(self, visited, stack, v)

        return stack[::-1]



def ParseVertices(input):
    verts = input.split(',')
    verts = list(map(str.strip, verts))
    if len(verts) > 0:
        return verts
    return None


def ParseEdges(input):
    def CreateEdge(edge):
        elements = edge.split(';')
        elements = list(map(str.strip, elements))
        if len(elements) != 2:
            raise Exception('Arista inválida')
        if len(elements[0]) < 1 or len(elements[1]) < 1:
            raise Exception('Arista inválida')
        edge = (elements[0][1:], elements[1][:-1])
        return tuple(map(str.strip, edge))

    # Allow empty edge sets
    if not input.strip():
        return []

    edges = input.split(',')
    edges = list(map(str.strip, edges))
    try:
        edges = list(map(CreateEdge, edges))
    except:
        return None

    return edges


while True:
    print('Digite los vértices del grafo A, separados por coma (,)')
    Va = ParseVertices(input())
    if Va is not None:
        break
    print('Vértices inválidos')

while True:
    print('Digite las aristas del grafo A, separadas por coma (,), en la forma (v; u), ejemplo: "(v1; v2), (v2; v3), (v3; v4)"')
    Ea = ParseEdges(input())
    if Ea is not None:
        break
    print('Aristas inválidas')

A = Graph(Va, Ea)

print('==' * 10)
print('Un orden topológico del grafo es')
print(A.topological_order())