from SkipList import SkipList
from Queue import Queue
from singleSource import BellmanFord
from singleSource import Dijkstra

def sortVertices1(edges, start):
    """Returns a sorted list of the vertices in a Directed Acyclic Graph

    edges: a dictionary, indexed by origin vertex, of edge lists
    start: a vertex from which all others are reachable

    Each edge list shows the edges out from a vertex as a list
    of destination vertices.

    Each vertex should be a key in edges, even with an empty list."""

    ## This procedure ignores start; it is provided for compatability
    ## with other procedures.

    result = []
    inDegree = {}
    for v in edges:
        inDegree[v] = 0
    for origin in edges:
        for destination in edges[origin]:
            inDegree[destination] += 1
    remaining = SkipList() # key: (inDegree[v], v), value: None
    for v in edges:
        remaining[inDegree[v], v] = None
    while len(remaining) != 0:
        (d, v), n = remaining.min()
        del remaining[d,v]
        if d != 0:
            raise ValueError("Graph is not acyclic")
        result.append(v)
        for v1 in edges[v]:
            del remaining[inDegree[v1],v1]
            inDegree[v1] -= 1
            remaining[inDegree[v1],v1] = None
    return result

def sortVertices2(edges, start):
    """Returns a sorted list of the vertices in a Directed Acyclic Graph

    edges: a dictionary, indexed by origin vertex, of edge lists
    start: a vertex from which all others are reachable

    Each edge list shows the edges out from a vertex as a list
    of destination vertices.

    Each vertex should be a key in edges, even with an empty list."""

    result = []
    q = Queue()
    q.add(start)
    found = {start}
    while len(q) != 0:
        v = q.remove()
        result.append(v)
        for v1 in edges[v]:
            if v1 not in found:
                found.add(v1)
                q.add(v1)
    return result

def sortVertices3(edges, start):
    """Returns a sorted list of the vertices in a Directed Acyclic Graph

    edges: a dictionary, indexed by origin vertex, of edge lists
    start: a vertex from which all others are reachable

    Each edge list shows the edges out from a vertex as a list
    of destination vertices.

    Each vertex should be a key in edges, even with an empty list."""

    weightedEdges = {}
    for v0 in edges:
        weightedEdges[v0] = []
        for v1 in edges[v0]:
            weightedEdges[v0].append((1, v1)) # each edge's weight = 1
    d = Dijkstra(weightedEdges, start)
    result = [(d[v], v) for v in d]
    result.sort()
    result = [v for (dv, v) in result]
    return result

def sortVertices4(edges, start):
    """Returns a sorted list of the vertices in a Directed Acyclic Graph

    edges: a dictionary, indexed by origin vertex, of edge lists
    start: a vertex from which all others are reachable

    Each edge list shows the edges out from a vertex as a list
    of destination vertices.

    Each vertex should be a key in edges, even with an empty list."""

    weightedEdges = {}
    for v0 in edges:
        weightedEdges[v0] = []
        for v1 in edges[v0]:
            weightedEdges[v0].append((-1, v1)) # each edge's weight = -1
    d = BellmanFord(weightedEdges, start)
    result = [(d[v], v) for v in d]
    result.sort()
    result = [v for (dv, v) in reversed(result)] # note: reversed
    return result