# Changes in /[1025:140c953ad5d1:1026:9312d6c89d02] in lemon

Ignore:
Files:
11 edited

Unmodified
Removed
• ## doc/coding_style.dox

 r463 \subsection pri-loc-var Private member variables Private member variables should start with underscore Private member variables should start with underscore. \code _start_with_underscores _start_with_underscore \endcode
• ## doc/groups.dox

 r999 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. In general NetworkSimplex is the most efficient implementation, but in special cases other algorithms could be faster. In general, \ref NetworkSimplex and \ref CostScaling are the most efficient implementations, but the other two algorithms could be faster in special cases. For example, if the total supply and/or capacities are rather small, CapacityScaling is usually the fastest algorithm (without effective scaling). \ref CapacityScaling is usually the fastest algorithm (without effective scaling). */ \ref dasdan98minmeancycle. In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. /** @defgroup planar Planarity Embedding and Drawing @defgroup planar Planar Embedding and Drawing @ingroup algs \brief Algorithms for planarity checking, embedding and drawing
• ## lemon/capacity_scaling.h

 r1025 /// \warning All input data (capacities, supply values, and costs) must /// be integer. /// \warning This algorithm does not support negative costs for such /// arcs that have infinite upper bound. /// \warning This algorithm does not support negative costs for /// arcs having infinite upper bound. #ifdef DOXYGEN template /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// with a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. ///
• ## lemon/core.h

 r988 } /// Check whether a graph is undirected. /// \brief Check whether a graph is undirected. /// /// This function returns \c true if the given graph is undirected.
• ## lemon/cost_scaling.h

 r1025 /// "preflow push-relabel" algorithm for the maximum flow problem. /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest /// implementations available in LEMON for this problem. /// /// Most of the parameters of the problem (except for the digraph) /// can be given using separate functions, and the algorithm can be /// \warning All input data (capacities, supply values, and costs) must /// be integer. /// \warning This algorithm does not support negative costs for such /// arcs that have infinite upper bound. /// \warning This algorithm does not support negative costs for /// arcs having infinite upper bound. /// /// \note %CostScaling provides three different internal methods, /// relabel operation. /// By default, the so called \ref PARTIAL_AUGMENT /// "Partial Augment-Relabel" method is used, which proved to be /// "Partial Augment-Relabel" method is used, which turned out to be /// the most efficient and the most robust on various test inputs. /// However, the other methods can be selected using the \ref run() /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// with a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. ///
• ## lemon/cycle_canceling.h

 r1025 /// \warning All input data (capacities, supply values, and costs) must /// be integer. /// \warning This algorithm does not support negative costs for such /// arcs that have infinite upper bound. /// \warning This algorithm does not support negative costs for /// arcs having infinite upper bound. /// /// \note For more information about the three available methods, /// \ref CycleCanceling provides three different cycle-canceling /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten" /// is used, which proved to be the most efficient and the most robust /// on various test inputs. /// is used, which is by far the most efficient and the most robust. /// However, the other methods can be selected using the \ref run() /// function with the proper parameter. /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// with a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. ///
• ## lemon/euler.h

 r956 ///Euler tour iterator for digraphs. /// \ingroup graph_prop /// \ingroup graph_properties ///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.
• ## lemon/grosso_locatelli_pullan_mc.h

 r999 /// /// This class provides a simple but highly efficient and robust heuristic /// method that quickly finds a large clique, but not necessarily the /// method that quickly finds a quite large clique, but not necessarily the /// largest one. /// The algorithm performs a certain number of iterations to find several /// cliques and selects the largest one among them. Various limits can be /// specified to control the running time and the effectiveness of the /// search process. /// /// \tparam GR The undirected graph type the algorithm runs on. }; /// \brief Constants for the causes of search termination. /// /// Enum type containing constants for the different causes of search /// termination. The \ref run() function returns one of these values. enum TerminationCause { /// The iteration count limit is reached. ITERATION_LIMIT, /// The step count limit is reached. STEP_LIMIT, /// The clique size limit is reached. SIZE_LIMIT }; private: // Note: vector is used instead of vector for efficiency reasons // The underlying graph const GR &_graph; IntNodeMap _id; BoolMatrix _gr; int _n; // Search options bool _delta_based_restart; int _restart_delta_limit; // Search limits int _iteration_limit; int _step_limit; int _size_limit; // The current clique GrossoLocatelliPullanMc(const GR& graph) : _graph(graph), _id(_graph), _rnd(rnd) {} { initOptions(); } /// \brief Constructor with random seed. GrossoLocatelliPullanMc(const GR& graph, int seed) : _graph(graph), _id(_graph), _rnd(seed) {} { initOptions(); } /// \brief Constructor with random number generator. GrossoLocatelliPullanMc(const GR& graph, const Random& random) : _graph(graph), _id(_graph), _rnd(random) {} { initOptions(); } /// \name Execution Control /// The \ref run() function can be used to execute the algorithm.\n /// The functions \ref iterationLimit(int), \ref stepLimit(int), and /// \ref sizeLimit(int) can be used to specify various limits for the /// search process. /// @{ /// \brief Runs the algorithm. /// /// This function runs the algorithm. /// /// \param step_num The maximum number of node selections (steps) /// during the search process. /// This parameter controls the running time and the success of the /// algorithm. For larger values, the algorithm runs slower but it more /// \brief Sets the maximum number of iterations. /// /// This function sets the maximum number of iterations. /// Each iteration of the algorithm finds a maximal clique (but not /// necessarily the largest one) by performing several search steps /// (node selections). /// /// This limit controls the running time and the success of the /// algorithm. For larger values, the algorithm runs slower, but it more /// likely finds larger cliques. For smaller values, the algorithm is /// faster but probably gives worse results. /// /// The default value is \c 1000. /// \c -1 means that number of iterations is not limited. /// /// \warning You should specify a reasonable limit for the number of /// iterations and/or the number of search steps. /// /// \return (*this) /// /// \sa stepLimit(int) /// \sa sizeLimit(int) GrossoLocatelliPullanMc& iterationLimit(int limit) { _iteration_limit = limit; return *this; } /// \brief Sets the maximum number of search steps. /// /// This function sets the maximum number of elementary search steps. /// Each iteration of the algorithm finds a maximal clique (but not /// necessarily the largest one) by performing several search steps /// (node selections). /// /// This limit controls the running time and the success of the /// algorithm. For larger values, the algorithm runs slower, but it more /// likely finds larger cliques. For smaller values, the algorithm is /// faster but probably gives worse results. /// /// The default value is \c -1, which means that number of steps /// is not limited explicitly. However, the number of iterations is /// limited and each iteration performs a finite number of search steps. /// /// \warning You should specify a reasonable limit for the number of /// iterations and/or the number of search steps. /// /// \return (*this) /// /// \sa iterationLimit(int) /// \sa sizeLimit(int) GrossoLocatelliPullanMc& stepLimit(int limit) { _step_limit = limit; return *this; } /// \brief Sets the desired clique size. /// /// This function sets the desired clique size that serves as a search /// limit. If a clique of this size (or a larger one) is found, then the /// algorithm terminates. /// /// This function is especially useful if you know an exact upper bound /// for the size of the cliques in the graph or if any clique above /// a certain size limit is sufficient for your application. /// /// The default value is \c -1, which means that the size limit is set to /// the number of nodes in the graph. /// /// \return (*this) /// /// \sa iterationLimit(int) /// \sa stepLimit(int) GrossoLocatelliPullanMc& sizeLimit(int limit) { _size_limit = limit; return *this; } /// \brief The maximum number of iterations. /// /// This function gives back the maximum number of iterations. /// \c -1 means that no limit is specified. /// /// \sa iterationLimit(int) int iterationLimit() const { return _iteration_limit; } /// \brief The maximum number of search steps. /// /// This function gives back the maximum number of search steps. /// \c -1 means that no limit is specified. /// /// \sa stepLimit(int) int stepLimit() const { return _step_limit; } /// \brief The desired clique size. /// /// This function gives back the desired clique size that serves as a /// search limit. \c -1 means that this limit is set to the number of /// nodes in the graph. /// /// \sa sizeLimit(int) int sizeLimit() const { return _size_limit; } /// \brief Runs the algorithm. /// /// This function runs the algorithm. If one of the specified limits /// is reached, the search process terminates. /// /// \param rule The node selection rule. For more information, see /// \ref SelectionRule. /// /// \return The size of the found clique. int run(int step_num = 100000, SelectionRule rule = PENALTY_BASED) /// \return The termination cause of the search. For more information, /// see \ref TerminationCause. TerminationCause run(SelectionRule rule = PENALTY_BASED) { init(); switch (rule) { case RANDOM: return start(step_num); return start(); case DEGREE_BASED: return start(step_num); case PENALTY_BASED: return start(step_num); } return 0; // avoid warning return start(); default: return start(); } } /// \name Query Functions /// The results of the algorithm can be obtained using these functions.\n /// The run() function must be called before using them. /// @{ private: // Initialize search options and limits void initOptions() { // Search options _delta_based_restart = true; _restart_delta_limit = 4; // Search limits _iteration_limit = 1000; _step_limit = -1;             // this is disabled by default _size_limit = -1;             // this is disabled by default } // Adds a node to the current clique // Executes the algorithm template int start(int max_select) { // Options for the restart rule const bool delta_based_restart = true; const int restart_delta_limit = 4; if (_n == 0) return 0; TerminationCause start() { if (_n == 0) return SIZE_LIMIT; if (_n == 1) { _best_clique[0] = true; _best_size = 1; return _best_size; } // Iterated local search return SIZE_LIMIT; } // Iterated local search algorithm const int max_size = _size_limit >= 0 ? _size_limit : _n; const int max_restart = _iteration_limit >= 0 ? _iteration_limit : std::numeric_limits::max(); const int max_select = _step_limit >= 0 ? _step_limit : std::numeric_limits::max(); SelectionRuleImpl sel_method(*this); int select = 0; int select = 0, restart = 0; IntVector restart_nodes; while (select < max_select) { while (select < max_select && restart < max_restart) { // Perturbation/restart if (delta_based_restart) { restart++; if (_delta_based_restart) { restart_nodes.clear(); for (int i = 0; i != _n; i++) { if (_delta[i] >= restart_delta_limit) if (_delta[i] >= _restart_delta_limit) restart_nodes.push_back(i); } _best_clique = _clique; _best_size = _size; if (_best_size == _n) return _best_size; if (_best_size >= max_size) return SIZE_LIMIT; } sel_method.update(); } return _best_size; return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT); }
• ## lemon/network_simplex.h

 r1025 /// flow problem. /// /// In general, %NetworkSimplex is the fastest implementation available /// in LEMON for this problem. /// Moreover, it supports both directions of the supply/demand inequality /// constraints. For more information, see \ref SupplyType. /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest /// implementations available in LEMON for this problem. /// Furthermore, this class supports both directions of the supply/demand /// inequality constraints. For more information, see \ref SupplyType. /// /// Most of the parameters of the problem (except for the digraph) /// of the algorithm. /// By default, \ref BLOCK_SEARCH "Block Search" is used, which /// proved to be the most efficient and the most robust on various /// turend out to be the most efficient and the most robust on various /// test inputs. /// However, another pivot rule can be selected using the \ref run() typedef std::vector CostVector; typedef std::vector CharVector; // Note: vector is used instead of vector and // Note: vector is used instead of vector and // vector for efficiency reasons /// /// \return (*this) /// /// \sa supplyType() template NetworkSimplex& supplyMap(const SupplyMap& map) { /// /// Using this function has the same effect as using \ref supplyMap() /// with such a map in which \c k is assigned to \c s, \c -k is /// with a map in which \c k is assigned to \c s, \c -k is /// assigned to \c t and all other nodes have zero supply value. ///
• ## lemon/path.h

 r956 /// /// In a sense, the path can be treated as a list of arcs. The /// lemon path type stores just this list. As a consequence, it /// LEMON path type stores just this list. As a consequence, it /// cannot enumerate the nodes of the path and the source node of /// a zero length path is undefined. void clear() { head.clear(); tail.clear(); } /// \brief The nth arc. /// \brief The n-th arc. /// /// \pre \c n is in the [0..length() - 1] range. } /// \brief Initialize arc iterator to point to the nth arc /// \brief Initialize arc iterator to point to the n-th arc /// /// \pre \c n is in the [0..length() - 1] range. /// /// In a sense, the path can be treated as a list of arcs. The /// lemon path type stores just this list. As a consequence it /// LEMON path type stores just this list. As a consequence it /// cannot enumerate the nodes in the path and the zero length paths /// cannot store the source. void clear() { data.clear(); } /// \brief The nth arc. /// \brief The n-th arc. /// /// \pre \c n is in the [0..length() - 1] range. } /// \brief  Initializes arc iterator to point to the nth arc. /// \brief  Initializes arc iterator to point to the n-th arc. ArcIt nthIt(int n) const { return ArcIt(*this, n); /// /// In a sense, the path can be treated as a list of arcs. The /// lemon path type stores just this list. As a consequence it /// LEMON path type stores just this list. As a consequence it /// cannot enumerate the nodes in the path and the zero length paths /// cannot store the source. }; /// \brief The nth arc. /// /// This function looks for the nth arc in O(n) time. /// \brief The n-th arc. /// /// This function looks for the n-th arc in O(n) time. /// \pre \c n is in the [0..length() - 1] range. const Arc& nth(int n) const { } /// \brief Initializes arc iterator to point to the nth arc. /// \brief Initializes arc iterator to point to the n-th arc. ArcIt nthIt(int n) const { Node *node = first; /// /// In a sense, the path can be treated as a list of arcs. The /// lemon path type stores just this list. As a consequence it /// LEMON path type stores just this list. As a consequence it /// cannot enumerate the nodes in the path and the source node of /// a zero length path is undefined. }; /// \brief The nth arc. /// \brief The n-th arc. /// /// \pre \c n is in the [0..length() - 1] range. } /// \brief The arc iterator pointing to the nth arc. /// \brief The arc iterator pointing to the n-th arc. ArcIt nthIt(int n) const { return ArcIt(*this, n); /// /// In a sense, the path can be treated as a list of arcs. The /// lemon path type stores only this list. As a consequence, it /// LEMON path type stores only this list. As a consequence, it /// cannot enumerate the nodes in the path and the zero length paths /// cannot have a source node.
• ## test/max_clique_test.cc

 r999 // Check with general graphs template void checkMaxCliqueGeneral(int max_sel, Param rule) { void checkMaxCliqueGeneral(Param rule) { typedef ListGraph GR; typedef GrossoLocatelliPullanMc McAlg; GR::NodeMap map(g); McAlg mc(g); check(mc.run(max_sel, rule) == 0, "Wrong clique size"); mc.iterationLimit(50); check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 0, "Wrong clique size"); check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt"); GR::Node u = g.addNode(); check(mc.run(max_sel, rule) == 1, "Wrong clique size"); check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 1, "Wrong clique size"); mc.cliqueMap(map); GR::Node v = g.addNode(); check(mc.run(max_sel, rule) == 1, "Wrong clique size"); check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 1, "Wrong clique size"); mc.cliqueMap(map); g.addEdge(u, v); check(mc.run(max_sel, rule) == 2, "Wrong clique size"); check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 2, "Wrong clique size"); mc.cliqueMap(map); McAlg mc(g); check(mc.run(max_sel, rule) == 4, "Wrong clique size"); mc.iterationLimit(50); check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 4, "Wrong clique size"); mc.cliqueMap(map); // Check with full graphs template void checkMaxCliqueFullGraph(int max_sel, Param rule) { void checkMaxCliqueFullGraph(Param rule) { typedef FullGraph GR; typedef GrossoLocatelliPullanMc McAlg; GR::NodeMap map(g); McAlg mc(g); check(mc.run(max_sel, rule) == size, "Wrong clique size"); check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == size, "Wrong clique size"); mc.cliqueMap(map); // Check with grid graphs template void checkMaxCliqueGridGraph(int max_sel, Param rule) { void checkMaxCliqueGridGraph(Param rule) { GridGraph g(5, 7); GridGraph::NodeMap map(g); GrossoLocatelliPullanMc mc(g); check(mc.run(max_sel, rule) == 2, "Wrong clique size"); mc.iterationLimit(100); check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 2, "Wrong clique size"); mc.stepLimit(100); check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 2, "Wrong clique size"); mc.sizeLimit(2); check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause"); check(mc.cliqueSize() == 2, "Wrong clique size"); } int main() { checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::RANDOM); checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::DEGREE_BASED); checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc::PENALTY_BASED); checkMaxCliqueGeneral(GrossoLocatelliPullanMc::RANDOM); checkMaxCliqueGeneral(GrossoLocatelliPullanMc::DEGREE_BASED); checkMaxCliqueGeneral(GrossoLocatelliPullanMc::PENALTY_BASED); checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::RANDOM); checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::DEGREE_BASED); checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc::PENALTY_BASED); checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::RANDOM); checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::DEGREE_BASED); checkMaxCliqueFullGraph(GrossoLocatelliPullanMc::PENALTY_BASED); checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::RANDOM); checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::DEGREE_BASED); checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc::PENALTY_BASED); checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::RANDOM); checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::DEGREE_BASED); checkMaxCliqueGridGraph(GrossoLocatelliPullanMc::PENALTY_BASED); return 0;
Note: See TracChangeset for help on using the changeset viewer.