/* Copyright (c) 1997-2006
   Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
   http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de

   This program is free software; you can redistribute it and/or modify it
   under the terms of the GNU General Public License as published by the
   Free Software Foundation; either version 2, or (at your option) any
   later version: http://www.gnu.org/licenses/gpl.txt.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
*/

#ifndef _POLYMAKE_SHORTEST_PATH_DIJKSTRA_H
#define _POLYMAKE_SHORTEST_PATH_DIJKSTRA_H "$Project: polymake $$Id: shortest_path_dijkstra.h 7406 2006-08-02 17:26:57Z gawrilow $"

#include <shortest_path_common.h>
#include <Heap.h>

namespace polymake { namespace graph {

template <typename _Adapter, typename _HeapConstructor=void>
class shortest_path_dijkstra
   : public shortest_path< shortest_path_dijkstra<_Adapter,_HeapConstructor>, _Adapter > {
protected:
   typedef shortest_path<shortest_path_dijkstra> super;
   friend class shortest_path<shortest_path_dijkstra>;

public:
   typedef typename _Adapter::node_id node_id;
   typedef typename _Adapter::edge_id edge_id;
   typedef typename _Adapter::distance_type distance_type;
   typedef typename _Adapter::distance_comparator_type distance_comparator_type;

protected:
   typedef operations::composed12<operations::property_map<typename super::distance_map>, distance_comparator_type, void>
      node_comparator;
   typedef typename pm::if_else< pm::identical<_HeapConstructor,void>::value, pm::HeapConstructor, _HeapConstructor>::type
      heap_constructor;
   typedef typename heap_constructor::template defs<node_id, pm::list(pm::Comparator<node_comparator>, pm::Adapter<_Adapter>)>::type
      heap_type;

public:
   shortest_path_dijkstra(const typename _Adapter::basic_graph_type& G)
      : super(G),
	heap(super::data, node_comparator(super::dist, super::data.get_distance_comparator()))
   { }
   
   shortest_path_dijkstra(const _Adapter& G)
      : super(G),
	heap(super::data, node_comparator(super::dist, super::data.get_distance_comparator()))
   { }

protected:
   void init_sources(const node_id source)
   {
      super::init_sources(source);
      heap.push(source);
   }
   using super::init_sources;

   void init()
   {
      super::init();
      heap.clear();
   }

   template <typename Targets>
   node_id _do_find (const Targets& targets)
   {
      while (!heap.empty()) {
      	 node_id n=heap.pop();
	 if (this->contains(targets,n)) return n;

	 const distance_type d=this->dist[n];
	 typename pm::attrib<typename _Adapter::OutEdges>::plus_const_ref arcs=this->data.out_edges(n);
	 for (typename Entire<typename _Adapter::OutEdges>::const_iterator ai=entire(arcs); !ai.at_end(); ++ai) {
	    edge_id a=*ai;
	    node_id t=this->data.to_node(a);
            pm::heap_element_state state=heap.get_state(t);
            if (state==pm::heap_element_removed) continue;

	    const distance_type dnew=d + this->data.get_edge_weight(a);
	    if (state==pm::heap_element_unvisited  ||
		heap.get_comparator().outer(dnew, this->dist[t]) < 0) {
	       this->dist[t]=dnew;
	       this->arc2s[t]=a;
	       heap.push(t);
	    }
	 }
      }

      throw std::runtime_error("shortest_path_dijkstra: target unreachable from the source");
   }

   node_id do_find (const node_id target) { return _do_find(target); }

   template <typename Targets>
   node_id do_find (const Targets& targets) { return _do_find(this->targets_map); }

   heap_type heap;
};

} } // end namespace polymake::graph

#endif // _POLYMAKE_SHORTEST_PATH_DIJKSTRA_H

// Local Variables:
// mode:C++
// c-basic-offset:3
// End:
