RhodeCode

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

 * purpose.

 *

 */

#ifndef LEMON_BELLMAN_FORD_H

#define LEMON_BELLMAN_FORD_H

/// \ingroup shortest_path

/// \file

/// \brief Bellman-Ford algorithm.

#include <lemon/bits/path_dump.h>

#include <lemon/core.h>

#include <lemon/error.h>

#include <lemon/maps.h>

#include <lemon/path.h>

#include <limits>

namespace lemon {

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

  ///  

    ///

    /// \pre Either \ref run() or \ref init() must be called before

    /// using this function.

    bool reached(Node v) const {

      return (*_dist)[v] != OperationTraits::infinity();

    }

    /// \brief Gives back a negative cycle.

    ///    

    /// This function gives back a directed cycle with negative total

    /// length if the algorithm has already found one.

    /// Otherwise it gives back an empty path.

      typename Digraph::template NodeMap<int> state(*_gr, -1);

      lemon::Path<Digraph> cycle;

      for (int i = 0; i < int(_process.size()); ++i) {

        if (state[_process[i]] != -1) continue;

        for (Node v = _process[i]; (*_pred)[v] != INVALID;

             v = _gr->source((*_pred)[v])) {

          if (state[v] == i) {

            cycle.addFront((*_pred)[v]);

            for (Node u = _gr->source((*_pred)[v]); u != v;

                 u = _gr->source((*_pred)[u])) {

              cycle.addFront((*_pred)[u]);

            }

    bf_test.start();

    bf_test.checkedStart();

    bf_test.limitedStart(k);

    l  = const_bf_test.dist(t);

    e  = const_bf_test.predArc(t);

    s  = const_bf_test.predNode(t);

    b  = const_bf_test.reached(t);

    d  = const_bf_test.distMap();

    p  = const_bf_test.predMap();

    pp = const_bf_test.path(t);

    for (BF::ActiveIt it(const_bf_test); it != INVALID; ++it) {}

  }

  {

    BF::SetPredMap<concepts::ReadWriteMap<Node,Arc> >

      ::SetDistMap<concepts::ReadWriteMap<Node,Value> >

      ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> >

      ::Create bf_test(gr,length);

    LengthMap length_map;

    concepts::ReadWriteMap<Node,Arc> pred_map;

    concepts::ReadWriteMap<Node,Value> dist_map;

    b = bf_test.processNextRound();

    b = bf_test.processNextWeakRound();

    bf_test.start();

    bf_test.checkedStart();

    bf_test.limitedStart(k);

    l  = bf_test.dist(t);

    e  = bf_test.predArc(t);

    s  = bf_test.predNode(t);

    b  = bf_test.reached(t);

    pp = bf_test.path(t);

  }

}

void checkBellmanFordFunctionCompile()

{

  typedef int Value;

  typedef concepts::Digraph Digraph;

  typedef Digraph::Arc Arc;

  typedef Digraph::Node Node;

  typedef concepts::ReadMap<Digraph::Arc,Value> LengthMap;

  Digraph g;