RhodeCode

  /// \brief Algorithm for finding arc-disjoint paths between two nodes

  /// having minimum total length.

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

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

  /// The default value is \c ListDigraph.

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

#ifdef DOXYGEN

  template <typename Digraph, typename LengthMap>

#else

  template < typename Digraph = ListDigraph,

#endif

    /// \brief Special implementation of the Dijkstra algorithm

      // The digraph the algorithm runs on

      /// \brief Run the algorithm. It returns \c true if a path is found

        // Process nodes

          // Traverse outgoing arcs

          // Traverse incoming arcs

        // Update potentials of processed nodes

    // The digraph the algorithm runs on

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

    /// \brief Set the flow map.

    /// This function sets the flow map.

    /// \brief Set the potential map.

    /// This function sets the potential map.

    /// \brief Run the algorithm.

    /// This function runs the algorithm.

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

    /// \brief Initialize the algorithm.

    /// This function initializes the algorithm.

      // Initialize maps

    /// \brief Execute the successive shortest path algorithm to find

    /// This function executes the successive shortest path algorithm to

    /// find a minimum cost flow, which is the union of \c k or less

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

      // Find shortest paths

        // Run Dijkstra

        // Set the flow along the found shortest path

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

    /// This function computes the paths from the flow.

      // Create the residual flow map (the union of the paths not found

      // so far)

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

    /// The results of the algorithm can be obtained using these

    /// \brief Return a const reference to the arc map storing the

    /// This function returns a const reference to the arc map storing

    /// the flow that is the union of the found arc-disjoint paths.

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

    /// this function.

    /// \brief Return a const reference to the node map storing the

    /// This function returns a const reference to the node map storing

    /// the found potentials that provide the dual solution of the

    /// underlying minimum cost flow problem.

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

    /// this function.

    /// \brief Return the flow on the given arc.

    /// This function returns the flow on the given arc.

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

    /// this function.

    /// \brief Return the potential of the given node.

    /// This function returns the potential of the given node.

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

    /// this function.

    /// \brief Return the total length (cost) of the found paths (flow).

    /// This function returns the total length (cost) of the found paths

    /// (flow). The complexity of the function is \f$ O(e) \f$.

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

    /// this function.

    /// \brief Return the number of the found paths.

    /// This function returns the number of the found paths.

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

    /// this function.

    /// \brief Return a const reference to the specified path.

    /// This function returns a const reference to the specified path.

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

    /// this function.

// Check the feasibility of the flow

// Check the optimalitiy of the flow

  // Check the "Complementary Slackness" optimality condition

// Check a path

template <typename Digraph, typename Path>

  // Check the "Complementary Slackness" optimality condition

  // Read the test digraph

  // Find 2 paths

  // Find 3 paths

  // Find 5 paths (only 3 can be found)