RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

    .other("...");

  // Throw an exception when problems occurs. The default behavior is to

  // exit(1) on these cases, but this makes Valgrind falsely warn

  // about memory leaks.

  ap.throwOnProblems();

  // Perform the parsing process

  // (in case of any error it terminates the program)

  // The try {} construct is necessary only if the ap.trowOnProblems()

  // setting is in use.

  try {

    ap.parse();

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

\section intro Introduction

<b>LEMON</b> stands for <i><b>L</b>ibrary for <b>E</b>fficient <b>M</b>odeling

and <b>O</b>ptimization in <b>N</b>etworks</i>.

It is a C++ template library providing efficient implementations of common

data structures and algorithms with focus on combinatorial optimization

<b>

LEMON is an <a class="el" href="http://opensource.org/">open&nbsp;source</a>

project.

You are free to use it in your commercial or

non-commercial applications under very permissive

\ref license "license terms".

</b>

<a href="http://www.cs.elte.hu/egres/">Egerv&aacute;ry Research Group on

Combinatorial Optimization</a> \ref egres

at the Operations Research Department of the

<a href="http://www.elte.hu/en/">E&ouml;tv&ouml;s Lor&aacute;nd University</a>,

Budapest, Hungary.

LEMON is also a member of the <a href="http://www.coin-or.org/">COIN-OR</a>

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;

   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.

 - For all \f$u\in V\f$ nodes:

   - \f$\pi(u)\leq 0\f$;

   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,

     then \f$\pi(u)=0\f$.

Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc

\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.

\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]

All algorithms provide dual solution (node potentials), as well,

if an optimal flow is found.

\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]

\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq

    sup(u) \quad \forall u\in V \f]

\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f]

total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or

positive) and all the demands have to be satisfied, but there

could be supplies that are not carried out from the supply

nodes.

