src/lemon/graph_wrapper.h
changeset 1398 2f21cc34a245
parent 1359 1581f961cfaa
equal deleted inserted replaced
24:0937b718a3c0 25:7826d4e0f002
    26 ///\author Marton Makai
    26 ///\author Marton Makai
    27 
    27 
    28 #include <lemon/invalid.h>
    28 #include <lemon/invalid.h>
    29 #include <lemon/maps.h>
    29 #include <lemon/maps.h>
    30 #include <lemon/bits/iterable_graph_extender.h>
    30 #include <lemon/bits/iterable_graph_extender.h>
       
    31 #include <lemon/bits/undir_graph_extender.h>
    31 #include <iostream>
    32 #include <iostream>
    32 
    33 
    33 namespace lemon {
    34 namespace lemon {
    34 
    35 
    35   // Graph wrappers
    36   // Graph wrappers
   149     RevGraphWrapperBase() : Parent() { }
   150     RevGraphWrapperBase() : Parent() { }
   150   public:
   151   public:
   151     typedef typename Parent::Node Node;
   152     typedef typename Parent::Node Node;
   152     typedef typename Parent::Edge Edge;
   153     typedef typename Parent::Edge Edge;
   153 
   154 
   154     using Parent::first;
   155     //    using Parent::first;
   155     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
   156     void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
   156     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
   157     void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
   157 
   158 
   158     using Parent::next;
   159     //    using Parent::next;
   159     void nextIn(Edge& i) const { Parent::nextOut(i); }
   160     void nextIn(Edge& i) const { Parent::nextOut(i); }
   160     void nextOut(Edge& i) const { Parent::nextIn(i); }
   161     void nextOut(Edge& i) const { Parent::nextIn(i); }
   161 
   162 
   162     Node source(const Edge& e) const { return Parent::target(e); }
   163     Node source(const Edge& e) const { return Parent::target(e); }
   163     Node target(const Edge& e) const { return Parent::source(e); }
   164     Node target(const Edge& e) const { return Parent::source(e); }
   563       Parent::setNodeFilterMap(const_true_map);
   564       Parent::setNodeFilterMap(const_true_map);
   564       Parent::setEdgeFilterMap(_edge_filter_map);
   565       Parent::setEdgeFilterMap(_edge_filter_map);
   565     }
   566     }
   566   };
   567   };
   567 
   568 
   568 
   569   template <typename _Graph>
   569   template<typename Graph>
   570   class UndirGraphWrapperBase : 
   570   class UndirGraphWrapper : public GraphWrapper<Graph> {
   571     public UndirGraphExtender<GraphWrapperBase<_Graph> > {
   571   public:
   572   public:
   572     typedef GraphWrapper<Graph> Parent; 
   573     typedef _Graph Graph;
   573   protected:
   574     typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
   574     UndirGraphWrapper() : GraphWrapper<Graph>() { }
   575   protected:
       
   576     UndirGraphWrapperBase() : Parent() { }
       
   577   public:
       
   578     typedef typename Parent::UndirEdge UndirEdge;
       
   579     typedef typename Parent::Edge Edge;
   575     
   580     
   576   public:
   581     /// \bug Why cant an edge say that it is forward or not??? 
   577     typedef typename GraphWrapper<Graph>::Node Node;
   582     /// By this, a pointer to the graph have to be stored
   578     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
   583     /// The implementation
   579     typedef typename GraphWrapper<Graph>::Edge Edge;
   584     template <typename T>
   580     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
   585     class EdgeMap {
   581 
   586     protected:
   582     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { }  
   587       const UndirGraphWrapperBase<_Graph>* g;
   583 
   588       template <typename TT> friend class EdgeMap;
   584     class OutEdgeIt {
   589       typename _Graph::template EdgeMap<T> forward_map, backward_map; 
   585       friend class UndirGraphWrapper<Graph>;
       
   586       bool out_or_in; //true iff out
       
   587       typename Graph::OutEdgeIt out;
       
   588       typename Graph::InEdgeIt in;
       
   589     public:
   590     public:
   590       OutEdgeIt() { }
   591       typedef T Value;
   591       OutEdgeIt(const Invalid& i) : Edge(i) { }
   592       typedef Edge Key;
   592       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
   593       
   593 	out_or_in=true; _G.graph->first(out, _n);
   594       EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g), 
   594 	if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);	}
   595 	forward_map(*(g->graph)), backward_map(*(g->graph)) { }
   595       } 
   596 
   596       operator Edge() const { 
   597       EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g), 
   597 	if (out_or_in) return Edge(out); else return Edge(in); 
   598 	forward_map(*(g->graph), a), backward_map(*(g->graph), a) { }
       
   599       
       
   600       void set(Edge e, T a) { 
       
   601 	if (g->forward(e)) 
       
   602 	  forward_map.set(e, a); 
       
   603 	else 
       
   604 	  backward_map.set(e, a); 
       
   605       }
       
   606 
       
   607       T operator[](Edge e) const { 
       
   608 	if (g->forward(e)) 
       
   609 	  return forward_map[e]; 
       
   610 	else 
       
   611 	  return backward_map[e]; 
   598       }
   612       }
   599     };
   613     };
   600 
   614         
   601     typedef OutEdgeIt InEdgeIt; 
   615     template <typename T>
   602 
   616     class UndirEdgeMap {
   603     using GraphWrapper<Graph>::first;
   617       template <typename TT> friend class UndirEdgeMap;
   604     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const { 
   618       typename _Graph::template EdgeMap<T> map; 
   605       i=OutEdgeIt(*this, p); return i;
   619     public:
   606     }
   620       typedef T Value;
   607 
   621       typedef UndirEdge Key;
   608     using GraphWrapper<Graph>::next;
   622       
   609 
   623       UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) : 
   610     OutEdgeIt& next(OutEdgeIt& e) const {
   624 	map(*(g.graph)) { }
   611       if (e.out_or_in) {
   625 
   612 	typename Graph::Node n=this->graph->source(e.out);
   626       UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) : 
   613 	this->graph->next(e.out);
   627 	map(*(g.graph), a) { }
   614 	if (!this->graph->valid(e.out)) { 
   628       
   615 	  e.out_or_in=false; this->graph->first(e.in, n); }
   629       void set(UndirEdge e, T a) { 
   616       } else {
   630 	map.set(e, a); 
   617 	this->graph->next(e.in);
   631       }
   618       }
   632 
   619       return e;
   633       T operator[](UndirEdge e) const { 
   620     }
   634 	return map[e]; 
   621 
   635       }
   622     Node aNode(const OutEdgeIt& e) const { 
   636     };
   623       if (e.out_or_in) return this->graph->source(e); else 
   637       
   624 	return this->graph->target(e); }
   638   };
   625     Node bNode(const OutEdgeIt& e) const { 
   639 
   626       if (e.out_or_in) return this->graph->target(e); else 
   640   /// \brief An undirected graph is made from a directed graph by a wrapper
   627 	return this->graph->source(e); }
   641   ///
   628 
   642   /// Undocumented, untested!!!
   629     //    KEEP_MAPS(Parent, UndirGraphWrapper);
   643   /// If somebody knows nice demo application, let's polulate it.
   630 
   644   /// 
   631   };
   645   /// \author Marton Makai
   632   
   646   template<typename _Graph>
   633 //   /// \brief An undirected graph template.
   647   class UndirGraphWrapper : 
   634 //   ///
   648     public IterableUndirGraphExtender<
   635 //   ///\warning Graph wrappers are in even more experimental state than the other
   649     UndirGraphWrapperBase<_Graph> > {
   636 //   ///parts of the lib. Use them at your own risk.
   650   public:
   637 //   ///
   651     typedef _Graph Graph;
   638 //   /// An undirected graph template.
   652     typedef IterableUndirGraphExtender<
   639 //   /// This class works as an undirected graph and a directed graph of 
   653       UndirGraphWrapperBase<_Graph> > Parent;
   640 //   /// class \c Graph is used for the physical storage.
   654   protected:
   641 //   /// \ingroup graphs
   655     UndirGraphWrapper() { }
   642   template<typename Graph>
   656   public:
   643   class UndirGraph : public UndirGraphWrapper<Graph> {
   657     UndirGraphWrapper(_Graph& _graph) { 
   644     typedef UndirGraphWrapper<Graph> Parent;
   658       setGraph(_graph);
   645   protected:
   659     }
   646     Graph gr;
       
   647   public:
       
   648     UndirGraph() : UndirGraphWrapper<Graph>() { 
       
   649       Parent::setGraph(gr); 
       
   650     }
       
   651 
       
   652     //    KEEP_MAPS(Parent, UndirGraph);
       
   653   };
   660   };
   654 
   661 
   655   
   662   
   656   template <typename _Graph, 
   663   template <typename _Graph, 
   657 	    typename ForwardFilterMap, typename BackwardFilterMap>
   664 	    typename ForwardFilterMap, typename BackwardFilterMap>