# Changes in /[929:65a0521e744e:933:ac5f72c48367] in lemon

Ignore:
Files:
75 edited

Unmodified
Removed

• ## doc/Doxyfile.in

 r379 # Doxyfile 1.5.7.1 # Doxyfile 1.5.9 #--------------------------------------------------------------------------- QT_AUTOBRIEF           = NO MULTILINE_CPP_IS_BRIEF = NO DETAILS_AT_TOP         = YES INHERIT_DOCS           = NO SEPARATE_MEMBER_PAGES  = NO "@abs_top_srcdir@/demo" \ "@abs_top_srcdir@/tools" \ "@abs_top_srcdir@/test/test_tools.h" "@abs_top_srcdir@/test/test_tools.h" \ "@abs_top_builddir@/doc/references.dox" INPUT_ENCODING         = UTF-8 FILE_PATTERNS          = *.h \ SKIP_FUNCTION_MACROS   = YES #--------------------------------------------------------------------------- # Configuration::additions related to external references # Options related to the search engine #--------------------------------------------------------------------------- TAGFILES               = "@abs_top_srcdir@/doc/libstdc++.tag = http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/  "
• ## doc/Makefile.am

 r720 edge_biconnected_components.eps \ node_biconnected_components.eps \ planar.eps \ strongly_connected_components.eps fi html-local: $(DOC_PNG_IMAGES) references.dox: doc/references.bib if test${python_found} = yes; then \ cd doc; \ python @abs_top_srcdir@/scripts/bib2dox.py @abs_top_builddir@/$< >$@; \ cd ..; \ else \ echo; \ echo "Python not found."; \ echo; \ exit 1; \ fi html-local: $(DOC_PNG_IMAGES) references.dox if test${doxygen_found} = yes; then \ cd doc; \
• ## doc/groups.dox

 r762 This group contains the common graph search algorithms, namely \e breadth-first \e search (BFS) and \e depth-first \e search (DFS). \e breadth-first \e search (BFS) and \e depth-first \e search (DFS) \ref clrs01algorithms. */ \brief Algorithms for finding shortest paths. This group contains the algorithms for finding shortest paths in digraphs. This group contains the algorithms for finding shortest paths in digraphs \ref clrs01algorithms. - \ref Dijkstra algorithm for finding shortest paths from a source node This group contains the algorithms for finding minimum cost spanning trees and arborescences. trees and arborescences \ref clrs01algorithms. */ This group contains the algorithms for finding maximum flows and feasible circulations. feasible circulations \ref clrs01algorithms, \ref amo93networkflows. The \e maximum \e flow \e problem is to find a flow of maximum value between LEMON contains several algorithms for solving maximum flow problems: - \ref EdmondsKarp Edmonds-Karp algorithm. - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm. - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees. - \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees. In most cases the \ref Preflow "Preflow" algorithm provides the - \ref EdmondsKarp Edmonds-Karp algorithm \ref edmondskarp72theoretical. - \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm \ref goldberg88newapproach. - \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees \ref dinic70algorithm, \ref sleator83dynamic. - \ref GoldbergTarjan !Preflow push-relabel algorithm with dynamic trees \ref goldberg88newapproach, \ref sleator83dynamic. In most cases the \ref Preflow algorithm provides the fastest method for computing a maximum flow. All implementations also provide functions to query the minimum cut, which is the dual This group contains the algorithms for finding minimum cost flows and circulations. For more information about this problem and its dual solution see \ref min_cost_flow "Minimum Cost Flow Problem". circulations \ref amo93networkflows. For more information about this problem and its dual solution, see \ref min_cost_flow "Minimum Cost Flow Problem". LEMON contains several algorithms for this problem. - \ref NetworkSimplex Primal Network Simplex algorithm with various pivot strategies. - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on cost scaling. - \ref CapacityScaling Successive Shortest %Path algorithm with optional capacity scaling. - \ref CancelAndTighten The Cancel and Tighten algorithm. - \ref CycleCanceling Cycle-Canceling algorithms. pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. - \ref CostScaling Cost Scaling algorithm based on push/augment and relabel operations \ref goldberg90approximation, \ref goldberg97efficient, \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. In general NetworkSimplex is the most efficient implementation, If you want to find minimum cut just between two distinict nodes, see the \ref max_flow "maximum flow problem". */ /** @defgroup min_mean_cycle Minimum Mean Cycle Algorithms @ingroup algs \brief Algorithms for finding minimum mean cycles. This group contains the algorithms for finding minimum mean cycles \ref clrs01algorithms, \ref amo93networkflows. The \e minimum \e mean \e cycle \e problem is to find a directed cycle of minimum mean length (cost) in a digraph. The mean length of a cycle is the average length of its arcs, i.e. the ratio between the total length of the cycle and the number of arcs on it. This problem has an important connection to \e conservative \e length \e functions, too. A length function on the arcs of a digraph is called conservative if and only if there is no directed cycle of negative total length. For an arbitrary length function, the negative of the minimum cycle mean is the smallest \f$\epsilon\f$ value so that increasing the arc lengths uniformly by \f$\epsilon\f$ results in a conservative length function. LEMON contains three algorithms for solving the minimum mean cycle problem: - \ref Karp "Karp"'s original algorithm \ref amo93networkflows, \ref dasdan98minmeancycle. - \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved version of Karp's algorithm \ref dasdan98minmeancycle. - \ref Howard "Howard"'s policy iteration algorithm \ref dasdan98minmeancycle. In practice, the Howard algorithm proved to be by far the most efficient one, though the best known theoretical bound on its running time is exponential. Both Karp and HartmannOrlin algorithms run in time O(ne) and use space O(n2+e), but the latter one is typically faster due to the applied early termination scheme. */ /** @defgroup lp_group Lp and Mip Solvers @defgroup lp_group LP and MIP Solvers @ingroup gen_opt_group \brief Lp and Mip solver interfaces for LEMON. This group contains Lp and Mip solver interfaces for LEMON. The various LP solvers could be used in the same manner with this interface. \brief LP and MIP solver interfaces for LEMON. This group contains LP and MIP solver interfaces for LEMON. Various LP solvers could be used in the same manner with this high-level interface. The currently supported solvers are \ref glpk, \ref clp, \ref cbc, \ref cplex, \ref soplex. */ \brief Skeleton and concept checking classes for graph structures This group contains the skeletons and concept checking classes of LEMON's graph structures and helper classes used to implement these. This group contains the skeletons and concept checking classes of graph structures. */
• ## doc/mainpage.dox

 r705 \section intro Introduction \subsection whatis What is LEMON LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library aimed at combinatorial optimization tasks which often involve in working with graphs. LEMON stands for Library for Efficient Modeling and Optimization in Networks. It is a C++ template library providing efficient implementations of common data structures and algorithms with focus on combinatorial optimization tasks connected mainly with graphs and networks. \subsection howtoread How to read the documentation The project is maintained by the Egerváry Research Group on Combinatorial Optimization \ref egres at the Operations Research Department of the Eötvös Loránd University, Budapest, Hungary. LEMON is also a member of the COIN-OR initiative \ref coinor. \section howtoread How to Read the Documentation If you would like to get to know the library, see LEMON Tutorial. If you are interested in starting to use the library, see the Installation Guide. If you know what you are looking for, then try to find it under the
• ## doc/min_cost_flow.dox

 r710 minimum total cost from a set of supply nodes to a set of demand nodes in a network with capacity constraints (lower and upper bounds) and arc costs. and arc costs \ref amo93networkflows. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)<=0\f$; - \f$\pi(u)\leq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$. - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$. - For all \f$u\in V\f$ nodes: - \f$\pi(u)>=0\f$; - \f$\pi(u)\geq 0\f$; - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$, then \f$\pi(u)=0\f$.
• ## lemon/Makefile.am

 r929 lemon/binomial_heap.h \ lemon/bucket_heap.h \ lemon/capacity_scaling.h \ lemon/cbc.h \ lemon/circulation.h \ lemon/concept_check.h \ lemon/connectivity.h \ lemon/core.h \ lemon/cost_scaling.h \ lemon/counter.h \ lemon/core.h \ lemon/cplex.h \ lemon/cycle_canceling.h \ lemon/dfs.h \ lemon/dheap.h \ lemon/graph_to_eps.h \ lemon/grid_graph.h \ lemon/hartmann_orlin.h \ lemon/howard.h \ lemon/hypercube_graph.h \ lemon/karp.h \ lemon/kruskal.h \ lemon/hao_orlin.h \ lemon/pairing_heap.h \ lemon/path.h \ lemon/planarity.h \ lemon/preflow.h \ lemon/quad_heap.h \ lemon/smart_graph.h \ lemon/soplex.h \ lemon/static_graph.h \ lemon/suurballe.h \ lemon/time_measure.h \

• ## lemon/arg_parser.cc

 r463 namespace lemon { void ArgParser::_terminate(ArgParserException::Reason reason) const { if(_exit_on_problems) exit(1); else throw(ArgParserException(reason)); } void ArgParser::_showHelp(void *p) { (static_cast(p))->showHelp(); exit(1); (static_cast(p))->_terminate(ArgParserException::HELP); } ArgParser::ArgParser(int argc, const char * const *argv) :_argc(argc), _argv(argv), _command_name(argv[0]) { :_argc(argc), _argv(argv), _command_name(argv[0]), _exit_on_problems(true) { funcOption("-help","Print a short help message",_showHelp,this); synonym("help","-help"); i!=_others_help.end();++i) showHelp(i); for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i); exit(1); _terminate(ArgParserException::HELP); } std::cerr << "\nType '" << _command_name << " --help' to obtain a short summary on the usage.\n\n"; exit(1); _terminate(ArgParserException::UNKNOWN_OPT); } std::cerr << "\nType '" << _command_name << " --help' to obtain a short summary on the usage.\n\n"; exit(1); _terminate(ArgParserException::INVALID_OPT); } }
