python graph lib

               
               
                #!/usr/bin/env  python
"""
python graph
"""
__author__ = "lynn lin"
__license__ = "MIT"
# imports
from stack import stack
from queue import queue
class graph(object):
    """
    directed graph class
    """
    def __initvar__(self):
        self.container = {}
        self.indegree  = {}
        self.outdegree = {}
        self.postfdn   = 0
        self.prefdn    = 0
        self.pre       = {}
        self.post      = {}
        self.toplist   = {}
# visited flag,default is unvisited
        self.visited   = {}
    def __init__(self):
        """
        initial node list
        """
        self.__initvar__()
        
    def __len__(self):
        """
        return number of graph nodes
        """
        return len(self.container.keys())
    def addnode(self,node,arc = []):
        if node not in self.container.keys():
            self.container[node] = arc
            self.indegree[node] = 0
            self.outdegree[node] = 0
        else :
                 self.container[node] += arc
        for item in arc :
                if item not in self.container.keys():
                    self.container[item] = []
                    self.indegree[item] = 0
                    self.indegree[item] += 1
                    self.outdegree[node] += 1           
                    self.outdegree[item] = 0
                else :
                    self.indegree[item] += 1
                    self.outdegree[node] += 1
   
   
    def delNode(self,node):
            if node not in self.container.keys():
                return
            else :
                self.container.pop(node)
# decrease outdegree
                for v in self.container.keys():
                    if node in self.container[v]:
                        self.outdegree[v] -= 1
                        self.container[v].remove(node)
               
   
    def delEge(self,u,v):
        """
        del ege (u->v)
        """
        if u not in self.container.keys():
            return
        if v in self.container:
            print 'deleting ege u->v...'
            self.container.remove(v)
            self.indegree[v] -=1
            self.outdegree -= 1
        
    def getNodeArc(self,node):
        if node in self.container.keys():
            return self.container[node]
    def getNodeIndegree(self,node):
        if node in self.container.keys():
            return self.indegree[node]
        else :
            raise "node is not in graph"
    def getNodeOutdegree(self,node):
        if node in self.container.keys():
            return self.outdegree[node]
        else :
            raise "node is not in graph"
    def SearchPath(self,start,goal):
        def generate(path,goal,solns):
            state = path[-1]
            if state == goal:
                solns.append(path)
            else :
                for arc in self.container[state]:
                    if arc not in path:
                        generate(path + [arc],goal,solns)
        solns = []
        generate([start],goal,solns)
        solns.sort(lambda x,y:cmp(len(x),len(y)))
        return solns
   
    def Breadth_first_search(self):
        """
        using queue datastructure
        """
        for v in self.container.keys():
            self.visited[v] = 0
# initialize queue
        que = queue()
        for vetex in self.container.keys():
            if self.visited[vetex] == 0 :
                que.EnQueue(vetex)
            while que.QueueEmpty() > 0 :
                node = que.DeQueue()
                if self.visited[node] == 0 :
                    print 'node',node
                    self.visited[node] = 1
                for adj in self.container[node]:
                    if self.visited[adj] == 0 :
                        que.EnQueue(adj)
            
        
    def Depth_first_search(self):
        """
        using stack datastructure
        """
        for v in self.container.keys():
            self.visited[v] = 0
# initialize stack
        sta = stack()
        for vetex in self.container.keys():
            if self.visited[vetex] == 0 :
                sta.push(vetex)
            while sta.StackEmpty() > 0 :
                node = sta.pop()
                if self.visited[node] == 0 :
                    print 'node',node
                    self.visited[node] = 1
                for adj in self.container[node]:
                    if self.visited[adj] == 0 :
                        sta.push(adj)
        
    def dfs(self):
        """
        dfs using recurisive tech
        """
        def _dfs(v):
#            print v
            self.visited[v] = 1
            self.prefdn += 1
            self.pre[v] = self.prefdn
            for vetex in self.container[v]:
                if self.visited[vetex] == 0 :
                    _dfs(vetex)
            self.postfdn += 1
            self.post[v] = self.postfdn
        for v in self.container.keys():
             self.visited[v] = 0
        for v in self.container.keys():
            if self.visited[v] == 0 :
                _dfs(v)
    def Top_Sort(self):
        """
        running is O(V*E)
        """
#    initialize topsort stack
        topstack = stack()
        for v in self.container.keys():
            if self.indegree[v] == 0 :
                topstack.push(v)
        count = 0
        R = {}
        while (topstack.StackEmpty() != 0):
            u = topstack.pop()
            count += 1
            R[count] = u
            for item in self.container:
                self.indegree[item] = self.indegree[item] -1
                if self.indegree[item] == 0:
                    topstack.push(item)
        print R
        
    def Top_Sort2(self):
        self.dfs()
        return self.post
        
    def Shortest_Path(self,start):
        """
        unweighted shortest path
        """
        que = queue()
        path = {}
        path[start] = 0
        for vetx in self.container.keys():
            self.visited[vetx] = 0
        que.EnQueue(start)
        while (que.QueueEmpty() != 0):
            node = que.DeQueue()
            if self.visited[node] == 0 :
                self.visited[node] = 1
            for arc in self.container[node]:
                if self.visited[arc] == 0 :
                    path[arc] = path[node] + 1
                    que.EnQueue(arc)
        return path
   
if __name__ == '__main__':
    G = graph()
    G.addnode('v1',['v2','v4'])
    G.addnode('v2',['v5'])
    G.addnode('v3',['v1','v6'])
    G.addnode('v4',['v6','v7'])
    G.addnode('v5',['v7'])
    G.addnode('v6',[])
    G.addnode('v7',['v6'])
#   G.addnode('c',['b','e'])
#   G.delNode('b')
#    G.delNode('c')
  #  for v in G.container.keys():
  #      print v,G.getNodeOutdegree(v)
   # G.Breadth_first_search()   
    print '=================='   
    path = G.Shortest_Path('v3')
    print path