The directef graph file (dgraph.py) content:
#!/usr/bin/python
from collections import namedtuple
import Queue
import priority_dict
Edge = namedtuple("Edge", ['fromm','to', 'weight','color'])
""" directed graph class"""
class dgraph:
def __init__(self):
# empty underlying dictionary
self.g = {}
""" adds an edge from fromN to toN. if fromN or toN doesn't
exist then they are created """
def addEdge(self,fromN,toN,w=0,color='white'):
#check if fromN Node is not available
if not self.g.has_key(fromN):
self.g[fromN]=[]
#check if toN Node is not available
if not self.g.has_key(toN):
self.g[toN]=[]
self.g[fromN].append(Edge(fromN,toN,w,color))
""" adds a new node to the graph if it is not already there"""
def addNode(self, N):
if not self.g.has_key(N):
self.g[N]=[]
""" returns the list of edges from node N"""
def edgesOf(self, N):
if self.g.has_key(N):
edges=[]
for edge in self.g[N]:
edges.append(edge.to)
return edges
return None
""" dyes edge from node fromN to node toN with the given color"""
def setEdgeColor(self,fromN,toN,color):
for edge in (self.g[fromN]):
if edge.to == toN:
self.g[fromN].remove(edge)
self.g[fromN].append(Edge(fromN,toN,edge.weight,color))
""" gets teh color of the edge from fromN node to toN node"""
def edgeColor(self,fromN,toN):
for edge in self.g[fromN]:
if edge.to == toN:
return edge.color
""" returns nodes of the graph as a list"""
def nodes(self):
return self.g.keys()
""" returns number of nodes in te graph"""
def numOfNodes(self):
return len(self.g.keys())
""" returns number of edges in the graph"""
def numOfEdges(self):
num=0
for key in self.g.keys():
num = num + len(self.g[key])
return num
""" returns number of edges node N have """
def numOfEdgesNode(self,N):
return len(self.g[N])
""" returns True if there is an edge from sourceN node to toN node
False otherwise"""
def hasEdge(self,fromN, toN):
for edge in self.g[fromN]:
if edge.to == toN:
return True
return False
""" returns the weight from fromN node to toN node,
None if there is no edge between them"""
def weight(self,fromN,toN):
for edge in self.g[fromN]:
if edge.to == toN:
return edge.weight
return None
def readFileContent(self,file_name):
file_location = file_name.strip()
input_data_file = open(file_location, 'r')
input_data = ''.join(input_data_file.readlines())
input_data_file.close()
return input_data
""" implements dijkstra's shortest path algorithm """
def shortestPathDijkstra(self,fromN,toN=None):
dist ={} #define distance dictionary
prev ={} #define previous node dictionary
S =[] #list of shortest path
Q = priority_dict.priority_dict()
#initialize distances and predecessors
for node in self.g.keys():
if node != fromN :
dist[node]=float('inf')
else:
dist[node] =0
prev[node]=None
Q.setdefault(node,dist[node])
while not Q.empty():
u = Q.pop_smallest()
if u == toN:
break
if dist[u] == float('inf'):
break
#traverse each neighbour of u
for edge in self.g[u]:
alt = dist[u] + self.weight(u,edge.to)
if alt < dist[edge.to]:
dist[edge.to] = alt
prev[edge.to] = u
Q.update([(edge.to,alt)])
while prev[toN] != None:
S.append(toN)
toN = prev[toN]
S.append(toN)
return S
if __name__ == '__main__':
x = dgraph()
x.addEdge('1','2',w=6)
x.addEdge('1','3',w=2)
x.addEdge('1','4',w=16)
x.addEdge('2','4',w=5)
x.addEdge('2','5',w=4)
x.addEdge('3','2',w=7)
x.addEdge('3','5',w=3)
x.addEdge('3','6',w=8)
x.addEdge('4','7',w=3)
x.addEdge('5','4',w=4)
x.addEdge('5','7',w=10)
x.addEdge('6','7',w=1)
"""x.addNode('Yalova')
x.addEdge('Adana','Yalova',weight=300)
x.addEdge('Yalova','Istanbul',weight=200,color='blue')
#x.addEdge('Yalova','Adana',600)
print x.edgesOf('Yalova')
print x.edgesOf('Adana')
print x.edgeColor('Yalova','Istanbul')
x.setEdgeColor('Adana','Istanbul','red')
print x.edgeColor('Adana','Istanbul')
print x.numOfNodes(),x.nodes(),x.numOfEdges(),x.numOfEdgesNode('Yalova')
print x.hasEdge('Adana','Istanbul')
print x.hasEdge('Adana','Adana')"""
print x.shortestPathDijkstra('1','7')
The following file is taken from
http://code.activestate.com/recipes/522995-priority-dict-a-priority-queue-with-updatable-prio/
which has the implementation of a priority queue with updatable priorities.
priority_dict.py
from heapq import heapify, heappush, heappop
class priority_dict(dict):
"""Dictionary that can be used as a priority queue.
Keys of the dictionary are items to be put into the queue, and values
are their respective priorities. All dictionary methods work as expected.
The advantage over a standard heapq-based priority queue is
that priorities of items can be efficiently updated (amortized O(1))
using code as 'thedict[item] = new_priority.'
The 'smallest' method can be used to return the object with lowest
priority, and 'pop_smallest' also removes it.
The 'sorted_iter' method provides a destructive sorted iterator.
"""
def __init__(self, *args, **kwargs):
super(priority_dict, self).__init__(*args, **kwargs)
self._rebuild_heap()
def _rebuild_heap(self):
self._heap = [(v, k) for k, v in self.iteritems()]
heapify(self._heap)
def smallest(self):
"""Return the item with the lowest priority.
Raises IndexError if the object is empty.
"""
heap = self._heap
v, k = heap[0]
while k not in self or self[k] != v:
heappop(heap)
v, k = heap[0]
return k
def pop_smallest(self):
"""Return the item with the lowest priority and remove it.
Raises IndexError if the object is empty.
"""
heap = self._heap
v, k = heappop(heap)
while k not in self or self[k] != v:
v, k = heappop(heap)
del self[k]
return k
def __setitem__(self, key, val):
# We are not going to remove the previous value from the heap,
# since this would have a cost O(n).
super(priority_dict, self).__setitem__(key, val)
if len(self._heap) < 2 * len(self):
heappush(self._heap, (val, key))
else:
# When the heap grows larger than 2 * len(self), we rebuild it
# from scratch to avoid wasting too much memory.
self._rebuild_heap()
def setdefault(self, key, val):
if key not in self:
self[key] = val
return val
return self[key]
def update(self, *args, **kwargs):
# Reimplementing dict.update is tricky -- see e.g.
# http://mail.python.org/pipermail/python-ideas/2007-May/000744.html
# We just rebuild the heap from scratch after passing to super.
super(priority_dict, self).update(*args, **kwargs)
self._rebuild_heap()
def sorted_iter(self):
"""Sorted iterator of the priority dictionary items.
Beware: this will destroy elements as they are returned.
"""
while self:
yield self.pop_smallest()
def empty(self):
return (len(self._heap) == 0)