• ## lemon/arg_parser.h

 r463 namespace lemon { ///Exception used by ArgParser class ArgParserException : public Exception { public: enum Reason { HELP,         /// --help option was given UNKNOWN_OPT,  /// Unknown option was given INVALID_OPT   /// Invalid combination of options }; private: Reason _reason; public: ///Constructor ArgParserException(Reason r) throw() : _reason(r) {} ///Virtual destructor virtual ~ArgParserException() throw() {} ///A short description of the exception virtual const char* what() const throw() { switch(_reason) { case HELP: return "lemon::ArgParseException: ask for help"; break; case UNKNOWN_OPT: return "lemon::ArgParseException: unknown option"; break; case INVALID_OPT: return "lemon::ArgParseException: invalid combination of options"; break; } return ""; } ///Return the reason for the failure Reason reason() const {return _reason; } }; ///Command line arguments parser std::string _command_name; private: //Bind a function to an option. const std::string &help, void (*func)(void *),void *data); bool _exit_on_problems; void _terminate(ArgParserException::Reason reason) const; public: const std::vector &files() const { return _file_args; } ///Throw instead of exit in case of problems void throwOnProblems() { _exit_on_problems=false; } }; }

• ## lemon/bfs.h

 r764 ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. ///\tparam GR The type of the digraph the algorithm runs on. ///The default type is \ref ListDigraph. ///\tparam TR The traits class that defines various types used by the ///algorithm. By default, it is \ref BfsDefaultTraits ///"BfsDefaultTraits". ///In most cases, this parameter should not be set directly, ///consider to use the named template parameters instead. #ifdef DOXYGEN template b.run(s) is just a shortcut of the following code. ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. /// This class should only be used through the \ref bfs() function, /// which makes it easier to use the algorithm. /// /// \tparam TR The traits class that defines various types used by the /// algorithm. template class BfsWizard : public TR ///Runs BFS algorithm to visit all nodes in the digraph. ///This method runs BFS algorithm in order to compute ///the shortest path to each node. ///This method runs BFS algorithm in order to visit all nodes ///in the digraph. void run() { /// does not observe the BFS events. If you want to observe the BFS /// events, you should implement your own visitor class. /// \tparam TR Traits class to set various data types used by the /// algorithm. The default traits class is /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits". /// See \ref BfsVisitDefaultTraits for the documentation of /// a BFS visit traits class. /// \tparam TR The traits class that defines various types used by the /// algorithm. By default, it is \ref BfsVisitDefaultTraits /// "BfsVisitDefaultTraits". /// In most cases, this parameter should not be set directly, /// consider to use the named template parameters instead. #ifdef DOXYGEN template /// \brief Runs the algorithm to visit all nodes in the digraph. /// /// This method runs the %BFS algorithm in order to /// compute the shortest path to each node. /// /// The algorithm computes /// - the shortest path tree (forest), /// - the distance of each node from the root(s). /// This method runs the %BFS algorithm in order to visit all nodes /// in the digraph. /// /// \note b.run(s) is just a shortcut of the following code.
• ## lemon/bits/graph_extender.h

 r732 } Node fromId(int id, Node) const { static Node fromId(int id, Node) { return Parent::nodeFromId(id); } Arc fromId(int id, Arc) const { static Arc fromId(int id, Arc) { return Parent::arcFromId(id); } } Node fromId(int id, Node) const { static Node fromId(int id, Node) { return Parent::nodeFromId(id); } Arc fromId(int id, Arc) const { static Arc fromId(int id, Arc) { return Parent::arcFromId(id); } Edge fromId(int id, Edge) const { static Edge fromId(int id, Edge) { return Parent::edgeFromId(id); }
• ## lemon/bits/map_extender.h

 r765 typedef typename Map::Value Value; MapIt() {} MapIt(Invalid i) : Parent(i) { } explicit MapIt(Map& _map) : map(_map) { map.notifier()->first(*this); MapIt() : map(NULL) {} MapIt(Invalid i) : Parent(i), map(NULL) {} explicit MapIt(Map& _map) : map(&_map) { map->notifier()->first(*this); } MapIt(const Map& _map, const Item& item) : Parent(item), map(&_map) {} MapIt& operator++() { map->notifier()->next(*this); return *this; } typename MapTraits::ConstReturnValue operator*() const { return (*map)[*this]; } typename MapTraits::ReturnValue operator*() { return (*map)[*this]; } void set(const Value& value) { map->set(*this, value); } protected: Map* map; }; class ConstMapIt : public Item { typedef Item Parent; public: typedef typename Map::Value Value; ConstMapIt() : map(NULL) {} ConstMapIt(Invalid i) : Parent(i), map(NULL) {} explicit ConstMapIt(Map& _map) : map(&_map) { map->notifier()->first(*this); } ConstMapIt(const Map& _map, const Item& item) : Parent(item), map(_map) {} MapIt& operator++() { map.notifier()->next(*this); ConstMapIt& operator++() { map->notifier()->next(*this); return *this; } } typename MapTraits::ReturnValue operator*() { return map[*this]; } void set(const Value& value) { map.set(*this, value); } protected: Map& map; }; class ConstMapIt : public Item { typedef Item Parent; public: typedef typename Map::Value Value; ConstMapIt() {} ConstMapIt(Invalid i) : Parent(i) { } explicit ConstMapIt(Map& _map) : map(_map) { map.notifier()->first(*this); } ConstMapIt(const Map& _map, const Item& item) : Parent(item), map(_map) {} ConstMapIt& operator++() { map.notifier()->next(*this); return *this; } typename MapTraits::ConstReturnValue operator*() const { return map[*this]; } protected: const Map& map; protected: const Map* map; }; public: ItemIt() {} ItemIt(Invalid i) : Parent(i) { } explicit ItemIt(Map& _map) : map(_map) { map.notifier()->first(*this); ItemIt() : map(NULL) {} ItemIt(Invalid i) : Parent(i), map(NULL) {} explicit ItemIt(Map& _map) : map(&_map) { map->notifier()->first(*this); } ItemIt(const Map& _map, const Item& item) : Parent(item), map(_map) {} : Parent(item), map(&_map) {} ItemIt& operator++() { map.notifier()->next(*this); return *this; } protected: const Map& map; map->notifier()->next(*this); return *this; } protected: const Map* map; }; typedef typename Map::Value Value; MapIt() {} MapIt(Invalid i) : Parent(i) { } explicit MapIt(Map& _map) : map(_map) { map.graph.first(*this); MapIt() : map(NULL) {} MapIt(Invalid i) : Parent(i), map(NULL) { } explicit MapIt(Map& _map) : map(&_map) { map->graph.first(*this); } MapIt(const Map& _map, const Item& item) : Parent(item), map(_map) {} : Parent(item), map(&_map) {} MapIt& operator++() { map.graph.next(*this); map->graph.next(*this); return *this; } typename MapTraits::ConstReturnValue operator*() const { return map[*this]; return (*map)[*this]; } typename MapTraits::ReturnValue operator*() { return map[*this]; return (*map)[*this]; } void set(const Value& value) { map.set(*this, value); } protected: Map& map; map->set(*this, value); } protected: Map* map; }; typedef typename Map::Value Value; ConstMapIt() {} ConstMapIt(Invalid i) : Parent(i) { } explicit ConstMapIt(Map& _map) : map(_map) { map.graph.first(*this); ConstMapIt() : map(NULL) {} ConstMapIt(Invalid i) : Parent(i), map(NULL) { } explicit ConstMapIt(Map& _map) : map(&_map) { map->graph.first(*this); } ConstMapIt(const Map& _map, const Item& item) : Parent(item), map(_map) {} : Parent(item), map(&_map) {} ConstMapIt& operator++() { map.graph.next(*this); map->graph.next(*this); return *this; } typename MapTraits::ConstReturnValue operator*() const { return map[*this]; } protected: const Map& map; return (*map)[*this]; } protected: const Map* map; }; public: ItemIt() {} ItemIt(Invalid i) : Parent(i) { } explicit ItemIt(Map& _map) : map(_map) { map.graph.first(*this); ItemIt() : map(NULL) {} ItemIt(Invalid i) : Parent(i), map(NULL) { } explicit ItemIt(Map& _map) : map(&_map) { map->graph.first(*this); } ItemIt(const Map& _map, const Item& item) : Parent(item), map(_map) {} : Parent(item), map(&_map) {} ItemIt& operator++() { map.graph.next(*this); return *this; } protected: const Map& map; map->graph.next(*this); return *this; } protected: const Map* map; };
• ## lemon/cbc.cc

 r623 } int CbcMip::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { std::vector indexes; std::vector values; for(ExprIterator it = b; it != e; ++it) { indexes.push_back(it->first); values.push_back(it->second); } _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); return _prob->numberRows() - 1; } void CbcMip::_eraseCol(int i) {
• ## lemon/cbc.h

 r623 virtual int _addCol(); virtual int _addRow(); virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i);
• ## lemon/circulation.h

 r762 \tparam SM The type of the supply map. The default map type is \ref concepts::Digraph::NodeMap "GR::NodeMap". \tparam TR The traits class that defines various types used by the algorithm. By default, it is \ref CirculationDefaultTraits "CirculationDefaultTraits". In most cases, this parameter should not be set directly, consider to use the named template parameters instead. */ #ifdef DOXYGEN /// able to automatically created by the algorithm (i.e. the /// digraph and the maximum level should be passed to it). /// However an external elevator object could also be passed to the /// However, an external elevator object could also be passed to the /// algorithm with the \ref elevator(Elevator&) "elevator()" function /// before calling \ref run() or \ref init().
• ## lemon/clp.cc

 r623 } int ClpLp::_addRow(Value l, ExprIterator b, ExprIterator e, Value u) { std::vector indexes; std::vector values; for(ExprIterator it = b; it != e; ++it) { indexes.push_back(it->first); values.push_back(it->second); } _prob->addRow(values.size(), &indexes.front(), &values.front(), l, u); return _prob->numberRows() - 1; } void ClpLp::_eraseCol(int c) {
• ## lemon/clp.h

 r623 virtual int _addCol(); virtual int _addRow(); virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i);
