1.1 --- a/src/work/list_graph.h	Wed Apr 21 19:52:09 2004 +0000
     1.2 +++ b/src/work/list_graph.h	Wed Apr 21 20:48:00 2004 +0000
     1.3 @@ -539,6 +539,7 @@
     1.4    };
     1.5  
     1.6    class UndirListGraph : public ListGraph {
     1.7 +  public:
     1.8      typedef SymEdgeIt OutEdgeIt;
     1.9      typedef SymEdgeIt InEdgeIt;
    1.10    };

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/marci/bipartite_graph_wrapper_test.cc	Wed Apr 21 20:48:00 2004 +0000
     2.3 @@ -0,0 +1,84 @@
     2.4 +// -*- c++ -*-
     2.5 +#include <iostream>
     2.6 +#include <fstream>
     2.7 +#include <vector>
     2.8 +
     2.9 +#include <list_graph.h>
    2.10 +#include <smart_graph.h>
    2.11 +//#include <dimacs.h>
    2.12 +#include <time_measure.h>
    2.13 +#include <for_each_macros.h>
    2.14 +#include <bfs_iterator.h>
    2.15 +#include <graph_wrapper.h>
    2.16 +
    2.17 +using namespace hugo;
    2.18 +
    2.19 +int main() {
    2.20 +  typedef UndirListGraph Graph; 
    2.21 +  typedef Graph::Node Node;
    2.22 +  typedef Graph::NodeIt NodeIt;
    2.23 +  typedef Graph::Edge Edge;
    2.24 +  typedef Graph::EdgeIt EdgeIt;
    2.25 +  typedef Graph::OutEdgeIt OutEdgeIt;
    2.26 +
    2.27 +  Graph g;
    2.28 +  //Node s, t;
    2.29 +  //Graph::EdgeMap<int> cap(g);
    2.30 +  //readDimacsMaxFlow(std::cin, g, s, t, cap);
    2.31 +  std::vector<Graph::Node> s_nodes;
    2.32 +  std::vector<Graph::Node> t_nodes;
    2.33 +  for (int i=0; i<3; ++i) s_nodes.push_back(g.addNode());
    2.34 +  for (int i=0; i<3; ++i) t_nodes.push_back(g.addNode());
    2.35 +  g.addEdge(s_nodes[0], t_nodes[2]);
    2.36 +  g.addEdge(t_nodes[1], s_nodes[2]);
    2.37 +  
    2.38 +  Graph::NodeMap<int> ref_map(g, -1);
    2.39 +  IterableBoolMap< Graph::NodeMap<int> > bipartite_map(ref_map);
    2.40 +  for (int i=0; i<3; ++i) bipartite_map.insert(s_nodes[i], false);
    2.41 +  for (int i=0; i<3; ++i) bipartite_map.insert(t_nodes[i], true);
    2.42 +  typedef BipartiteGraphWrapper<Graph> BGW;
    2.43 +  BGW bgw(g, bipartite_map);
    2.44 +  FOR_EACH_LOC(BGW::EdgeIt, e, bgw) {
    2.45 +    std::cout << bgw.tail(e) << "->" << bgw.head(e) << std::endl;
    2.46 +  }
    2.47 +//   Graph::NodeMap<OutEdgeIt> pred(G);
    2.48 +//   Timer ts;
    2.49 +//   {
    2.50 +//     ts.reset();
    2.51 +//     Graph::NodeMap<bool> reached(G);
    2.52 +//     reached.set(s, true);
    2.53 +//     pred.set(s, INVALID);
    2.54 +//     std::queue<Node> bfs_queue;
    2.55 +//     bfs_queue.push(t);
    2.56 +//     while (!bfs_queue.empty()) {
    2.57 +//       Node v=bfs_queue.front();	
    2.58 +//       bfs_queue.pop();
    2.59 +//       OutEdgeIt e;
    2.60 +//       for(G.first(e,v); G.valid(e); G.next(e)) {
    2.61 +// 	Node w=G.head(e);
    2.62 +// 	if (!reached[w]) {
    2.63 +// 	  bfs_queue.push(w);
    2.64 +// 	  reached.set(w, true);
    2.65 +// 	  pred.set(w, e);
    2.66 +// 	}
    2.67 +//       }
    2.68 +//     }
    2.69 +
    2.70 +//     std::cout << ts << std::endl;
    2.71 +//   }
    2.72 +
    2.73 +//   {
    2.74 +//     ts.reset();      
    2.75 +//     BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
    2.76 +//     bfs.pushAndSetReached(s);
    2.77 +//     pred.set(s, INVALID);
    2.78 +//     while (!bfs.finished()) { 
    2.79 +//       ++bfs; 
    2.80 +//       if (G.valid(bfs) && bfs.isBNodeNewlyReached()) 
    2.81 +// 	pred.set(bfs.bNode(), bfs);
    2.82 +//     }
    2.83 +//     std::cout << ts << std::endl;
    2.84 +//   }
    2.85 +
    2.86 +  return 0;
    2.87 +}

     3.1 --- a/src/work/marci/graph_wrapper.h	Wed Apr 21 19:52:09 2004 +0000
     3.2 +++ b/src/work/marci/graph_wrapper.h	Wed Apr 21 20:48:00 2004 +0000
     3.3 @@ -3,6 +3,7 @@
     3.4  #define HUGO_GRAPH_WRAPPER_H
     3.5  
     3.6  #include <invalid.h>
     3.7 +#include <iter_map.h>
     3.8  
     3.9  namespace hugo {
    3.10  
    3.11 @@ -865,6 +866,115 @@
    3.12      }
    3.13    };
    3.14  
    3.15 +  /// A wrapper for composing a bipartite graph.
    3.16 +  /// \c _graph have to be a reference to an undirected graph \c Graph 
    3.17 +  /// and 
    3.18 +  /// \c _s_false_t_true_map is an \c IterableBoolMap 
    3.19 +  /// reference containing the elements for the 
    3.20 +  /// color classes S and T.
    3.21 +  /// It results in a directed graph such that the edges are oriented from 
    3.22 +  /// S to T.
    3.23 +  template<typename Graph> 
    3.24 +  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
    3.25 +    typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
    3.26 +    SFalseTTrueMap* s_false_t_true_map;
    3.27 +    
    3.28 +  public:
    3.29 +    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map) 
    3.30 +      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
    3.31 +    }
    3.32 +    typedef typename GraphWrapper<Graph>::Node Node;
    3.33 +    //using GraphWrapper<Graph>::NodeIt;
    3.34 +    typedef typename GraphWrapper<Graph>::Edge Edge;
    3.35 +    //using GraphWrapper<Graph>::EdgeIt;
    3.36 +    class SNodeIt {
    3.37 +      Node n;
    3.38 +    public:
    3.39 +      SNodeIt() { }
    3.40 +      SNodeIt(const Invalid& i) : n(i) { }
    3.41 +      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
    3.42 +	_G.s_false_t_true_map->first(n, false); 
    3.43 +      }
    3.44 +      operator Node() const { return n; }
    3.45 +    };
    3.46 +    class TNodeIt {
    3.47 +      Node n;
    3.48 +    public:
    3.49 +      TNodeIt() { }
    3.50 +      TNodeIt(const Invalid& i) : n(i) { }
    3.51 +      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) { 
    3.52 +	_G.s_false_t_true_map->first(n, true); 
    3.53 +      }
    3.54 +      operator Node() const { return n; }
    3.55 +    };
    3.56 +    class OutEdgeIt { 
    3.57 +    public:
    3.58 +      typename Graph::OutEdgeIt e;
    3.59 +    public:
    3.60 +      OutEdgeIt() { }
    3.61 +      OutEdgeIt(const Invalid& i) : e(i) { }
    3.62 +      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    3.63 +	if (!(*(_G.s_false_t_true_map))[_n]) 
    3.64 +	  e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
    3.65 +	else 
    3.66 +	  e=INVALID;
    3.67 +      }
    3.68 +      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    3.69 +    };
    3.70 +    class InEdgeIt { 
    3.71 +    public:
    3.72 +      typename Graph::InEdgeIt e;
    3.73 +    public:
    3.74 +      InEdgeIt() { }
    3.75 +      InEdgeIt(const Invalid& i) : e(i) { }
    3.76 +      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
    3.77 +	if ((*(_G.s_false_t_true_map))[_n]) 
    3.78 +	  e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
    3.79 +	else 
    3.80 +	  e=INVALID;
    3.81 +      }
    3.82 +      operator Edge() const { return Edge(typename Graph::Edge(e)); }
    3.83 +    };
    3.84 +
    3.85 +    using GraphWrapper<Graph>::first;
    3.86 +    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
    3.87 +    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
    3.88 +
    3.89 +    using GraphWrapper<Graph>::next;
    3.90 +    SNodeIt& next(SNodeIt& n) const { 
    3.91 +      this->s_false_t_true_map->next(n); return n; 
    3.92 +    }
    3.93 +    TNodeIt& next(TNodeIt& n) const { 
    3.94 +      this->s_false_t_true_map->next(n); return n; 
    3.95 +    }
    3.96 +
    3.97 +    Node tail(const Edge& e) { 
    3.98 +      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
    3.99 +	return Node(this->graph->tail(e));
   3.100 +      else
   3.101 +	return Node(this->graph->head(e));	
   3.102 +    }
   3.103 +    Node head(const Edge& e) { 
   3.104 +      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)]) 
   3.105 +	return Node(this->graph->head(e));
   3.106 +      else
   3.107 +	return Node(this->graph->tail(e));	
   3.108 +    }
   3.109 +
   3.110 +    Node aNode(const OutEdgeIt& e) const { 
   3.111 +      return Node(this->graph->aNode(e.e)); 
   3.112 +    }
   3.113 +    Node aNode(const InEdgeIt& e) const { 
   3.114 +      return Node(this->graph->aNode(e.e)); 
   3.115 +    }
   3.116 +    Node bNode(const OutEdgeIt& e) const { 
   3.117 +      return Node(this->graph->bNode(e.e)); 
   3.118 +    }
   3.119 +    Node bNode(const InEdgeIt& e) const { 
   3.120 +      return Node(this->graph->bNode(e.e)); 
   3.121 +    }
   3.122 +  };
   3.123 +
   3.124  
   3.125  
   3.126  //   /// experimentral, do not try it.

     4.1 --- a/src/work/marci/makefile	Wed Apr 21 19:52:09 2004 +0000
     4.2 +++ b/src/work/marci/makefile	Wed Apr 21 20:48:00 2004 +0000
     4.3 @@ -1,10 +1,7 @@
     4.4 -#CXX3 = g++-3.0
     4.5  CXX2 = g++-2.95
     4.6 -#CXX3.3 = g++
     4.7  CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
     4.8  CXX=$(CXX3)
     4.9  CC=$(CXX)
    4.10 -#CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
    4.11  #LEDAROOT ?= /ledasrc/LEDA-4.1
    4.12  BOOSTROOT ?= /home/marci/boost
    4.13  INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos} -I$(BOOSTROOT)
    4.14 @@ -12,7 +9,7 @@
    4.15  CXXFLAGS = -g -O -W -Wall $(INCLUDEDIRS) -ansi -pedantic -ftemplate-depth-30
    4.16  
    4.17  LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    4.18 -BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand
    4.19 +BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test
    4.20  #gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    4.21  
    4.22  all: $(BINARIES)