RhodeCode

  /// finding arc-disjoint paths having minimum total length (cost)

  /// from a given source node to a given target node in a digraph.

  ///

  /// Note that this problem is a special case of the \ref min_cost_flow

  /// "minimum cost flow problem". This implementation is actually an

  /// efficient specialized version of the \ref CapacityScaling

  /// Therefore this class provides query functions for flow values and

  /// node potentials (the dual solution) just like the minimum cost flow

  /// algorithms.

  ///

  /// \tparam GR The digraph type the algorithm runs on.

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

  /// The default value is <tt>GR::ArcMap<int></tt>.

  ///

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

  ///

  /// along with the \ref SplitNodes adaptor.

#ifdef DOXYGEN

  template <typename GR, typename LEN>

#else

  template < typename GR,

             typename LEN = typename GR::template ArcMap<int> >

    {

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

      typedef BinHeap<Length, HeapCrossRef> Heap;

    private:

      const Digraph &_graph;

      const FlowMap &_flow;

      PredMap &_pred;

      Node _s;

      Node _t;

    public:

        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;

          _dist[u] = heap.prio();

          heap.pop();

          _proc_nodes.push_back(u);

          // Traverse outgoing arcs

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

            if (_flow[e] == 0) {

              v = _graph.target(e);

              switch(heap.state(v)) {

              case Heap::PRE_HEAP:

                _pred[v] = e;

                break;

              case Heap::IN_HEAP:

                  _pred[v] = e;

                }

                break;

              case Heap::POST_HEAP:

                break;

              }

          // Traverse incoming arcs

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

            if (_flow[e] == 1) {

              v = _graph.source(e);

              switch(heap.state(v)) {

              case Heap::PRE_HEAP:

                _pred[v] = e;

                break;

              case Heap::IN_HEAP:

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

        return true;

      }

    }; //class ResidualDijkstra

  private:

    bool _local_flow;

    // Node map of the current potentials

    PotentialMap *_potential;

    bool _local_potential;

    // The source node

    // The target node

    // Container to store the found paths

    int _path_num;

    // The pred arc map

    PredMap _pred;

  public:

    /// \brief Constructor.

    ///

    /// Constructor.

    {}

    /// Destructor.

    ~Suurballe() {

      if (_local_flow) delete _flow;

      if (_local_potential) delete _potential;

    }

    /// \brief Set the flow map.

    ///

    /// This function sets the flow map.

    /// If it is not used before calling \ref run() or \ref init(),

    /// \brief Initialize the algorithm.

    ///

    /// This function initializes the algorithm.

    ///

    /// \param s The source node.

    void init(const Node& s) {

      // Initialize maps

      if (!_flow) {

        _flow = new FlowMap(_graph);

        _local_flow = true;

      }

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

    /// the source node to the given node \c t in the digraph.

    /// Otherwise it returns the number of arc-disjoint paths found.

    ///

    /// \pre \ref init() must be called before using this function.

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

      // Find shortest paths

      _path_num = 0;

      while (_path_num < k) {

        // Run Dijkstra

        ++_path_num;

        // Set the flow along the found shortest path

        Arc e;

        while ((e = _pred[u]) != INVALID) {

          if (u == _graph.target(e)) {

            (*_flow)[e] = 1;

            u = _graph.source(e);

          } else {

      }

      return _path_num;

    }

    /// \brief Compute the paths from the flow.

    ///

    ///

    /// \pre \ref init() and \ref findFlow() must be called before using

    /// this function.

    void findPaths() {

      FlowMap res_flow(_graph);

      for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];

      for (int i = 0; i < _path_num; ++i) {

          OutArcIt e(_graph, n);

          for ( ; res_flow[e] == 0; ++e) ;

          n = _graph.target(e);

          res_flow[e] = 0;

        }

      }

    }

    /// @}

    /// \param i The function returns the <tt>i</tt>-th path.

    /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.

    ///

    /// \pre \ref run() or \ref findPaths() must be called before using

    /// this function.

    const Path& path(int i) const {

    }

    /// @}

  }; //class Suurballe