• ## lemon/concepts/digraph.h

 r627 /// \brief Class describing the concept of directed graphs. /// /// This class describes the \ref concept "concept" of the /// immutable directed digraphs. /// This class describes the common interface of all directed /// graphs (digraphs). /// /// Note that actual digraph implementation like @ref ListDigraph or /// @ref SmartDigraph may have several additional functionality. /// Like all concept classes, it only provides an interface /// without any sensible implementation. So any general algorithm for /// directed graphs should compile with this class, but it will not /// run properly, of course. /// An actual digraph implementation like \ref ListDigraph or /// \ref SmartDigraph may have additional functionality. /// /// \sa concept /// \sa Graph class Digraph { private: ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. /// Digraph(const Digraph &) {}; ///\brief Assignment of \ref Digraph "Digraph"s to another ones are ///\e not allowed. Use DigraphCopy() instead. ///Assignment of \ref Digraph "Digraph"s to another ones are ///\e not allowed.  Use DigraphCopy() instead. /// Diraphs are \e not copy constructible. Use DigraphCopy instead. Digraph(const Digraph &) {} /// \brief Assignment of a digraph to another one is \e not allowed. /// Use DigraphCopy instead. void operator=(const Digraph &) {} public: ///\e /// Defalult constructor. /// Defalult constructor. /// /// Default constructor. Digraph() { } /// Class for identifying a node of the digraph /// The node type of the digraph /// This class identifies a node of the digraph. It also serves /// as a base class of the node iterators, /// thus they will convert to this type. /// thus they convert to this type. class Node { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Node() { } /// Copy constructor. Node(const Node&) { } /// Invalid constructor \& conversion. /// This constructor initializes the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Node(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Node) const { return true; } /// Inequality operator /// \sa operator==(Node n) /// /// Inequality operator. bool operator!=(Node) const { return true; } /// Artificial ordering operator. /// To allow the use of digraph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the nodes; this order has nothing to do with the iteration /// ordering of the nodes. bool operator<(Node) const { return false; } }; /// This iterator goes through each node. /// This iterator goes through each node. /// Its usage is quite simple, for example you can count the number /// of nodes in digraph \c g of type \c Digraph like this: }; /// Iterator class for the nodes. /// This iterator goes through each node of the digraph. /// Its usage is quite simple, for example, you can count the number /// of nodes in a digraph \c g of type \c %Digraph like this: ///\code /// int count=0; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. NodeIt() { } /// Copy constructor. /// NodeIt(const NodeIt& n) : Node(n) { } /// Invalid constructor \& conversion. /// Initialize the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. NodeIt(Invalid) { } /// Sets the iterator to the first node. /// Sets the iterator to the first node of \c g. /// NodeIt(const Digraph&) { } /// Node -> NodeIt conversion. /// Sets the iterator to the node of \c the digraph pointed by /// the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first node of the given digraph. /// explicit NodeIt(const Digraph&) { } /// Sets the iterator to the given node. /// Sets the iterator to the given node of the given digraph. /// NodeIt(const Digraph&, const Node&) { } /// Next node. /// Class for identifying an arc of the digraph /// The arc type of the digraph /// This class identifies an arc of the digraph. It also serves /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Arc() { } /// Copy constructor. /// Arc(const Arc&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Arc(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Arc) const { return true; } /// Inequality operator /// \sa operator==(Arc n) /// /// Inequality operator. bool operator!=(Arc) const { return true; } /// Artificial ordering operator. /// To allow the use of digraph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the arcs; this order has nothing to do with the iteration /// ordering of the arcs. bool operator<(Arc) const { return false; } }; /// This iterator goes trough the outgoing arcs of a node. /// Iterator class for the outgoing arcs of a node. /// This iterator goes trough the \e outgoing arcs of a certain node /// of a digraph. /// Its usage is quite simple, for example you can count the number /// Its usage is quite simple, for example, you can count the number /// of outgoing arcs of a node \c n /// in digraph \c g of type \c Digraph as follows. /// in a digraph \c g of type \c %Digraph as follows. ///\code /// int count=0; /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class OutArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. OutArcIt() { } /// Copy constructor. /// OutArcIt(const OutArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. OutArcIt(Invalid) { } /// This constructor sets the iterator to the first outgoing arc. /// This constructor sets the iterator to the first outgoing arc of /// the node. /// Sets the iterator to the first outgoing arc. /// Sets the iterator to the first outgoing arc of the given node. /// OutArcIt(const Digraph&, const Node&) { } /// Arc -> OutArcIt conversion /// Sets the iterator to the value of the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given digraph. /// OutArcIt(const Digraph&, const Arc&) { } ///Next outgoing arc /// Next outgoing arc /// Assign the iterator to the next }; /// This iterator goes trough the incoming arcs of a node. /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming arcs of a certain node /// of a digraph. /// Its usage is quite simple, for example you can count the number /// of outgoing arcs of a node \c n /// in digraph \c g of type \c Digraph as follows. /// Its usage is quite simple, for example, you can count the number /// of incoming arcs of a node \c n /// in a digraph \c g of type \c %Digraph as follows. ///\code /// int count=0; /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count; /// for(Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class InArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. InArcIt() { } /// Copy constructor. /// InArcIt(const InArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. InArcIt(Invalid) { } /// This constructor sets the iterator to first incoming arc. /// This constructor set the iterator to the first incoming arc of /// the node. /// Sets the iterator to the first incoming arc. /// Sets the iterator to the first incoming arc of the given node. /// InArcIt(const Digraph&, const Node&) { } /// Arc -> InArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given digraph. /// InArcIt(const Digraph&, const Arc&) { } /// Next incoming arc /// Assign the iterator to the next inarc of the corresponding node. /// /// Assign the iterator to the next /// incoming arc of the corresponding node. InArcIt& operator++() { return *this; } }; /// This iterator goes through each arc. /// This iterator goes through each arc of a digraph. /// Its usage is quite simple, for example you can count the number /// of arcs in a digraph \c g of type \c Digraph as follows: /// Iterator class for the arcs. /// This iterator goes through each arc of the digraph. /// Its usage is quite simple, for example, you can count the number /// of arcs in a digraph \c g of type \c %Digraph as follows: ///\code /// int count=0; /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count; /// for(Digraph::ArcIt a(g); a!=INVALID; ++a) ++count; ///\endcode class ArcIt : public Arc { /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. ArcIt() { } /// Copy constructor. /// ArcIt(const ArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. ArcIt(Invalid) { } /// This constructor sets the iterator to the first arc. /// This constructor sets the iterator to the first arc of \c g. ///@param g the digraph ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } /// Arc -> ArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first arc. /// Sets the iterator to the first arc of the given digraph. /// explicit ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); } /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given digraph. /// ArcIt(const Digraph&, const Arc&) { } ///Next arc /// Next arc /// Assign the iterator to the next arc. /// ArcIt& operator++() { return *this; } }; ///Gives back the target node of an arc. ///Gives back the target node of an arc. /// /// \brief The source node of the arc. /// /// Returns the source node of the given arc. Node source(Arc) const { return INVALID; } /// \brief The target node of the arc. /// /// Returns the target node of the given arc. Node target(Arc) const { return INVALID; } ///Gives back the source node of an arc. ///Gives back the source node of an arc. /// Node source(Arc) const { return INVALID; } /// \brief Returns the ID of the node. /// \brief The ID of the node. /// /// Returns the ID of the given node. int id(Node) const { return -1; } /// \brief Returns the ID of the arc. /// \brief The ID of the arc. /// /// Returns the ID of the given arc. int id(Arc) const { return -1; } /// \brief Returns the node with the given ID. /// /// \pre The argument should be a valid node ID in the graph. /// \brief The node with the given ID. /// /// Returns the node with the given ID. /// \pre The argument should be a valid node ID in the digraph. Node nodeFromId(int) const { return INVALID; } /// \brief Returns the arc with the given ID. /// /// \pre The argument should be a valid arc ID in the graph. /// \brief The arc with the given ID. /// /// Returns the arc with the given ID. /// \pre The argument should be a valid arc ID in the digraph. Arc arcFromId(int) const { return INVALID; } /// \brief Returns an upper bound on the node IDs. /// \brief An upper bound on the node IDs. /// /// Returns an upper bound on the node IDs. int maxNodeId() const { return -1; } /// \brief Returns an upper bound on the arc IDs. /// \brief An upper bound on the arc IDs. /// /// Returns an upper bound on the arc IDs. int maxArcId() const { return -1; } int maxId(Arc) const { return -1; } /// \brief The opposite node on the arc. /// /// Returns the opposite node on the given arc. Node oppositeNode(Node, Arc) const { return INVALID; } /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. /// It is always the target of the pointed arc. Node baseNode(const InArcIt&) const { return INVALID; } /// Returns the base node of the given outgoing arc iterator /// (i.e. the source node of the corresponding arc). Node baseNode(OutArcIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. /// It is always the source of the pointed arc. Node runningNode(const InArcIt&) const { return INVALID; } /// Returns the running node of the given outgoing arc iterator /// (i.e. the target node of the corresponding arc). Node runningNode(OutArcIt) const { return INVALID; } /// \brief The base node of the iterator. /// /// Gives back the base node of the iterator. /// It is always the source of the pointed arc. Node baseNode(const OutArcIt&) const { return INVALID; } /// Returns the base node of the given incomming arc iterator /// (i.e. the target node of the corresponding arc). Node baseNode(InArcIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Gives back the running node of the iterator. /// It is always the target of the pointed arc. Node runningNode(const OutArcIt&) const { return INVALID; } /// \brief The opposite node on the given arc. /// /// Gives back the opposite node on the given arc. Node oppositeNode(const Node&, const Arc&) const { return INVALID; } /// \brief Reference map of the nodes to type \c T. /// /// Reference map of the nodes to type \c T. /// Returns the running node of the given incomming arc iterator /// (i.e. the source node of the corresponding arc). Node runningNode(InArcIt) const { return INVALID; } /// \brief Standard graph map type for the nodes. /// /// Standard graph map type for the nodes. /// It conforms to the ReferenceMap concept. template class NodeMap : public ReferenceMap { public: ///\e NodeMap(const Digraph&) { } ///\e /// Constructor explicit NodeMap(const Digraph&) { } /// Constructor with given initial value NodeMap(const Digraph&, T) { } }; /// \brief Reference map of the arcs to type \c T. /// /// Reference map of the arcs to type \c T. /// \brief Standard graph map type for the arcs. /// /// Standard graph map type for the arcs. /// It conforms to the ReferenceMap concept. template class ArcMap : public ReferenceMap { public: ///\e ArcMap(const Digraph&) { } ///\e /// Constructor explicit ArcMap(const Digraph&) { } /// Constructor with given initial value ArcMap(const Digraph&, T) { } private: ///Copy constructor
