MinCostFlowModule.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_MIN_COST_FLOW_MODULE_H
#define OGDF_MIN_COST_FLOW_MODULE_H


#include <ogdf/basic/Graph.h>


namespace ogdf {


class OGDF_EXPORT 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<int> &cost,       // cost of an edge
        const NodeArray<int> &supply,     // supply (if neg. demand) of a node
        EdgeArray<int> &flow,             // computed flow
        NodeArray<int> &dual            // computed dual variables
        ) = 0;


    //
    // static functions
    //

    static void generateProblem(
        Graph &G,
        int n,
        int m,
        EdgeArray<int> &lowerBound,
        EdgeArray<int> &upperBound,
        EdgeArray<int> &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,
        EdgeArray<int> &lowerBound,
        EdgeArray<int> &upperBound,
        EdgeArray<int> &cost,
        NodeArray<int> &supply,
        EdgeArray<int> &flow,
        int &value);

    static bool checkComputedFlow(
        const Graph &G,
        EdgeArray<int> &lowerBound,
        EdgeArray<int> &upperBound,
        EdgeArray<int> &cost,
        NodeArray<int> &supply,
        EdgeArray<int> &flow)
    {
        int value;
        return checkComputedFlow(
            G,lowerBound,upperBound,cost,supply,flow,value);
    }
};


} // end namespace ogdf


#endif