Changeset 368:0beed7a49063 in lemon-0.x for src/work/marci/graph_wrapper.h

Timestamp:

04/21/04 22:48:00 (21 years ago)

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

experimental bipartite graph wrapper

File:

• src/work/marci/graph_wrapper.h (modified) (2 diffs)

src/work/marci/graph_wrapper.h

@@ -4 +4 @@
 
 #include <invalid.h>
+#include <iter_map.h>
 
 namespace hugo {
@@ -863 +864 @@
       this->next(f);
       first_out_edges->set(this->tail(e), f.e);
+    }
+  };
+
+  /// A wrapper for composing a bipartite graph.
+  /// \c _graph have to be a reference to an undirected graph \c Graph 
+  /// and 
+  /// \c _s_false_t_true_map is an \c IterableBoolMap 
+  /// reference containing the elements for the 
+  /// color classes S and T.
+  /// It results in a directed graph such that the edges are oriented from 
+  /// S to T.
+  template<typename Graph> 
+  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
+    typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
+    SFalseTTrueMap* s_false_t_true_map;
+    
+  public:
+    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
+      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
+    }
+    typedef typename GraphWrapper<Graph>::Node Node;
+    //using GraphWrapper<Graph>::NodeIt;
+    typedef typename GraphWrapper<Graph>::Edge Edge;
+    //using GraphWrapper<Graph>::EdgeIt;
+    class SNodeIt {
+      Node n;
+    public:
+      SNodeIt() { }
+      SNodeIt(const Invalid& i) : n(i) { }
+      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
+        _G.s_false_t_true_map->first(n, false); 
+      }
+      operator Node() const { return n; }
+    };
+    class TNodeIt {
+      Node n;
+    public:
+      TNodeIt() { }
+      TNodeIt(const Invalid& i) : n(i) { }
+      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
+        _G.s_false_t_true_map->first(n, true); 
+      }
+      operator Node() const { return n; }
+    };
+    class OutEdgeIt { 
+    public:
+      typename Graph::OutEdgeIt e;
+    public:
+      OutEdgeIt() { }
+      OutEdgeIt(const Invalid& i) : e(i) { }
+      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
+        if (!(*(_G.s_false_t_true_map))[_n]) 
+          e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
+        else 
+          e=INVALID;
+      }
+      operator Edge() const { return Edge(typename Graph::Edge(e)); }
+    };
+    class InEdgeIt { 
+    public:
+      typename Graph::InEdgeIt e;
+    public:
+      InEdgeIt() { }
+      InEdgeIt(const Invalid& i) : e(i) { }
+      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
+        if ((*(_G.s_false_t_true_map))[_n]) 
+          e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
+        else 
+          e=INVALID;
+      }
+      operator Edge() const { return Edge(typename Graph::Edge(e)); }
+    };
+
+    using GraphWrapper<Graph>::first;
+    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
+    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
+
+    using GraphWrapper<Graph>::next;
+    SNodeIt& next(SNodeIt& n) const { 
+      this->s_false_t_true_map->next(n); return n; 
+    }
+    TNodeIt& next(TNodeIt& n) const { 
+      this->s_false_t_true_map->next(n); return n; 
+    }
+
+    Node tail(const Edge& e) { 
+      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
+        return Node(this->graph->tail(e));
+      else
+        return Node(this->graph->head(e));      
+    }
+    Node head(const Edge& e) { 
+      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
+        return Node(this->graph->head(e));
+      else
+        return Node(this->graph->tail(e));      
+    }
+
+    Node aNode(const OutEdgeIt& e) const { 
+      return Node(this->graph->aNode(e.e)); 
+    }
+    Node aNode(const InEdgeIt& e) const { 
+      return Node(this->graph->aNode(e.e)); 
+    }
+    Node bNode(const OutEdgeIt& e) const { 
+      return Node(this->graph->bNode(e.e)); 
+    }
+    Node bNode(const InEdgeIt& e) const { 
+      return Node(this->graph->bNode(e.e)); 
     }
   };