Merge lists maintaining order

merge_lists.py

# Merge multiple lists of distinct elements into a single list, maintaining the order within each list.
# The result is a list of distinct elements, consisting of the union of the elements in the constituent lists.
# If A precedes B in one of the input lists, then A must precede B in the result.

# If this is not possible, then None is returned.

from collections import defaultdict

# Class to represent a graph - adapted from http://www.geeksforgeeks.org/topological-sorting-indegree-based-solution/
class Graph:
    def __init__(self,vertices):
        self.graph = defaultdict(list) #dictionary containing adjacency List
        self.V = vertices #No. of vertices

    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)


    # The function to do Topological Sort.
    def topologicalSort(self):

        # Create a vector to store indegrees of all
        # vertices. Initialize all indegrees as 0.
        in_degree = [0]*(self.V)

        # Traverse adjacency lists to fill indegrees of
        # vertices.  This step takes O(V+E) time
        for i in self.graph:
            for j in self.graph[i]:
                in_degree[j] += 1

        # Create an queue and enqueue all vertices with
        # indegree 0
        queue = []
        for i in range(self.V):
            if in_degree[i] == 0:
                queue.append(i)

        #Initialize count of visited vertices
        cnt = 0

        # Create a vector to store result (A topological
        # ordering of the vertices)
        top_order = []

        # One by one dequeue vertices from queue and enqueue
        # adjacents if indegree of adjacent becomes 0
        while queue:

            # Extract front of queue (or perform dequeue)
            # and add it to topological order
            u = queue.pop(0)
            top_order.append(u)

            # Iterate through all neighbouring nodes
            # of dequeued node u and decrease their in-degree
            # by 1
            for i in self.graph[u]:
                in_degree[i] -= 1
                # If in-degree becomes zero, add it to queue
                if in_degree[i] == 0:
                    queue.append(i)

            cnt += 1

        # Return the topological ordering (or None if a cycle exists)
        if cnt == self.V:
            return top_order


def merge_lists(*lists):
    vertices = sorted(set(v for list_ in lists for v in list_))
    vertex_dict = {vertex: index for index, vertex in enumerate(vertices)}
    graph = Graph(len(vertices))
    for list_ in lists:
        for v, w in zip(list_, list_[1:]):
            graph.addEdge(vertex_dict[v], vertex_dict[w])
    sorted_graph = graph.topologicalSort()
    if sorted_graph is not None:
        return [vertices[index] for index in sorted_graph]


if __name__ == '__main__':
    list1 = [1, 3, 6]
    list2 = [2, 3, 5]
    list3 = [2, 4, 6]
    print (merge_lists(list1, list2, list3)) # Should print [1, 2, 3, 4, 5, 6]

    list4 = [2, 3, 5]
    list5 = [1, 5, 6]
    list6 = [6, 3]
    print (merge_lists(list4, list5, list6)) # Should print None