#!/usr/local/bin/py

# Rajarshi Guha <rajarshi@presidency.com>
# 4/10/2002
#
# Calculates number of paths of length N for a 
# undirected graph. Includes a simple Graph class

import copy

def revlist(l):
    n = []
    for i in range(len(l)-1, -1, -1):
       n.append(l[i])
    return n       

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 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, 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    


    def __list_path(self, v, num):

        li = [ [v] ]

        for counter in range(1, num+1):
            la = copy.deepcopy(li)
            for l in li:
                vs = self.connected_to( l[len(l)-1] )
                la.remove(l)
                for i in vs:
                    t = copy.deepcopy(l)
                    if i not in t: t.append(i)
                    la.append( t)
            li = copy.deepcopy(la)
        
        li = []
        for l in la:
            if len(l) == num+1: li.append(l)
        return li                

    def list_all_path(self,num):

        if num == 0: return None
        ml = []
        for v in self.vlist:
            l = self.__list_path(v,num)
            for i in l:
                if revlist(i) not in ml: ml.append(i)
        return ml        


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 = [1,2,3,4]
    e = [ Edge(1,2), Edge(2,3), Edge(3,4) ]

    g = Graph(v,e)
    #print g.__list_path(5,3)
    l =  g.list_all_path(1)
    print l
    print len(l)