Changeset 1697:4c593a4096da in lemon-0.x for lemon/graph_adaptor.h

Timestamp:

10/03/05 12:17:53 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Preliminary SplitGraphAdaptor?
And some other improvments

File:

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

lemon/graph_adaptor.h

@@ -66 +66 @@
   public:
     typedef _Graph Graph;
-    /// \todo Is it needed?
-    typedef Graph BaseGraph;
     typedef Graph ParentGraph;
 
@@ -94 +92 @@
     Node target(const Edge& e) const { return graph->target(e); }
 
+    typedef NodeNumTagIndicator<Graph> NodeNumTag;
     int nodeNum() const { return graph->nodeNum(); }
+    
+    typedef EdgeNumTagIndicator<Graph> EdgeNumTag;
     int edgeNum() const { return graph->edgeNum(); }
+
+    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;
+    Edge findEdge(const Node& source, const Node& target, 
+                  const Edge& prev = INVALID) {
+      return graph->findEdge(source, target, prev);
+    }
   
-    Node addNode() const { return Node(graph->addNode()); }
+    Node addNode() const { 
+      return Node(graph->addNode()); 
+    }
+
     Edge addEdge(const Node& source, const Node& target) const { 
-      return Edge(graph->addEdge(source, target)); }
+      return Edge(graph->addEdge(source, target)); 
+    }
 
     void erase(const Node& i) const { graph->erase(i); }
@@ -157 +168 @@
     typedef typename Parent::Edge Edge;
 
-    //    using Parent::first;
     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
 
-    //    using Parent::next;
     void nextIn(Edge& i) const { Parent::nextOut(i); }
     void nextOut(Edge& i) const { Parent::nextIn(i); }
@@ -305 +314 @@
     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; 
-    }
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
   };
 
@@ -414 +406 @@
     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; 
-    }
+    typedef False NodeNumTag;
+    typedef False EdgeNumTag;
   };
 
@@ -441 +416 @@
   
   SubGraphAdaptor shows the graph with filtered node-set and 
-  edge-set. 
+  edge-set. If the \c checked parameter is true then it filters the edgeset
+  to do not get invalid edges without source or target.
   Let \f$G=(V, A)\f$ be a directed graph 
   and suppose that the graph instance \c g of type ListGraph implements 
@@ -454 +430 @@
   only on edges leaving and entering a specific node which have true value.
 
-  We have to note that this does not mean that an 
-  induced subgraph is obtained, the node-iterator cares only the filter 
-  on the node-set, and the edge-iterators care only the filter on the 
-  edge-set. 
+  If the \c checked template parameter is false then we have to note that 
+  the node-iterator cares only the filter on the node-set, and the 
+  edge-iterator cares only the filter on the edge-set. This way the edge-map
+  should filter all edges which's source or target is filtered by the 
+  node-filter.
   \code
   typedef ListGraph Graph;
@@ -520 +497 @@
   An adaptor for hiding nodes from a graph.
   This adaptor specializes SubGraphAdaptor in the way that only the node-set 
-  can be filtered. Note that this does not mean of considering induced 
-  subgraph, the edge-iterators consider the original edge-set.
+  can be filtered. In usual case the checked parameter is true, we get the
+  induced subgraph. But if the checked parameter is false then we can only
+  filter only isolated nodes.
   \author Marton Makai
   */
@@ -704 +682 @@
     typedef typename Parent::Edge Edge;
     
-    /// \bug Why cant an edge say that it is forward or not??? 
-    /// By this, a pointer to the graph have to be stored
-    /// The implementation
     template <typename T>
     class EdgeMap {
@@ -1123 +1098 @@
       return 2*this->graph->edgeNum();
     }
-    //    KEEP_MAPS(Parent, BidirGraphAdaptor);
   };
 
@@ -1332 +1306 @@
 
   template <typename _Graph>
+  class SplitGraphAdaptorBase 
+    : public GraphAdaptorBase<_Graph> {
+  public:
+    typedef GraphAdaptorBase<_Graph> Parent;
+
+    class Node;
+    class Edge;
+    template <typename T> class NodeMap;
+    template <typename T> class EdgeMap;
+    
+
+    class Node : public Parent::Node {
+      friend class SplitGraphAdaptorBase;
+      template <typename T> friend class NodeMap;
+      typedef typename Parent::Node NodeParent;
+    private:
+
+      bool entry;
+      Node(typename Parent::Node _node, bool _entry)
+        : Parent::Node(_node), entry(_entry) {}
+      
+    public:
+      Node() {}
+      Node(Invalid) : NodeParent(INVALID), entry(true) {}
+
+      bool operator==(const Node& node) const {
+        return NodeParent::operator==(node) && entry == node.entry;
+      }
+      
+      bool operator!=(const Node& node) const {
+        return !(*this == node);
+      }
+      
+      bool operator<(const Node& node) const {
+        return NodeParent::operator<(node) || 
+          (NodeParent::operator==(node) && entry < node.entry);
+      }
+    };
+
+    /// \todo May we want VARIANT/union type
+    class Edge : public Parent::Edge {
+      friend class SplitGraphAdaptorBase;
+      template <typename T> friend class EdgeMap;
+    private:
+      typedef typename Parent::Edge EdgeParent;
+      typedef typename Parent::Node NodeParent;
+      NodeParent bind;
+
+      Edge(const EdgeParent& edge, const NodeParent& node)
+        : EdgeParent(edge), bind(node) {}
+    public:
+      Edge() {}
+      Edge(Invalid) : EdgeParent(INVALID), bind(INVALID) {}
+
+      bool operator==(const Edge& edge) const {
+        return EdgeParent::operator==(edge) && bind == edge.bind;
+      }
+      
+      bool operator!=(const Edge& edge) const {
+        return !(*this == edge);
+      }
+      
+      bool operator<(const Edge& edge) const {
+        return EdgeParent::operator<(edge) || 
+          (EdgeParent::operator==(edge) && bind < edge.bind);
+      }
+    };
+
+    void first(Node& node) const {
+      Parent::first(node);
+      node.entry = true;
+    } 
+
+    void next(Node& node) const {
+      if (node.entry) {
+        node.entry = false;
+      } else {
+        node.entry = true;
+        Parent::next(node);
+      }
+    }
+
+    void first(Edge& edge) const {
+      Parent::first(edge);
+      if ((typename Parent::Edge&)edge == INVALID) {
+        Parent::first(edge.bind);
+      } else {
+        edge.bind = INVALID;
+      }
+    }
+
+    void next(Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+        Parent::next(edge);
+        if ((typename Parent::Edge&)edge == INVALID) {
+          Parent::first(edge.bind);
+        }
+      } else {
+        Parent::next(edge.bind);
+      }      
+    }
+
+    void firstIn(Edge& edge, const Node& node) const {
+      if (node.entry) {
+        Parent::firstIn(edge, node);
+        edge.bind = INVALID;
+      } else {
+        (typename Parent::Edge&)edge = INVALID;
+        edge.bind = node;
+      }
+    }
+
+    void nextIn(Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+        Parent::nextIn(edge);
+      } else {
+        edge.bind = INVALID;
+      }      
+    }
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (!node.entry) {
+        Parent::firstOut(edge, node);
+        edge.bind = INVALID;
+      } else {
+        (typename Parent::Edge&)edge = INVALID;
+        edge.bind = node;
+      }
+    }
+
+    void nextOut(Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+        Parent::nextOut(edge);
+      } else {
+        edge.bind = INVALID;
+      }
+    }
+
+    Node source(const Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+        return Node(Parent::source(edge), false);
+      } else {
+        return Node(edge.bind, true);
+      }
+    }
+
+    Node target(const Edge& edge) const {
+      if ((typename Parent::Edge&)edge != INVALID) {
+        return Node(Parent::target(edge), true);
+      } else {
+        return Node(edge.bind, false);
+      }
+    }
+
+    static bool entryNode(const Node& node) {
+      return node.entry;
+    }
+
+    static bool exitNode(const Node& node) {
+      return !node.entry;
+    }
+
+    static Node getEntry(const typename Parent::Node& node) {
+      return Node(node, true);
+    }
+
+    static Node getExit(const typename Parent::Node& node) {
+      return Node(node, false);
+    }
+
+    static bool originalEdge(const Edge& edge) {
+      return (typename Parent::Edge&)edge != INVALID;
+    }
+
+    static bool bindingEdge(const Edge& edge) {
+      return edge.bind != INVALID;
+    }
+
+    static Node getBindedNode(const Edge& edge) {
+      return edge.bind;
+    }
+
+    int nodeNum() const {
+      return Parent::nodeNum() * 2;
+    }
+
+    typedef CompileTimeAnd<typename Parent::NodeNumTag, 
+                           typename Parent::EdgeNumTag> EdgeNumTag;
+    
+    int edgeNum() const {
+      return Parent::edgeNum() + Parent::nodeNum();
+    }
+
+    Edge findEdge(const Node& source, const Node& target, 
+                  const Edge& prev = INVALID) const {
+      if (exitNode(source) && entryNode(target)) {
+        return Parent::findEdge(source, target, prev);
+      } else {
+        if (prev == INVALID && entryNode(source) && exitNode(target) && 
+            (typename Parent::Node&)source == (typename Parent::Node&)target) {
+          return Edge(INVALID, source);
+        } else {
+          return INVALID;
+        }
+      }
+    }
+    
+    template <typename T>
+    class NodeMap : public MapBase<Node, T> {
+      typedef typename Parent::template NodeMap<T> NodeImpl;
+    public:
+      NodeMap(const SplitGraphAdaptorBase& _graph) 
+        : entry(_graph), exit(_graph) {}
+      NodeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
+        : entry(_graph, t), exit(_graph, t) {}
+      
+      void set(const Node& key, const T& val) {
+        if (key.entry) { entry.set(key, val); }
+        else {exit.set(key, val); }
+      }
+      
+      typename ReferenceMapTraits<NodeImpl>::Reference 
+      operator[](const Node& key) {
+        if (key.entry) { return entry[key]; }
+        else { return exit[key]; }
+      }
+
+      T operator[](const Node& key) const {
+        if (key.entry) { return entry[key]; }
+        else { return exit[key]; }
+      }
+
+    private:
+      NodeImpl entry, exit;
+    };
+
+    template <typename T>
+    class EdgeMap : public MapBase<Edge, T> {
+      typedef typename Parent::template NodeMap<T> NodeImpl;
+      typedef typename Parent::template EdgeMap<T> EdgeImpl;
+    public:
+      EdgeMap(const SplitGraphAdaptorBase& _graph) 
+        : bind(_graph), orig(_graph) {}
+      EdgeMap(const SplitGraphAdaptorBase& _graph, const T& t) 
+        : bind(_graph, t), orig(_graph, t) {}
+      
+      void set(const Edge& key, const T& val) {
+        if ((typename Parent::Edge&)key != INVALID) { orig.set(key, val); }
+        else {bind.set(key.bind, val); }
+      }
+      
+      typename ReferenceMapTraits<EdgeImpl>::Reference
+      operator[](const Edge& key) {
+        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
+        else {return bind[key.bind]; }
+      }
+
+      T operator[](const Edge& key) const {
+        if ((typename Parent::Edge&)key != INVALID) { return orig[key]; }
+        else {return bind[key.bind]; }
+      }
+
+    private:
+      typename Parent::template NodeMap<T> bind;
+      typename Parent::template EdgeMap<T> orig;
+    };
+
+    template <typename EntryMap, typename ExitMap>
+    class CombinedNodeMap : public MapBase<Node, typename EntryMap::Value> {
+    public:
+      typedef MapBase<Node, typename EntryMap::Value> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+
+      CombinedNodeMap(EntryMap& _entryMap, ExitMap& _exitMap) 
+        : entryMap(_entryMap), exitMap(_exitMap) {}
+
+      Value& operator[](const Key& key) {
+        if (key.entry) {
+          return entryMap[key];
+        } else {
+          return exitMap[key];
+        }
+      }
+
+      Value operator[](const Key& key) const {
+        if (key.entry) {
+          return entryMap[key];
+        } else {
+          return exitMap[key];
+        }
+      }
+
+      void set(const Key& key, const Value& value) {
+        if (key.entry) {
+          entryMap.set(key, value);
+        } else {
+          exitMap.set(key, value);
+        }
+      }
+      
+    private:
+      
+      EntryMap& entryMap;
+      ExitMap& exitMap;
+      
+    };
+
+    template <typename EdgeMap, typename NodeMap>
+    class CombinedEdgeMap : public MapBase<Edge, typename EdgeMap::Value> {
+    public:
+      typedef MapBase<Edge, typename EdgeMap::Value> Parent;
+
+      typedef typename Parent::Key Key;
+      typedef typename Parent::Value Value;
+
+      CombinedEdgeMap(EdgeMap& _edgeMap, NodeMap& _nodeMap) 
+        : edgeMap(_edgeMap), nodeMap(_nodeMap) {}
+
+      void set(const Edge& edge, const Value& val) {
+        if (SplitGraphAdaptorBase::originalEdge(edge)) {
+          edgeMap.set(edge, val);
+        } else {
+          nodeMap.set(SplitGraphAdaptorBase::bindedNode(edge), val);
+        }
+      }
+
+      Value operator[](const Key& edge) const {
+        if (SplitGraphAdaptorBase::originalEdge(edge)) {
+          return edgeMap[edge];
+        } else {
+          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
+        }
+      }      
+
+      Value& operator[](const Key& edge) {
+        if (SplitGraphAdaptorBase::originalEdge(edge)) {
+          return edgeMap[edge];
+        } else {
+          return nodeMap[SplitGraphAdaptorBase::bindedNode(edge)];
+        }
+      }      
+      
+    private:
+      EdgeMap& edgeMap;
+      NodeMap& nodeMap;
+    };
+
+  };
+
+  template <typename _Graph>
+  class SplitGraphAdaptor 
+    : public IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > {
+  public:
+    typedef IterableGraphExtender<SplitGraphAdaptorBase<_Graph> > Parent;
+
+    SplitGraphAdaptor(_Graph& graph) {
+      Parent::setGraph(graph);
+    }
+
+
+  };
+
+  template <typename _Graph>
   class NewEdgeSetAdaptorBase {
   public: