ssp.py

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