source: lemon-0.x/src/work/athos/dijkstra_at.h @ 660:edb42cb9d352

/*
Egy pontból összes többibe vezetõ legrövidebb utak irányított gráfban

Preconditions:
A gráf típus tud:
- pontból kimenõ éleket sorban visszaadni
A T számtípus, ami tud összehasonlítást, összedást
A bemenetre:
weight nemnegatív

*/
#ifndef DIJKSTRA_AT_H
#define DIJKSTRA_AT_H



//#include <algorithm>
//#include <deque>
//#include <vector>
//#include "pf_hiba.hh"
//#include <marci_list_graph.hh>
//#include <marci_graph_traits.hh>


using namespace std;

namespace hugo {

  template <typename graph_type, typename T>
  class dijkstra_at {

    //Hasznos typedef-ek
    typedef typename graph_type::NodeIt NodeIt;
    typedef typename graph_type::EdgeIt EdgeIt;
    typedef typename graph_type::EachNodeIt EachNodeIt;
    typedef typename graph_type::EachEdgeIt EachEdgeIt;
    typedef typename graph_type::OutEdgeIt OutEdgeIt;
    typedef typename graph_type::InEdgeIt InEdgeIt;
    typedef typename graph_type::SymEdgeIt SymEdgeIt;



    //---------------------------------------------
    //Parameters of the algorithm
    //---------------------------------------------

    //---------------------------------------------
    //Parameters of the algorithm
    //---------------------------------------------
 
  private:
    //input
    graph_type& G;
    NodeIt s;
    typename graph_type::EdgeMap<T> &weight;
    //typename graph_type::EdgeMap<T>  &capacity;
    //output
    //typename graph_type::EdgeMap<T>  
    //    typename graph_type::EdgeMap<T> preflow;
      
    //auxiliary variables for computation
    deque<NodeIt> next_to_reach;
    
    
    typename graph_type::NodeMap<bool> reached;

    //Variables holding output
    //Predessors in the shortest paths arborescence
    typename graph_type::NodeMap<NodeIt> pred;


  public:
  

    dijkstra_at(
                      graph_type& _G, 
                      NodeIt _s, 
                      typename graph_type::EdgeMap<T> & _weight)
      : G(_G), s(_s),
      weight(_weight),
      next_to_reach(),
      reached(_G),
      pred(G)
        
    { 
    }
      /*By Misi.*/
      struct Node_dist_comp
      {
        NodeMap<graph_type, T> &d;
        Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 
        
        bool operator()(const NodeIt& u, const NodeIt& v) const 
        { return d.get(u) < d.get(v); }
      };


      
      void run() {
        
        NodeMap<graph_type, bool> scanned(G, false);
        std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 
          heap(( Node_dist_comp(distance) ));
        
        heap.push(s);
        reached.set(s, true);
        
      }

      
    };
  




 
  };  //class dijkstra_at  


}//namespace hugo

#endif //DIJKSTRA_AT