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;
}
 
}