# HG changeset patch # User klao # Date 1108861327 0 # Node ID 29961fa390a33c26416ba7e365b1ee123e9ed316 # Parent 3996d20980907c817be7b0ed2b4604bc57b775c6 Graph and UndirGraph concept modifications. * For incidence iterators ({In,Out,Inc}EdgeIt) there is now baseNode and runningNode functions in graph interface * For Edge in undir graphs: Edge(UndirGraph const &, UndirEdge, Node) constructor. Same for IncEdgeIt * Edge(UndirEdge, bool) constructor is no more in the public interface. (But we need it in the developpers interface). diff -r 3996d2098090 -r 29961fa390a3 src/lemon/concept/graph_component.h --- a/src/lemon/concept/graph_component.h Sat Feb 19 21:11:20 2005 +0000 +++ b/src/lemon/concept/graph_component.h Sun Feb 20 01:02:07 2005 +0000 @@ -625,11 +625,19 @@ ++(++it1); Edge e = it1; e = it2; + + const_constraits(); } - Edge& edge; - Node& node; - Graph& graph; + void const_constraits() { + Node n = graph.baseNode(it); + n = graph.runningNode(it); + } + + Edge edge; + Node node; + Graph graph; + _GraphIncIterator it; }; }; diff -r 3996d2098090 -r 29961fa390a3 src/lemon/concept/undir_graph.h --- a/src/lemon/concept/undir_graph.h Sat Feb 19 21:11:20 2005 +0000 +++ b/src/lemon/concept/undir_graph.h Sun Feb 20 01:02:07 2005 +0000 @@ -36,8 +36,10 @@ /// Skeleton class which describes an edge with direction in \ref /// UndirGraph "undirected graph". - template - class UndirGraphEdge : public UndirEdge { + template + class UndirGraphEdge : public UndirGraph::UndirEdge { + typedef typename UndirGraph::UndirEdge UndirEdge; + typedef typename UndirGraph::Node Node; public: /// \e @@ -49,14 +51,16 @@ /// \e UndirGraphEdge(Invalid) {} - /// \brief Constructs a directed version of an undirected edge + /// \brief Directed edge from undirected edge and a source node. /// - /// \param forward If \c true the direction of the contructed edge - /// is the same as the inherent direction of the \c undir_edge; if - /// \c false --- the opposite. - UndirGraphEdge(UndirEdge undir_edge, bool forward) { + /// Constructs a directed edge from undirected edge and a source node. + /// + /// \note You have to specify the graph for this constructor. + UndirGraphEdge(const UndirGraph &g, + UndirEdge undir_edge, Node n) { ignore_unused_variable_warning(undir_edge); - ignore_unused_variable_warning(forward); + ignore_unused_variable_warning(g); + ignore_unused_variable_warning(n); } /// \e @@ -73,16 +77,20 @@ template struct Constraints { void constraints() { + const_constraints(); + } + void const_constraints() const { /// \bug This should be is_base_and_derived ... UndirEdge ue = e; ue = e; - Edge forward(ue, true); - Edge backward(ue, false); - ignore_unused_variable_warning(forward); - ignore_unused_variable_warning(backward); + Edge e_with_source(graph,ue,n); + ignore_unused_variable_warning(e_with_source); } Edge e; + UndirEdge ue; + UndirGraph graph; + Node n; }; }; @@ -99,7 +107,7 @@ void constraints() { checkConcept(); checkConcept, UndirEdge>(); - checkConcept, Edge>(); + checkConcept, Edge>(); graph.first(ue); graph.next(ue); @@ -234,7 +242,7 @@ /// Type describing an UndirEdge with direction #ifndef DOXYGEN - typedef UndirGraphEdge Edge; + typedef UndirGraphEdge Edge; #else typedef UndirGraphEdge Edge; #endif @@ -430,6 +438,48 @@ void nextIn(Edge&) const {} + /// Base node of the iterator + /// + /// Returns the base node (the source in this case) of the iterator + Node baseNode(OutEdgeIt e) const { + return source(e); + } + /// Running node of the iterator + /// + /// Returns the running node (the target in this case) of the + /// iterator + Node runningNode(OutEdgeIt e) const { + return target(e); + } + + /// Base node of the iterator + /// + /// Returns the base node (the target in this case) of the iterator + Node baseNode(InEdgeIt e) const { + return target(e); + } + /// Running node of the iterator + /// + /// Returns the running node (the source in this case) of the + /// iterator + Node runningNode(InEdgeIt e) const { + return source(e); + } + + /// Base node of the iterator + /// + /// Returns the base node of the iterator + Node baseNode(IncEdgeIt e) const { + return INVALID; + } + /// Running node of the iterator + /// + /// Returns the running node of the iterator + Node runningNode(IncEdgeIt e) const { + return INVALID; + } + + template struct Constraints { void constraints() { diff -r 3996d2098090 -r 29961fa390a3 src/lemon/iterable_graph_extender.h --- a/src/lemon/iterable_graph_extender.h Sat Feb 19 21:11:20 2005 +0000 +++ b/src/lemon/iterable_graph_extender.h Sun Feb 20 01:02:07 2005 +0000 @@ -110,6 +110,42 @@ }; + /// Base node of the iterator + /// + /// Returns the base node (ie. the source in this case) of the iterator + /// + /// \todo Document in the concept! + Node baseNode(const OutEdgeIt &e) const { + return source(e); + } + /// Running node of the iterator + /// + /// Returns the running node (ie. the target in this case) of the + /// iterator + /// + /// \todo Document in the concept! + Node runningNode(const OutEdgeIt &e) const { + return target(e); + } + + /// Base node of the iterator + /// + /// Returns the base node (ie. the target in this case) of the iterator + /// + /// \todo Document in the concept! + Node baseNode(const InEdgeIt &e) const { + return target(e); + } + /// Running node of the iterator + /// + /// Returns the running node (ie. the source in this case) of the + /// iterator + /// + /// \todo Document in the concept! + Node runningNode(const InEdgeIt &e) const { + return source(e); + } + using Parent::first; private: @@ -124,6 +160,11 @@ void first(InEdgeIt &) const; }; + + + + + template class IterableUndirGraphExtender : public IterableGraphExtender<_Base> { @@ -169,18 +210,17 @@ IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { } - explicit IncEdgeIt(const Graph& _graph, const Node &n) + IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { _graph._dirFirstOut(*this, n); } - // FIXME: Do we need this type of constructor here? - // IncEdgeIt(const Graph& _graph, const Edge& e) : - // UndirEdge(e), graph(&_graph), forward(_graph.forward(e)) { } - // or - // IncEdgeIt(const Graph& _graph, const Node& n, - // Const UndirEdge &e) ... ? + IncEdgeIt(const Graph& _graph, const UndirEdge &ue, const Node &n) + : graph(&_graph), UndirEdge(ue) + { + forward = (_graph.source(ue) == n); + } IncEdgeIt& operator++() { graph->_dirNextOut(*this); @@ -188,23 +228,22 @@ } }; - Node source(const IncEdgeIt &e) const { + using Parent::baseNode; + using Parent::runningNode; + + /// Base node of the iterator + /// + /// Returns the base node of the iterator + Node baseNode(const IncEdgeIt &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 IncEdgeIt &e) const { + /// Running node of the iterator + /// + /// Returns the running node of the iterator + Node runningNode(const IncEdgeIt &e) const { return _dirTarget(e); } - /// \todo Shouldn't the "target" of an undirected edge be called "bNode" - /// or something??? - using Parent::target; - }; } diff -r 3996d2098090 -r 29961fa390a3 src/lemon/max_matching.h --- a/src/lemon/max_matching.h Sat Feb 19 21:11:20 2005 +0000 +++ b/src/lemon/max_matching.h Sun Feb 20 01:02:07 2005 +0000 @@ -180,7 +180,7 @@ if ( todo[v] && _mate[v]!=INVALID ) { Node u=_mate[v]; for(IncEdgeIt e(g,v); e!=INVALID; ++e) { - if ( g.target(e) == u ) { + if ( g.runningNode(e) == u ) { map.set(u,e); map.set(v,e); todo.set(u,false); @@ -227,7 +227,7 @@ if ( todo[v] && _mate[v]!=INVALID ) { Node u=_mate[v]; for(IncEdgeIt e(g,v); e!=INVALID; ++e) { - if ( g.target(e) == u ) { + if ( g.runningNode(e) == u ) { map.set(e,true); todo.set(u,false); todo.set(v,false); @@ -332,7 +332,7 @@ R.pop(); for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) { - Node y=g.target(e); + Node y=g.runningNode(e); if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { //x and y must be in the same tree @@ -388,7 +388,7 @@ Q.pop(); for( IncEdgeIt e(g,x); e!=INVALID; ++e ) { - Node y=g.target(e); + Node y=g.runningNode(e); switch ( position[y] ) { case D: //x and y must be in the same tree @@ -453,7 +453,7 @@ for(NodeIt v(g); v!=INVALID; ++v) if ( _mate[v]==INVALID ) { for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { - Node y=g.target(e); + Node y=g.runningNode(e); if ( _mate[y]==INVALID && y!=v ) { _mate.set(v,y); _mate.set(y,v); @@ -484,7 +484,7 @@ bool MaxMatching::noShrinkStep(Node x, typename Graph::NodeMap& ear, UFE& blossom, UFE& tree, std::queue& Q) { for( IncEdgeIt e(g,x); e!= INVALID; ++e ) { - Node y=g.target(e); + Node y=g.runningNode(e); if ( position[y]==C ) { if ( _mate[y]!=INVALID ) { //grow diff -r 3996d2098090 -r 29961fa390a3 src/lemon/undir_graph_extender.h --- a/src/lemon/undir_graph_extender.h Sat Feb 19 21:11:20 2005 +0000 +++ b/src/lemon/undir_graph_extender.h Sun Feb 20 01:02:07 2005 +0000 @@ -44,9 +44,22 @@ public: Edge() {} - /// Construct a direct edge from undirect edge and a direction. + + /// \brief Directed edge from undirected edge and a direction. + /// + /// This constructor is not a part of the concept interface of + /// undirected graph, so please avoid using it if possible! Edge(const UndirEdge &ue, bool _forward) : - UndirEdge(ue), forward(_forward) {} + UndirEdge(ue), forward(_forward) {} + + /// \brief Directed edge from undirected edge and a source node. + /// + /// Constructs a directed edge from undirected edge and a source node. + /// + /// \note You have to specify the graph for this constructor. + Edge(const Graph &g, const UndirEdge &ue, const Node &n) : + UndirEdge(ue) { forward = (g.source(ue) == n); } + /// Invalid edge constructor Edge(Invalid i) : UndirEdge(i), forward(true) {} @@ -63,9 +76,9 @@ }; - /// \brief Returns the Edge of opposite direction. + /// \brief Edge of opposite direction. /// - /// \bug Is this a good name for this? Or "reverse" is better? + /// Returns the Edge of opposite direction. Edge opposite(const Edge &e) const { return Edge(e,!e.forward); } @@ -117,6 +130,17 @@ return INVALID; } + /// Directed edge from an undirected edge and a source node. + /// + /// Returns a (directed) Edge corresponding to the specified UndirEdge + /// and source Node. + /// + ///\todo Do we need this? + /// + ///\todo Better name... + Edge edgeWithSource(const UndirEdge &ue, const Node &s) const { + return Edge(*this, eu, s); + } using Parent::first; void first(Edge &e) const { diff -r 3996d2098090 -r 29961fa390a3 src/test/max_matching_test.cc --- a/src/test/max_matching_test.cc Sat Feb 19 21:11:20 2005 +0000 +++ b/src/test/max_matching_test.cc Sun Feb 20 01:02:07 2005 +0000 @@ -159,7 +159,7 @@ Node w=Q.front(); Q.pop(); for(IncEdgeIt e(g,w); e!=INVALID; ++e) { - Node u=g.target(e); + Node u=g.runningNode(e); if ( pos[u]==max_matching.D && todo[u] ) { ++comp_size; Q.push(u);