Changeset 209:765619b7cbb2 in lemon for lemon/concepts

Ignore:
Timestamp:
07/13/08 20:51:02 (11 years ago)
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

Location:
lemon/concepts
Files:
6 edited

Unmodified
Removed
• lemon/concepts/digraph.h

 r125 /* -*- C++ -*- /* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 private: ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. ///Digraphs are \e not copy constructible. Use DigraphCopy() instead. /// ///\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. /// Inequality operator /// \sa operator==(Node n) /// 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. bool operator<(Node) const { return false; } }; /// 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. bool operator<(Node) const { return false; } }; /// This iterator goes through each node. NodeIt() { } /// Copy constructor. /// Copy constructor. /// /// 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 /// 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. NodeIt(const Digraph&, const Node&) { } NodeIt& operator++() { return *this; } }; /// Class for identifying an arc of the digraph 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. bool operator<(Arc) const { return false; } }; /// 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. bool operator<(Arc) const { return false; } }; /// This iterator goes trough the outgoing arcs of a node. /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; ///\endcode class OutArcIt : public Arc { public: 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 value of the trivial iterator. /// This feature necessitates that each time we /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. OutArcIt(const Digraph&, const Arc&) { } ///Next outgoing arc /// Assign the iterator to the next /// Assign the iterator to the next /// outgoing arc of the corresponding node. OutArcIt& operator++() { return *this; } 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 value of the trivial iterator \c e. /// This feature necessitates that each time we /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. InArcIt(const Digraph&, const Arc&) { } 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 /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. ArcIt(const Digraph&, const Arc&) { } ArcIt(const Digraph&, const Arc&) { } ///Next arc /// Assign the iterator to the next arc. ArcIt& operator++() { return *this; } /// \brief Returns the ID of the node. int id(Node) const { return -1; } int id(Node) const { return -1; } /// \brief Returns the ID of the arc. int id(Arc) const { return -1; } 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. Node nodeFromId(int) const { return INVALID; } 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. Arc arcFromId(int) const { return INVALID; } Arc arcFromId(int) const { return INVALID; } /// \brief Returns an upper bound on the node IDs. int maxNodeId() const { return -1; } int maxNodeId() const { return -1; } /// \brief Returns an upper bound on the arc IDs. int maxArcId() const { return -1; } int maxArcId() const { return -1; } void first(Node&) const {} // Dummy parameter. int maxId(Node) const { return -1; } int maxId(Node) const { return -1; } // Dummy parameter. int maxId(Arc) const { return -1; } int maxId(Arc) const { return -1; } /// \brief The base node of the iterator. /// \brief Read write map of the nodes to type \c T. /// /// /// ReadWrite map of the nodes to type \c T. /// \sa Reference template template class NodeMap : public ReadWriteMap< Node, T > { public: ///Assignment operator template NodeMap& operator=(const CMap&) { NodeMap& operator=(const CMap&) { checkConcept, CMap>(); return *this; return *this; } }; /// Reference map of the arcs to type \c T. /// \sa Reference template template class ArcMap : public ReadWriteMap { public: ///Assignment operator template ArcMap& operator=(const CMap&) { ArcMap& operator=(const CMap&) { checkConcept, CMap>(); return *this; return *this; } }; void constraints() { checkConcept, _Digraph>(); checkConcept, _Digraph>(); checkConcept, _Digraph>(); checkConcept, _Digraph>(); } }; } //namespace concepts } //namespace concepts } //namespace lemon
• lemon/concepts/graph.h

 r125 /* -*- C++ -*- /* -*- mode: C++; indent-tabs-mode: nil; -*- * * This file is a part of LEMON, a generic C++ optimization library * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2008 /// direction. The IncEdgeIt iterates also on the same edges /// as the OutArcIt and InArcIt but it is not convertible to Arc just /// to Edge. /// to Edge. class Graph { public: /// /// The undirected graph should be tagged by the UndirectedTag. This /// tag helps the enable_if technics to make compile time /// specializations for undirected graphs. /// tag helps the enable_if technics to make compile time /// specializations for undirected graphs. typedef True UndirectedTag; /// \brief The base type of node iterators, /// \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 /// More precisely each kind of node iterator should be inherited /// from the trivial node iterator. class Node { /// Inequality operator /// \sa operator==(Node n) /// 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 /// the items; this order has nothing to do with the iteration /// ordering of the items. bool operator<(Node) const { return false; } }; /// 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. bool operator<(Node) const { return false; } }; /// This iterator goes through each node. NodeIt() { } /// Copy constructor. /// Copy constructor. /// /// 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 /// 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. NodeIt(const Graph&, const Node&) { } NodeIt& operator++() { return *this; } }; /// The base type of the edge iterators. 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. bool operator<(Edge) const { return false; } /// 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. bool operator<(Edge) const { return false; } }; EdgeIt(Invalid) { } /// This constructor sets the iterator to the first edge. /// This constructor sets the iterator to the first edge. EdgeIt(const Graph&) { } /// 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. EdgeIt(const Graph&, const Edge&) { } /// iterate the edge-set, the iteration order is the /// same. 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 /// \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 /// 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. /// in graph \c g of type \c Graph as follows. /// ///\code 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 value of the trivial iterator \c e. /// This feature necessitates that each time we /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. IncEdgeIt(const Graph&, const Edge&) { } /// Assign the iterator to the next incident arc /// of the corresponding node. /// of the corresponding node. IncEdgeIt& operator++() { return *this; } }; 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. bool operator<(Arc) const { return false; } }; /// 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. bool operator<(Arc) const { return false; } }; /// This iterator goes through each directed arc. 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 /// Sets the iterator to the value of the trivial iterator \c e. /// This feature necessitates that each time we /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. ArcIt(const Graph&, const Arc&) { } ArcIt(const Graph&, const 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. /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count; ///\endcode class OutArcIt : public Arc { public: 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 g the graph OutArcIt(const Graph& n, const Node& g) { ignore_unused_variable_warning(n); ignore_unused_variable_warning(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 /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. OutArcIt(const Graph&, const Arc&) { } ///Next outgoing arc /// Assign the iterator to the next /// Assign the iterator to the next /// outgoing arc of the corresponding node. OutArcIt& operator++() { return *this; } 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 InArcIt(const Graph& g, const Node& n) { ignore_unused_variable_warning(n); ignore_unused_variable_warning(g); } 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 /// This feature necessitates that each time we /// iterate the arc-set, the iteration order is the same. InArcIt(const Graph&, const Arc&) { } /// \brief Read write map of the nodes to type \c T. /// /// /// ReadWrite map of the nodes to type \c T. /// \sa Reference template template class NodeMap : public ReadWriteMap< Node, T > { ///Assignment operator template NodeMap& operator=(const CMap&) { NodeMap& operator=(const CMap&) { checkConcept, CMap>(); return *this; return *this; } }; /// Reference map of the directed arcs to type \c T. /// \sa Reference template template class ArcMap : public ReadWriteMap { ///Assignment operator template ArcMap& operator=(const CMap&) { ArcMap& operator=(const CMap&) { checkConcept, CMap>(); return *this; return *this; } }; /// Reference map of the arcs to type \c T. /// \sa Reference template template class EdgeMap : public ReadWriteMap { ///Assignment operator template EdgeMap& operator=(const CMap&) { EdgeMap& operator=(const CMap&) { checkConcept, CMap>(); return *this; return *this; } }; /// will be the given node. Arc direct(const Edge&, const Node&) const { return INVALID; return INVALID; } /// the directed arc is the same when the given bool is true. Arc direct(const Edge&, bool) const { return INVALID; return INVALID; } /// \brief Returns the id of the node. int id(Node) const { return -1; } int id(Node) const { return -1; } /// \brief Returns the id of the edge. int id(Edge) const { return -1; } int id(Edge) const { return -1; } /// \brief Returns the id of the arc. int id(Arc) const { return -1; } 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. Node nodeFromId(int) const { return INVALID; } 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. Edge edgeFromId(int) const { return INVALID; } 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. Arc arcFromId(int) const { return INVALID; } Arc arcFromId(int) const { return INVALID; } /// \brief Returns an upper bound on the node IDs. int maxNodeId() const { return -1; } int maxNodeId() const { return -1; } /// \brief Returns an upper bound on the edge IDs. int maxEdgeId() const { return -1; } int maxEdgeId() const { return -1; } /// \brief Returns an upper bound on the arc IDs. int maxArcId() const { return -1; } int maxArcId() const { return -1; } void first(Node&) const {} // Dummy parameter. int maxId(Node) const { return -1; } int maxId(Node) const { return -1; } // Dummy parameter. int maxId(Edge) const { return -1; } int maxId(Edge) const { return -1; } // Dummy parameter. int maxId(Arc) const { return -1; } 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); return source(e); } /// \brief Running node of the iterator /// iterator Node runningNode(OutArcIt e) const { return target(e); return target(e); } /// Returns the base node (the target in this case) of the iterator Node baseNode(InArcIt e) const { return target(e); return target(e); } /// \brief Running node of the iterator /// iterator Node runningNode(InArcIt e) const { return source(e); return source(e); } /// Returns the base node of the iterator Node baseNode(IncEdgeIt) const { return INVALID; return INVALID; } /// \brief Running node of the iterator /// /// Returns the running node of the iterator Node runningNode(IncEdgeIt) const { return INVALID; return INVALID; } template struct Constraints { void constraints() { checkConcept, _Graph>(); checkConcept, _Graph>(); checkConcept, _Graph>(); } void constraints() { checkConcept, _Graph>(); checkConcept, _Graph>(); checkConcept, _Graph>(); } };