bellman_ford.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file bellman_ford.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   bellman_ford.h
//
//==========================================================================
// $Id: bellman_ford.h,v 1.5 2003/03/24 15:58:54 raitner Exp $ 

#ifndef GTL_BELLMAN_FORD_H
#define GTL_BELLMAN_FORD_H

#include <GTL/GTL.h>
#include <GTL/algorithm.h>
#include <GTL/node_map.h>
#include <GTL/edge_map.h>

__GTL_BEGIN_NAMESPACE


class GTL_EXTERN bellman_ford : public algorithm 
{
public:

    bellman_ford();

    virtual ~bellman_ford();

    int check (graph& G);

    int run (graph& G);

    void reset ();

    void source (const node& n) {s = n;}    

    node source () const {return s;}

    void weights (const edge_map<double>& weight) {w = weight; vars_set = true; }
    
    void store_preds (bool set);

    bool store_preds () const {return preds != 0;}

    bool reached (const node& n) const {return !inf[n];}

    double distance (const node& n) const {return d[n];}

    edge predecessor_edge (const node& n) const
        {assert (preds); return (*preds)[n];}

    node predecessor_node (const node& n) const
        {edge e = predecessor_edge(n); return e == edge() ? node() : e.opposite(n); }

    bool negative_cycle() const
        {return cycle;}

private:

    
    void relax (const edge& e, bool dir);

    node s;

    edge_map<double> w;
    
    bool vars_set; 

    node_map<double> d; 

    node_map<bool> inf;

    node_map<edge>* preds;

    bool cycle; 
};

__GTL_END_NAMESPACE

#endif // GTL_BELLMAN_FORD_H