Topological sort (Kahn's algorithm) trouble

Question

I am having trouble wrapping my head around my code in the nested for loop. I am following the Kahn's algorithm here on wiki: Kahn's. I don't understand how to test for if outgoingEdge has incoming edges for each endArray element (m).

Here is what I have so far:

    def topOrdering(self, graph):

    retList = []
    candidates = set()
    left = []
    right = []

    for key in graph:
        left.append(key)
        right.append(graph[key])

    flattenedRight = [val for sublist in right for val in sublist]

    for element in left:
        if element not in flattenedRight:
            #set of all nodes with no incoming edges
            candidates.add(element)

    candidates = sorted(candidates)

    while len(candidates) != 0:
        a = candidates.pop(0)
        retList.append(a)
        endArray = graph[a]

        for outGoingEdge in endArray:

            if outGoingEdge not in flattenedRight:
                candidates.append(outGoingEdge)
                #flattenedRight.remove(outGoingEdge)

            del outGoingEdge


    if not graph:
        return "the input graph is not a DAG"
    else:
        return retList

Here is a picture visualizing my algorithm. Graph is in a form of an adjacency list.

Answer 1

You can store indegree (number of incoming edges) separately and decrement the count every time you remove a vertex from empty set. When count becomes 0 add the vertex to empty set to be processed later. Here's example:

def top_sort(adj_list):
    # Find number of incoming edges for each vertex
    in_degree = {}
    for x, neighbors in adj_list.items():
        in_degree.setdefault(x, 0)
        for n in neighbors:
            in_degree[n] = in_degree.get(n, 0) + 1

    # Iterate over edges to find vertices with no incoming edges
    empty = {v for v, count in in_degree.items() if count == 0}

    result = []
    while empty:
        # Take random vertex from empty set
        v = empty.pop()
        result.append(v)

        # Remove edges originating from it, if vertex not present
        # in adjacency list use empty list as neighbors
        for neighbor in adj_list.get(v, []):
            in_degree[neighbor] -= 1

            # If neighbor has no more incoming edges add it to empty set
            if in_degree[neighbor] == 0:
                empty.add(neighbor)

    if len(result) != len(in_degree):
        return None # Not DAG
    else:
        return result

ADJ_LIST = {
    1: [2],
    2: [3],
    4: [2],
    5: [3]
}

print(top_sort(ADJ_LIST))

Output:

[1, 4, 5, 2, 3]