import numpy

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 addDependency(self, src, dst):
        if not type(dst) is ListType:
            dst = [ dst ]

        vl = len(self.values)
        dl = len(self.deps)
        si = self.values.index(src)
        

        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[:])
                
        for d in dst:
            if d in self.values:
                di = self.values.index(d)
                self.deps[si][di] = True


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

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

        retVal = myVals

        if len(deps) != len(myVals):
            subVals = self.directedGraphInternal(deps)
            for val in myVals:
                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 directedGraph(self):
        deps = self.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