RhodeCode

      void erase(const Arc&) {}

      template <typename _Digraph>

      struct Constraints {

	void constraints() {

          checkConcept<Base, _Digraph>();

	  typename _Digraph::Node node;

	  digraph.erase(node);

	  typename _Digraph::Arc arc;

	  digraph.erase(arc);

	}

	_Digraph& digraph;

      };

    };

    /// \brief An empty erasable base undirected graph class.

    ///  

    /// This class provides beside the core undirected graph features

    /// core erase functions for the undirceted graph structure. The

    /// main difference between the base and this interface is that

    /// the graph alterations should handled already on this level.

    template <typename _Base = BaseGraphComponent>

    class ErasableGraphComponent : public _Base {

    public:

      typedef _Base Base;

      typedef typename Base::Node Node;

      typedef typename Base::Edge Edge;

      /// \brief Erase a node from the graph.

      ///

      /// Erase a node from the graph. This function should erase

      /// arcs connecting to the node.

      void erase(const Node&) {}    

      /// \brief Erase an arc from the graph.

      ///

      /// Erase an arc from the graph.

      ///

      void erase(const Edge&) {}

      template <typename _Graph>

      struct Constraints {

	void constraints() {

          checkConcept<Base, _Graph>();

	  typename _Graph::Node node;

	  graph.erase(node);

	}

	_Graph& graph;

      };

    };

    /// \brief An empty clearable base digraph class.

    ///

    /// This class provides beside the core digraph features core clear

    /// functions for the digraph structure. The main difference between

    /// the base and this interface is that the digraph alterations

    /// should handled already on this level.

    template <typename _Base = BaseDigraphComponent>

    class ClearableDigraphComponent : public _Base {

    public:

      typedef _Base Base;

      /// \brief Erase all nodes and arcs from the digraph.

      ///

      /// Erase all nodes and arcs from the digraph.

      ///

      void clear() {}    

      template <typename _Digraph>

      struct Constraints {

	void constraints() {

          checkConcept<Base, _Digraph>();

	  digraph.clear();

	}

	_Digraph digraph;

      };

    };

    /// \brief An empty clearable base undirected graph class.

    ///

    /// This class provides beside the core undirected graph features

    /// core clear functions for the undirected graph structure. The

    /// main difference between the base and this interface is that

    /// the graph alterations should handled already on this level.

    template <typename _Base = BaseGraphComponent>

    class ClearableGraphComponent : public ClearableDigraphComponent<_Base> {

    public:

      typedef _Base Base;

      template <typename _Graph>

/* -*- C++ -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_DIJKSTRA_H

#define LEMON_DIJKSTRA_H

///\ingroup shortest_path

///\file

///\brief Dijkstra algorithm.

#include <lemon/bin_heap.h>

#include <lemon/bits/path_dump.h>

#include <lemon/bits/invalid.h>

#include <lemon/error.h>

#include <lemon/maps.h>

namespace lemon {

  /// \brief Default OperationTraits for the Dijkstra algorithm class.

  ///  

  /// It defines all computational operations and constants which are

  /// used in the Dijkstra algorithm.

  template <typename Value>

  struct DijkstraDefaultOperationTraits {

    /// \brief Gives back the zero value of the type.

    static Value zero() {

      return static_cast<Value>(0);

    }

    /// \brief Gives back the sum of the given two elements.

    static Value plus(const Value& left, const Value& right) {

      return left + right;

    }

    /// \brief Gives back true only if the first value less than the second.

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  /// \brief Widest path OperationTraits for the Dijkstra algorithm class.

  ///  

  /// It defines all computational operations and constants which are

  /// used in the Dijkstra algorithm for widest path computation.

  template <typename Value>

  struct DijkstraWidestPathOperationTraits {

    /// \brief Gives back the maximum value of the type.

    static Value zero() {

      return std::numeric_limits<Value>::max();

    }

    /// \brief Gives back the minimum of the given two elements.

    static Value plus(const Value& left, const Value& right) {

      return std::min(left, right);

    }

    /// \brief Gives back true only if the first value less than the second.

    static bool less(const Value& left, const Value& right) {

      return left < right;

    }

  };

  ///Default traits class of Dijkstra class.

  ///Default traits class of Dijkstra class.

  ///\tparam GR Digraph type.

  ///\tparam LM Type of length map.

  template<class GR, class LM>

  template <typename _Graph>

  class ConArcIt : public _Graph::Arc {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Arc Parent;

    typedef typename Graph::Arc Arc;

    typedef typename Graph::Node Node;

    /// \brief Constructor.

    ///

    /// Construct a new ConArcIt iterating on the arcs which

    /// connects the \c u and \c v node.

    ConArcIt(const Graph& g, Node u, Node v) : _graph(g) {

      Parent::operator=(findArc(_graph, u, v));

    }

    /// \brief Constructor.

    ///

    /// Construct a new ConArcIt which continues the iterating from 

    /// the \c e arc.

    ConArcIt(const Graph& g, Arc a) : Parent(a), _graph(g) {}

    /// \brief Increment operator.

    ///

    /// It increments the iterator and gives back the next arc.

    ConArcIt& operator++() {

      Parent::operator=(findArc(_graph, _graph.source(*this), 

				_graph.target(*this), *this));

      return *this;

    }

  private:

    const Graph& _graph;

  };

  namespace _graph_utils_bits {

    template <typename Graph, typename Enable = void>

    struct FindEdgeSelector {

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      static Edge find(const Graph &g, Node u, Node v, Edge e) {

        bool b;

        if (u != v) {

          if (e == INVALID) {

            g.firstInc(e, b, u);

          } else {

            g.nextInc(e, b);

          }

            g.nextInc(e, b);

          }

        } else {

          if (e == INVALID) {

            g.firstInc(e, b, u);

          } else {

            b = true;

            g.nextInc(e, b);

          }

            g.nextInc(e, b);

          }

        }

        return e;

      }

    };

    template <typename Graph>

    struct FindEdgeSelector<

      Graph, 

      typename enable_if<typename Graph::FindEdgeTag, void>::type> 

    {

      typedef typename Graph::Node Node;

      typedef typename Graph::Edge Edge;

      static Edge find(const Graph &g, Node u, Node v, Edge prev) {

        return g.findEdge(u, v, prev);

      }

    };    

  }

  /// \brief Finds an edge between two nodes of a graph.

  ///

  /// Finds an edge from node \c u to node \c v in graph \c g.

  /// If the node \c u and node \c v is equal then each loop edge

  /// will be enumerated once.

  ///

  /// If \c prev is \ref INVALID (this is the default value), then

  /// it finds the first arc from \c u to \c v. Otherwise it looks for

  /// the next arc from \c u to \c v after \c prev.

  /// \return The found arc or \ref INVALID if there is no such an arc.

  ///

  /// Thus you can iterate through each arc from \c u to \c v as it follows.

  ///\code

  /// for(Edge e = findEdge(g,u,v); e != INVALID; 

  ///     e = findEdge(g,u,v,e)) {

  ///   ...

  /// }

  ///\endcode

  ///

  template <typename Graph>

  inline typename Graph::Edge 

  findEdge(const Graph &g, typename Graph::Node u, typename Graph::Node v,

            typename Graph::Edge p = INVALID) {

    return _graph_utils_bits::FindEdgeSelector<Graph>::find(g, u, v, p);

  }

  /// \brief Iterator for iterating on edges connected the same nodes.

  ///

  /// Iterator for iterating on edges connected the same nodes. It is 

  /// higher level interface for the findEdge() function. You can

  /// use it the following way:

  ///\code

  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {

  ///   ...

  /// }

  ///\endcode

  ///

  ///\sa findEdge()

  template <typename _Graph>

  class ConEdgeIt : public _Graph::Edge {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Edge Parent;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::Node Node;

    /// \brief Constructor.

    ///

    /// Construct a new ConEdgeIt iterating on the edges which

    /// connects the \c u and \c v node.

    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {

      Parent::operator=(findEdge(_graph, u, v));

    }

    /// \brief Constructor.

    ///

    /// Construct a new ConEdgeIt which continues the iterating from 

    /// the \c e edge.

    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}

    /// \brief Increment operator.

    ///

    /// It increments the iterator and gives back the next edge.

    ConEdgeIt& operator++() {

      return *this;

    }

  private:

    const Graph& _graph;

  };

  namespace _graph_utils_bits {

    template <typename Digraph, typename Item, typename RefMap>

    class MapCopyBase {

    public:

      virtual void copy(const Digraph& from, const RefMap& refMap) = 0;

      virtual ~MapCopyBase() {}

    };

    template <typename Digraph, typename Item, typename RefMap, 

              typename ToMap, typename FromMap>

    class MapCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      MapCopy(ToMap& tmap, const FromMap& map) 

        : _tmap(tmap), _map(map) {}

      virtual void copy(const Digraph& digraph, const RefMap& refMap) {

        typedef typename ItemSetTraits<Digraph, Item>::ItemIt ItemIt;

        for (ItemIt it(digraph); it != INVALID; ++it) {

          _tmap.set(refMap[it], _map[it]);

        }

      }

    private:

      ToMap& _tmap;

      const FromMap& _map;

    };

    template <typename Digraph, typename Item, typename RefMap, typename It>

    class ItemCopy : public MapCopyBase<Digraph, Item, RefMap> {

    public:

      ItemCopy(It& it, const Item& item) : _it(it), _item(item) {}

      virtual void copy(const Digraph&, const RefMap& refMap) {

        _it = refMap[_item];

      }

    private:

      It& _it;