• ## lemon/concepts/graph.h

 r704 ///\ingroup graph_concepts ///\file ///\brief The concept of Undirected Graphs. ///\brief The concept of undirected graphs. #ifndef LEMON_CONCEPTS_GRAPH_H #include #include #include #include /// \ingroup graph_concepts /// /// \brief Class describing the concept of Undirected Graphs. /// \brief Class describing the concept of undirected graphs. /// /// This class describes the common interface of all Undirected /// Graphs. /// This class describes the common interface of all undirected /// graphs. /// /// As all concept describing classes it provides only interface /// without any sensible implementation. So any algorithm for /// undirected graph should compile with this class, but it will not /// Like all concept classes, it only provides an interface /// without any sensible implementation. So any general algorithm for /// undirected graphs should compile with this class, but it will not /// run properly, of course. /// An actual graph implementation like \ref ListGraph or /// \ref SmartGraph may have additional functionality. /// /// The LEMON undirected graphs also fulfill the concept of /// directed graphs (\ref lemon::concepts::Digraph "Digraph /// Concept"). Each edges can be seen as two opposite /// directed arc and consequently the undirected graph can be /// seen as the direceted graph of these directed arcs. The /// Graph has the Edge inner class for the edges and /// the Arc type for the directed arcs. The Arc type is /// convertible to Edge or inherited from it so from a directed /// arc we can get the represented edge. /// The undirected graphs also fulfill the concept of \ref Digraph /// "directed graphs", since each edge can also be regarded as two /// oppositely directed arcs. /// Undirected graphs provide an Edge type for the undirected edges and /// an Arc type for the directed arcs. The Arc type is convertible to /// Edge or inherited from it, i.e. the corresponding edge can be /// obtained from an arc. /// EdgeIt and EdgeMap classes can be used for the edges, while ArcIt /// and ArcMap classes can be used for the arcs (just like in digraphs). /// Both InArcIt and OutArcIt iterates on the same edges but with /// opposite direction. IncEdgeIt also iterates on the same edges /// as OutArcIt and InArcIt, but it is not convertible to Arc, /// only to Edge. /// /// In the sense of the LEMON each edge has a default /// direction (it should be in every computer implementation, /// because the order of edge's nodes defines an /// orientation). With the default orientation we can define that /// the directed arc is forward or backward directed. With the \c /// direction() and \c direct() function we can get the direction /// of the directed arc and we can direct an edge. /// In LEMON, each undirected edge has an inherent orientation. /// Thus it can defined if an arc is forward or backward oriented in /// an undirected graph with respect to this default oriantation of /// the represented edge. /// With the direction() and direct() functions the direction /// of an arc can be obtained and set, respectively. /// /// The EdgeIt is an iterator for the edges. We can use /// the EdgeMap to map values for the edges. The InArcIt and /// OutArcIt iterates on the same edges but with opposite /// direction. The IncEdgeIt iterates also on the same edges /// as the OutArcIt and InArcIt but it is not convertible to Arc just /// to Edge. /// Only nodes and edges can be added to or removed from an undirected /// graph and the corresponding arcs are added or removed automatically. /// /// \sa Digraph class Graph { private: /// Graphs are \e not copy constructible. Use DigraphCopy instead. Graph(const Graph&) {} /// \brief Assignment of a graph to another one is \e not allowed. /// Use DigraphCopy instead. void operator=(const Graph&) {} public: /// \brief The undirected graph should be tagged by the /// UndirectedTag. /// /// The undirected graph should be tagged by the UndirectedTag. This /// tag helps the enable_if technics to make compile time /// Default constructor. Graph() {} /// \brief Undirected graphs should be tagged with \c UndirectedTag. /// /// Undirected graphs should be tagged with \c UndirectedTag. /// /// This tag helps the \c enable_if technics to make compile time /// specializations for undirected graphs. typedef True UndirectedTag; /// \brief The base type of node iterators, /// or in other words, the trivial node iterator. /// /// This is the base type of each node iterator, /// thus each kind of node iterator converts to this. /// More precisely each kind of node iterator should be inherited /// from the trivial node iterator. /// The node type of the graph /// This class identifies a node of the graph. It also serves /// as a base class of the node iterators, /// thus they convert to this type. class Node { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Node() { } /// Copy constructor. Node(const Node&) { } /// Invalid constructor \& conversion. /// This constructor initializes the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Node(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Node) const { return true; } /// Inequality operator /// \sa operator==(Node n) /// /// Inequality operator. bool operator!=(Node) const { return true; } /// Artificial ordering operator. /// To allow the use of graph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. }; /// This iterator goes through each node. /// This iterator goes through each node. /// Its usage is quite simple, for example you can count the number /// of nodes in graph \c g of type \c Graph like this: /// Iterator class for the nodes. /// This iterator goes through each node of the graph. /// Its usage is quite simple, for example, you can count the number /// of nodes in a graph \c g of type \c %Graph like this: ///\code /// int count=0; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. NodeIt() { } /// Copy constructor. /// NodeIt(const NodeIt& n) : Node(n) { } /// Invalid constructor \& conversion. /// Initialize the iterator to be invalid. /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. NodeIt(Invalid) { } /// Sets the iterator to the first node. /// Sets the iterator to the first node of \c g. /// NodeIt(const Graph&) { } /// Node -> NodeIt conversion. /// Sets the iterator to the node of \c the graph pointed by /// the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first node of the given digraph. /// explicit NodeIt(const Graph&) { } /// Sets the iterator to the given node. /// Sets the iterator to the given node of the given digraph. /// NodeIt(const Graph&, const Node&) { } /// Next node. /// The base type of the edge iterators. /// The base type of the edge iterators. /// /// The edge type of the graph /// This class identifies an edge of the graph. It also serves /// as a base class of the edge iterators, /// thus they will convert to this type. class Edge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Edge() { } /// Copy constructor. /// Edge(const Edge&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Edge(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Edge) const { return true; } /// Inequality operator /// \sa operator==(Edge n) /// /// Inequality operator. bool operator!=(Edge) const { return true; } /// Artificial ordering operator. /// To allow the use of graph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the edges; this order has nothing to do with the iteration /// ordering of the edges. bool operator<(Edge) const { return false; } }; /// This iterator goes through each edge. /// This iterator goes through each edge of a graph. /// Its usage is quite simple, for example you can count the number /// of edges in a graph \c g of type \c Graph as follows: /// Iterator class for the edges. /// This iterator goes through each edge of the graph. /// Its usage is quite simple, for example, you can count the number /// of edges in a graph \c g of type \c %Graph as follows: ///\code /// int count=0; /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. EdgeIt() { } /// Copy constructor. /// EdgeIt(const EdgeIt& e) : Edge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. EdgeIt(Invalid) { } /// This constructor sets the iterator to the first edge. /// This constructor sets the iterator to the first edge. EdgeIt(const Graph&) { } /// Edge -> EdgeIt conversion /// Sets the iterator to the value of the trivial iterator. /// This feature necessitates that each time we /// iterate the edge-set, the iteration order is the /// same. /// Sets the iterator to the first edge. /// Sets the iterator to the first edge of the given graph. /// explicit EdgeIt(const Graph&) { } /// Sets the iterator to the given edge. /// Sets the iterator to the given edge of the given graph. /// EdgeIt(const Graph&, const Edge&) { } /// Next edge /// Assign the iterator to the next edge. /// EdgeIt& operator++() { return *this; } }; /// \brief This iterator goes trough the incident undirected /// arcs of a node. /// /// This iterator goes trough the incident edges /// of a certain node of a graph. You should assume that the /// loop arcs will be iterated twice. /// /// Its usage is quite simple, for example you can compute the /// degree (i.e. count the number of incident arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// Iterator class for the incident edges of a node. /// This iterator goes trough the incident undirected edges /// of a certain node of a graph. /// Its usage is quite simple, for example, you can compute the /// degree (i.e. the number of incident edges) of a node \c n /// in a graph \c g of type \c %Graph as follows. /// ///\code /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count; ///\endcode /// /// \warning Loop edges will be iterated twice. class IncEdgeIt : public Edge { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. IncEdgeIt() { } /// Copy constructor. /// IncEdgeIt(const IncEdgeIt& e) : Edge(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. IncEdgeIt(Invalid) { } /// This constructor sets the iterator to first incident arc. /// This constructor set the iterator to the first incident arc of /// the node. /// Sets the iterator to the first incident edge. /// Sets the iterator to the first incident edge of the given node. /// IncEdgeIt(const Graph&, const Node&) { } /// Edge -> IncEdgeIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given edge. /// Sets the iterator to the given edge of the given graph. /// IncEdgeIt(const Graph&, const Edge&) { } /// Next incident arc /// Assign the iterator to the next incident arc /// Next incident edge /// Assign the iterator to the next incident edge /// of the corresponding node. IncEdgeIt& operator++() { return *this; } }; /// The directed arc type. /// The directed arc type. It can be converted to the /// edge or it should be inherited from the undirected /// edge. /// The arc type of the graph /// This class identifies a directed arc of the graph. It also serves /// as a base class of the arc iterators, /// thus they will convert to this type. class Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the object to an undefined value. Arc() { } /// Copy constructor. /// Arc(const Arc&) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the object to be invalid. /// \sa Invalid for more details. Arc(Invalid) { } /// Equality operator /// Equality operator. /// /// Two iterators are equal if and only if they point to the /// same object or both are invalid. /// same object or both are \c INVALID. bool operator==(Arc) const { return true; } /// Inequality operator /// \sa operator==(Arc n) /// /// Inequality operator. bool operator!=(Arc) const { return true; } /// Artificial ordering operator. /// To allow the use of graph descriptors as key type in std::map or /// similar associative container we require this. /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. /// Artificial ordering operator. /// /// \note This operator only has to define some strict ordering of /// the arcs; this order has nothing to do with the iteration /// ordering of the arcs. bool operator<(Arc) const { return false; } /// Converison to Edge /// Converison to \c Edge /// Converison to \c Edge. /// operator Edge() const { return Edge(); } }; /// This iterator goes through each directed arc. /// This iterator goes through each arc of a graph. /// Its usage is quite simple, for example you can count the number /// of arcs in a graph \c g of type \c Graph as follows: /// Iterator class for the arcs. /// This iterator goes through each directed arc of the graph. /// Its usage is quite simple, for example, you can count the number /// of arcs in a graph \c g of type \c %Graph as follows: ///\code /// int count=0; /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count; /// for(Graph::ArcIt a(g); a!=INVALID; ++a) ++count; ///\endcode class ArcIt : public Arc { /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. ArcIt() { } /// Copy constructor. /// ArcIt(const ArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. ArcIt(Invalid) { } /// This constructor sets the iterator to the first arc. /// This constructor sets the iterator to the first arc of \c g. ///@param g the graph ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } /// Arc -> ArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the first arc. /// Sets the iterator to the first arc of the given graph. /// explicit ArcIt(const Graph &g) { ignore_unused_variable_warning(g); } /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given graph. /// ArcIt(const Graph&, const Arc&) { } ///Next arc /// Next arc /// Assign the iterator to the next arc. /// ArcIt& operator++() { return *this; } }; /// This iterator goes trough the outgoing directed arcs of a node. /// This iterator goes trough the \e outgoing arcs of a certain node /// of a graph. /// Its usage is quite simple, for example you can count the number /// Iterator class for the outgoing arcs of a node. /// This iterator goes trough the \e outgoing directed arcs of a /// certain node of a graph. /// Its usage is quite simple, for example, you can count the number /// of outgoing arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// in a graph \c g of type \c %Graph as follows. ///\code /// int count=0; /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; /// for (Digraph::OutArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class OutArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. OutArcIt() { } /// Copy constructor. /// OutArcIt(const OutArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. OutArcIt(Invalid) { } /// This constructor sets the iterator to the first outgoing arc. /// This constructor sets the iterator to the first outgoing arc of /// the node. ///@param n the node ///@param g the graph /// Sets the iterator to the first outgoing arc. /// Sets the iterator to the first outgoing arc of the given node. /// OutArcIt(const Graph& n, const Node& g) { ignore_unused_variable_warning(n); ignore_unused_variable_warning(g); } /// Arc -> OutArcIt conversion /// Sets the iterator to the value of the trivial iterator. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given graph. /// OutArcIt(const Graph&, const Arc&) { } ///Next outgoing arc /// Next outgoing arc /// Assign the iterator to the next }; /// This iterator goes trough the incoming directed arcs of a node. /// This iterator goes trough the \e incoming arcs of a certain node /// of a graph. /// Its usage is quite simple, for example you can count the number /// of outgoing arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// Iterator class for the incoming arcs of a node. /// This iterator goes trough the \e incoming directed arcs of a /// certain node of a graph. /// Its usage is quite simple, for example, you can count the number /// of incoming arcs of a node \c n /// in a graph \c g of type \c %Graph as follows. ///\code /// int count=0; /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count; /// for (Digraph::InArcIt a(g, n); a!=INVALID; ++a) ++count; ///\endcode class InArcIt : public Arc { public: /// Default constructor /// @warning The default constructor sets the iterator /// to an undefined value. /// Default constructor. /// \warning It sets the iterator to an undefined value. InArcIt() { } /// Copy constructor. /// InArcIt(const InArcIt& e) : Arc(e) { } /// Initialize the iterator to be invalid. /// Initialize the iterator to be invalid. /// /// %Invalid constructor \& conversion. /// Initializes the iterator to be invalid. /// \sa Invalid for more details. InArcIt(Invalid) { } /// This constructor sets the iterator to first incoming arc. /// This constructor set the iterator to the first incoming arc of /// the node. ///@param n the node ///@param g the graph /// Sets the iterator to the first incoming arc. /// Sets the iterator to the first incoming arc of the given node. /// InArcIt(const Graph& g, const Node& n) { ignore_unused_variable_warning(n); ignore_unused_variable_warning(g); } /// Arc -> InArcIt conversion /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. /// Sets the iterator to the given arc. /// Sets the iterator to the given arc of the given graph. /// InArcIt(const Graph&, const Arc&) { } /// Next incoming arc /// Assign the iterator to the next inarc of the corresponding node. /// /// Assign the iterator to the next /// incoming arc of the corresponding node. InArcIt& operator++() { return *this; } }; /// \brief Reference map of the nodes to type \c T. /// /// Reference map of the nodes to type \c T. /// \brief Standard graph map type for the nodes. /// /// Standard graph map type for the nodes. /// It conforms to the ReferenceMap concept. template class NodeMap : public ReferenceMap public: ///\e NodeMap(const Graph&) { } ///\e /// Constructor explicit NodeMap(const Graph&) { } /// Constructor with given initial value NodeMap(const Graph&, T) { } }; /// \brief Reference map of the arcs to type \c T. /// /// Reference map of the arcs to type \c T. /// \brief Standard graph map type for the arcs. /// /// Standard graph map type for the arcs. /// It conforms to the ReferenceMap concept. template class ArcMap : public ReferenceMap public: ///\e ArcMap(const Graph&) { } ///\e /// Constructor explicit ArcMap(const Graph&) { } /// Constructor with given initial value ArcMap(const Graph&, T) { } private: ///Copy constructor }; /// Reference map of the edges to type \c T. /// Reference map of the edges to type \c T. /// \brief Standard graph map type for the edges. /// /// Standard graph map type for the edges. /// It conforms to the ReferenceMap concept. template class EdgeMap : public ReferenceMap public: ///\e EdgeMap(const Graph&) { } ///\e /// Constructor explicit EdgeMap(const Graph&) { } /// Constructor with given initial value EdgeMap(const Graph&, T) { } private: ///Copy constructor }; /// \brief Direct the given edge. /// /// Direct the given edge. The returned arc source /// will be the given node. Arc direct(const Edge&, const Node&) const { return INVALID; } /// \brief Direct the given edge. /// /// Direct the given edge. The returned arc /// represents the given edge and the direction comes /// from the bool parameter. The source of the edge and /// the directed arc is the same when the given bool is true. Arc direct(const Edge&, bool) const { return INVALID; } /// \brief Returns true if the arc has default orientation. /// /// Returns whether the given directed arc is same orientation as /// the corresponding edge's default orientation. bool direction(Arc) const { return true; } /// \brief Returns the opposite directed arc. /// /// Returns the opposite directed arc. Arc oppositeArc(Arc) const { return INVALID; } /// \brief Opposite node on an arc /// /// \return The opposite of the given node on the given edge. Node oppositeNode(Node, Edge) const { return INVALID; } /// \brief First node of the edge. /// /// \return The first node of the given edge. /// /// Naturally edges don't have direction and thus /// don't have source and target node. However we use \c u() and \c v() /// methods to query the two nodes of the arc. The direction of the /// arc which arises this way is called the inherent direction of the /// edge, and is used to define the "default" direction /// of the directed versions of the arcs. /// \brief The first node of the edge. /// /// Returns the first node of the given edge. /// /// Edges don't have source and target nodes, however, methods /// u() and v() are used to query the two end-nodes of an edge. /// The orientation of an edge that arises this way is called /// the inherent direction, it is used to define the default /// direction for the corresponding arcs. /// \sa v() /// \sa direction() Node u(Edge) const { return INVALID; } /// \brief Second node of the edge. /// /// \return The second node of the given edge. /// /// Naturally edges don't have direction and thus /// don't have source and target node. However we use \c u() and \c v() /// methods to query the two nodes of the arc. The direction of the /// arc which arises this way is called the inherent direction of the /// edge, and is used to define the "default" direction /// of the directed versions of the arcs. /// \brief The second node of the edge. /// /// Returns the second node of the given edge. /// /// Edges don't have source and target nodes, however, methods /// u() and v() are used to query the two end-nodes of an edge. /// The orientation of an edge that arises this way is called /// the inherent direction, it is used to define the default /// direction for the corresponding arcs. /// \sa u() /// \sa direction() Node v(Edge) const { return INVALID; } /// \brief Source node of the directed arc. /// \brief The source node of the arc. /// /// Returns the source node of the given arc. Node source(Arc) const { return INVALID; } /// \brief Target node of the directed arc. /// \brief The target node of the arc. /// /// Returns the target node of the given arc. Node target(Arc) const { return INVALID; } /// \brief Returns the id of the node. /// \brief The ID of the node. /// /// Returns the ID of the given node. int id(Node) const { return -1; } /// \brief Returns the id of the edge. /// \brief The ID of the edge. /// /// Returns the ID of the given edge. int id(Edge) const { return -1; } /// \brief Returns the id of the arc. /// \brief The ID of the arc. /// /// Returns the ID of the given arc. int id(Arc) const { return -1; } /// \brief Returns the node with the given id. /// /// \pre The argument should be a valid node id in the graph. /// \brief The node with the given ID. /// /// Returns the node with the given ID. /// \pre The argument should be a valid node ID in the graph. Node nodeFromId(int) const { return INVALID; } /// \brief Returns the edge with the given id. /// /// \pre The argument should be a valid edge id in the graph. /// \brief The edge with the given ID. /// /// Returns the edge with the given ID. /// \pre The argument should be a valid edge ID in the graph. Edge edgeFromId(int) const { return INVALID; } /// \brief Returns the arc with the given id. /// /// \pre The argument should be a valid arc id in the graph. /// \brief The arc with the given ID. /// /// Returns the arc with the given ID. /// \pre The argument should be a valid arc ID in the graph. Arc arcFromId(int) const { return INVALID; } /// \brief Returns an upper bound on the node IDs. /// \brief An upper bound on the node IDs. /// /// Returns an upper bound on the node IDs. int maxNodeId() const { return -1; } /// \brief Returns an upper bound on the edge IDs. /// \brief An upper bound on the edge IDs. /// /// Returns an upper bound on the edge IDs. int maxEdgeId() const { return -1; } /// \brief Returns an upper bound on the arc IDs. /// \brief An upper bound on the arc IDs. /// /// Returns an upper bound on the arc IDs. int maxArcId() const { return -1; } /// \brief The direction of the arc. /// /// Returns \c true if the direction of the given arc is the same as /// the inherent orientation of the represented edge. bool direction(Arc) const { return true; } /// \brief Direct the edge. /// /// Direct the given edge. The returned arc /// represents the given edge and its direction comes /// from the bool parameter. If it is \c true, then the direction /// of the arc is the same as the inherent orientation of the edge. Arc direct(Edge, bool) const { return INVALID; } /// \brief Direct the edge. /// /// Direct the given edge. The returned arc represents the given /// edge and its source node is the given node. Arc direct(Edge, Node) const { return INVALID; } /// \brief The oppositely directed arc. /// /// Returns the oppositely directed arc representing the same edge. Arc oppositeArc(Arc) const { return INVALID; } /// \brief The opposite node on the edge. /// /// Returns the opposite node on the given edge. Node oppositeNode(Node, Edge) const { return INVALID; } void first(Node&) const {} int maxId(Arc) const { return -1; } /// \brief Base node of the iterator /// /// Returns the base node (the source in this case) of the iterator Node baseNode(OutArcIt e) const { return source(e); } /// \brief Running node of the iterator /// /// Returns the running node (the target in this case) of the /// iterator Node runningNode(OutArcIt e) const { return target(e); } /// \brief Base node of the iterator /// /// Returns the base node (the target in this case) of the iterator Node baseNode(InArcIt e) const { return target(e); } /// \brief Running node of the iterator /// /// Returns the running node (the source in this case) of the /// iterator Node runningNode(InArcIt e) const { return source(e); } /// \brief Base node of the iterator /// /// Returns the base node of the iterator Node baseNode(IncEdgeIt) const { return INVALID; } /// \brief Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(IncEdgeIt) const { return INVALID; } /// \brief The base node of the iterator. /// /// Returns the base node of the given incident edge iterator. Node baseNode(IncEdgeIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Returns the running node of the given incident edge iterator. Node runningNode(IncEdgeIt) const { return INVALID; } /// \brief The base node of the iterator. /// /// Returns the base node of the given outgoing arc iterator /// (i.e. the source node of the corresponding arc). Node baseNode(OutArcIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Returns the running node of the given outgoing arc iterator /// (i.e. the target node of the corresponding arc). Node runningNode(OutArcIt) const { return INVALID; } /// \brief The base node of the iterator. /// /// Returns the base node of the given incomming arc iterator /// (i.e. the target node of the corresponding arc). Node baseNode(InArcIt) const { return INVALID; } /// \brief The running node of the iterator. /// /// Returns the running node of the given incomming arc iterator /// (i.e. the source node of the corresponding arc). Node runningNode(InArcIt) const { return INVALID; } template
