RhodeCode

\endcode

\subsection pri-loc-var Private member variables

\code

\endcode

\subsection cs-excep Exceptions

   shortest path method \ref edmondskarp72theoretical.

 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are

   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.

For example, if the total supply and/or capacities are rather small,

*/

/**

@defgroup min_cut Minimum Cut Algorithms

  version of Karp's algorithm \ref dasdan98minmeancycle.

- \ref HowardMmc Howard's policy iteration algorithm

  \ref dasdan98minmeancycle.

most efficient one, though the best known theoretical bound on its running

time is exponential.

Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms

run in time O(ne) and use space O(n<sup>2</sup>+e), but the latter one is

\image latex connected_components.eps "Connected components" width=\textwidth

*/

/**

@ingroup algs

\brief Algorithms for planarity checking, embedding and drawing

This group contains the algorithms for planarity checking,

  ///

  /// \warning Both \c V and \c C must be signed number types.

  /// \warning All input data (capacities, supply values, and costs) must

  /// be integer.

#ifdef DOXYGEN

  template <typename GR, typename V, typename C, typename TR>

#else

  template < typename GR, typename V = int, typename C = V,

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

    };

  }

  ///

  /// This function returns \c true if the given graph is undirected.

#ifdef DOXYGEN

  template <typename GR>

  /// It is a highly efficient primal-dual solution method, which

  /// can be viewed as the generalization of the \ref Preflow

  /// "preflow push-relabel" algorithm for the maximum flow problem.

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

  /// specified, then default values will be used.

  ///

  /// \warning Both \c V and \c C must be signed number types.

  /// \warning All input data (capacities, supply values, and costs) must

  /// be integer.

  ///

  /// \note %CostScaling provides three different internal methods,

  /// from which the most efficient one is used by default.

  /// For more information, see \ref Method.

    /// \ref CostScaling provides three internal methods that differ mainly

    /// in their base operations, which are used in conjunction with the

    /// relabel operation.

    /// By default, the so called \ref PARTIAL_AUGMENT

    /// the most efficient and the most robust on various test inputs.

    /// However, the other methods can be selected using the \ref run()

    /// function with the proper parameter.

    enum Method {

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

  ///

  /// \warning Both \c V and \c C must be signed number types.

  /// \warning All input data (capacities, supply values, and costs) must

  /// be integer.

  ///

  /// \note For more information about the three available methods,

  /// see \ref Method.

#ifdef DOXYGEN

    /// for the \ref run() function.

    ///

    /// \ref CycleCanceling provides three different cycle-canceling

    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"

    /// However, the other methods can be selected using the \ref run()

    /// function with the proper parameter.

    enum Method {

      /// A simple cycle-canceling method, which uses the

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

namespace lemon {

  ///Euler tour iterator for digraphs.

  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed

  ///graph (if there exists) and it converts to the \c Arc type of the digraph.

  ///

  ///For example, if the given digraph has an Euler tour (i.e it has only one

  /// undirected graph, i.e., the largest set of nodes where each

  /// pair of nodes is connected.

  ///

  /// This class provides a simple but highly efficient and robust heuristic

  /// largest one.

  ///

  /// \tparam GR The undirected graph type the algorithm runs on.

  ///

  /// \note %GrossoLocatelliPullanMc provides three different node selection

      /// search process.

      PENALTY_BASED

    };

  private:

    TEMPLATE_GRAPH_TYPEDEFS(GR);

    typedef std::vector<char> BoolVector;

    typedef std::vector<BoolVector> BoolMatrix;

    // Note: vector<char> is used instead of vector<bool> for efficiency reasons

    const GR &_graph;

    IntNodeMap _id;

    // Internal matrix representation of the graph

    BoolMatrix _gr;

    int _n;

    // The current clique

    BoolVector _clique;

    int _size;

    ///

    /// \param graph The undirected graph the algorithm runs on.

    GrossoLocatelliPullanMc(const GR& graph) :

      _graph(graph), _id(_graph), _rnd(rnd)

    /// \brief Constructor with random seed.

    ///

    /// Constructor with random seed.

    /// \param seed Seed value for the internal random number generator

    /// that is used during the algorithm.

    GrossoLocatelliPullanMc(const GR& graph, int seed) :

      _graph(graph), _id(_graph), _rnd(seed)

    /// \brief Constructor with random number generator.

    ///

    /// Constructor with random number generator.

    /// \param random A random number generator that is used during the

    /// algorithm.

    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :

      _graph(graph), _id(_graph), _rnd(random)

    /// \name Execution Control

    /// @{

    /// \brief Runs the algorithm.

    ///

    ///

    /// \param rule The node selection rule. For more information, see

    /// \ref SelectionRule.

    ///

    {

      init();

      switch (rule) {

        case RANDOM:

        case DEGREE_BASED:

      }

    }

    /// @}

    /// \name Query Functions

    /// @{

    /// \brief The size of the found clique

    ///

    /// @}

  private:

    // Adds a node to the current clique

    void addCliqueNode(int u) {

      if (_clique[u]) return;

    }

    // Executes the algorithm

    template <typename SelectionRuleImpl>

      if (_n == 1) {

        _best_clique[0] = true;

        _best_size = 1;

      }

      SelectionRuleImpl sel_method(*this);

      IntVector restart_nodes;

        // Perturbation/restart

          restart_nodes.clear();

          for (int i = 0; i != _n; i++) {

              restart_nodes.push_back(i);

          }

        }

        int rs_node = -1;

        }

        if (_size > _best_size) {

          _best_clique = _clique;

          _best_size = _size;

        }

        sel_method.update();

      }

    }

  }; //class GrossoLocatelliPullanMc

  /// This algorithm is a highly efficient specialized version of the

  /// linear programming simplex method directly for the minimum cost

  /// flow problem.

  ///

  ///

  /// Most of the parameters of the problem (except for the digraph)

  /// can be given using separate functions, and the algorithm can be

  /// executed using the \ref run() function. If some parameters are not

    /// \ref NetworkSimplex provides five different pivot rule

    /// implementations that significantly affect the running time

    /// of the algorithm.

    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which

    /// test inputs.

    /// However, another pivot rule can be selected using the \ref run()

    /// function with the proper parameter.

    enum PivotRule {

    typedef std::vector<int> IntVector;

    typedef std::vector<Value> ValueVector;

    typedef std::vector<Cost> CostVector;

    typedef std::vector<signed char> CharVector;

    // vector<ArcDirection> for efficiency reasons

    // State constants for arcs

    enum ArcState {

    /// Its \c Value type must be convertible to the \c Value type

    /// of the algorithm.

    ///

    /// \return <tt>(*this)</tt>

    template<typename SupplyMap>

    NetworkSimplex& supplyMap(const SupplyMap& map) {

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

        _supply[_node_id[n]] = map[n];

    /// If neither this function nor \ref supplyMap() is used before

    /// calling \ref run(), the supply of each node will be set to zero.

    ///

    /// Using this function has the same effect as using \ref supplyMap()

    /// assigned to \c t and all other nodes have zero supply value.

    ///

    /// \param s The source node.

    /// \param t The target node.

  /// A structure for representing directed path in a digraph.

  /// \tparam GR The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// cannot enumerate the nodes of the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is a back and front insertable and erasable

    /// \brief Reset the path to an empty one.

    void clear() { head.clear(); tail.clear(); }

    ///

    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.

    const Arc& nth(int n) const {

      return n < int(head.size()) ? *(head.rbegin() + n) :

        *(tail.begin() + (n - head.size()));

    }

    ///

    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

  /// A structure for representing directed path in a digraph.

  /// \tparam GR The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// cannot enumerate the nodes in the path and the zero length paths

  /// cannot store the source.

  ///

  /// This implementation is a just back insertable and erasable path

    /// \brief Reset the path to an empty one.

    void clear() { data.clear(); }

    ///

    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.

    const Arc& nth(int n) const {

      return data[n];

    }

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

  /// A structure for representing directed path in a digraph.

  /// \tparam GR The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// cannot enumerate the nodes in the path and the zero length paths

  /// cannot store the source.

  ///

  /// This implementation is a back and front insertable and erasable

      const ListPath *path;

      Node *node;

    };

    ///

    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.

    const Arc& nth(int n) const {

      Node *node = first;

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

      }

      return node->arc;

    }

    ArcIt nthIt(int n) const {

      Node *node = first;

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

        node = node->next;

  /// A structure for representing directed path in a digraph.

  /// \tparam GR The digraph type in which the path is.

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// cannot enumerate the nodes in the path and the source node of

  /// a zero length path is undefined.

  ///

  /// This implementation is completly static, i.e. it can be copy constucted

      const StaticPath *path;

      int idx;

    };

    ///

    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.

    const Arc& nth(int n) const {

      return arcs[n];

    }

    ArcIt nthIt(int n) const {

      return ArcIt(*this, n);

    }

  /// \brief Class which helps to iterate through the nodes of a path

  ///

  /// In a sense, the path can be treated as a list of arcs. The

  /// cannot enumerate the nodes in the path and the zero length paths

  /// cannot have a source node.

  ///

  /// This class implements the node iterator of a path structure. To

// Check with general graphs

template <typename Param>

  typedef ListGraph GR;

  typedef GrossoLocatelliPullanMc<GR> McAlg;

  typedef McAlg::CliqueNodeIt CliqueIt;

  {

    GR g;

    GR::NodeMap<bool> map(g);

    McAlg mc(g);

    check(mc.cliqueSize() == 0, "Wrong clique size");

    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");

    GR::Node u = g.addNode();

    check(mc.cliqueSize() == 1, "Wrong clique size");

    mc.cliqueMap(map);

    check(map[u], "Wrong clique map");

    CliqueIt it1(mc);

    check(static_cast<GR::Node>(it1) == u && ++it1 == INVALID,

          "Wrong CliqueNodeIt");

    GR::Node v = g.addNode();

    check(mc.cliqueSize() == 1, "Wrong clique size");

    mc.cliqueMap(map);

    check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");

    CliqueIt it2(mc);

    check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");

    g.addEdge(u, v);

    check(mc.cliqueSize() == 2, "Wrong clique size");

    mc.cliqueMap(map);

    check(map[u] && map[v], "Wrong clique map");

    CliqueIt it3(mc);

      .nodeMap("max_clique", max_clique)

      .run();

    McAlg mc(g);

    check(mc.cliqueSize() == 4, "Wrong clique size");

    mc.cliqueMap(map);

    for (GR::NodeIt n(g); n != INVALID; ++n) {

      check(map[n] == max_clique[n], "Wrong clique map");

}

// Check with full graphs

template <typename Param>

  typedef FullGraph GR;

  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;

  typedef McAlg::CliqueNodeIt CliqueIt;

  for (int size = 0; size <= 40; size = size * 3 + 1) {

    GR g(size);

    GR::NodeMap<bool> map(g);

    McAlg mc(g);

    check(mc.cliqueSize() == size, "Wrong clique size");

    mc.cliqueMap(map);

    for (GR::NodeIt n(g); n != INVALID; ++n) {

      check(map[n], "Wrong clique map");

}

// Check with grid graphs

template <typename Param>

  GridGraph g(5, 7);

  GridGraph::NodeMap<char> map(g);

  GrossoLocatelliPullanMc<GridGraph> mc(g);

  check(mc.cliqueSize() == 2, "Wrong clique size");

}

int main() {

  return 0;

}