# HG changeset patch
# User marci
# Date 1082580480 0
# Node ID 0beed7a490636398513120fdcb415906e17e54c8
# Parent  825647d4eca747611a7d2fc3890c8d2e97397a87
experimental bipartite graph wrapper

diff -r 825647d4eca7 -r 0beed7a49063 src/work/list_graph.h
--- a/src/work/list_graph.h	Wed Apr 21 19:52:09 2004 +0000
+++ b/src/work/list_graph.h	Wed Apr 21 20:48:00 2004 +0000
@@ -539,6 +539,7 @@
   };
 
   class UndirListGraph : public ListGraph {
+  public:
     typedef SymEdgeIt OutEdgeIt;
     typedef SymEdgeIt InEdgeIt;
   };
diff -r 825647d4eca7 -r 0beed7a49063 src/work/marci/bipartite_graph_wrapper_test.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Wed Apr 21 20:48:00 2004 +0000
@@ -0,0 +1,84 @@
+// -*- c++ -*-
+#include <iostream>
+#include <fstream>
+#include <vector>
+
+#include <list_graph.h>
+#include <smart_graph.h>
+//#include <dimacs.h>
+#include <time_measure.h>
+#include <for_each_macros.h>
+#include <bfs_iterator.h>
+#include <graph_wrapper.h>
+
+using namespace hugo;
+
+int main() {
+  typedef UndirListGraph Graph; 
+  typedef Graph::Node Node;
+  typedef Graph::NodeIt NodeIt;
+  typedef Graph::Edge Edge;
+  typedef Graph::EdgeIt EdgeIt;
+  typedef Graph::OutEdgeIt OutEdgeIt;
+
+  Graph g;
+  //Node s, t;
+  //Graph::EdgeMap<int> cap(g);
+  //readDimacsMaxFlow(std::cin, g, s, t, cap);
+  std::vector<Graph::Node> s_nodes;
+  std::vector<Graph::Node> t_nodes;
+  for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
+  for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
+  g.addEdge(s_nodes[0], t_nodes[2]);
+  g.addEdge(t_nodes[1], s_nodes[2]);
+  
+  Graph::NodeMap<int> ref_map(g, -1);
+  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
+  for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
+  for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
+  typedef BipartiteGraphWrapper<Graph> BGW;
+  BGW bgw(g, bipartite_map);
+  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
+    std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
+  }
+//   Graph::NodeMap<OutEdgeIt> pred(G);
+//   Timer ts;
+//   {
+//     ts.reset();
+//     Graph::NodeMap<bool> reached(G);
+//     reached.set(s, true);
+//     pred.set(s, INVALID);
+//     std::queue<Node> bfs_queue;
+//     bfs_queue.push(t);
+//     while (!bfs_queue.empty()) {
+//       Node v=bfs_queue.front();	
+//       bfs_queue.pop();
+//       OutEdgeIt e;
+//       for(G.first(e,v); G.valid(e); G.next(e)) {
+// 	Node w=G.head(e);
+// 	if (!reached[w]) {
+// 	  bfs_queue.push(w);
+// 	  reached.set(w, true);
+// 	  pred.set(w, e);
+// 	}
+//       }
+//     }
+
+//     std::cout << ts << std::endl;
+//   }
+
+//   {
+//     ts.reset();      
+//     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
+//     bfs.pushAndSetReached(s);
+//     pred.set(s, INVALID);
+//     while (!bfs.finished()) { 
+//       ++bfs; 
+//       if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
+// 	pred.set(bfs.bNode(), bfs);
+//     }
+//     std::cout << ts << std::endl;
+//   }
+
+  return 0;
+}
diff -r 825647d4eca7 -r 0beed7a49063 src/work/marci/graph_wrapper.h
--- a/src/work/marci/graph_wrapper.h	Wed Apr 21 19:52:09 2004 +0000
+++ b/src/work/marci/graph_wrapper.h	Wed Apr 21 20:48:00 2004 +0000
@@ -3,6 +3,7 @@
 #define HUGO_GRAPH_WRAPPER_H
 
 #include <invalid.h>
+#include <iter_map.h>
 
 namespace hugo {
 
@@ -865,6 +866,115 @@
     }
   };
 
+  /// 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)); 
+    }
+  };
+
 
 
 //   /// experimentral, do not try it.
diff -r 825647d4eca7 -r 0beed7a49063 src/work/marci/makefile
--- a/src/work/marci/makefile	Wed Apr 21 19:52:09 2004 +0000
+++ b/src/work/marci/makefile	Wed Apr 21 20:48:00 2004 +0000
@@ -1,10 +1,7 @@
-#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
 INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
@@ -12,7 +9,7 @@
 CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
 
 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
 
 all: $(BINARIES)