# HG changeset patch # User klao # Date 1101394104 0 # Node ID fd1d073b6557c77d1d7a1b928039ab51849cf52e # Parent f42cb3146ed450b2c7592778497537b5dd2abba2 Advances in UndirGraph. * IterableExtender is complete diff -r f42cb3146ed4 -r fd1d073b6557 src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Mon Nov 22 17:50:26 2004 +0000 +++ b/src/lemon/concept/graph_component.h Thu Nov 25 14:48:24 2004 +0000 @@ -505,62 +505,66 @@ /// base class, the _selector is a additional template parameter. For /// InEdgeIt you should instantiate it with character 'i' and for /// OutEdgeIt with 'o'. - /// \todo check the name of the concept GraphIncEdgeIterator - template - class GraphIncEdgeIterator : public _Graph::Edge { + /// \todo Is this a good name for this concept? + template + class GraphIncIterator : public Edge { public: /// Default constructor. /// @warning The default constructor sets the iterator /// to an undefined value. - GraphIncEdgeIterator() {} + GraphIncIterator() {} /// Copy constructor. /// Copy constructor. /// - GraphIncEdgeIterator(GraphIncEdgeIterator const&) {} + GraphIncIterator(GraphIncIterator const&) {} /// Sets the iterator to the first edge incoming into or outgoing from the node. /// Sets the iterator to the first edge incoming into or outgoing from the node. /// - explicit GraphIncEdgeIterator(const _Graph&, const typename _Graph::Node&) {} + explicit GraphIncIterator(const Graph&, const typename Graph::Node&) {} /// Invalid constructor \& conversion. /// This constructor initializes the item to be invalid. /// \sa Invalid for more details. - GraphIncEdgeIterator(Invalid) {} + GraphIncIterator(Invalid) {} /// Assign operator for nodes. /// The nodes are assignable. /// - GraphIncEdgeIterator& operator=(GraphIncEdgeIterator const&) { return *this; } + GraphIncIterator& operator=(GraphIncIterator const&) { return *this; } /// Next edge. /// Assign the iterator to the next node. /// - GraphIncEdgeIterator& operator++() { return *this; } + GraphIncIterator& operator++() { return *this; } + // Node operator*() const { return INVALID; } + /// Equality operator /// Two iterators are equal if and only if they point to the /// same object or both are invalid. - bool operator==(const GraphIncEdgeIterator&) const { return true;} + bool operator==(const GraphIncIterator&) const { return true;} + /// Inequality operator /// \sa operator==(Node n) /// - bool operator!=(const GraphIncEdgeIterator&) const { return true;} + bool operator!=(const GraphIncIterator&) const { return true;} - template + template struct Constraints { - typedef typename _Graph::Node Node; - typedef typename _Graph::Edge Edge; + typedef typename Graph::Node Node; void constraints() { - checkConcept, _GraphIncEdgeIterator>(); - _GraphIncEdgeIterator it1(graph, node); + checkConcept, _GraphIncIterator>(); + _GraphIncIterator it1(graph, node); /// \todo Do we need OutEdgeIt(Edge) kind of constructor? - // _GraphIncEdgeIterator it2(edge); - _GraphIncEdgeIterator it2; + // _GraphIncIterator it2(edge); + _GraphIncIterator it2; it2 = ++it1; ++it2 = it1; @@ -571,9 +575,11 @@ Edge& edge; Node& node; - _Graph& graph; + Graph& graph; }; }; + + /// An empty iterable base graph class. /// This class provides beside the core graph features @@ -602,12 +608,12 @@ /// This iterator goes trough the \e inccoming edges of a certain node /// of a graph. - typedef GraphIncEdgeIterator InEdgeIt; + typedef GraphIncIterator InEdgeIt; /// This iterator goes trough the outgoing edges of a node. /// This iterator goes trough the \e outgoing edges of a certain node /// of a graph. - typedef GraphIncEdgeIterator OutEdgeIt; + typedef GraphIncIterator OutEdgeIt; }; template @@ -617,8 +623,8 @@ checkConcept, typename _Graph::EdgeIt >(); checkConcept, typename _Graph::NodeIt >(); - checkConcept, typename _Graph::InEdgeIt >(); - checkConcept, typename _Graph::OutEdgeIt >(); + checkConcept, typename _Graph::InEdgeIt >(); + checkConcept, typename _Graph::OutEdgeIt >(); } }; diff -r f42cb3146ed4 -r fd1d073b6557 src/lemon/concept/undir_graph.h --- a/src/lemon/concept/undir_graph.h Mon Nov 22 17:50:26 2004 +0000 +++ b/src/lemon/concept/undir_graph.h Thu Nov 25 14:48:24 2004 +0000 @@ -67,8 +67,13 @@ typedef typename Graph::UndirEdge UndirEdge; typedef typename Graph::UndirEdgeIt UndirEdgeIt; + typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt; checkConcept< GraphIterator, UndirEdgeIt >(); + + checkConcept< + GraphIncIterator, + UndirIncEdgeIt >(); } }; diff -r f42cb3146ed4 -r fd1d073b6557 src/lemon/iterable_graph_extender.h --- a/src/lemon/iterable_graph_extender.h Mon Nov 22 17:50:26 2004 +0000 +++ b/src/lemon/iterable_graph_extender.h Thu Nov 25 14:48:24 2004 +0000 @@ -131,6 +131,7 @@ typedef IterableGraphExtender<_Base> Parent; typedef IterableUndirGraphExtender<_Base> Graph; + typedef typename Parent::Node Node; typedef typename Parent::UndirEdge UndirEdge; @@ -156,6 +157,50 @@ }; + class UndirIncEdgeIt : public UndirEdge { + const Graph* graph; + bool forward; + friend class IterableUndirGraphExtender; + template + friend class UndirGraphExtender; + public: + + UndirIncEdgeIt() { } + + UndirIncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } + + explicit UndirIncEdgeIt(const Graph& _graph, const Node &n) + : graph(&_graph) + { + _graph._dirFirstOut(*this, n); + } + + // FIXME: Do we need this type of constructor here? + // UndirIncEdgeIt(const Graph& _graph, const UndirEdge& e) : + // UndirEdge(e), graph(&_graph) { } + + UndirIncEdgeIt& operator++() { + graph->_dirNextOut(*this); + return *this; + } + }; + + Node source(const UndirIncEdgeIt &e) const { + return _dirSource(e); + } + + /// \todo Shouldn't the "source" of an undirected edge be called "aNode" + /// or something??? + using Parent::source; + + /// Target of the given Edge. + Node target(const UndirIncEdgeIt &e) const { + return _dirTarget(e); + } + + /// \todo Shouldn't the "target" of an undirected edge be called "bNode" + /// or something??? + using Parent::target; }; } diff -r f42cb3146ed4 -r fd1d073b6557 src/lemon/undir_graph_extender.h --- a/src/lemon/undir_graph_extender.h Mon Nov 22 17:50:26 2004 +0000 +++ b/src/lemon/undir_graph_extender.h Thu Nov 25 14:48:24 2004 +0000 @@ -70,24 +70,37 @@ return Edge(e,!e.forward); } - /// Source of the given Edge. - Node source(const Edge &e) const { + protected: + + template + Node _dirSource(const E &e) const { return e.forward ? Parent::source(e) : Parent::target(e); } + template + Node _dirTarget(const E &e) const { + return e.forward ? Parent::target(e) : Parent::source(e); + } + + public: /// \todo Shouldn't the "source" of an undirected edge be called "aNode" /// or something??? using Parent::source; - /// Target of the given Edge. - Node target(const Edge &e) const { - return e.forward ? Parent::target(e) : Parent::source(e); + /// Source of the given Edge. + Node source(const Edge &e) const { + return _dirSource(e); } /// \todo Shouldn't the "target" of an undirected edge be called "bNode" /// or something??? using Parent::target; + /// Target of the given Edge. + Node target(const Edge &e) const { + return _dirTarget(e); + } + /// Returns whether the given directed edge is same orientation as the /// corresponding undirected edge. /// @@ -122,7 +135,11 @@ } } - void firstOut(Edge &e, const Node &n) const { + + protected: + + template + void _dirFirstOut(E &e, const Node &n) const { Parent::firstOut(e,n); if( UndirEdge(e) != INVALID ) { e.forward = true; @@ -132,7 +149,8 @@ e.forward = false; } } - void firstIn(Edge &e, const Node &n) const { + template + void _dirFirstIn(E &e, const Node &n) const { Parent::firstIn(e,n); if( UndirEdge(e) != INVALID ) { e.forward = true; @@ -143,7 +161,8 @@ } } - void nextOut(Edge &e) const { + template + void _dirNextOut(E &e) const { if( e.forward ) { Parent::nextOut(e); if( UndirEdge(e) == INVALID ) { @@ -155,7 +174,8 @@ Parent::nextIn(e); } } - void nextIn(Edge &e) const { + template + void _dirNextIn(E &e) const { if( e.forward ) { Parent::nextIn(e); if( UndirEdge(e) == INVALID ) { @@ -168,21 +188,52 @@ } } + public: + + void firstOut(Edge &e, const Node &n) const { + _dirFirstOut(e, n); + } + void firstIn(Edge &e, const Node &n) const { + _dirFirstIn(e, n); + } + + void nextOut(Edge &e) const { + _dirNextOut(e); + } + void nextIn(Edge &e) const { + _dirNextIn(e); + } + // Miscellaneous stuff: /// \todo these methods (id, maxEdgeId) should be moved into separate /// Extender - using Parent::id; + // using Parent::id; + // Using "using" is not a good idea, cause it could be that there is + // no "id" in Parent... + + int id(const Node &n) const { + return Parent::id(n); + } + + int id(const UndirEdge &e) const { + return Parent::id(e); + } int id(const Edge &e) const { return 2 * Parent::id(e) + int(e.forward); } - int maxId(Edge = INVALID) const { + + int maxId(Node n) const { + return Parent::maxId(Node()); + } + + int maxId(Edge) const { return 2 * Parent::maxId(typename Parent::Edge()) + 1; } - int maxId(UndirEdge = INVALID) const { + int maxId(UndirEdge) const { return Parent::maxId(typename Parent::Edge()); }