Commits

David Jones  committed 6c8987b

added code for push flow, made a few changes to support it in the other code.

  • Participants
  • Parent commits aa60653

Comments (0)

Files changed (3)

File graph_generator.py

 from pprint import pprint
 
 def make_euclidean_with_radius(N, radius):
-
     points = [(random.random(), random.random())
               for k in xrange(N)]
 
-
     def calc_distance(a,b):
         dx = a[0] - b[0]
         dy = a[1] - b[1]
 class Edge(object):
     def __init__(self, v, w):
         self.v, self.w = v, w
+    def __repr__(self):
+        return "%d-%d" % (self.v, self.w)
     
 
 class Graph(object):
         self.vertices = range(number_vertices)
         self.edges = [list() for v in self.vertices]
 
-    def add_edge(self, edge):
-        self.edges[edge.v].append(edge.w)
+    def add_edge(self,edge):
+        self.edges[edge.v].append(edge)
 
+    def add_edge_to_vertex(self, edge, vertex):
+        self.edges[vertex].append(edge)
+        
 
     def __repr__(self):
         output = []
     """Return the reverse of a directed graph"""
     result = Graph(graph.number_vertices)
     for v in graph.vertices:
-        for w in graph.get_edge_iterator(v):
-            result.add_edge(Edge(w, v))
+        for edge in graph.get_edge_iterator(v):
+            result.add_edge(Edge(edge.w, v))
     return result
 
 
         print depth, "dfs", w
         self.depth += " "
         for t in graph.get_edge_iterator(w):
-            if (self.id[t] == -1):
-                self.dfs(graph, t)
+            if (self.id[t.w] == -1):
+                self.dfs(graph, t.w)
         self.postorder[self.count] = w
         self.count += 1
         self.depth = depth

File push_flow.py

+""" Push-flow maxflow algorithm from Algorithms in C++, part 5"""
+
+import graphs
+
+
+class Edge(object):
+    def __init__(self, from_, to, capacity):
+        self.u = from_
+        self.v = to
+        self.capacity = capacity
+        self.flow = 0
+    def __repr__(self):
+        return "<edge %s-%s  cap: %d  flow %d>" %( self.u, self.v, self.capacity,
+                                                   self.flow)
+    def from_(self, w):
+        return self.u == w
+    
+    def other(self, w):
+        if self.from_(w):
+            return self.v
+        return self.u
+
+    def capacity_to(self, w):
+        if self.from_(w):
+            return self.flow
+        else:
+            return self.capacity - self.flow
+
+    def add_flow_to(self, v, d):
+        if self.from_(v):
+            self.flow -= d
+        else:
+            self.flow += d
+
+def pushflow(graph, s, t):
+    # Find the max capacity on a vertex
+    M = 0
+    for v in graph.vertices:
+        for e in graph.get_edge_iterator(v):
+            M = max(M, e.capacity)
+
+    V = graph.number_vertices
+
+    # init heights and wts
+    h,wt = {}, {}
+    for v in xrange(V):
+        h[v] = 0
+        wt[v] = 0
+    h[s] = V
+    
+    wt[s] = M * V + 1
+    wt[t] = - wt[s]
+    queue = [s]
+
+
+    while queue:
+        v = queue[0]
+        queue = queue[1:]
+        for e in graph.get_edge_iterator(v):
+            w = e.other(v)
+            capacity = e.capacity_to(w)
+            P = min(capacity, wt[v])
+            if (P > 0 and (v == s or h[v] == h[w] + 1)):
+                e.add_flow_to(w, P)
+                wt[v] -= P
+                wt[w] += P
+                if (w != s) and (w != t):
+                    if w not in queue:
+                        queue.append(w)
+        if (v != s and v != t and wt[v] > 0):
+            h[v] += 1
+            if v not in queue:
+                queue.append(v)
+
+
+def make_graph(edge_data):
+    """Load a graph from a list of [src, dst, capacity] triples"""
+    
+    edges = {}
+    vertices = set()
+    for f,t,c in edge_data:
+        vertices.add(f)
+        vertices.add(t)
+        edge = Edge(f,t,c)
+        if f not in edges:
+            edges[f] = []
+        if t not in edges:
+            edges[t] = []
+        edges[f].append(edge)
+        edges[t].append(edge)
+
+    V = max(vertices) + 1
+    pprint (edges)
+    pprint( vertices)
+    
+    graph = graphs.Graph(V)
+    for v in xrange(V):
+        if v in edges:
+            for e in edges[v]:
+                print v, e
+                graph.add_edge_to_vertex(e, v)
+    return graph
+
+def check_flow(graph, source, sink):
+    source_flow = 0
+    sink_flow = 0
+
+    for v in graph.vertices:
+        s = 0
+        for edge in graph.get_edge_iterator(v):
+            if edge.from_(v):
+                s += edge.flow
+            else:
+                s -= edge.flow
+        if v == source:
+            source_flow = s
+        elif v == sink:
+            sink_flow = s
+        elif s != 0:
+            print "bad flow", s, "at vertex", v
+    if source_flow != -sink_flow:
+        print "source and sink flow did not match:", source_flow, sink_flow
+        
+
+
+if __name__ == "__main__":
+    from pprint import pprint    
+    graph = make_graph([[0, 1, 12], [1, 2, 10], [1, 3, 14],
+                        [2, 4,3], [3, 4, 20]])
+
+
+    print "foo"
+    print(graph)
+
+    pushflow(graph, 0, 4)
+
+    print "done"
+    check_flow(graph, 0, 4)
+
+    pprint(graph)