• ## lemon/concepts/graph_components.h

 r713 ///\ingroup graph_concepts ///\file ///\brief The concept of graph components. ///\brief The concepts of graph components. #ifndef LEMON_CONCEPTS_GRAPH_COMPONENTS_H /// associative containers (e.g. \c std::map). /// /// \note This operator only have to define some strict ordering of /// \note This operator only has to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items.
• ## lemon/concepts/heap.h

 r757 /// handle the cross references. The assigned value must be /// \c PRE_HEAP (-1) for each item. #ifdef DOXYGEN explicit Heap(ItemIntMap &map) {} #else explicit Heap(ItemIntMap&) {} #endif /// \brief Constructor. /// \c PRE_HEAP (-1) for each item. /// \param comp The function object used for comparing the priorities. #ifdef DOXYGEN explicit Heap(ItemIntMap &map, const CMP &comp) {} #else explicit Heap(ItemIntMap&, const CMP&) {} #endif /// \brief The number of items stored in the heap. /// \param p The priority of the item. /// \pre \e i must not be stored in the heap. #ifdef DOXYGEN void push(const Item &i, const Prio &p) {} #else void push(const Item&, const Prio&) {} #endif /// \brief Return the item having minimum priority. /// This function returns the item having minimum priority. /// \pre The heap must be non-empty. Item top() const {} Item top() const { return Item(); } /// \brief The minimum priority. /// This function returns the minimum priority. /// \pre The heap must be non-empty. Prio prio() const {} Prio prio() const { return Prio(); } /// \brief Remove the item having minimum priority. /// \param i The item to delete. /// \pre \e i must be in the heap. #ifdef DOXYGEN void erase(const Item &i) {} #else void erase(const Item&) {} #endif /// \brief The priority of the given item. /// \param i The item. /// \pre \e i must be in the heap. #ifdef DOXYGEN Prio operator[](const Item &i) const {} #else Prio operator[](const Item&) const { return Prio(); } #endif /// \brief Set the priority of an item or insert it, if it is /// \param i The item. /// \param p The priority. #ifdef DOXYGEN void set(const Item &i, const Prio &p) {} #else void set(const Item&, const Prio&) {} #endif /// \brief Decrease the priority of an item to the given value. /// \param p The priority. /// \pre \e i must be stored in the heap with priority at least \e p. #ifdef DOXYGEN void decrease(const Item &i, const Prio &p) {} #else void decrease(const Item&, const Prio&) {} #endif /// \brief Increase the priority of an item to the given value. /// \param p The priority. /// \pre \e i must be stored in the heap with priority at most \e p. #ifdef DOXYGEN void increase(const Item &i, const Prio &p) {} #else void increase(const Item&, const Prio&) {} #endif /// \brief Return the state of an item. /// to the heap again. /// \param i The item. #ifdef DOXYGEN State state(const Item &i) const {} #else State state(const Item&) const { return PRE_HEAP; } #endif /// \brief Set the state of an item in the heap. /// \param i The item. /// \param st The state. It should not be \c IN_HEAP. #ifdef DOXYGEN void state(const Item& i, State st) {} #else void state(const Item&, State) {} #endif
