RhodeCode

#include <lemon/dijkstra.h>

    typedef typename Digraph::template NodeMap<int> HeapCrossRef;

    typedef BinHeap<Length, HeapCrossRef> Heap;

    // Data for full init

    PotentialMap *_init_dist;

    PredMap *_init_pred;

    bool _full_init;

      _potential(0), _local_potential(false), _pred(graph),

      _init_dist(0), _init_pred(0)

      delete _init_dist;

      delete _init_pred;

    /// function.\n

    /// If you need to execute the algorithm many times using the same

    /// source node, then you may call fullInit() once and start()

    /// for each target node.\n

    /// arc-disjoint paths, then you may call findFlow() instead of

    /// start().

    ///   s.start(t, k);

      start(t, k);

    /// This function initializes the algorithm with the given source node.

      _full_init = false;

    }

    /// \brief Initialize the algorithm and perform Dijkstra.

    ///

    /// This function initializes the algorithm and performs a full

    /// Dijkstra search from the given source node. It makes consecutive

    /// executions of \ref start() "start(t, k)" faster, since they

    /// have to perform %Dijkstra only k-1 times.

    ///

    /// This initialization is usually worth using instead of \ref init()

    /// if the algorithm is executed many times using the same source node.

    ///

    /// \param s The source node.

    void fullInit(const Node& s) {

      // Initialize maps

      init(s);

      if (!_init_dist) {

        _init_dist = new PotentialMap(_graph);

      }

      if (!_init_pred) {

        _init_pred = new PredMap(_graph);

      }

      // Run a full Dijkstra

      typename Dijkstra<Digraph, LengthMap>

        ::template SetStandardHeap<Heap>

        ::template SetDistMap<PotentialMap>

        ::template SetPredMap<PredMap>

        ::Create dijk(_graph, _length);

      dijk.distMap(*_init_dist).predMap(*_init_pred);

      dijk.run(s);

      _full_init = true;

    }

    /// \brief Execute the algorithm.

    ///

    /// This function executes the algorithm.

    ///

    /// \param t The target node.

    /// \param k The number of paths to be found.

    ///

    /// \return \c k if there are at least \c k arc-disjoint paths from

    /// \c s to \c t in the digraph. Otherwise it returns the number of

    /// arc-disjoint paths found.

    ///

    /// \note Apart from the return value, <tt>s.start(t, k)</tt> is

    /// just a shortcut of the following code.

    /// \code

    ///   s.findFlow(t, k);

    ///   s.findPaths();

    /// \endcode

    int start(const Node& t, int k = 2) {

      findFlow(t, k);

      findPaths();

      return _path_num;

      // Initialization

      for (ArcIt e(_graph); e != INVALID; ++e) {

        (*_flow)[e] = 0;

      }

      if (_full_init) {

        for (NodeIt n(_graph); n != INVALID; ++n) {

          (*_potential)[n] = (*_init_dist)[n];

        }

        Node u = _t;

        Arc e;

        while ((e = (*_init_pred)[u]) != INVALID) {

          (*_flow)[e] = 1;

          u = _graph.source(e);

        }        

        _path_num = 1;

      } else {

        for (NodeIt n(_graph); n != INVALID; ++n) {

          (*_potential)[n] = 0;

        }

        _path_num = 0;

      }

  suurb_test.fullInit(n);

  suurb_test.start(n);

  suurb_test.start(n, k);