MinCostFlowModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
 
#include <ogdf/basic/graph_generators.h>
#include <ogdf/basic/simple_graph_alg.h>
 
 
namespace ogdf {
 
 
template<typename TCost>
class MinCostFlowModule
{
public:
    MinCostFlowModule() { }
 
    // destruction
    virtual ~MinCostFlowModule() { }
 
    virtual bool call(
        const Graph &G,                   // directed graph
        const EdgeArray<int> &lowerBound, // lower bound for flow
        const EdgeArray<int> &upperBound, // upper bound for flow
        const EdgeArray<TCost> &cost,     // cost of an edge
        const NodeArray<int> &supply,     // supply (if neg. demand) of a node
        EdgeArray<int> &flow)             // computed flow
    {
        NodeArray<TCost> dual(G);
        return call(G, lowerBound, upperBound, cost, supply, flow, dual);
    }
 
    virtual bool call(
        const Graph &G,                   // directed graph
        const EdgeArray<int> &lowerBound, // lower bound for flow
        const EdgeArray<int> &upperBound, // upper bound for flow
        const EdgeArray<TCost> &cost,     // cost of an edge
        const NodeArray<int> &supply,     // supply (if neg. demand) of a node
        EdgeArray<int> &flow,             // computed flow
        NodeArray<TCost> &dual            // computed dual variables
        ) = 0;
 
 
    //
    // static functions
    //
 
    static void generateProblem(
        Graph &G,
        int n,
        int m,
        EdgeArray<int> &lowerBound,
        EdgeArray<int> &upperBound,
        EdgeArray<TCost> &cost,
        NodeArray<int> &supply);
 
 
    static bool checkProblem(
        const Graph &G,
        const EdgeArray<int> &lowerBound,
        const EdgeArray<int> &upperBound,
        const NodeArray<int> &supply);
 
 
 
    static bool checkComputedFlow(
        const Graph &G,
        const EdgeArray<int> &lowerBound,
        const EdgeArray<int> &upperBound,
        const EdgeArray<TCost> &cost,
        const NodeArray<int> &supply,
        const EdgeArray<int> &flow,
        TCost &value);
 
    static bool checkComputedFlow(
        const Graph &G,
        const EdgeArray<int> &lowerBound,
        const EdgeArray<int> &upperBound,
        const EdgeArray<TCost> &cost,
        const NodeArray<int> &supply,
        const EdgeArray<int> &flow)
    {
        TCost value;
        return checkComputedFlow(
            G,lowerBound,upperBound,cost,supply,flow,value);
    }
};
 
// Implementation
 
template<typename TCost>
void MinCostFlowModule<TCost>::generateProblem(
    Graph &G,
    int n,
    int m,
    EdgeArray<int> &lowerBound,
    EdgeArray<int> &upperBound,
    EdgeArray<TCost> &cost,
    NodeArray<int> &supply)
{
    ogdf::randomGraph(G,n,m);
 
    node s = G.firstNode();
    node t = G.lastNode();
 
    for(node v : G.nodes) {
        G.newEdge(s,v);
        G.newEdge(v,t);
    }
 
    for(edge e : G.edges) {
        lowerBound[e] = 0;
        upperBound[e] = (e->source() != s) ? ogdf::randomNumber(1,10) : ogdf::randomNumber(2,13);
        cost[e] = static_cast<TCost>(ogdf::randomNumber(0,100));
    }
 
 
    for(node v = G.firstNode(), vl = G.lastNode(); true; v = v->succ(), vl = vl->pred()) {
        if (v == vl) {
            supply[v] = 0;
            break;
        }
 
        supply[v] = -(supply[vl] = ogdf::randomNumber(-1,1));
 
        if (vl == v->succ())
            break;
    }
 
}
 
template<typename TCost>
bool MinCostFlowModule<TCost>::checkProblem(
    const Graph &G,
    const EdgeArray<int> &lowerBound,
    const EdgeArray<int> &upperBound,
    const NodeArray<int> &supply)
{
    if(!isConnected(G))
        return false;
 
    for(edge e : G.edges) {
        if (lowerBound[e] > upperBound[e])
            return false;
    }
 
    int sum = 0;
    for(node v : G.nodes) {
        sum += supply[v];
    }
 
    return sum == 0;
}
 
 
template<typename TCost>
bool MinCostFlowModule<TCost>::checkComputedFlow(
    const Graph &G,
    const EdgeArray<int> &lowerBound,
    const EdgeArray<int> &upperBound,
    const EdgeArray<TCost> &cost,
    const NodeArray<int> &supply,
    const EdgeArray<int> &flow,
    TCost &value)
{
    value = 0;
 
    for (edge e : G.edges) {
        if (flow[e] < lowerBound[e] || upperBound[e] < flow[e]) {
            return false;
        }
 
        value += flow[e] * cost[e];
    }
 
    for (node v : G.nodes) {
        int sum = 0;
 
        for(adjEntry adj : v->adjEntries) {
            edge e = adj->theEdge();
 
            if (e->isSelfLoop()) {
                continue;
            }
 
            if (e->source() == v) {
                sum += flow[e];
            } else {
                sum -= flow[e];
            }
        }
        if (sum != supply[v]) {
            return false;
        }
    }
 
    return true;
}
 
}