• ## lemon/concepts/path.h

 r606 ///\ingroup concept ///\file ///\brief Classes for representing paths in digraphs. ///\brief The concept of paths /// /// A skeleton structure for representing directed paths in a /// digraph. /// In a sense, a path can be treated as a list of arcs. /// LEMON path types just store this list. As a consequence, they cannot /// enumerate the nodes on the path directly and a zero length path /// cannot store its source node. /// /// The arcs of a path should be stored in the order of their directions, /// i.e. the target node of each arc should be the same as the source /// node of the next arc. This consistency could be checked using /// \ref checkPath(). /// The source and target nodes of a (consistent) path can be obtained /// using \ref pathSource() and \ref pathTarget(). /// /// A path can be constructed from another path of any type using the /// copy constructor or the assignment operator. /// /// \tparam GR The digraph type in which the path is. /// /// 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 /// cannot enumerate the nodes in the path and the zero length /// paths cannot store the source. /// template class Path { Path() {} /// \brief Template constructor /// \brief Template copy constructor template Path(const CPath& cpath) {} /// \brief Template assigment /// \brief Template assigment operator template Path& operator=(const CPath& cpath) { } /// Length of the path ie. the number of arcs in the path. /// Length of the path, i.e. the number of arcs on the path. int length() const { return 0;} void clear() {} /// \brief LEMON style iterator for path arcs /// \brief LEMON style iterator for enumerating the arcs of a path. /// /// This class is used to iterate on the arcs of the paths. /// LEMON style iterator class for enumerating the arcs of a path. class ArcIt { public: /// Invalid constructor ArcIt(Invalid) {} /// Constructor for first arc /// Sets the iterator to the first arc of the given path ArcIt(const Path &) {} /// Conversion to Arc /// Conversion to \c Arc operator Arc() const { return INVALID; } /// /// A skeleton structure for path dumpers. The path dumpers are /// the generalization of the paths. The path dumpers can /// enumerate the arcs of the path wheter in forward or in /// backward order.  In most time these classes are not used /// directly rather it used to assign a dumped class to a real /// path type. /// the generalization of the paths, they can enumerate the arcs /// of the path either in forward or in backward order. /// These classes are typically not used directly, they are rather /// used to be assigned to a real path type. /// /// The main purpose of this concept is that the shortest path /// algorithms can enumerate easily the arcs in reverse order. /// If we would like to give back a real path from these /// algorithms then we should create a temporarly path object. In /// LEMON such algorithms gives back a path dumper what can /// assigned to a real path and the dumpers can be implemented as /// algorithms can enumerate the arcs easily in reverse order. /// In LEMON, such algorithms give back a (reverse) path dumper that /// can be assigned to a real path. The dumpers can be implemented as /// an adaptor class to the predecessor map. /// /// \tparam GR The digraph type in which the path is. /// /// The paths can be constructed from any path type by a /// template constructor or a template assignment operator. template class PathDumper { typedef typename Digraph::Arc Arc; /// Length of the path ie. the number of arcs in the path. /// Length of the path, i.e. the number of arcs on the path. int length() const { return 0;} /// \brief Forward or reverse dumping /// /// If the RevPathTag is defined and true then reverse dumping /// is provided in the path dumper. In this case instead of the /// ArcIt the RevArcIt iterator should be implemented in the /// dumper. /// If this tag is defined to be \c True, then reverse dumping /// is provided in the path dumper. In this case, \c RevArcIt /// iterator should be implemented instead of \c ArcIt iterator. typedef False RevPathTag; /// \brief LEMON style iterator for path arcs /// \brief LEMON style iterator for enumerating the arcs of a path. /// /// This class is used to iterate on the arcs of the paths. /// LEMON style iterator class for enumerating the arcs of a path. class ArcIt { public: /// Invalid constructor ArcIt(Invalid) {} /// Constructor for first arc /// Sets the iterator to the first arc of the given path ArcIt(const PathDumper&) {} /// Conversion to Arc /// Conversion to \c Arc operator Arc() const { return INVALID; } }; /// \brief LEMON style iterator for path arcs /// \brief LEMON style iterator for enumerating the arcs of a path /// in reverse direction. /// /// This class is used to iterate on the arcs of the paths in /// reverse direction. /// LEMON style iterator class for enumerating the arcs of a path /// in reverse direction. class RevArcIt { public: /// Invalid constructor RevArcIt(Invalid) {} /// Constructor for first arc /// Sets the iterator to the last arc of the given path RevArcIt(const PathDumper &) {} /// Conversion to Arc /// Conversion to \c Arc operator Arc() const { return INVALID; }
• ## lemon/counter.h

 r463 /// 'Do nothing' version of Counter. /// This class can be used in the same way as \ref Counter however it /// This class can be used in the same way as \ref Counter, but it /// does not count at all and does not print report on destruction. ///
• ## lemon/cplex.cc

 r623 } int CplexBase::_addRow(Value lb, ExprIterator b, ExprIterator e, Value ub) { int i = CPXgetnumrows(cplexEnv(), _prob); if (lb == -INF) { const char s = 'L'; CPXnewrows(cplexEnv(), _prob, 1, &ub, &s, 0, 0); } else if (ub == INF) { const char s = 'G'; CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); } else if (lb == ub){ const char s = 'E'; CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, 0, 0); } else { const char s = 'R'; double len = ub - lb; CPXnewrows(cplexEnv(), _prob, 1, &lb, &s, &len, 0); } std::vector indices; std::vector rowlist; std::vector values; for(ExprIterator it=b; it!=e; ++it) { indices.push_back(it->first); values.push_back(it->second); rowlist.push_back(i); } CPXchgcoeflist(cplexEnv(), _prob, values.size(), &rowlist.front(), &indices.front(), &values.front()); return i; } void CplexBase::_eraseCol(int i) {
• ## lemon/cplex.h

 r623 virtual int _addCol(); virtual int _addRow(); virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i);
