RhodeCode

#include <lemon/dijkstra.h>

  /// "successive shortest path" algorithm directly for this problem.

  /// \warning Length values should be \e non-negative.

  /// \note For finding \e node-disjoint paths, this algorithm can be used

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

    typedef BinHeap<Length, HeapCrossRef> Heap;

    private:

      const Digraph &_graph;

      const LengthMap &_length;

      const FlowMap &_flow;

      PotentialMap &_pi;

      PredMap &_pred;

      Node _s;

      Node _t;

      PotentialMap _dist;

      std::vector<Node> _proc_nodes;

    public:

      // Constructor

      ResidualDijkstra(Suurballe &srb) :

        _graph(srb._graph), _length(srb._length),

        _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), 

        _s(srb._s), _t(srb._t), _dist(_graph) {}

      // Run the algorithm and return true if a path is found

      // from the source node to the target node.

      bool run(int cnt) {

        return cnt == 0 ? startFirst() : start();

      }

      // Execute the algorithm for the first time (the flow and potential

      // functions have to be identically zero).

      bool startFirst() {

          Length d = heap.prio(), dn;

          _proc_nodes.push_back(u);

          // Traverse outgoing arcs

          for (OutArcIt e(_graph, u); e != INVALID; ++e) {

            v = _graph.target(e);

            switch(heap.state(v)) {

              case Heap::PRE_HEAP:

                heap.push(v, d + _length[e]);

                _pred[v] = e;

                break;

              case Heap::IN_HEAP:

                dn = d + _length[e];

                if (dn < heap[v]) {

                  heap.decrease(v, dn);

                  _pred[v] = e;

                }

                break;

              case Heap::POST_HEAP:

                break;

            }

          }

        }

        if (heap.empty()) return false;

        // Update potentials of processed nodes

        Length t_dist = heap.prio();

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

          _pi[_proc_nodes[i]] = _dist[_proc_nodes[i]] - t_dist;

        return true;

      }

      // Execute the algorithm.

      bool start() {

        HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP);

        Heap heap(heap_cross_ref);

        heap.push(_s, 0);

        _pred[_s] = INVALID;

        _proc_nodes.clear();

        // Process nodes

        while (!heap.empty() && heap.top() != _t) {

          Node u = heap.top(), v;

          Length d = heap.prio() + _pi[u], dn;

          _dist[u] = heap.prio();

          heap.pop();

                  heap.push(v, d + _length[e] - _pi[v]);

                  dn = d + _length[e] - _pi[v];

                  if (dn < heap[v]) {

                    heap.decrease(v, dn);

                  heap.push(v, d - _length[e] - _pi[v]);

                  dn = d - _length[e] - _pi[v];

                  if (dn < heap[v]) {

                    heap.decrease(v, dn);

          _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - t_dist;

    Node _s;

    Node _t;

    std::vector<Path> _paths;

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

      _s = s;

      _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;

      _t = t;

      ResidualDijkstra dijkstra(*this);

      // 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;

      }

        if (!dijkstra.run(_path_num)) break;

        Node u = _t;

    /// This function computes arc-disjoint paths from the found minimum

    /// cost flow, which is the union of them.

      _paths.clear();

      _paths.resize(_path_num);

        Node n = _s;

        while (n != _t) {

          _paths[i].addBack(e);

    const Path& path(int i) const {

      return _paths[i];

  suurb_test.fullInit(n);

  suurb_test.start(n);

  suurb_test.start(n, k);