|
#!/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[u]:
print 'deleting ege u->v...'
self.container[u].remove(v)
self.indegree[v] -=1
self.outdegree[u] -= 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[u]:
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
|