• ## lemon/dfs.h

 r764 ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. ///\tparam GR The type of the digraph the algorithm runs on. ///The default type is \ref ListDigraph. ///\tparam TR The traits class that defines various types used by the ///algorithm. By default, it is \ref DfsDefaultTraits ///"DfsDefaultTraits". ///In most cases, this parameter should not be set directly, ///consider to use the named template parameters instead. #ifdef DOXYGEN template d.run() is just a shortcut of the following code. ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. /// This class should only be used through the \ref dfs() function, /// which makes it easier to use the algorithm. /// /// \tparam TR The traits class that defines various types used by the /// algorithm. template class DfsWizard : public TR ///Runs DFS algorithm to visit all nodes in the digraph. ///This method runs DFS algorithm in order to compute ///the DFS path to each node. ///This method runs DFS algorithm in order to visit all nodes ///in the digraph. void run() { /// does not observe the DFS events. If you want to observe the DFS /// events, you should implement your own visitor class. /// \tparam TR Traits class to set various data types used by the /// algorithm. The default traits class is /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits". /// See \ref DfsVisitDefaultTraits for the documentation of /// a DFS visit traits class. /// \tparam TR The traits class that defines various types used by the /// algorithm. By default, it is \ref DfsVisitDefaultTraits /// "DfsVisitDefaultTraits". /// In most cases, this parameter should not be set directly, /// consider to use the named template parameters instead. #ifdef DOXYGEN template /// \brief Runs the algorithm to visit all nodes in the digraph. /// This method runs the %DFS algorithm in order to /// compute the %DFS path to each node. /// /// The algorithm computes /// - the %DFS tree (forest), /// - the distance of each node from the root(s) in the %DFS tree. /// This method runs the %DFS algorithm in order to visit all nodes /// in the digraph. /// /// \note d.run() is just a shortcut of the following code.
• ## lemon/dijkstra.h

 r764 ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a \c ProcessedMap. ///it is necessary. The default map type is \ref ///concepts::Digraph::ArcMap "GR::ArcMap". ///\tparam TR The traits class that defines various types used by the ///algorithm. By default, it is \ref DijkstraDefaultTraits ///"DijkstraDefaultTraits". ///In most cases, this parameter should not be set directly, ///consider to use the named template parameters instead. #ifdef DOXYGEN template ///The type of the arc lengths. typedef typename TR::LengthMap::Value Value; typedef typename TR::Value Value; ///The type of the map that stores the arc lengths. typedef typename TR::LengthMap LengthMap; ///passed to the constructor of the cross reference and the cross ///reference should be passed to the constructor of the heap). ///However external heap and cross reference objects could also be ///However, external heap and cross reference objects could also be ///passed to the algorithm using the \ref heap() function before ///calling \ref run(Node) "run()" or \ref init(). ///\ref named-templ-param "Named parameter" for setting ///\c OperationTraits type. /// For more information see \ref DijkstraDefaultOperationTraits. /// For more information, see \ref DijkstraDefaultOperationTraits. template struct SetOperationTraits ///The type of the map that indicates which nodes are processed. ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. ///By default, it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. /// This class should only be used through the \ref dijkstra() function, /// which makes it easier to use the algorithm. /// /// \tparam TR The traits class that defines various types used by the /// algorithm. template class DijkstraWizard : public TR
• ## lemon/edge_set.h

 r717 /// all arcs incident to the given node is erased from the arc set. /// /// This class fully conforms to the \ref concepts::Digraph /// "Digraph" concept. /// It provides only linear time counting for nodes and arcs. /// /// \param GR The type of the graph which shares its node set with /// this class. Its interface must conform to the /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" /// concept. /// /// This class fully conforms to the \ref concepts::Digraph /// "Digraph" concept. template class ListArcSet : public ArcSetExtender > { /// incident to the given node is erased from the arc set. /// /// This class fully conforms to the \ref concepts::Graph "Graph" /// concept. /// It provides only linear time counting for nodes, edges and arcs. /// /// \param GR The type of the graph which shares its node set /// with this class. Its interface must conform to the /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph" /// concept. /// /// This class fully conforms to the \ref concepts::Graph "Graph" /// concept. template } void next(Arc& arc) const { static void next(Arc& arc) { --arc.id; } /// arcs. Therefore the arcs cannot be erased from the arc sets. /// /// This class fully conforms to the \ref concepts::Digraph "Digraph" /// concept. /// It provides only linear time counting for nodes and arcs. /// /// \warning If a node is erased from the underlying graph and this /// node is the source or target of one arc in the arc set, then /// the arc set is invalidated, and it cannot be used anymore. The /// validity can be checked with the \c valid() member function. /// /// This class fully conforms to the \ref concepts::Digraph /// "Digraph" concept. template class SmartArcSet : public ArcSetExtender > { } void next(Arc& arc) const { static void next(Arc& arc) { --arc.id; } } void next(Edge& arc) const { static void next(Edge& arc) { --arc.id; } /// edges cannot be erased from the edge sets. /// /// This class fully conforms to the \ref concepts::Graph "Graph" /// concept. /// It provides only linear time counting for nodes, edges and arcs. /// /// \warning If a node is erased from the underlying graph and this /// node is incident to one edge in the edge set, then the edge set /// is invalidated, and it cannot be used anymore. The validity can /// be checked with the \c valid() member function. /// /// This class fully conforms to the \ref concepts::Graph /// "Graph" concept. template class SmartEdgeSet : public EdgeSetExtender > {
• ## lemon/full_graph.h

 r664 ///\ingroup graphs ///\file ///\brief FullGraph and FullDigraph classes. ///\brief FullDigraph and FullGraph classes. namespace lemon { Node operator()(int ix) const { return Node(ix); } int index(const Node& node) const { return node._id; } static int index(const Node& node) { return node._id; } Arc arc(const Node& s, const Node& t) const { /// \ingroup graphs /// /// \brief A full digraph class. /// /// This is a simple and fast directed full graph implementation. /// From each node go arcs to each node (including the source node), /// therefore the number of the arcs in the digraph is the square of /// the node number. This digraph type is completely static, so you /// can neither add nor delete either arcs or nodes, and it needs /// constant space in memory. /// /// This class fully conforms to the \ref concepts::Digraph /// "Digraph concept". /// /// The \c FullDigraph and \c FullGraph classes are very similar, /// \brief A directed full graph class. /// /// FullDigraph is a simple and fast implmenetation of directed full /// (complete) graphs. It contains an arc from each node to each node /// (including a loop for each node), therefore the number of arcs /// is the square of the number of nodes. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or arcs, however /// the structure can be resized using resize(). /// /// This type fully conforms to the \ref concepts::Digraph "Digraph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// This class provides constant time counting for nodes and arcs. /// /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While this class conforms only /// to the \ref concepts::Digraph "Digraph" concept, the \c FullGraph /// class conforms to the \ref concepts::Graph "Graph" concept, /// moreover \c FullGraph does not contain a loop arc for each /// node as \c FullDigraph does. /// to the \ref concepts::Digraph "Digraph" concept, FullGraph /// conforms to the \ref concepts::Graph "Graph" concept, /// moreover FullGraph does not contain a loop for each /// node as this class does. /// /// \sa FullGraph public: /// \brief Constructor /// \brief Default constructor. /// /// Default constructor. The number of nodes and arcs will be zero. FullDigraph() { construct(0); } /// \brief Resizes the digraph /// /// Resizes the digraph. The function will fully destroy and /// rebuild the digraph. This cause that the maps of the digraph will /// This function resizes the digraph. It fully destroys and /// rebuilds the structure, therefore the maps of the digraph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Since it is a static /// digraph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the given node. /// /// Returns the index of the given node. Since it is a static /// digraph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// \sa operator() int index(const Node& node) const { return Parent::index(node); } /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. /// \sa operator()() static int index(const Node& node) { return Parent::index(node); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& u, const Node& v) const { Arc arc(Node u, Node v) const { return Parent::arc(u, v); } Node operator()(int ix) const { return Node(ix); } int index(const Node& node) const { return node._id; } static int index(const Node& node) { return node._id; } Edge edge(const Node& u, const Node& v) const { /// \brief An undirected full graph class. /// /// This is a simple and fast undirected full graph /// implementation. From each node go edge to each other node, /// therefore the number of edges in the graph is \f$n(n-1)/2\f$. /// This graph type is completely static, so you can neither /// add nor delete either edges or nodes, and it needs constant /// space in memory. /// /// This class fully conforms to the \ref concepts::Graph "Graph concept". /// /// The \c FullGraph and \c FullDigraph classes are very similar, /// but there are two differences. While the \c FullDigraph class /// FullGraph is a simple and fast implmenetation of undirected full /// (complete) graphs. It contains an edge between every distinct pair /// of nodes, therefore the number of edges is n(n-1)/2. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges, however /// the structure can be resized using resize(). /// /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// This class provides constant time counting for nodes, edges and arcs. /// /// \note FullDigraph and FullGraph classes are very similar, /// but there are two differences. While FullDigraph /// conforms only to the \ref concepts::Digraph "Digraph" concept, /// this class conforms to the \ref concepts::Graph "Graph" concept, /// moreover \c FullGraph does not contain a loop arc for each /// node as \c FullDigraph does. /// moreover this class does not contain a loop for each /// node as FullDigraph does. /// /// \sa FullDigraph public: /// \brief Constructor /// \brief Default constructor. /// /// Default constructor. The number of nodes and edges will be zero. FullGraph() { construct(0); } /// \brief Resizes the graph /// /// Resizes the graph. The function will fully destroy and /// rebuild the graph. This cause that the maps of the graph will /// This function resizes the graph. It fully destroys and /// rebuilds the structure, therefore the maps of the graph will be /// reallocated automatically and the previous values will be lost. void resize(int n) { /// \brief Returns the node with the given index. /// /// Returns the node with the given index. Since it is a static /// graph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// Returns the node with the given index. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. /// \sa index() Node operator()(int ix) const { return Parent::operator()(ix); } /// \brief Returns the index of the given node. /// /// Returns the index of the given node. Since it is a static /// graph its nodes can be indexed with integers from the range /// [0..nodeNum()-1]. /// \sa operator() int index(const Node& node) const { return Parent::index(node); } /// Returns the index of the given node. Since this structure is /// completely static, the nodes can be indexed with integers from /// the range [0..nodeNum()-1]. /// The index of a node is the same as its ID. /// \sa operator()() static int index(const Node& node) { return Parent::index(node); } /// \brief Returns the arc connecting the given nodes. /// /// Returns the arc connecting the given nodes. Arc arc(const Node& s, const Node& t) const { Arc arc(Node s, Node t) const { return Parent::arc(s, t); } /// \brief Returns the edge connects the given nodes. /// /// Returns the edge connects the given nodes. Edge edge(const Node& u, const Node& v) const { /// \brief Returns the edge connecting the given nodes. /// /// Returns the edge connecting the given nodes. Edge edge(Node u, Node v) const { return Parent::edge(u, v); }
