#!/usr/bin/python

# Rajarshi Guha <rajarshi@presidency.com>
# 9/02/2003
#
# Does a depth first traversal of a graph and does'nt care
# whether its a directed or undirected graph
# 

import copy

class GraphException:
    def __init__(self,code):
        self.errmsg = { 'badvertex':'Non existant vertex in edge list'}
        self.msg = self.errmsg[code]
    def __str__(self):    
        return( self.msg )
    
class Edge:
    def __init__(self, v1,v2):
        self.v1 = v1
        self.v2 = v2
    def __str__(self):
        return( str(self.v1)+' - '+str(self.v2))

class Vertex:
    def __init__(self,vid,data = None):
        self.vid = vid
        self.data = data

class Graph:
    def __init__(self, vlist, edgelist):

        # Make some checks before we save these elements
        self.datalist = {}
        self.vlist = []

        for v in vlist:
            self.vlist.append(v.vid)
            self.datalist[v.vid] = v.data
            
        for e in edgelist:
            if e.v1 not in self.vlist:
                raise GraphException('badvertex')
            if e.v2 not in self.vlist:
                raise GraphException('badvertex')

        self.elist = edgelist
        self.numv = len(vlist)

    def connected_to(self, v):
        l =[]
        for e in self.elist:
            if v == e.v1 and e.v2 not in l: l.append(e.v2)
            if v == e.v2 and e.v1 not in l: l.append(e.v1)
        return l    

class DepthFirstTraversal:
    def __init__(self, graph):
        self.graph = graph
        for node in self.graph.vlist:
            self.graph.datalist[node] = 0
    
    def _visit(self,node):
        print 'Visited node: '+str(node)
        self.graph.datalist[node] = 1
        return
    
    def _dft(self,node):
        self._visit(node)
        yl = []
        for edge in self.graph.elist:
            if edge.v1 == node:
                yl.append(edge.v2)
            elif edge.v2 == node:
                yl.append(edge.v1)
        for y in yl:
            if not self.graph.datalist[y]:
                self._dft(y)
        return                

    def do_dft(self,node = 1):
        self._dft(node)
        
            
        
if __name__ == '__main__':

#    v = [1,2,3,4,5,6,7,8]
#    e = [Edge(1,3), Edge(3,2), Edge(3,4), Edge(3,1),
#    Edge(3,5), Edge(5,3), Edge(5,6), Edge(5,8),
#    Edge(6,5), Edge(6,7), Edge(7,6), Edge(7,8), Edge(8,7),
#    Edge(8,5) ]
    
    v = [Vertex(1,0), Vertex(2,0), Vertex(3,0), Vertex(4,0),Vertex(5,0),
    Vertex(6,0),Vertex(7,0), Vertex(8,0)]
    e = [ Edge(1,2), Edge(2,3), Edge(3,4),Edge(2,5), Edge(2,5),
    Edge(5,6), Edge(6,7), Edge(7,6),Edge(3,8)]

    g = Graph(v,e)
    
    dft = DepthFirstTraversal(g)
    dft.do_dft()