#!/usr/bin/python

# Rajarshi Guha <rajarshi@presidency.com>
# 07/06/2004
#
# Implements a breadth first algorithm to find the smallest
# ring containing the specified node. 
#
# Implemented from  Figueras, J. Chem. Inf. Comput. Sci., 1996, 36, 986-991
import string

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, label, data = None, path= []):
        self.label = int(label)
        self.data = data 
        self.path = path
    def __str__(self):
        return 'V'+str(self.label)+'('+str(self.data)+')'
    def getLabel(self):
        return self.label
    
class Graph:
    def __init__(self, vlist, edgelist):

        # Make some checks before we save these elements
        for e in edgelist:
            if e.v1 not in vlist:
                raise GraphException('badvertex')
            if e.v2 not in vlist:
                raise GraphException('badvertex')

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

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

    def getVertex(self, label):
        for vertex in self.vlist:
            if vertex.label == label:
                return vertex
        return None            

class Queue:

    def __init__(self):
        self.q = []

    def enqueue(self, item):
        self.q.append(item)
    
    def dequeue(self):
        val = self.q[0]
        del self.q[0]
        return val

    def isempty(self):
        if len(self.q) == 0: return 1
        else: return 0

def bfRingSet(g, startnode):

    levelcount = 1
    startnode.data = levelcount
    levelcount += 1
    
    q = Queue()

    nbrs = g.connected_to( startnode.getLabel() )
    for nbr in nbrs:
        nbr.path = [ startnode.getLabel(), nbr.getLabel() ]
        nbr.source = startnode.getLabel()
        q.enqueue( nbr )

    while not q.isempty():

        node = q.dequeue()
        nbrs = g.connected_to(node.getLabel())

        for nbr in nbrs:

            if nbr.getLabel() == node.source:
                continue
            
            if len(nbr.path) == 0:
                nbr.path =newPath( node.path, nbr.getLabel() )
                nbr.source = node.getLabel()
                q.enqueue( nbr )
            else:
                isect = intersection( node.path, nbr.path )
                if len(isect) == 1:
                    ringset = union( node.path, nbr.path )
                    return ringset
                
def parseGraphString( gstr ):

    s = string.split(string.strip(gstr),'\n')
    s = [string.strip(x) for x in s]

    vlist = [Vertex(int(x)) for x in string.split(s[0])[2:]]
    tmp = string.split(s[1])[2:]
    elist = []
    for pair in tmp:
        labels = [int(x) for x in string.split(pair,',')]
        v1 = None
        v2 = None
        for v in vlist:
            if v.getLabel() == labels[0]:
                v1 = v
                break
        for v in vlist:
            if v.getLabel() == labels[1]:
                v2 = v
                break
        elist.append( Edge(v1,v2) )
    return Graph(vlist,elist)
                    
def newPath( oldPath, newMember ):
    np = []
    for i in oldPath:
        np.append(i)
    np.append(newMember)
    return np

def intersection( list1 , list2 ):
    i = []
    for item in list1:
        if item in list2 and item not in i:
            i.append(item)
    return i
def union( list1, list2 ):
    u = []
    for i in list1:
        if i not in u:
            u.append(i)
    for i in list2:
        if i not in u:
            u.append(i)
    return u            
    
if __name__ == '__main__':

    gstr = """
    v = 1 2 3 4 5 
    e = 1,2 2,3 3,4 4,1 3,5
    """
    g = parseGraphString(gstr)
    rs = bfRingSet(g, g.getVertex(2))
    print rs