Changeset 1158:29961fa390a3 in lemon-0.x for src

Timestamp:

02/20/05 02:02:07 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1559

Message:

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).

Location:

src

Files:

• lemon/concept/graph_component.h (modified) (1 diff)
• lemon/concept/undir_graph.h (modified) (6 diffs)
• lemon/iterable_graph_extender.h (modified) (5 diffs)
• lemon/max_matching.h (modified) (6 diffs)
• lemon/undir_graph_extender.h (modified) (3 diffs)
• test/max_matching_test.cc (modified) (1 diff)

src/lemon/concept/graph_component.h

@@ -626 +626 @@
           Edge e = it1;
           e = it2;
-        }
-
-        Edge& edge;
-        Node& node;
-        Graph& graph;
+
+          const_constraits();
+        }
+
+        void const_constraits() {
+          Node n = graph.baseNode(it);
+          n = graph.runningNode(it);
+        }
+
+        Edge edge;
+        Node node;
+        Graph graph;
+        _GraphIncIterator it;
       };
     };

src/lemon/concept/undir_graph.h

@@ -37 +37 @@
     /// Skeleton class which describes an edge with direction in \ref
     /// UndirGraph "undirected graph".
-    template <typename UndirEdge>
-    class UndirGraphEdge : public UndirEdge {
+    template <typename UndirGraph>
+    class UndirGraphEdge : public UndirGraph::UndirEdge {
+      typedef typename UndirGraph::UndirEdge UndirEdge;
+      typedef typename UndirGraph::Node Node;
     public:
 
@@ -50 +52 @@
       UndirGraphEdge(Invalid) {}
 
-      /// \brief Constructs a directed version of an undirected edge
-      ///
-      /// \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) {
+      /// \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.
+      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);
       }
 
@@ -74 +78 @@
       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;
       };
     };
@@ -100 +108 @@
           checkConcept<BaseIterableGraphComponent, Graph>();
           checkConcept<GraphItem<>, UndirEdge>();
-          checkConcept<UndirGraphEdge<UndirEdge>, Edge>();
+          checkConcept<UndirGraphEdge<Graph>, Edge>();
 
           graph.first(ue);
@@ -235 +243 @@
       /// Type describing an UndirEdge with direction
 #ifndef DOXYGEN
-      typedef UndirGraphEdge<UndirEdge> Edge;
+      typedef UndirGraphEdge<UndirGraph> Edge;
 #else
       typedef UndirGraphEdge Edge;
@@ -431 +439 @@
 
 
+      /// 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 <typename Graph>
       struct Constraints {

src/lemon/iterable_graph_extender.h

@@ -111 +111 @@
     };
 
+    /// 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;
 
@@ -125 +161 @@
 
   };
+
+
+
+
+
   
   template <typename _Base>
@@ -170 +211 @@
       IncEdgeIt(Invalid i) : UndirEdge(i), forward(false) { }
 
-      explicit IncEdgeIt(const Graph& _graph, const Node &n)
+      IncEdgeIt(const Graph& _graph, const Node &n)
         : graph(&_graph)
       {
@@ -176 +217 @@
       }
 
-      // 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++() {
@@ -189 +229 @@
     };
 
-    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;
 
   };

src/lemon/max_matching.h

@@ -181 +181 @@
           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);
@@ -228 +228 @@
           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);
@@ -333 +333 @@
         
       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) ) { 
@@ -389 +389 @@
         
       for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
-        Node y=g.target(e);
+        Node y=g.runningNode(e);
               
         switch ( position[y] ) {
@@ -454 +454 @@
       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);
@@ -485 +485 @@
                                         UFE& blossom, UFE& tree, std::queue<Node>& Q) {
     for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
-      Node y=g.target(e);
+      Node y=g.runningNode(e);
         
       if ( position[y]==C ) {

src/lemon/undir_graph_extender.h

@@ -45 +45 @@
     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) {}
@@ -64 +77 @@
 
 
-    /// \brief Returns the Edge of opposite direction.
-    ///
-    /// \bug Is this a good name for this? Or "reverse" is better?
+    /// \brief Edge of opposite direction.
+    ///
+    /// Returns the Edge of opposite direction.
     Edge opposite(const Edge &e) const {
       return Edge(e,!e.forward);
@@ -118 +131 @@
     }
 
+    /// 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;

src/test/max_matching_test.cc

@@ -160 +160 @@
         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;