/* Copyright (c) 1997-2004
   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_COMMON_H
#define _POLYMAKE_SHORTEST_PATH_COMMON_H "$Project: polymake $$Id: shortest_path_common.h 7315 2006-04-02 21:37:53Z gawrilow $"

namespace polymake { namespace graph {

template <typename Algo, typename _Adapter=typename Algo::adapter>
class shortest_path {
public:
   typedef _Adapter adapter;
protected:
   adapter data;
public:
   typedef typename adapter::node_id node_id;
   typedef typename adapter::edge_id edge_id;
   typedef typename adapter::distance_type distance_type;

   const adapter& get_data() const { return data; }

protected:
   typedef typename adapter::template property_map<node_id, distance_type>::type distance_map;
   typedef typename adapter::template property_map<node_id, bool>::type terminal_map;

   shortest_path(const typename adapter::basic_graph_type& G)
      : data(G) { }

   shortest_path(const adapter& G)
      : data(G) { }

   bool contains(const node_id target, const node_id n) { return n==target; }
   bool contains(const terminal_map& targets, const node_id n) { return targets(n); }

   Algo& top() { return static_cast<Algo&>(*this); }
   const Algo& top() const { return static_cast<const Algo&>(*this); }

   void init()
   {
      data.init(dist);
      data.init(arc2s);
   }

   void init_sources(const node_id source)
   {
      dist[source]=distance_type(0);
      arc2s[source]=data.void_edge_id();
   }

   template <typename Sources>
   void init_sources(const Sources& sources)
   {
      for (typename Entire<Sources>::const_iterator s=entire(sources);  !s.at_end();  ++s)
	 top().init_sources(*s);
   }

   template <typename Targets>
   void init_targets(const Targets& targets)
   {
      data.clear(targets_map);
      for (typename Entire<Targets>::const_iterator t=entire(targets);  !t.at_end();  ++t)
	 targets_map(*t)=true;
   }

   template <typename OutIterator>
   void reconstruct_path(OutIterator& path_consumer, const node_id target, type2type<node_id>)
   {
      node_id n=target;
      while (true) {
	 *path_consumer++ =n;
	 edge_id a=arc2s[n];
	 if (a == data.void_edge_id()) return;
	 n=data.from_node(a);
      }
   }

   template <typename OutIterator>
   void reconstruct_path(OutIterator& path_consumer, const node_id target, type2type<edge_id>)
   {
      node_id n=target;
      while (true) {
	 edge_id a=arc2s[n];
	 if (a == data.void_edge_id()) return;
	 *path_consumer++ =a;
	 n=data.from_node(a);
      }
   }

   template <typename OutIterator>
   void reconstruct_path(OutIterator& path_consumer, const node_id target)
   {
      reconstruct_path(path_consumer, target, type2type< typename pm::iterator_traits<OutIterator>::value_type >());
   }

   template <typename X>
   void reconstruct_path(black_hole<X>&, const X&, const node_id) { }

public:
   // one source - one target
   template <typename OutIterator>
   distance_type find (const node_id source, const node_id target, OutIterator path_consumer)
   {
      top().init();
      top().init_sources(source);
      node_id n=top().do_find(target);
      reconstruct_path(path_consumer, n);
      return dist[n];
   }

   // one source - many targets
   template <typename Targets, typename OutIterator>
   distance_type find (const node_id source, const Targets& targets, OutIterator path_consumer)
   {
      top().init();
      top().init_sources(source);
      top().init_targets(targets);
      node_id n=top().do_find(targets);
      reconstruct_path(path_consumer, n);
      return dist[n];
   }

   // many sources - one target
   template <typename Sources, typename OutIterator>
   distance_type find (const Sources& sources, const node_id target, OutIterator path_consumer)
   {
      top().init();
      top().init_sources(sources);
      node_id n=top().do_find(target);
      reconstruct_path(path_consumer, n);
      return dist[n];
   }

   // many sources - many targets
   template <typename Sources, typename Targets, typename OutIterator>
   distance_type find (const Sources& sources, const Targets& targets, OutIterator path_consumer)
   {
      top().init();
      top().init_sources(sources);
      top().init_targets(targets);
      node_id n=top().do_find(targets);
      reconstruct_path(path_consumer, n);
      return dist[n];
   }

   template <typename Sources, typename Targets>
   distance_type find(const Sources& sources, const Targets& targets)
   {
      return find(sources, targets, black_hole<node_id>());
   }

protected:
   distance_map dist;
   typename adapter::template property_map<node_id,edge_id>::type arc2s;
   terminal_map targets_map;
};

} } // end namespace polymake::graph

#endif // _POLYMAKE_SHORTEST_PATH_COMMON_H

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