bid_dijkstra.h

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

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

#ifndef GTL_BID_DIJKSTRA_H
#define GTL_BID_DIJKSTRA_H

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

__GTL_BEGIN_NAMESPACE

class GTL_EXTERN bid_dijkstra : public algorithm
{
public:
    typedef list<node>::const_iterator shortest_path_node_iterator;

    typedef list<edge>::const_iterator shortest_path_edge_iterator;

    enum node_color {white, grey, black};

    bid_dijkstra();

    virtual ~bid_dijkstra();

    void source_target(const node& s, const node& t);

    void weights(const edge_map<double>& weight);
    
    void store_path(bool set);

    virtual int check(graph& G);
            
    int run(graph& G);

    node source() const;

    node target() const;

    bool store_path() const;

    bool reached() const;

    double distance() const;

    shortest_path_node_iterator shortest_path_nodes_begin();

    shortest_path_node_iterator shortest_path_nodes_end();

    shortest_path_edge_iterator shortest_path_edges_begin();

    shortest_path_edge_iterator shortest_path_edges_end();

    virtual void reset();
private:
    node s;

    node t;

    bool weights_set;

    bool path_set;

    edge_map<double> weight;

    double dist;

    bool reached_t;

    node_map<edge> pred;

    node_map<edge> succ;

    node_map<int> source_mark;

    node_map<int> target_mark;

    node_map<double> source_dist;

    node_map<double> target_dist;

    list<node> shortest_path_node_list;

    list<edge> shortest_path_edge_list;

    void reset_algorithm();
    
    void init(graph& G);

    void fill_node_edge_lists(const node& n);
};

__GTL_END_NAMESPACE

#endif // GTL_BID_DIJKSTRA_H

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------