The equality form is also a special case of this form, of course.

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

    SubDigraphBase()

      : Parent(), _node_filter(0), _arc_filter(0) { }

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

      return arc;

    }

  public:

    template <typename V>

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

    public:

      typedef V Value;

      NodeMap(const SubDigraphBase<DGR, NF, AF, ch>& adaptor)

        : Parent(adaptor) {}

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, ch>,

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

    SubDigraphBase()

      : Parent(), _node_filter(0), _arc_filter(0) { }

    void initialize(DGR& digraph, NF& node_filter, AF& arc_filter) {

      Parent::initialize(digraph);

      _node_filter = &node_filter;

    }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

        arc = Parent::findArc(source, target, arc);

      }

      return arc;

    }

    template <typename V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, NodeMap<V>)> Parent;

    public:

      typedef V Value;

      NodeMap(const SubDigraphBase<DGR, NF, AF, false>& adaptor)

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename V>

      : public SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

          LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> {

      typedef SubMapExtender<SubDigraphBase<DGR, NF, AF, false>,

        LEMON_SCOPE_FIX(DigraphAdaptorBase<DGR>, ArcMap<V>)> Parent;

    public:

        edge = Parent::findEdge(u, v, edge);

      }

      return edge;

    }

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

    public:

      typedef V Value;

      NodeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

      ArcMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, ch>,

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> Parent;

    public:

      typedef V Value;

      EdgeMap(const SubGraphBase<GR, NF, EF, ch>& adaptor)

    typedef EF EdgeFilterMap;

    typedef SubGraphBase Adaptor;

  protected:

    NF* _node_filter;

    EF* _edge_filter;

    void initialize(GR& graph, NF& node_filter, EF& edge_filter) {

      Parent::initialize(graph);

      _node_filter = &node_filter;

      _edge_filter = &edge_filter;

    }

        edge = Parent::findEdge(u, v, edge);

      }

      return edge;

    }

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, NodeMap<V>)> Parent;

    public:

      typedef V Value;

      NodeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

          LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> {

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, ArcMap<V>)> Parent;

    public:

      typedef V Value;

      ArcMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

        Parent::operator=(cmap);

        return *this;

      }

    };

    template <typename V>

      : public SubMapExtender<SubGraphBase<GR, NF, EF, false>,

        LEMON_SCOPE_FIX(GraphAdaptorBase<GR>, EdgeMap<V>)> {

    public:

      typedef V Value;

      EdgeMap(const SubGraphBase<GR, NF, EF, false>& adaptor)

        : Parent(adaptor) {}

  class FilterNodes :

    public DigraphAdaptorExtender<

      SubDigraphBase<GR, NF, ConstMap<typename GR::Arc, Const<bool, true> >,

                     true> > {

#endif

    typedef DigraphAdaptorExtender<

                     true> > Parent;

  public:

    typedef GR Digraph;

    typedef NF NodeFilterMap;

  public:

    /// \brief Constructor

    ///

    /// Creates a subgraph for the given digraph or graph with the

    /// given node filter map.

      : Parent(), const_true_map()

    {

      Parent::initialize(graph, node_filter, const_true_map);

    }

    /// \brief Sets the status of the given node

  };

  template<typename GR, typename NF>

  class FilterNodes<GR, NF,

                    typename enable_if<UndirectedTagIndicator<GR> >::type> :

    public GraphAdaptorExtender<

                   true> > {

    typedef GraphAdaptorExtender<

                   true> > Parent;

  public:

    typedef GR Graph;

    typedef NF NodeFilterMap;

  class FilterArcs :

    public DigraphAdaptorExtender<

      SubDigraphBase<DGR, ConstMap<typename DGR::Node, Const<bool, true> >,

                     AF, false> > {

#endif

    typedef DigraphAdaptorExtender<

                     AF, false> > Parent;

  public:

    /// The type of the adapted digraph.

    typedef DGR Digraph;

  class FilterEdges {

#else

  template<typename GR,

           typename EF = typename GR::template EdgeMap<bool> >

  class FilterEdges :

    public GraphAdaptorExtender<

                   EF, false> > {

#endif

    typedef GraphAdaptorExtender<

                   EF, false> > Parent;

  public:

    /// The type of the adapted graph.

    typedef GR Graph;

  public:

    /// \brief Constructor

    ///

    /// Creates a subgraph for the given graph with the given edge

    /// filter map.

      : Parent(), const_true_map() {

      Parent::initialize(graph, const_true_map, edge_filter);

    }

    /// \brief Sets the status of the given edge

    ///

    class Arc {

      friend class UndirectorBase;

    protected:

      Edge _edge;

      bool _forward;

        : _edge(edge), _forward(forward) {}

    public:

      Arc() {}

      Arc(Invalid) : _edge(INVALID), _forward(true) {}

      typedef typename MapTraits<MapImpl>::ReturnValue Reference;

      ArcMapBase(const UndirectorBase<DGR>& adaptor) :

        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}

      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)

          _backward(*adaptor._digraph, value) {}

      void set(const Arc& a, const V& value) {

        if (direction(a)) {

          _forward.set(a, value);

        } else {

    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;

    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }

    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;

    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }

    typedef EdgeNotifier ArcNotifier;

    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }

  protected:

    UndirectorBase() : _digraph(0) {}

  class ResidualDigraph

#else

  template<typename DGR,

           typename CM = typename DGR::template ArcMap<int>,

           typename FM = CM,

           typename TL = Tolerance<typename CM::Value> >

    : public SubDigraph<

        Undirector<const DGR>,

        ConstMap<typename DGR::Node, Const<bool, true> >,

        typename Undirector<const DGR>::template CombinedArcMap<

          _adaptor_bits::ResForwardFilter<const DGR, CM, FM, TL>,

          _adaptor_bits::ResBackwardFilter<const DGR, CM, FM, TL> > >

    /// \brief Constructor

    ///

    /// Constructor of the residual digraph adaptor. The parameters are the

    /// digraph, the capacity map, the flow map, and a tolerance object.

    ResidualDigraph(const DGR& digraph, const CM& capacity,

                    FM& flow, const TL& tolerance = Tolerance())

        _graph(digraph), _node_filter(),

        _forward_filter(capacity, flow, tolerance),

        _backward_filter(capacity, flow, tolerance),

        _arc_filter(_forward_filter, _backward_filter)

    {

      Parent::initialize(_graph, _node_filter, _arc_filter);

      /// The key type of the map

      typedef Arc Key;

      /// The value type of the map

      typedef typename CapacityMap::Value Value;

      /// Constructor

        : _adaptor(&adaptor) {}

      /// Returns the value associated with the given residual arc

      Value operator[](const Arc& a) const {

        return _adaptor->residualCapacity(a);

      }

    /// \brief Node map combined from two original node maps

    ///

    /// This map adaptor class adapts two node maps of the original digraph

    /// to get a node map of the split digraph.

    /// Its value type is inherited from the first node map type (\c IN).

    /// \tparam OUT The type of the node map for the out-nodes.

    template <typename IN, typename OUT>

    class CombinedNodeMap {

    public:

      /// The key type of the map

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

  void ArgParser::_terminate(ArgParserException::Reason reason) const

  {

    if(_exit_on_problems)

      exit(1);

    else throw(ArgParserException(reason));

  }

  void ArgParser::_showHelp(void *p)

  {

    (static_cast<ArgParser*>(p))->showHelp();

    (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);

  }

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

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

 *

 * 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.

  public:

    enum Reason {

      HELP,         /// <tt>--help</tt> option was given

      UNKNOWN_OPT,  /// Unknown option was given

      INVALID_OPT   /// Invalid combination of options

    };

  private:

    Reason _reason;

  public:

    ///Constructor

    ArgParserException(Reason r) throw() : _reason(r) {}

    ///Virtual destructor

    virtual ~ArgParserException() throw() {}

    ///A short description of the exception

    };

    std::vector<OtherArg> _others_help;

    std::vector<std::string> _file_args;

    std::string _command_name;

  private:

    //Bind a function to an option.

    //\param name The name of the option. The leading '-' must be omitted.

    //\param help A help string.

    //\retval func The function to be called when the option is given. It

    //\param data Data to be passed to \c func

    ArgParser &funcOption(const std::string &name,

                    const std::string &help,

                    void (*func)(void *),void *data);

    bool _exit_on_problems;

    void _terminate(ArgParserException::Reason reason) const;

  public:

    ///Constructor

    ArgParser(int argc, const char * const *argv);

    ///Give back a reference to a vector consisting of the program arguments

    ///not starting with a '-' character.

    const std::vector<std::string> &files() const { return _file_args; }

    ///Throw instead of exit in case of problems

    {

      _exit_on_problems=false;

    }

  };

}

 *

 *

 * 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.

#include <limits>

namespace lemon {

  /// \brief Default operation traits for the BellmanFord algorithm class.

  /// This operation traits class defines all computational operations

  /// and constants that are used in the Bellman-Ford algorithm.

  /// The default implementation is based on the \c numeric_limits class.

  /// If the numeric type does not have infinity value, then the maximum

  /// value is used as extremal infinity value.

  ///

  /// \see BellmanFordToleranceOperationTraits

  template <

    bool has_inf = std::numeric_limits<V>::has_infinity>

  struct BellmanFordDefaultOperationTraits {

    /// \brief Value type for the algorithm.

    typedef V Value;

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

    static Value zero() {

      return left + right;

    }

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

      return left < right;

    }

  };

  /// \brief Operation traits for the BellmanFord algorithm class

  /// using tolerance.

  ///

  /// This operation traits class defines all computational operations

  /// and constants that are used in the Bellman-Ford algorithm.

  /// The only difference between this implementation and

  ///

  /// Default traits class of BellmanFord class.

  /// \param GR The type of the digraph.

  /// \param LEN The type of the length map.

  template<typename GR, typename LEN>

  struct BellmanFordDefaultTraits {

    typedef GR Digraph;

    /// \brief The type of the map that stores the arc lengths.

    ///

    /// The type of the map that stores the arc lengths.

    /// It must conform to the \ref concepts::ReadMap "ReadMap" concept.

    ///

    /// It defines the used operations and the infinity value for the

    /// given \c Value type.

    /// \see BellmanFordDefaultOperationTraits,

    /// BellmanFordToleranceOperationTraits

    typedef BellmanFordDefaultOperationTraits<Value> OperationTraits;

    /// shortest paths.

    /// The type of the map that stores the last

    /// arcs of the shortest paths.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename GR::template NodeMap<typename GR::Arc> PredMap;

    /// \brief Instantiates a \c PredMap.

    /// \param g is the digraph to which we would like to define the

    /// \ref PredMap.

    static PredMap *createPredMap(const GR& g) {

      return new PredMap(g);

    }

    /// The type of the map that stores the distances of the nodes.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    typedef typename GR::template NodeMap<typename LEN::Value> DistMap;

    /// \brief Instantiates a \c DistMap.

    ///

    /// \ref DistMap.

    static DistMap *createDistMap(const GR& g) {

      return new DistMap(g);

    }

  };

  /// \brief %BellmanFord algorithm class.

  ///

  /// \ingroup shortest_path

  /// algorithm. The maximum time complexity of the algorithm is

  /// <tt>O(ne)</tt>.

  ///

  /// The Bellman-Ford algorithm solves the single-source shortest path

  /// problem when the arcs can have negative lengths, but the digraph

  /// should not contain directed cycles with negative total length.

  /// If all arc costs are non-negative, consider to use the Dijkstra

  /// algorithm instead, since it is more efficient.

  ///

  /// The arc lengths are passed to the algorithm using a

  /// kind of length. The type of the length values is determined by the

  /// \ref concepts::ReadMap::Value "Value" type of the length map.

  ///

  /// There is also a \ref bellmanFord() "function-type interface" for the

  /// Bellman-Ford algorithm, which is convenient in the simplier cases and

  /// it can be used easier.

#endif

  class BellmanFord {

  public:

    ///The type of the underlying digraph.

    typedef typename TR::Digraph Digraph;

    /// \brief The type of the arc lengths.

    typedef typename TR::LengthMap::Value Value;

    /// \brief The type of the map that stores the arc lengths.

    typedef typename TR::LengthMap LengthMap;

    /// \brief The type of the map that stores the last

    /// arcs of the shortest paths.

    std::vector<Node> _process;

    // Creates the maps if necessary.

    void create_maps() {

      if(!_pred) {

      }

      if(!_dist) {

      }

      if(!_mask) {

        _mask = new MaskMap(*_gr);

      }

    }

  public :

    typedef BellmanFord Create;

    /// \name Named Template Parameters

    ///@{

    /// \c PredMap type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c PredMap type.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

      : public BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetPredMapTraits<T> > Create;

    };

    template <class T>

    struct SetDistMapTraits : public Traits {

      typedef T DistMap;

      static DistMap *createDistMap(const Digraph&) {

        LEMON_ASSERT(false, "DistMap is not initialized");

        return 0; // ignore warnings

    /// \c DistMap type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c DistMap type.

    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.

    template <class T>

      : public BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetDistMapTraits<T> > Create;

    };

    template <class T>

    struct SetOperationTraitsTraits : public Traits {

      typedef T OperationTraits;

    };

    /// \c OperationTraits type.

    ///

    /// \ref named-templ-param "Named parameter" for setting

    /// \c OperationTraits type.

    /// For more information, see \ref BellmanFordDefaultOperationTraits.

    template <class T>

    struct SetOperationTraits

      : public BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> > {

      typedef BellmanFord< Digraph, LengthMap, SetOperationTraitsTraits<T> >

      Create;

    };

    ///@}

  protected:

    BellmanFord() {}

    /// \brief Constructor.

    ///

    /// Constructor.

    /// \param g The digraph the algorithm runs on.

    /// \param length The length map used by the algorithm.

    BellmanFord(const Digraph& g, const LengthMap& length) :

      _gr(&g), _length(&length),

      _pred(0), _local_pred(false),

      _dist(0), _local_dist(false), _mask(0) {}

    ///Destructor.

    ~BellmanFord() {

      if(_local_pred) delete _pred;

      if(_local_dist) delete _dist;

      if(_mask) delete _mask;

    }

    /// or \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

    /// \return <tt>(*this)</tt>

    BellmanFord &predMap(PredMap &map) {

      if(_local_pred) {

      }

      _pred = ↦

      return *this;

    }

    /// \brief Sets the map that stores the distances of the nodes.

    /// or \ref init(), an instance will be allocated automatically.

    /// The destructor deallocates this automatically allocated map,

    /// of course.

    /// \return <tt>(*this)</tt>

    BellmanFord &distMap(DistMap &map) {

      if(_local_dist) {

      }

      _dist = ↦

      return *this;

    }

    /// \name Execution Control

    /// performed with \ref start(), \ref checkedStart() or

    /// \ref limitedStart().

    ///@{

    /// \brief Initializes the internal data structures.

    /// Initializes the internal data structures. The optional parameter

    /// is the initial distance of each node.

    void init(const Value value = OperationTraits::infinity()) {

      create_maps();

      for (NodeIt it(*_gr); it != INVALID; ++it) {

      }

      _process.clear();

      if (OperationTraits::less(value, OperationTraits::infinity())) {

      } else {