import copy
from types import *

class DepGraph:
    def __init__(self):
        self.deps = []
        self.values = []

    def add(self, value):
        if value in self.values:
            raise ValueError
        self.values.append(value)


    def rightSize(self):
        vl = len(self.values)
        dl = len(self.deps)

        if dl != vl:
            full = []
            for i in range(0, vl):
                full.append(False)

            exp = []
            for i in range(dl, vl):
                exp.append(False)
                self.deps.append(full[:])

            for i in range(0, dl):
                self.deps[i].append(exp[:])

    def addDependency(self, src, dst):
        if not type(dst) is ListType:
            dst = [ dst ]

        self.rightSize()

        si = self.values.index(src)
        for d in dst:
            if d in self.values:
                di = self.values.index(d)
                self.deps[si][di] = True

    @staticmethod
    def identifyStronglyConnectedComponents(deps):
        """Tarjan's algorithm"""
        S=[]
        vindex={}
        lowlink={}
        retVal=[]
        for v in range(len(deps)):
            if not v in vindex:
                retVal.extend(DepGraph.strongconnect(deps, v, 0, vindex, lowlink, S))
        return retVal

    @staticmethod
    def successors(deps, v):
        retVal = []
        for w in range(len(deps)):
            if deps[w][v]:
                retVal.append(w)
        return retVal

    @staticmethod
    def strongconnect(deps, v, index, vindex, lowlink, S):
        retVal = []
        # Set the depth index for v to the smallest unused index
        vindex[v] = index
        lowlink[v] = index
        S.append(v)

        # Consider successors of v
        for w in DepGraph.successors(deps, v):
            if not w in vindex:
                # Successor w has not yet been visited; recurse on it
                res = DepGraph.strongconnect(deps, w, index + 1, vindex, lowlink, S)
                retVal.extend(res)
                lowlink[v] = min(lowlink[v], lowlink[w])
            elif w in S:
                # Successor w is in stack S and hence in the current SCC
                lowlink[v] = min(lowlink[v], vindex[w])

        # If v is a root node, pop the stack and generate an SCC
        if lowlink[v] == vindex[v]:
            #start a new strongly connected component
            component = []
            w = None
            while w != v:
                w = S.pop()
                #add w to current strongly connected component
                component.append(w)
            retVal.append(component)
        return retVal

    @staticmethod
    def dissolveStronglyConnectedComponents(deps):
        dissolved = True
        while dissolved:
            dissolved = False
            strong = DepGraph.identifyStronglyConnectedComponents(deps)
            for s in strong:
                if len(s) > 1:
                    #We remove the first dependency, and see how it goes.
                    #FIXME: This may not be the best strategy to achieve this
                    v = s[0]
                    for w in s[1:]:
                        if deps[w][v]:
                            #print "Remove link %d -> %d" % (w, v)
                            deps[w][v] = False
                            dissolved = True
                            break
        return deps

    @staticmethod
    def directedGraphInternal(deps):
        dl = len(deps)
        startPoints = []
        for i in range(dl):
            if not max(deps[i]):
                startPoints.append(i)

        for i in startPoints:
            for j in range(dl):
                deps[j][i] = False

        retVal = startPoints

        if len(deps) != len(startPoints):
            subVals = DepGraph.directedGraphInternal(deps)
            for val in startPoints:
                if val in subVals:
                    ind = subVals.index(val)
                    del subVals[ind]

            if subVals:
                retVal.extend(subVals)

        return retVal

    @staticmethod
    def printableDepgraph(deps):
        res=''
        for i in range(len(deps)):
            if res:
                res += '\n'
            s = ''
            for j in range(len(deps[i])):
                if deps[i][j]:
                    s += '1'
                else:
                    s += '0'
            res += s
        return res

    def depGraphRepr(self):
        return self.printableDepgraph(self.deps)

    def directedGraph(self, force = True):
        deps = copy.deepcopy(self.deps)
        if force:
            deps = self.dissolveStronglyConnectedComponents(deps)
        vals = self.directedGraphInternal(deps)
        retVal = []
        for i in vals:
            retVal.append(self.values[i])
        return retVal


    def toplevelDependencies(self):
        dl = len(self.deps)
        retVal = []
        for i in range(dl):
            if not max(self.deps[i]):
                print max(self.deps[i])
                retVal.append(self.values[i])
        return retVal