Skip to content

Instantly share code, notes, and snippets.

@felipecruz

felipecruz/ssp.py

Created Jun 4, 2014
Embed
What would you like to do?
import logging
import sys
from graph import *
from residual import *
from dijkstras import Dijkstra
first_from_set = lambda s: list(s)[0]
excess_criteria = lambda x: x.supply > 0
deficit_criteria = lambda x: x.supply < 0
wrt_reduced_cost = lambda x: x.reduced_cost
def SuccessiveShortestPath_Initialize(G):
G.add_vertex('SUPER', {supply: 0})
for g in G.vertexes:
if g.supply > 0 or g.supply < 0:
G.add_edge('SUPER', g.id, data={capacity: L*10, cost:L*2, flow:0})
G.add_edge(g.id, 'SUPER', data={capacity: L*10, cost:L*2, flow:0})
for edge, source, target in G.edges:
edge.reduced_cost = edge.cost
edge.flow = 0
source.p = 0
target.p = 0
source.e = source.supply
target.e = target.supply
if hasattr(edge, 'lower'):
source.supply += edge.lower
target.supply -= edge.lower
def remaining_capacity(x):
if x.is_reverse:
return x.capacity > 0
else:
return x.capacity - x.flow > 0
def SuccessiveShortestPath(G):
SuccessiveShortestPath_Initialize(G)
E = set(G.get_vertexes(excess_criteria))
D = set(G.get_vertexes(deficit_criteria))
flow = 0
Gr = residual_graph(G)
i = 0
while E:
l = first_from_set(D)
k = first_from_set(E)
total_remaining = 0
for el in list(E):
total_remaining += el.e
distances, predecessors, visited = Dijkstra(Gr,
s=k, t=l, constraint_func=remaining_capacity,
wrt_func=wrt_reduced_cost)
# backtrack shortest path and get the bottleneck
edge, p = predecessors[l.id]
P = []
while p:
P.append((edge.capacity, edge, p))
if not p.id in predecessors:
break
edge, p = predecessors[p.id]
if not p:
break
path_bottleneck = min(P)[0]
# pi update
for v in Gr.vertexes:
distance = distances[v.id]
new_p = v.p - distance
v.p = new_p
#update reduced costs
for edge, source, target in Gr.edges:
if not edge.is_reverse:
edge.reduced_cost = edge.cost - source.p + target.p
edge.reverse.reduced_cost = edge.reduced_cost
# get min from e and bottleneck
gama = min(k.e, -l.e, path_bottleneck)
flow += gama
# send flow along P
for p in P:
edge = p[1]
#import ipdb; ipdb.set_trace()
edge.send_flow(gama)
# update excess and defict values
k.e -= gama
l.e += gama
# if it's balanced, remove from it's set
if k.e == 0:
E = E - set([k])
if l.e == 0:
D = D - set([l])
i+=1
min_cost_flow = 0
for e, s, t in Gr.edges:
edge_cost = 0
if e.is_reverse:
edge_cost = e.capacity * e.cost
min_cost_flow += edge_cost
print("Min {}".format(min_cost_flow))
return Gr, min_cost_flow
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment