ShortestPathModule.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_SHORTEST_PATH_MODULE_H
#define OGDF_SHORTEST_PATH_MODULE_H


#include <ogdf/basic/Graph.h>


namespace ogdf {


class OGDF_EXPORT ShortestPathModule
{
public:
    ShortestPathModule() { }
    virtual ~ShortestPathModule() {}

    // computes shortest paths
    // Precond.: 
    // returns true iff a feasible min-cost flow exists
    virtual bool call(
        const Graph &G,                   // directed graph
        const node s,                     // source node
        const EdgeArray<int> &length,     // length of an edge
        NodeArray<int> &d,                // contains shortest path distances after call
        NodeArray<edge> &pi
    ) = 0;



protected:
    //
    // static functions
    //

    // generates a shortest path problem instance with n nodes and m+n edges
    /*
    static void generateProblem(
        Graph &G,
        int n,
        int m,
        EdgeArray<int> &lowerBound,
        EdgeArray<int> &upperBound,
        EdgeArray<int> &cost,
        NodeArray<int> &supply);


    // checks if a given min-cost flow problem instance satisfies
    // the preconditions
    //    
    //    lowerBound[e] <= upperBound[e] for all edges e
    //    cost[e] >= 0 for all edges e
    //    sum over all supply[v] = 0
    static bool checkProblem(
        const Graph &G,
        const EdgeArray<int> &lowerBound,
        const EdgeArray<int> &upperBound,
        const EdgeArray<int> &cost,
        const NodeArray<int> &supply);



    // checks if a computed flow is a feasible solution to the given problem
    // instance, i.e., checks if
    //    lowerBound[e] <= flow[e] <= upperBound[e]
    //    sum flow[e], e is outgoing edge of v -
    //      sum flow[e], e is incoming edge of v = supply[v] for each v
    // returns true iff the solution is feasible and in value the value of
    //   the computed flow
    static bool checkComputedFlow(
        Graph &G,
        EdgeArray<int> &lowerBound,
        EdgeArray<int> &upperBound,
        EdgeArray<int> &cost,
        NodeArray<int> &supply,
        EdgeArray<int> &flow,
        int &value);

    static bool checkComputedFlow(
        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