Added Bellman, FW and Johnsons

prakhar1989 · Jan 14, 2013 · 94666ff · 94666ff
1 parent d0568f6
commit 94666ff
Show file tree

Hide file tree

Showing 10 changed files with 446 additions and 101 deletions.
diff --git a/README.md b/README.md
@@ -1,7 +1,7 @@
 Algos in Python
 ======
 
-Implementation for the algorithms and datastructures taught in [CS161](http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms), in Python
+Implementations of a few algorithms and datastructures for fun and profit!
 
 Completed
 ---
@@ -20,6 +20,9 @@ Completed
     - Prim's Minimum Cost Spanning Tree - O(mlogn)
     - Kruskal's Minimum Spanning Tree - O(mlogn)
     - Max k Clustering
+    - Bellman Ford
+    - Floyd Warshall
+    - Johnson's Algorithm
 - Heap datastructure
 	- Max heaps
 	- Min heaps (priority queue)

diff --git a/dp/bellman_ford.py b/dp/bellman_ford.py
@@ -0,0 +1,44 @@
+""" The bellman ford algorithm for calculating single source shortest
+paths - CLRS style """
+graph = { 
+    's' : {'t':6, 'y':7},
+    't' : {'x':5, 'z':-4, 'y':8 },
+    'y' : {'z':9, 'x':-3},
+    'z' : {'x':7, 's': 2},
+    'x' : {'t':-2}
+}
+
+INF = float('inf')
+
+dist = {}
+predecessor = {}
+
+def initialize_single_source(graph, s):
+    for v in graph:
+        dist[v] = INF
+        predecessor[v] = None
+    dist[s] = 0
+
+def relax(graph, u, v):
+    if dist[v] > dist[u] + graph[u][v]:
+        dist[v] = dist[u] + graph[u][v]
+        predecessor[v] = u
+
+def bellman_ford(graph, s):
+    initialize_single_source(graph, s)
+    edges = [(u, v) for u in graph for v in graph[u].keys()]
+    number_vertices = len(graph)
+    for i in range(number_vertices-1):
+        for (u, v) in edges:
+            relax(graph, u, v)
+    for (u, v) in edges:
+        if dist[v] > dist[u] + graph[u][v]:
+            return False # there exists a negative cycle
+    return True
+
+def get_distances(graph, s):
+    if bellman_ford(graph, s):
+        return dist
+    return "Graph contains a negative cycle"
+
+print get_distances(graph, 's')
diff --git a/dp/dijkstra.py b/dp/dijkstra.py
@@ -0,0 +1,43 @@
+from heapq import heappush, heappop
+# graph = { 
+#     's' : {'t':6, 'y':7},
+#     't' : {'x':5, 'z':4, 'y':8 },
+#     'y' : {'z':9, 'x':3},
+#     'z' : {'x':7, 's': 2},
+#     'x' : {'t':2}
+# }
+
+def read_graph(file):
+    graph = dict()
+    with open(file) as f:
+        for l in f:
+            (u, v, w) = l.split()
+            if int(u) not in graph:
+                graph[int(u)] = dict()
+            graph[int(u)][int(v)] = int(w)
+    return graph
+
+inf = float('inf')
+def dijkstra(graph, s):
+    n = len(graph.keys())
+    dist = dict()
+    Q = list()
+
+    for v in graph:
+        dist[v] = inf
+    dist[s] = 0
+
+    heappush(Q, (dist[s], s))
+
+    while Q:
+        d, u = heappop(Q)
+        if d < dist[u]:
+            dist[u] = d
+        for v in graph[u]:
+            if dist[v] > dist[u] + graph[u][v]:
+                dist[v] = dist[u] + graph[u][v]
+                heappush(Q, (dist[v], v))
+    return dist
+
+graph = read_graph("graph.txt")
+print dijkstra(graph, 1)
diff --git a/dp/floyd.py b/dp/floyd.py
@@ -0,0 +1,58 @@
+""" Floyd warshall in numpy and standard implementation """
+from numpy import * 
+inf = float('inf')
+graph = [
+    [0, 3, 8, inf, -4], 
+    [inf, 0, inf, 1, 7], 
+    [inf, 4, 0, inf, inf], 
+    [2, inf, -5, 0, inf], 
+    [inf, inf, inf, 6, 0]
+]
+
+def make_matrix(file, n):
+    graph = [[inf for i in range(n)] for i in range(n)]
+    with open(file) as f:
+        for l in f:
+           (i, j, w) = l.split() 
+           graph[int(i)-1][int(j)-1] = int(w)
+    return graph
+
+def floyd_warshall(graph):
+    n = len(graph)
+    D = graph
+    for k in range(n):
+        for i in range(n):
+            for j in range(n):
+                if i==j:
+                    D[i][j] = 0
+                else:
+                    D[i][j] = min(D[i][j], D[i][k] + D[k][j])
+    return D
+
+def fastfloyd(D):
+	_,n = D.shape
+	for k in xrange(n):
+		i2k = reshape(D[k,:],(1,n))
+		k2j = reshape(D[:,k],(n,1))
+		D = minimum(D,i2k+k2j)
+	return D.min() if not any(D.diagonal() < 0) else None
+
+def get_min_dist(D):
+    if negative_cost_cycle(D):
+        return "Negative cost cycle"
+    return min(i for d in D for i in d)
+
+def negative_cost_cycle(D):
+    n = len(D)
+    for i in range(n):
+        if D[i][i] < 0:
+            return True
+    return False
+
+# print get_min_dist(floyd_warshall(graph))
+n = 1000
+gr = make_matrix("g1.txt", n)
+#D = floyd_warshall(gr)
+print fastfloyd(array(gr))
+# print get_min_dist(D)
+# print D
diff --git a/dp/johnsons_apsp.py b/dp/johnsons_apsp.py
@@ -0,0 +1,114 @@
+from heapq import heappush, heappop
+from datetime import datetime
+from copy import deepcopy
+graph = { 
+    'a' : {'b':-2},
+    'b' : {'c':-1},
+    'c' : {'x':2, 'a':4, 'y':-3},
+    'z' : {'x':1, 'y':-4},
+    'x' : {},
+    'y' : {},
+}
+
+inf = float('inf')
+dist = {}
+
+def read_graph(file,n):
+    graph = dict()
+    with open(file) as f:
+        for l in f:
+            (u, v, w) = l.split()
+            if int(u) not in graph:
+                graph[int(u)] = dict()
+            graph[int(u)][int(v)] = int(w)
+    for i in range(n):
+        if i not in graph:
+            graph[i] = dict()
+    return graph
+
+def dijkstra(graph, s):
+    n = len(graph.keys())
+    dist = dict()
+    Q = list()
+
+    for v in graph:
+        dist[v] = inf
+    dist[s] = 0
+
+    heappush(Q, (dist[s], s))
+
+    while Q:
+        d, u = heappop(Q)
+        if d < dist[u]:
+            dist[u] = d
+        for v in graph[u]:
+            if dist[v] > dist[u] + graph[u][v]:
+                dist[v] = dist[u] + graph[u][v]
+                heappush(Q, (dist[v], v))
+    return dist
+
+def initialize_single_source(graph, s):
+    for v in graph:
+        dist[v] = inf
+    dist[s] = 0
+
+def relax(graph, u, v):
+    if dist[v] > dist[u] + graph[u][v]:
+        dist[v] = dist[u] + graph[u][v]
+
+def bellman_ford(graph, s):
+    initialize_single_source(graph, s)
+    edges = [(u, v) for u in graph for v in graph[u].keys()]
+    number_vertices = len(graph)
+    for i in range(number_vertices-1):
+        for (u, v) in edges:
+            relax(graph, u, v)
+    for (u, v) in edges:
+        if dist[v] > dist[u] + graph[u][v]:
+            return False # there exists a negative cycle
+    return True
+
+def add_extra_node(graph):
+    graph[0] = dict()
+    for v in graph.keys():
+        if v != 0:
+            graph[0][v] = 0
+
+def reweighting(graph_new):
+    add_extra_node(graph_new)
+    if not bellman_ford(graph_new, 0):
+        # graph contains negative cycles
+        return False
+    for u in graph_new:
+        for v in graph_new[u]:
+            if u != 0:
+                graph_new[u][v] += dist[u] - dist[v]
+    del graph_new[0]
+    return graph_new
+
+def johnsons(graph_new):
+    graph = reweighting(graph_new)
+    if not graph:
+        return False
+    final_distances = {}
+    for u in graph:
+        final_distances[u] = dijkstra(graph, u)
+
+    for u in final_distances:
+        for v in final_distances[u]:
+            final_distances[u][v] += dist[v] - dist[u]
+    return final_distances
+
+def compute_min(final_distances):
+    return min(final_distances[u][v] for u in final_distances for v in final_distances[u])
+
+if __name__ == "__main__":
+    # graph = read_graph("graph.txt", 1000)
+    graph_new = deepcopy(graph)
+    t1 = datetime.utcnow()
+    final_distances =  johnsons(graph_new)
+    if not final_distances:
+        print "Negative cycle"
+    else:
+        print compute_min(final_distances)
+    print datetime.utcnow() - t1
diff --git a/dp/kpdata2.txt b/dp/kpdata2.txt