# Changes in /[733:abf31e4af617:742:8e68671af789] in lemon-1.2

Ignore:
Files:
11 edited

Unmodified
Removed
• ## doc/groups.dox

 r715 \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. */
• ## lemon/concepts/digraph.h

 r580 /// \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. }; /// 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 digraph \c g of type \c Digraph like this: /// 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 /// 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. /// 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. /// 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: /// 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

 r657 ///\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. /// 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 graph \c g of type \c Graph like this: /// 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. /// 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: /// 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. /// /// 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. count the number of incident arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// 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. /// 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: /// 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. /// 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. /// 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 outgoing arcs of a node \c n /// in graph \c g of type \c Graph as follows. /// 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

 r666 /// 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/full_graph.h

 r617 ///\ingroup graphs ///\file ///\brief FullGraph and FullDigraph classes. ///\brief FullDigraph and FullGraph classes. namespace lemon { /// \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. /// /// \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]. /// \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]. /// \sa operator()() int index(Node node) const { 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); } /// \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. /// /// \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]. /// \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]. /// \sa operator()() int index(Node node) const { 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/grid_graph.h

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

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