• ## lemon/glpk.cc

 r623 int i = glp_add_rows(lp, 1); glp_set_row_bnds(lp, i, GLP_FR, 0.0, 0.0); return i; } int GlpkBase::_addRow(Value lo, ExprIterator b, ExprIterator e, Value up) { int i = glp_add_rows(lp, 1); if (lo == -INF) { if (up == INF) { glp_set_row_bnds(lp, i, GLP_FR, lo, up); } else { glp_set_row_bnds(lp, i, GLP_UP, lo, up); } } else { if (up == INF) { glp_set_row_bnds(lp, i, GLP_LO, lo, up); } else if (lo != up) { glp_set_row_bnds(lp, i, GLP_DB, lo, up); } else { glp_set_row_bnds(lp, i, GLP_FX, lo, up); } } std::vector indexes; std::vector values; indexes.push_back(0); values.push_back(0); for(ExprIterator it = b; it != e; ++it) { indexes.push_back(it->first); values.push_back(it->second); } glp_set_mat_row(lp, i, values.size() - 1, &indexes.front(), &values.front()); return i; }
• ## lemon/glpk.h

 r697 #include // forward declaration #if !defined _GLP_PROB && !defined GLP_PROB #define _GLP_PROB #define GLP_PROB typedef struct { double _opaque_prob; } glp_prob; /* LP/MIP problem object */ #endif namespace lemon { namespace _solver_bits { class VoidPtr { private: void *_ptr; public: VoidPtr() : _ptr(0) {} template VoidPtr(T* ptr) : _ptr(reinterpret_cast(ptr)) {} template VoidPtr& operator=(T* ptr) { _ptr = reinterpret_cast(ptr); return *this; } template operator T*() const { return reinterpret_cast(_ptr); } }; } /// \brief Base interface for the GLPK LP and MIP solver protected: typedef glp_prob LPX; glp_prob* lp; _solver_bits::VoidPtr lp; GlpkBase(); virtual int _addCol(); virtual int _addRow(); virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u); virtual void _eraseCol(int i); ///Pointer to the underlying GLPK data structure. LPX *lpx() {return lp;} _solver_bits::VoidPtr lpx() {return lp;} ///Const pointer to the underlying GLPK data structure. const LPX *lpx() const {return lp;} _solver_bits::VoidPtr lpx() const {return lp;} ///Returns the constraint identifier understood by GLPK.
• ## lemon/gomory_hu.h

 r760 /// \pre \ref run() must be called before using this function. template Value minCutMap(const Node& s, ///< Value minCutMap(const Node& s, const Node& t, ///< CutMap& cutMap ///< ) const { Node sn = s, tn = t; /// \endcode /// does not necessarily give the same set of nodes. /// However it is ensured that /// However, it is ensured that /// \code /// MinCutNodeIt(gomory, s, t, true);
• ## lemon/graph_to_eps.h

 r664 ///\param gr  Reference to the graph to be printed. ///\param ost Reference to the output stream. ///By default it is std::cout. ///By default, it is std::cout. ///\param pros If it is \c true, then the \c ostream referenced by \c os ///will be explicitly deallocated by the destructor. ///Turn on/off pre-scaling ///By default graphToEps() rescales the whole image in order to avoid ///By default, graphToEps() rescales the whole image in order to avoid ///very big or very small bounding boxes. /// #else os << bits::getWinFormattedDate(); os << std::endl; #endif } os << std::endl; if (_autoArcWidthScale) { ///\param g Reference to the graph to be printed. ///\param os Reference to the output stream. ///By default it is std::cout. ///By default, it is std::cout. /// ///This function also has a lot of ///\endcode /// ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file. ///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file. /// ///\warning Don't forget to put the \ref GraphToEps::run() "run()"
• ## lemon/grid_graph.h

 r664 /// \brief Grid graph class /// /// This class implements a special graph type. The nodes of the /// graph can be indexed by two integer \c (i,j) value where \c i is /// in the \c [0..width()-1] range and j is in the \c /// [0..height()-1] range. Two nodes are connected in the graph if /// the indexes differ exactly on one position and exactly one is /// the difference. The nodes of the graph can be indexed by position /// with the \c operator()() function. The positions of the nodes can be /// get with \c pos(), \c col() and \c row() members. The outgoing /// GridGraph implements a special graph type. The nodes of the /// graph can be indexed by two integer values \c (i,j) where \c i is /// in the range [0..width()-1] and j is in the range /// [0..height()-1]. Two nodes are connected in the graph if /// the indices differ exactly on one position and the difference is /// also exactly one. The nodes of the graph can be obtained by position /// using the \c operator()() function and the indices of the nodes can /// be obtained using \c pos(), \c col() and \c row() members. The outgoing /// arcs can be retrieved with the \c right(), \c up(), \c left() /// and \c down() functions, where the bottom-left corner is the /// origin. /// /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges, however /// the structure can be resized using resize(). /// /// \image html grid_graph.png ///\endcode /// /// This graph type fully conforms to the \ref concepts::Graph /// "Graph concept". /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// This class provides constant time counting for nodes, edges and arcs. class GridGraph : public ExtendedGridGraphBase { typedef ExtendedGridGraphBase Parent; public: /// \brief Map to get the indices of the nodes as dim2::Point. /// /// Map to get the indices of the nodes as dim2::Point. /// \brief Map to get the indices of the nodes as \ref dim2::Point /// "dim2::Point". /// /// Map to get the indices of the nodes as \ref dim2::Point /// "dim2::Point". class IndexMap { public: /// \brief Constructor /// /// Constructor IndexMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.pos(key); /// \brief Constructor /// /// Constructor ColMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.col(key); /// \brief Constructor /// /// Constructor RowMap(const GridGraph& graph) : _graph(graph) {} /// \brief The subscript operator /// /// The subscript operator. Value operator[](Key key) const { return _graph.row(key); /// \brief Constructor /// /// Construct a grid graph with given size. /// Construct a grid graph with the given size. GridGraph(int width, int height) { construct(width, height); } /// \brief Resize the graph /// /// Resize the graph. The function will fully destroy and rebuild /// the graph.  This cause that the maps of the graph will /// reallocated automatically and the previous values will be /// lost. /// \brief Resizes the graph /// /// This function resizes the graph. It fully destroys and /// rebuilds the structure, therefore the maps of the graph will be /// reallocated automatically and the previous values will be lost. void resize(int width, int height) { Parent::notifier(Arc()).clear(); } /// \brief Gives back the column index of the node. /// \brief The column index of the node. /// /// Gives back the column index of the node. } /// \brief Gives back the row index of the node. /// \brief The row index of the node. /// /// Gives back the row index of the node. } /// \brief Gives back the position of the node. /// \brief The position of the node. /// /// Gives back the position of the node, ie. the (col,row) pair. } /// \brief Gives back the number of the columns. /// \brief The number of the columns. /// /// Gives back the number of the columns. } /// \brief Gives back the number of the rows. /// \brief The number of the rows. /// /// Gives back the number of the rows. } /// \brief Gives back the arc goes right from the node. /// \brief The arc goes right from the node. /// /// Gives back the arc goes right from the node. If there is not } /// \brief Gives back the arc goes left from the node. /// \brief The arc goes left from the node. /// /// Gives back the arc goes left from the node. If there is not } /// \brief Gives back the arc goes up from the node. /// \brief The arc goes up from the node. /// /// Gives back the arc goes up from the node. If there is not } /// \brief Gives back the arc goes down from the node. /// \brief The arc goes down from the node. /// /// Gives back the arc goes down from the node. If there is not
• ## lemon/hypercube_graph.h

 r664 } int index(Node node) const { static int index(Node node) { return node._id; } /// \brief Hypercube graph class /// /// This class implements a special graph type. The nodes of the graph /// are indiced with integers with at most \c dim binary digits. /// HypercubeGraph implements a special graph type. The nodes of the /// graph are indexed with integers having at most \c dim binary digits. /// Two nodes are connected in the graph if and only if their indices /// differ only on one position in the binary form. /// This class is completely static and it needs constant memory space. /// Thus you can neither add nor delete nodes or edges, however, /// the structure can be resized using resize(). /// /// This type fully conforms to the \ref concepts::Graph "Graph concept". /// Most of its member functions and nested classes are documented /// only in the concept class. /// /// This class provides constant time counting for nodes, edges and arcs. /// /// \note The type of the indices is chosen to \c int for efficiency /// reasons. Thus the maximum dimension of this implementation is 26 /// (assuming that the size of \c int is 32 bit). /// /// This graph type fully conforms to the \ref concepts::Graph /// "Graph concept". class HypercubeGraph : public ExtendedHypercubeGraphBase { typedef ExtendedHypercubeGraphBase Parent; /// Constructs a hypercube graph with \c dim dimensions. HypercubeGraph(int dim) { construct(dim); } /// \brief Resizes the graph /// /// This function resizes the graph. It fully destroys and /// rebuilds the structure, therefore the maps of the graph will be /// reallocated automatically and the previous values will be lost. void resize(int dim) { Parent::notifier(Arc()).clear(); Parent::notifier(Edge()).clear(); Parent::notifier(Node()).clear(); construct(dim); Parent::notifier(Node()).build(); Parent::notifier(Edge()).build(); Parent::notifier(Arc()).build(); } /// \brief The number of dimensions. /// /// Gives back the dimension id of the given edge. /// It is in the [0..dim-1] range. /// It is in the range [0..dim-1]. int dimension(Edge edge) const { return Parent::dimension(edge); /// /// Gives back the dimension id of the given arc. /// It is in the [0..dim-1] range. /// It is in the range [0..dim-1]. int dimension(Arc arc) const { return Parent::dimension(arc); /// Gives back the index of the given node. /// The lower bits of the integer describes the node. int index(Node node) const { static int index(Node node) { return Parent::index(node); }

 r646 ///\endcode /// /// By default the reader uses the first section in the file of the /// By default, the reader uses the first section in the file of the /// proper type. If a section has an optional name, then it can be /// selected for reading by giving an optional name parameter to the /// whitespaces are trimmed from each processed string. /// /// For example let's see a section, which contain several /// For example, let's see a section, which contain several /// integers, which should be inserted into a vector. ///\code