Changeset 1021:fd1d073b6557 in lemon-0.x

Timestamp:

11/25/04 15:48:24 (20 years ago)

Author:

Mihaly Barasz

Branch:

default

Phase:

public

Convert:

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

Message:

Advances in UndirGraph?.

• IterableExtender? is complete

Location:

src/lemon

Files:

• concept/graph_component.h (modified) (5 diffs)
• concept/undir_graph.h (modified) (1 diff)
• iterable_graph_extender.h (modified) (2 diffs)
• undir_graph_extender.h (modified) (9 diffs)

src/lemon/concept/graph_component.h

@@ -506 +506 @@
     /// InEdgeIt you should instantiate it with character 'i' and for 
     /// OutEdgeIt with 'o'.
-    /// \todo check the name of the concept GraphIncEdgeIterator
-    template <typename _Graph, char _selector>
-    class GraphIncEdgeIterator : public _Graph::Edge {
+    /// \todo Is this a good name for this concept?
+    template <typename Graph,
+              typename Edge = typename Graph::Edge,
+              char _selector = '0'>
+    class GraphIncIterator : public Edge {
     public:
       /// Default constructor.
@@ -514 +516 @@
       /// @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;}
-
-      template <typename _GraphIncEdgeIterator>
-      struct Constraints {
-        typedef typename _Graph::Node Node;
-        typedef typename _Graph::Edge Edge;
-        void constraints() {
-          checkConcept<GraphItem<'e'>, _GraphIncEdgeIterator>();
-          _GraphIncEdgeIterator it1(graph, node);
+      bool operator!=(const GraphIncIterator&) const { return true;}
+
+      template <typename _GraphIncIterator>
+      struct Constraints {
+        typedef typename Graph::Node Node;
+        void constraints() {
+          checkConcept<GraphItem<'e'>, _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;
@@ -572 +576 @@
         Edge& edge;
         Node& node;
-        _Graph& graph;
-      };
-    };
+        Graph& graph;
+      };
+    };
+
+
     /// An empty iterable base graph class.
   
@@ -603 +609 @@
       /// This iterator goes trough the \e inccoming edges of a certain node
       /// of a graph.
-      typedef GraphIncEdgeIterator<Graph, 'i'> InEdgeIt;
+      typedef GraphIncIterator<Graph, Edge, 'i'> 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<Graph, 'o'> OutEdgeIt;
+      typedef GraphIncIterator<Graph, Edge, 'o'> OutEdgeIt;
     };
     
@@ -618 +624 @@
         checkConcept<GraphIterator<_Graph, typename _Graph::Edge>, typename _Graph::EdgeIt >();
         checkConcept<GraphIterator<_Graph, typename _Graph::Node>, typename _Graph::NodeIt >();
-        checkConcept<GraphIncEdgeIterator<_Graph, 'i'>, typename _Graph::InEdgeIt >();
-        checkConcept<GraphIncEdgeIterator<_Graph, 'o'>, typename _Graph::OutEdgeIt >();
+        checkConcept<GraphIncIterator<_Graph>, typename _Graph::InEdgeIt >();
+        checkConcept<GraphIncIterator<_Graph>, typename _Graph::OutEdgeIt >();
       }
     };

src/lemon/concept/undir_graph.h

@@ -68 +68 @@
         typedef typename Graph::UndirEdge UndirEdge;
         typedef typename Graph::UndirEdgeIt UndirEdgeIt;
+        typedef typename Graph::UndirIncEdgeIt UndirIncEdgeIt;
 
         checkConcept< GraphIterator<Graph, UndirEdge>, UndirEdgeIt >();
+
+        checkConcept<
+          GraphIncIterator<Graph, UndirEdge>,
+          UndirIncEdgeIt >();
       }
     };

src/lemon/iterable_graph_extender.h

@@ -132 +132 @@
     typedef IterableGraphExtender<_Base> Parent;
     typedef IterableUndirGraphExtender<_Base> Graph;
+    typedef typename Parent::Node Node;
 
     typedef typename Parent::UndirEdge UndirEdge;
@@ -157 +158 @@
     };
 
+    class UndirIncEdgeIt : public UndirEdge { 
+      const Graph* graph;
+      bool forward;
+      friend class IterableUndirGraphExtender;
+      template <typename G>
+      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;
 
   };

src/lemon/undir_graph_extender.h

@@ -71 +71 @@
     }
 
-    /// Source of the given Edge.
-    Node source(const Edge &e) const {
+  protected:
+
+    template <typename E>
+    Node _dirSource(const E &e) const {
       return e.forward ? Parent::source(e) : Parent::target(e);
     }
 
+    template <typename E>
+    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);
     }
 
@@ -88 +96 @@
     /// 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
@@ -123 +136 @@
     }
 
-    void firstOut(Edge &e, const Node &n) const {
+    
+  protected:
+
+    template <typename E>
+    void _dirFirstOut(E &e, const Node &n) const {
       Parent::firstOut(e,n);
       if( UndirEdge(e) != INVALID ) {
@@ -133 +150 @@
       }
     }
-    void firstIn(Edge &e, const Node &n) const {
+    template <typename E>
+    void _dirFirstIn(E &e, const Node &n) const {
       Parent::firstIn(e,n);
       if( UndirEdge(e) != INVALID ) {
@@ -144 +162 @@
     }
 
-    void nextOut(Edge &e) const {
+    template <typename E>
+    void _dirNextOut(E &e) const {
       if( e.forward ) {
         Parent::nextOut(e);
@@ -156 +175 @@
       }
     }
-    void nextIn(Edge &e) const {
+    template <typename E>
+    void _dirNextIn(E &e) const {
       if( e.forward ) {
         Parent::nextIn(e);
@@ -169 +189 @@
     }
 
+  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:
 
@@ -174 +210 @@
     /// 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 {
@@ -180 +226 @@
     }
 
-    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());
     }