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

Timestamp:

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

Author:

marci

Branch:

default

Phase:

public

Convert:

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

Message:

experimental bipartite graph wrapper

Location:

src/work

Files:

• list_graph.h (modified) (1 diff)
• marci/bipartite_graph_wrapper_test.cc (added)
• marci/graph_wrapper.h (modified) (2 diffs)
• marci/makefile (modified) (2 diffs)

src/work/list_graph.h

@@ -540 +540 @@
 
   class UndirListGraph : public ListGraph {
+  public:
     typedef SymEdgeIt OutEdgeIt;
     typedef SymEdgeIt InEdgeIt;

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)); 
     }
   };

src/work/marci/makefile

@@ -1 @@
-#CXX3 = g++-3.0
 CXX2 = g++-2.95
-#CXX3.3 = g++
 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
 CXX=$(CXX3)
 CC=$(CXX)
-#CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
 #LEDAROOT ?= /ledasrc/LEDA-4.1
 BOOSTROOT ?= /home/marci/boost
@@ -13 +10 @@
 
 LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
-BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand
+BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test
 #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda