Changeset 1681:84e43c7ca1e3 in lemon-0.x for lemon/graph_adaptor.h

Timestamp:

09/12/05 13:24:54 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

SubGraphAdaptors? with edge checking functionality.

Improved grid_graph_demo

File:

• lemon/graph_adaptor.h (modified) (8 diffs)

lemon/graph_adaptor.h

@@ -207 +207 @@
 
   
-  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  template <typename _Graph, typename NodeFilterMap, 
+            typename EdgeFilterMap, bool checked = true>
   class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {
   public:
@@ -226 +227 @@
 
   public:
-//     SubGraphAdaptorBase(Graph& _graph, 
-//                      NodeFilterMap& _node_filter_map, 
-//                      EdgeFilterMap& _edge_filter_map) : 
-//       Parent(&_graph), 
-//       node_filter_map(&node_filter_map), 
-//       edge_filter_map(&edge_filter_map) { }
 
     typedef typename Parent::Node Node;
@@ -240 +235 @@
       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
     }
+
     void first(Edge& i) const { 
       Parent::first(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
-    }
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+             || !(*node_filter_map)[Parent::source(i)]
+             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
     void firstIn(Edge& i, const Node& n) const { 
       Parent::firstIn(i, n); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
-    }
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
+    }
+
     void firstOut(Edge& i, const Node& n) const { 
       Parent::firstOut(i, n); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
     }
 
@@ -257 +259 @@
       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
     }
+
     void next(Edge& i) const { 
       Parent::next(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
-    }
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+             || !(*node_filter_map)[Parent::source(i)]
+             || !(*node_filter_map)[Parent::target(i)])) Parent::next(i); 
+    }
+
     void nextIn(Edge& i) const { 
       Parent::nextIn(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
-    }
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+             || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i); 
+    }
+
     void nextOut(Edge& i) const { 
       Parent::nextOut(i); 
-      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
+      while (i!=INVALID && (!(*edge_filter_map)[i] 
+             || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i); 
     }
 
@@ -315 +324 @@
       return i; 
     }
-
-
+  };
+
+  template <typename _Graph, typename NodeFilterMap, typename EdgeFilterMap>
+  class SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, false> 
+    : public GraphAdaptorBase<_Graph> {
+  public:
+    typedef _Graph Graph;
+    typedef GraphAdaptorBase<_Graph> Parent;
+  protected:
+    NodeFilterMap* node_filter_map;
+    EdgeFilterMap* edge_filter_map;
+    SubGraphAdaptorBase() : Parent(), 
+                            node_filter_map(0), edge_filter_map(0) { }
+
+    void setNodeFilterMap(NodeFilterMap& _node_filter_map) {
+      node_filter_map=&_node_filter_map;
+    }
+    void setEdgeFilterMap(EdgeFilterMap& _edge_filter_map) {
+      edge_filter_map=&_edge_filter_map;
+    }
+
+  public:
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    void first(Node& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+
+    void first(Edge& i) const { 
+      Parent::first(i); 
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
+    }
+
+    void firstIn(Edge& i, const Node& n) const { 
+      Parent::firstIn(i, n); 
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
+    }
+
+    void firstOut(Edge& i, const Node& n) const { 
+      Parent::firstOut(i, n); 
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
+    }
+
+    void next(Node& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i); 
+    }
+    void next(Edge& i) const { 
+      Parent::next(i); 
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::next(i); 
+    }
+    void nextIn(Edge& i) const { 
+      Parent::nextIn(i); 
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextIn(i); 
+    }
+
+    void nextOut(Edge& i) const { 
+      Parent::nextOut(i); 
+      while (i!=INVALID && !(*edge_filter_map)[i]) Parent::nextOut(i); 
+    }
+
+    /// This function hides \c n in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c n  
+    /// to be false in the corresponding node-map.
+    void hide(const Node& n) const { node_filter_map->set(n, false); }
+
+    /// This function hides \c e in the graph, i.e. the iteration 
+    /// jumps over it. This is done by simply setting the value of \c e  
+    /// to be false in the corresponding edge-map.
+    void hide(const Edge& e) const { edge_filter_map->set(e, false); }
+
+    /// The value of \c n is set to be true in the node-map which stores 
+    /// hide information. If \c n was hidden previuosly, then it is shown 
+    /// again
+     void unHide(const Node& n) const { node_filter_map->set(n, true); }
+
+    /// The value of \c e is set to be true in the edge-map which stores 
+    /// hide information. If \c e was hidden previuosly, then it is shown 
+    /// again
+    void unHide(const Edge& e) const { edge_filter_map->set(e, true); }
+
+    /// Returns true if \c n is hidden.
+    bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }
+
+    /// Returns true if \c n is hidden.
+    bool hidden(const Edge& e) const { return !(*edge_filter_map)[e]; }
+
+    /// \warning This is a linear time operation and works only if s
+    /// \c Graph::NodeIt is defined.
+    /// \todo assign tags.
+    int nodeNum() const { 
+      int i=0;
+      Node n;
+      for (first(n); n!=INVALID; next(n)) ++i;
+      return i; 
+    }
+
+    /// \warning This is a linear time operation and works only if 
+    /// \c Graph::EdgeIt is defined.
+    /// \todo assign tags.
+    int edgeNum() const { 
+      int i=0;
+      Edge e;
+      for (first(e); e!=INVALID; next(e)) ++i;
+      return i; 
+    }
   };
 
@@ -376 +492 @@
   */
   template<typename _Graph, typename NodeFilterMap, 
-           typename EdgeFilterMap>
+           typename EdgeFilterMap, bool checked = true>
   class SubGraphAdaptor : 
     public IterableGraphExtender<
-    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > {
+    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {
   public:
     typedef _Graph Graph;
@@ -408 +524 @@
   \author Marton Makai
   */
-  template<typename Graph, typename NodeFilterMap>
+  template<typename Graph, typename NodeFilterMap, bool checked = true>
   class NodeSubGraphAdaptor : 
     public SubGraphAdaptor<Graph, NodeFilterMap, 
-                           ConstMap<typename Graph::Edge,bool> > {
+                           ConstMap<typename Graph::Edge,bool>, checked> {
   public:
     typedef SubGraphAdaptor<Graph, NodeFilterMap, 
@@ -561 +677 @@
   class EdgeSubGraphAdaptor : 
     public SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 
-                           EdgeFilterMap> {
+                           EdgeFilterMap, false> {
   public:
     typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>,