RhodeCode

\code

all_lower_case_with_underscores

\endcode

\subsection pri-loc-var Private member variables

\code

\endcode

\subsection cs-excep Exceptions

When writing exceptions please comply the following naming conventions.

   \ref bunnagel98efficient.

 - \ref CapacityScaling Capacity Scaling algorithm based on the successive

   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

@ingroup algs

  \ref dasdan98minmeancycle.

- \ref HartmannOrlinMmc Hartmann-Orlin's algorithm, which is an improved

  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

typically faster due to the applied early termination scheme.

*/

\image html connected_components.png

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

embedding and drawing.

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///

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

             typename TR = CapacityScalingDefaultTraits<GR, V, C> >

#endif

    /// This function sets a single source node and a single target node

    /// and the required flow value.

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

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

        to.build(from, nodeRefMap, edgeRefMap);

      }

    };

  }

  ///

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

#ifdef DOXYGEN

  template <typename GR>

  bool undirected(const GR& g) { return false; }

#else

  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,

  /// \ref goldberg97efficient, \ref bunnagel98efficient.

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

  ///

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

  /// In most cases, this parameter should not be set directly,

  /// consider to use the named template parameters instead.

  ///

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

#ifdef DOXYGEN

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

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

    ///

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

      /// Local push operations are used, i.e. flow is moved only on one

      /// admissible arc at once.

    /// This function sets a single source node and a single target node

    /// and the required flow value.

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

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

  /// \tparam C The number type used for costs and potentials in the

  /// algorithm. By default, it is the same as \c V.

  ///

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

  template <typename GR, typename V, typename C>

#else

    ///

    /// Enum type containing constants for selecting the used method

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

      /// \ref BellmanFord "Bellman-Ford" algorithm with limited iteration

      /// number for detecting negative cycles in the residual network.

    /// This function sets a single source node and a single target node

    /// and the required flow value.

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

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

///if a (di)graph is \e Eulerian.

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

  ///non-trivial component and the in-degree is equal to the out-degree

  ///for all nodes), then the following code will put the arcs of \c g

  /// \e clique \e problem \ref grosso08maxclique.

  /// It is to find the largest complete subgraph (\e clique) in an

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

  /// rules, from which the most powerful one is used by default.

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

      /// A node of minimum penalty is selected randomly at each step.

      /// The node penalties are updated adaptively after each stage of the

      /// search process.

      PENALTY_BASED

    };

  private:

    TEMPLATE_GRAPH_TYPEDEFS(GR);

    typedef std::vector<int> IntVector;

    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;

    // The best clique found so far

    BoolVector _best_clique;

    /// The global \ref rnd "random number generator instance" is used

    /// during the algorithm.

    ///

    /// \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 graph The undirected graph the algorithm runs on.

    /// \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 graph The undirected graph the algorithm runs on.

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

    ///

    /// This function returns the size of the found clique.

    ///

    };

    /// @}

  private:

    // Adds a node to the current clique

    void addCliqueNode(int u) {

      if (_clique[u]) return;

      _clique[u] = true;

      _size++;

      BoolVector &row = _gr[u];

      _tabu.clear();

      _tabu.resize(_n, false);

    }

    // 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 (restart_nodes.size() > 0) {

          rs_node = restart_nodes[_rnd[restart_nodes.size()]];

          }

          else break;

        }

        if (_size > _best_size) {

          _best_clique = _clique;

          _best_size = _size;

        }

        sel_method.update();

      }

    }

  }; //class GrossoLocatelliPullanMc

  ///@}

  /// \ref amo93networkflows, \ref dantzig63linearprog,

  /// \ref kellyoneill91netsimplex.

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

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

  ///

    /// the \ref run() function.

    ///

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

      /// The \e First \e Eligible pivot rule.

    ///

    /// \param map A node map storing the supply values.

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

      }

      return *this;

    /// This function sets a single source node and a single target node

    /// and the required flow value.

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

    /// \param k The required amount of flow from node \c s to node \c t

    /// (i.e. the supply of \c s and the demand of \c t).

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// path type. It can be indexed in O(1) time. The front and back

  /// insertion and erase is done in O(1) (amortized) time. The

    /// \brief Return whether the path is empty.

    bool empty() const { return head.empty() && tail.empty(); }

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

    }

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// type. It can be indexed in O(1) time. The back insertion and

  /// erasure is amortized O(1) time. This implementation is faster

    /// \brief Return true if the path is empty.

    bool empty() const { return data.empty(); }

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

    }

    /// \brief The first arc of the path.

    const Arc& front() const {

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// path type. It can be indexed in O(k) time, where k is the rank

  /// of the arc in the path. The length can be computed in O(n)

    private:

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

        node = node->next;

      }

      return node->arc;

    }

    ArcIt nthIt(int n) const {

      Node *node = first;

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

        node = node->next;

      }

      return ArcIt(*this, node);

  /// \brief A structure for representing directed paths in a digraph.

  ///

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

  /// or copy assigned from another path, but otherwise it cannot be

  /// modified.

    private:

      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 The length of the path.

    int length() const { return len; }

    return path.empty() ? INVALID : digraph.target(path.back());

  }

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

  /// provide this feature, the underlying digraph should be passed to

  /// the constructor of the iterator.

  "5 7    14\n"

  "6 7    15\n";

// Check with general graphs

template <typename Param>

  typedef ListGraph GR;

  typedef GrossoLocatelliPullanMc<GR> McAlg;

  typedef McAlg::CliqueNodeIt CliqueIt;

  // Basic tests

  {

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

    check(it3 != INVALID && ++it3 != INVALID && ++it3 == INVALID,

          "Wrong CliqueNodeIt");

    std::istringstream input(test_lgf);

    graphReader(g, input)

      .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");

    }

    int cnt = 0;

    check(cnt == 4, "Wrong CliqueNodeIt");

  }

}

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

    }

    int cnt = 0;

    check(cnt == size, "Wrong CliqueNodeIt");

  }

}

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

}