lemon: comparison lemon/concepts/graph.h

equal deleted inserted replaced

-:1ff8cf24f3b5
+:0ba6f256cc7a
-/* -*- 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
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 /// 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.
 class 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
 /// 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.
 class Node {
 public:
 /// Default constructor
 /// Two iterators are equal if and only if they point to the
 /// same object or both are invalid.
 bool operator==(Node) const { return true; }
 /// Inequality operator
 /// \sa operator==(Node n)
 ///
 bool operator!=(Node) const { return true; }
-	/// Artificial ordering operator.
+/// Artificial ordering operator.
-	/// To allow the use of graph descriptors as key type in std::map or
+/// To allow the use of graph descriptors as key type in std::map or
-	/// similar associative container we require this.
+/// similar associative container we require this.
-	///
+///
-	/// \note This operator only have to define some strict ordering of
+/// \note This operator only have to define some strict ordering of
-	/// the items; this order has nothing to do with the iteration
+/// the items; this order has nothing to do with the iteration
-	/// ordering of the items.
+/// ordering of the items.
-	bool operator<(Node) const { return false; }
+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 graph \c g of type \c Graph like this:
 /// @warning The default constructor sets the iterator
 /// to an undefined value.
 NodeIt() { }
 /// Copy constructor.
 /// Copy constructor.
 ///
 NodeIt(const NodeIt& n) : Node(n) { }
 /// Invalid constructor \& conversion.
 /// 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.
+/// 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&) { }
 /// Next node.
 /// Assign the iterator to the next node.
 ///
 NodeIt& operator++() { return *this; }
 };
 /// The base type of the edge iterators.
 /// The base type of the edge iterators.
 ///
 class Edge {
 /// \sa operator==(Edge n)
 ///
 bool operator!=(Edge) const { return true; }
-	/// Artificial ordering operator.
+/// Artificial ordering operator.
-	/// To allow the use of graph descriptors as key type in std::map or
+/// To allow the use of graph descriptors as key type in std::map or
-	/// similar associative container we require this.
+/// similar associative container we require this.
-	///
+///
-	/// \note This operator only have to define some strict ordering of
+/// \note This operator only have to define some strict ordering of
-	/// the items; this order has nothing to do with the iteration
+/// the items; this order has nothing to do with the iteration
-	/// ordering of the items.
+/// ordering of the items.
-	bool operator<(Edge) const { return false; }
+bool operator<(Edge) const { return false; }
 };
 /// This iterator goes through each edge.
 /// This iterator goes through each edge of a graph.
 /// Initialize the iterator to be invalid.
 ///
 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.
+/// 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
 /// 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.
 ///
 ///\code
 /// int count=0;
 /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
 ///\endcode
 /// Initialize the iterator to be invalid.
 ///
 IncEdgeIt(Invalid) { }
 /// This constructor sets the iterator to first incident arc.
 /// This constructor set the iterator to the first incident arc of
 /// the 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.
 IncEdgeIt(const Graph&, const Edge&) { }
 /// Next incident arc
 /// Assign the iterator to the next incident arc
-	/// of the corresponding node.
+/// of the corresponding node.
 IncEdgeIt& operator++() { return *this; }
 };
 /// The directed arc type.
 /// \sa operator==(Arc n)
 ///
 bool operator!=(Arc) const { return true; }
-	/// Artificial ordering operator.
+/// Artificial ordering operator.
-	/// To allow the use of graph descriptors as key type in std::map or
+/// To allow the use of graph descriptors as key type in std::map or
-	/// similar associative container we require this.
+/// similar associative container we require this.
-	///
+///
-	/// \note This operator only have to define some strict ordering of
+/// \note This operator only have to define some strict ordering of
-	/// the items; this order has nothing to do with the iteration
+/// the items; this order has nothing to do with the iteration
-	/// ordering of the items.
+/// ordering of the items.
-	bool operator<(Arc) const { return false; }
+bool operator<(Arc) const { return false; }
 };
 /// 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:
 /// Initialize the iterator to be invalid.
 ///
 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.
 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.
 /// 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
 /// in graph \c g of type \c Graph as follows.
 ///\code
 /// int count=0;
 /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
 ///\endcode
 class OutArcIt : public Arc {
 public:
 /// Default constructor
 /// @warning The default constructor sets the iterator
 /// Initialize the iterator to be invalid.
 ///
 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
 OutArcIt(const Graph& n, const Node& g) {
-	  ignore_unused_variable_warning(n);
+ignore_unused_variable_warning(n);
-	  ignore_unused_variable_warning(g);
+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
 /// outgoing arc of the corresponding node.
 OutArcIt& operator++() { return *this; }
 };
 /// This iterator goes trough the incoming directed arcs of a node.
 /// Initialize the iterator to be invalid.
 ///
 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(n);
-	  ignore_unused_variable_warning(g);
+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.
 InArcIt(const Graph&, const Arc&) { }
 /// Next incoming arc
 /// Assign the iterator to the next inarc of the corresponding node.
 ///
 InArcIt& operator++() { return *this; }
 };
 /// \brief Read write map of the nodes to type \c T.
 ///
 /// ReadWrite map of the nodes to type \c T.
 /// \sa Reference
 template<class T>
 class NodeMap : public ReadWriteMap< Node, T >
 {
 public:
 ///\e
 ///Copy constructor
 NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
 ///Assignment operator
 template <typename CMap>
 NodeMap& operator=(const CMap&) {
 checkConcept<ReadMap<Node, T>, CMap>();
 return *this;
 }
 };
 /// \brief Read write map of the directed arcs to type \c T.
 ///
 /// Reference map of the directed arcs to type \c T.
 /// \sa Reference
 template<class T>
 class ArcMap : public ReadWriteMap<Arc,T>
 {
 public:
 ///\e
 ArcMap(const Graph&, T) { }
 ///Copy constructor
 ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 ///Assignment operator
 template <typename CMap>
 ArcMap& operator=(const CMap&) {
 checkConcept<ReadMap<Arc, T>, CMap>();
 return *this;
 }
 };
 /// Read write map of the edges to type \c T.
 /// Reference map of the arcs to type \c T.
 /// \sa Reference
 template<class T>
 class EdgeMap : public ReadWriteMap<Edge,T>
 {
 public:
 ///\e
 EdgeMap(const Graph&, T) { }
 ///Copy constructor
 EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
 ///Assignment operator
 template <typename CMap>
 EdgeMap& operator=(const CMap&) {
 checkConcept<ReadMap<Edge, T>, CMap>();
 return *this;
 }
 };
 /// \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;
+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;
+return INVALID;
 }
 /// \brief Returns true if the arc has default orientation.
 ///
 /// Returns whether the given directed arc is same orientation as
 /// \brief Target node of the directed arc.
 Node target(Arc) const { return INVALID; }
 /// \brief Returns the id of the node.
 int id(Node) const { return -1; }
 /// \brief Returns the id of the edge.
 int id(Edge) const { return -1; }
 /// \brief Returns the id of the 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.
 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; }
 /// \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; }
 /// \brief Returns an upper bound on the node IDs.
 int maxNodeId() const { return -1; }
 /// \brief Returns an upper bound on the edge IDs.
 int maxEdgeId() const { return -1; }
 /// \brief Returns an upper bound on the arc IDs.
 int maxArcId() const { return -1; }
 void first(Node&) const {}
 void next(Node&) const {}
 void first(Edge&) const {}
 Edge fromId(int, Edge) const { return INVALID; }
 // The second parameter is dummy.
 Arc fromId(int, Arc) const { return INVALID; }
 // Dummy parameter.
 int maxId(Node) const { return -1; }
 // Dummy parameter.
 int maxId(Edge) const { return -1; }
 // Dummy parameter.
 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
 ///
 /// Returns the running node (the target in this case) of the
 /// iterator
 Node runningNode(OutArcIt e) const {
-	return target(e);
+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);
+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);
+return source(e);
 }
 /// \brief Base node of the iterator
 ///
 /// 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 <typename _Graph>
 struct Constraints {
-	void constraints() {
+void constraints() {
-	  checkConcept<IterableGraphComponent<>, _Graph>();
+checkConcept<IterableGraphComponent<>, _Graph>();
-	  checkConcept<IDableGraphComponent<>, _Graph>();
+checkConcept<IDableGraphComponent<>, _Graph>();
-	  checkConcept<MappableGraphComponent<>, _Graph>();
+checkConcept<MappableGraphComponent<>, _Graph>();
-	}
+}
 };
 };
 }

changeset 209	765619b7cbb2
parent 125	19e82bda606a
child 220	a5d8c039f218