dijkstra.h

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

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   dijkstra.h
//
//==========================================================================
// $Id: dijkstra.h,v 1.8 2003/02/25 09:18:19 chris Exp $

#ifndef GTL_DIJKSTRA_H
#define GTL_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 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};

    dijkstra();

    virtual ~dijkstra();

    void source(const node& n);

    void target(const node& n);

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

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

    node source() const;

    node target() const;

    bool store_preds() const;

    bool reached(const node& n) const;

    double distance(const node& n) const;

    node predecessor_node(const node& n) const;

    edge predecessor_edge(const node& n) const;

    shortest_path_node_iterator shortest_path_nodes_begin(const node& dest);

    shortest_path_node_iterator shortest_path_nodes_end(const node& dest);

    shortest_path_edge_iterator shortest_path_edges_begin(const node& dest);

    shortest_path_edge_iterator shortest_path_edges_end(const node& dest);

    virtual void reset();
private:
    node s;

    node t;

    bool weights_set;

    bool preds_set;

    edge_map<double> weight;

    node_map<edge> pred;

    node_map<int> mark;

    node_map<double> dist;

    node_map<list<node> > shortest_path_node_list;

    node_map<list<edge> > shortest_path_edge_list;

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

    void fill_node_list(const node& t);

    void fill_edge_list(const node& t);
};

__GTL_END_NAMESPACE

#endif // GTL_DIJKSTRA_H

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