Floyd/Warshall algorithm to compute the min cost path between any two |
vertices. |
|
n is the number of vertices |
|
C is the cost matrix, where C[i, j] is the cost of taking the edge from |
vertex i to vertex j. If there is no edge the cost is infinite. Costs |
are always non-negative. C[i, i] = 0; |
|
M[l, i, j] is the min cost of going from i to j using l or fewer edges. |
|
Note that |
a) M[0, i, i] = 0, and for i != j, M[0, i, j] = infinity |
b) M[1, i, j] = C[i, j] |
c) for l >= n then M[l-1, i, j] = M[l, i, j] since you cannot have a |
path of more than n-1 edges in the graph. |
|
So M[n, i, j] is the min cost of a path from vertex i to vertex j |
in a graph with n vertices. |
|
Then the relationship between M for increasing l is as follows: |
|
M[l+1, i, j] = Min over k of M[l, i, k] + C[k, j] |
|
Computing this in the naive way is O(n^4), and needs two n x n |
matrices |
|
for l in range(2, n): |
for i in range(n): |
for j in range(n): |
M[l+1, i, j] = |
min over k of M[l, i, k] + C[k, j] |
|
Note C[i, j] = M[1, i, j] so we can rewrite the min as: |
|
M[l+1, i, j] = min over k of M[l, i, k] + M[1, k, j] |
|
This suggests that M is computed using a kind of matrix multiplication |
where instead of using the (+, *) inner product, we use the (min, +) |
inner product: |
|
M[n] = M[1] x M[1] x ... x M[1] |
|
So we could use the recursive doubling trick from the Diffie-Hellman |
key exchange to comput M[n] by log n squarings of M[1]. |
|
for l in range(log(n)) |
for i in range(n): |
for j in range(n): |
M[l+l, i, j] = |
min over k of M[l, i, k] + M[l, k, j] |
|
Which is of time complexity O(n^3 log n) |
|
This is still not particularly good. Consider a graph of 1000 vertices.` |
Define A[k,i,j] = the cost of going from vertex i to j using possibly |
intermediate vertices 0 upto k. |
|
Then A[n-1,i,j] = min cost of a path from vertex i to j. |
|
Consider A[k,i,j]. |
|
The least cost path between i and j either includes k or it doesn't |
include k. If it includes k then A[k,i,j] = A[k-1,i,k] + A[k-1,k,j]. |
If it does not include k then A[k,i,j] = A[k-1,i,j]. So, |
|
A[k,i,j] = min ( A[k-1,i,j], A[k-1,i,k] + A[k-1,k,j] ) |
|
k |
~ ~ |
A[k-1,i,k] ~ ~ A[k-1,k,j] |
~ ~ |
i ~~~~~~~~~~~~ j |
A[k-1,i,j] |
|
We can define the base case A[-1,i,j] = C[i,j], that is, the cost of |
going directly from i to j (i.e. not passing through any intermediate |
vertex). |
|
Now, unlike the previous algorithm, where one needs two matricies to |
store the current best cost for paths of length l edges and the new |
updated cost for paths of length l+1, this requires only one matrix A. |
|
The key is observing that |
A[k, i, j] <= A[k-1, i, j], |
that is, the cost can only get lower as you increase k. |
|
Also, A[k,i,k] = A[k-1,i,k], A[k,k,j] = A[k-1,k,j]. |
That is, the kth version of A does not change entries where i=k or j=k. |
|
So, rather than iterating over k in the inner loop, we move k to the |
outer loop and add new vertices (k) to consideration for each cost |
matrix. |
|
Now from the diagram above, for each new k we have |
|
A[k, i, j] = min ( A[k-1, i, j], A[k-1, i, k] + A[k-1, k, j] ) |
|
Now this expression has useful properties for i=j, i=k, or k=j |
since A[k-1, i, i] is 0 and A[k-1, k, k] = 0. |
|
This means that updating the [i, j] entry is always independent of |
the values of the [i,k] and [k,j] entries. So you can actually do |
the update in place. |
|
So our loops go: |
|
for k in range(n) |
for i in range(n) |
for j in range(n) |
A[i, j] = min ( A[i, j], A[i, k] + A[k, j] ) |
|
which O(n^3) time and O(n^2) space. This is still not a big |
improvement. |
""" |
Graph module for undirected graphs. |
""" |
|
import random |
|
try: |
import display |
except: |
print("Warning: failed to load display module. Graph drawing will not work.") |
|
class Digraph: |
""" |
Directed graph. The vertices must be immutable. |
|
To create an empty graph: |
>>> G = Digraph() |
>>> (G.num_vertices(), G.num_edges()) |
(0, 0) |
|
To create a circular graph with 3 vertices: |
>>> G = Digraph([(1, 2), (2, 3), (3, 1)]) |
>>> (G.num_vertices(), G.num_edges()) |
(3, 3) |
""" |
|
def __init__(self, edges = None): |
self._tosets = {} |
self._fromsets = {} |
|
if edges: |
for e in edges: self.add_edge(e) |
|
def __repr__(self): |
return "Digraph({}, {})".format(self.vertices(), self.edges()) |
|
def add_vertex(self, v): |
""" |
Adds a vertex to the graph. It starts with no edges. |
|
>>> G = Digraph() |
>>> G.add_vertex(1) |
>>> G.vertices() == {1} |
True |
""" |
if v not in self._tosets: |
self._tosets[v] = set() |
self._fromsets[v] = set() |
|
def add_edge(self, e): |
""" |
Adds an edge to graph. If vertices in the edge do not exist, it adds them. |
|
>>> G = Digraph() |
>>> G.add_vertex(1) |
>>> G.add_vertex(2) |
>>> G.add_edge((1, 2)) |
>>> G.add_edge((2, 1)) |
>>> G.add_edge((3, 4)) |
>>> G.add_edge((1, 2)) |
>>> G.num_edges() |
3 |
>>> G.num_vertices() |
4 |
""" |
# Adds the vertices (in case they don't already exist) |
for v in e: |
self.add_vertex(v) |
|
# Add the edge |
self._tosets[e[0]].add(e[1]) |
self._fromsets[e[1]].add(e[0]) |
|
def edges(self): |
""" |
Returns the set of edges in the graph as ordered tuples. |
""" |
return { (v, w) for v in self._tosets for w in self._tosets[v] } |
|
def vertices(self): |
""" |
Returns the set of vertices in the graph. |
""" |
return set(self._tosets.keys()) |
|
def draw(self, filename, attr = {}): |
""" |
Draws the graph into a dot file. |
""" |
display.write_dot_desc((self.vertices(), self.eges()), filename, attr) |
|
def num_edges(self): |
m = 0 |
for v in self._tosets: |
m += len(self._tosets[v]) |
return m |
|
def num_vertices(self): |
""" |
Returns the number of vertices in the graph. |
""" |
return len(self._tosets) |
|
def adj_to(self, v): |
""" |
Returns the set of vertices that contain an edge from v. |
|
>>> G = Digraph() |
>>> for v in [1, 2, 3]: G.add_vertex(v) |
>>> G.add_edge((1, 3)) |
>>> G.add_edge((1, 2)) |
>>> G.adj_to(3) == set() |
True |
>>> G.adj_to(1) == { 2, 3 } |
True |
""" |
return self._tosets[v] |
|
def adj_from(self, v): |
""" |
Returns the set of vertices that contain an edge to v. |
|
>>> G = Digraph() |
>>> G.add_edge((1, 3)) |
>>> G.add_edge((2, 3)) |
>>> G.adj_from(1) == set() |
True |
>>> G.adj_from(3) == { 1, 2 } |
True |
""" |
return self._fromsets[v] |
|
def is_path(self, path): |
""" |
Returns True if the list of vertices in the argument path are a |
valid path in the graph. Returns False otherwise. |
|
>>> G = Digraph([(1, 2), (2, 3), (2, 4), (1, 5), (2, 5), (4, 5), (5, 2)]) |
>>> G.is_path([1, 5, 2, 4, 5]) |
True |
>>> G.is_path([1, 5, 4, 2]) |
False |
""" |
pass |
|
def random_graph(n, m): |
""" |
Make a random Digraph with n vertices and m edges. |
|
>>> G = random_graph(10, 5) |
>>> G.num_edges() |
5 |
>>> G.num_vertices() |
10 |
>>> G = random_graph(1, 1) |
Traceback (most recent call last): |
... |
ValueError: For 1 vertices, you wanted 1 edges, but can only have a maximum of 0 |
""" |
G = Digraph() |
for v in range(n): |
G.add_vertex(v) |
|
max_num_edges = n * (n-1) |
if m > max_num_edges: |
raise ValueError("For {} vertices, you wanted {} edges, but can only have a maximum of {}".format(n, m, max_num_edges)) |
|
while G.num_edges() < m: |
G.add_edge(random.sample(range(n), 2)) |
|
return G |
|
def spanning_tree(G, start): |
""" |
Runs depth-first-search on G from vertex start to create a spanning tree. |
""" |
visited = set() |
todo = [ (start, None) ] |
|
T = Digraph() |
|
while todo: |
(cur, e) = todo.pop() |
|
if cur in visited: continue |
|
visited.add(cur) |
if e: T.add_edge(e) |
|
for n in G.adj_to(cur): |
if n not in visited: |
todo.append((n, (cur, n))) |
|
return T |
|
def shortest_path(G, source, dest): |
""" |
Returns the shortest path from vertex source to vertex dest. |
|
>>> G = Digraph([(1, 2), (2, 3), (3, 4), (4, 5), (1, 6), (3, 6), (6, 7)]) |
>>> path = shortest_path(G, 1, 7) |
>>> path |
[1, 6, 7] |
>>> G.is_path(path) |
True |
""" |
pass |
|
def compress(walk): |
""" |
Remove cycles from a walk to create a path. |
|
>>> compress([1, 2, 3, 4]) |
[1, 2, 3, 4] |
>>> compress([1, 3, 0, 1, 6, 4, 8, 6, 2]) |
[1, 6, 2] |
""" |
|
lasttime = {} |
|
for (i,v) in enumerate(walk): |
lasttime[v] = i |
|
rv = [] |
i = 0 |
while (i < len(walk)): |
rv.append(walk[i]) |
i = lasttime[walk[i]]+1 |
|
return rv |
|
|
|
if __name__ == "__main__": |
import doctest |
doctest.testmod() |
""" |
A module that takes graphs, G=(V, E) and attributes on |
vertices and edges, and generates a .dot file for display |
with graphviz. |
|
The type of graph to be rendered is normalyy just a undirected |
graph. To render a directed graph, set the keyword parameter |
graphtype='digraph' |
the default is graphtype='graph' |
|
V is a set of vertices |
E is a set of edges, in a |
graph - the tuple (u, v) for u, v in V is an edge between |
u and v. The pair (v, u) is equivalent, and only one |
of the two possibilities should appear in E. |
digraph - the tuple (u, v) for u, v in V is a directed edge |
from u to v. It is different from the tuple (v, u) |
which is the edge in the opposite direction. |
|
|
attributes is an optional argument. It is a dictionary of vertex and |
edge attributes with these possible (optional) keys: |
vertex_color |
vertex_label |
edge_color |
edge_label |
Each of these keys maps to a dictionary. |
atrributes['vertex_color'][v] if present is a string |
that gives the color of vertex v |
atrributes['vertex_label'][v] if present is a string |
that will be used as the label for vertex v. If |
not present, the label for v is v. |
atrributes['edge_color'][(u,v)] if present is a string |
that gives the color of edge (u, v) |
atrributes['edge_label'][(e,v)] if present is a string |
that will be used as the label for egde (u,v). If |
not present, the dge is unlabelled. |
|
""" |
import time |
import sys |
|
def gen_dot_desc(G, graphtype='graph', attributes={}): |
""" |
Given graph G, return a string that encodes the dot |
representation of G. |
|
>>> g = ({1, 2, 3}, {(1, 2), (1, 3)} ) |
>>> s = gen_dot_desc(g) |
|
""" |
if "vertex_color" in attributes: |
vertex_color=attributes["vertex_color"] |
else: |
vertex_color={ } |
|
if "edge_color" in attributes: |
edge_color=attributes["edge_color"] |
else: |
edge_color={ } |
|
if "vertex_label" in attributes: |
vertex_label=attributes["vertex_label"] |
else: |
vertex_label={ } |
|
if "edge_label" in attributes: |
edge_label=attributes["edge_label"] |
else: |
edge_label={ } |
|
(V, E) = G |
|
edgesym = "--" |
if graphtype != 'graph': |
graphtype = 'digraph' |
edgesym = "->" |
|
# generate the header |
dot_desc = ( graphtype + |
" g {\n" + |
" ordering=out;\n" + |
" node [shape=circle];\n" + |
" edge [penwidth=3];\n" |
) |
|
# now generate vertex and edges information |
if len(V) == 0: |
dot_desc += "Empty [shape=ellipse];\n" |
else: |
for n in V: |
color = "white" |
if n in vertex_color: |
color = vertex_color[n] |
|
label = str(n) |
if n in vertex_label: |
label = vertex_label[n] |
|
dot_desc += ' {v} [label="{l}", style=filled, fillcolor="{c}"];\n'.format( |
v=str(n), l=label, c=color) |
|
for e in E: |
(x, y) = e |
color = "black" |
if e in edge_color: |
color = edge_color[e] |
label = "" |
if e in edge_label: |
label = ', label="{}"'.format(edge_label[e]) |
|
dot_desc += ' {vx} {esym} {vy} [color="{c}" {l}];\n'.format( |
esym=edgesym, vx=str(x), vy=str(y), c=color, l=label) |
|
|
# close off the description |
dot_desc += "}\n" |
|
return dot_desc |
|
def write_dot_desc(G, file_name, graphtype='graph', attributes={}): |
""" |
Given graph G, write the dot description of G |
into the given file name, which should have extension .dot |
as in sample-graph.dot |
|
""" |
# Implementation note: |
# instead of f = open(file_name, 'w') inside a try block, use |
# the safe open that closes file on an exception, from |
# http://docs.python.org/3.2/tutorial/inputoutput.html |
|
with open(file_name, 'w') as f: |
f.write( gen_dot_desc(G, graphtype, attributes) ) |
|
def pause(time=1,prompt="next?"): |
""" |
if time > 0, then pause for time sec |
if time=0, then print the prompt and wait for a new line of |
input from the terminal before returning. |
""" |
if time > 0: |
time.sleep(time) |
else: |
x = input(prompt) |
|
|
|
if __name__ == "__main__": |
import doctest |
doctest.testmod() |
|
