#
# $Id: alg.py,v 1.1.1.1 2003/03/22 05:15:48 dbelan2 Exp $
#
# Contains implementation of important
# algorithms used such as DFS
#
# $Log: alg.py,v $
# Revision 1.1.1.1  2003/03/22 05:15:48  dbelan2
# Initial import of all public_html on www.cs.mcgill.ca.
#
# Revision 1.9  2001/09/30 22:27:12  dbelan2
# Removed old code.
#
# Revision 1.8  2001/09/26 20:25:15  hchen19
# Testing ci.
#
# Revision 1.7  2001/09/25 01:13:42  dbelan2
# - Improved code structure by making it more object
#   oriented.
# - Basic command interpreter running
# - Getting more general
#
# Revision 1.6  2001/09/22 02:02:19  dbelan2
# - Added dList, fList feature to DFS.
# - Commented out sorting alg, no longer needed.
# - Fixed detectCycle to reverse edges back again
# - Implemented topological sort
#
# Revision 1.5  2001/09/21 17:04:01  dbelan2
# - cycle detection works
# - needs more testing
# - does not work when given the simplified graph
#
# Revision 1.4  2001/09/21 16:51:26  dbelan2
# Reversing graph edges and post ordering sorting done.
#
# Revision 1.3  2001/09/20 21:05:11  dbelan2
# Added __str__() method.
#
# Revision 1.2  2001/09/20 17:31:35  dbelan2
# - adj attributes initization fixed.
# - initializing v attrib of obj in init
#
# Revision 1.1  2001/09/16 23:05:31  dbelan2
# DFS implemented and a small test was done.
#
#


# A vertex in the dependency graph
class Vertex:

    # adj - adjacencies list
    # obj - an object associated with the vertex
    #       for example an Integrator.  Not used
    #       by DFS.
    # colour - for DFS
    def __init__(self, adj = None, obj = None):
        
        if adj == None:
            self.adj = []
        else:
            self.adj = adj

        self.obj = obj
        if obj != None:
            self.obj.v = self

        self.colour = None
        
 
    def __str__(self):
        if self.obj != None:
            return str(self.obj)


WHITE, GRAY, BLACK = 0, 1, 2


class Graph:

    # edge info contained in Vertex object
    def __init__(self, vertices):
        self.V = vertices

    def __str__(self):
        s = ""
        for v in self.V:
            s = s + str(v.obj) + ' --> '
            dep = []
            for u in v.adj:
                dep.append(str(u.obj))
            s = s + `dep` + '\n'
        return s
            
                


    # *Note* : A source vertex is picked until
    #          all vertices are visited.
    #
    # At end of DFS dList and fList contains the vertices
    # in their order of discovery and finish time respectively
    def DFS(self):
        global time
        global dList, fList
        dList, fList = [], []
        for u in self.V:
            u.colour = WHITE
            u.parent = None
        time = 0
        for u in self.V:
            if u.colour == WHITE:
                self.DFSVisit(u)


    def DFSVisit(self, u):
        global time
        u.colour = GRAY  # white vertex u has just been discovered
        time = time + 1
        u.d = time
        dList.append(u)
        for v in u.adj:
            if v.colour == WHITE:
                v.parent = u
                self.DFSVisit(v)
        u.colour = BLACK  # Blacken u, it is finished
        time = time + 1
        u.f = time
        fList.append(u)


    def detectLoops(self):

        self.DFS()
        fList.reverse()     # reverse list of postorder vertices
        Gps = Graph(fList)  # graph with vertices listed in postorder
        self.reverseEdge()
        
        # rearrange set of vertices of Gr to change DFS order
        for v in self.V[:]:
            self.V[Gps.V.index(v)] = v

        self.DFS()

        # test for strong component
        # strong component ==> cycle
        # no cycle if all strong components have only 1 vertex
        isCyclic = 0
        for v in self.V:
            if v.parent != None:
                #print "cycle detected, contains ", str(v), str(v.parent)
                isCyclic = 1
        self.reverseEdge()  # put graph back to the way it was
        return isCyclic


    # Reverse edges
    #
    # need to keep same vertex object
    # and change only adj list
    def reverseEdge(self):
        adjs = []  # list of list
        for v in self.V:
            adjs.append([])
        for v in self.V:
            vnewadj = []
            for u in v.adj[:]:
                adjs[self.V.index(u)].append(v)
     
        for i in range(0, len(self.V)):
            self.V[i].adj = adjs[i] 

 
    # Returns an order.  It is assumed that G has been previously check
    # for cycle.
    def topologicalSort(self):
        self.DFS()
        #fList.reverse() not reverse because want 1st element 1st
        return fList