COIN-OR::LEMON - Graph Library

Changeset 1383:79b68a337f9f in lemon-0.x


Ignore:
Timestamp:
04/23/05 18:59:49 (15 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1836
Message:

A new implementation of UndirGraphWrapper?, accordig to the undirected concepts

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/graph_wrapper.h

    r1359 r1383  
    2929#include <lemon/maps.h>
    3030#include <lemon/bits/iterable_graph_extender.h>
     31#include <lemon/bits/undir_graph_extender.h>
    3132#include <iostream>
    3233
     
    152153    typedef typename Parent::Edge Edge;
    153154
    154     using Parent::first;
     155    //    using Parent::first;
    155156    void firstIn(Edge& i, const Node& n) const { Parent::firstOut(i, n); }
    156157    void firstOut(Edge& i, const Node& n ) const { Parent::firstIn(i, n); }
    157158
    158     using Parent::next;
     159    //    using Parent::next;
    159160    void nextIn(Edge& i) const { Parent::nextOut(i); }
    160161    void nextOut(Edge& i) const { Parent::nextIn(i); }
     
    566567  };
    567568
    568 
    569   template<typename Graph>
    570   class UndirGraphWrapper : public GraphWrapper<Graph> {
    571   public:
    572     typedef GraphWrapper<Graph> Parent;
    573   protected:
    574     UndirGraphWrapper() : GraphWrapper<Graph>() { }
     569  template <typename _Graph>
     570  class UndirGraphWrapperBase :
     571    public UndirGraphExtender<GraphWrapperBase<_Graph> > {
     572  public:
     573    typedef _Graph Graph;
     574    typedef UndirGraphExtender<GraphWrapperBase<_Graph> > Parent;
     575  protected:
     576    UndirGraphWrapperBase() : Parent() { }
     577  public:
     578    typedef typename Parent::UndirEdge UndirEdge;
     579    typedef typename Parent::Edge Edge;
    575580   
    576   public:
    577     typedef typename GraphWrapper<Graph>::Node Node;
    578     typedef typename GraphWrapper<Graph>::NodeIt NodeIt;
    579     typedef typename GraphWrapper<Graph>::Edge Edge;
    580     typedef typename GraphWrapper<Graph>::EdgeIt EdgeIt;
    581 
    582     UndirGraphWrapper(Graph& _graph) : GraphWrapper<Graph>(_graph) { } 
    583 
    584     class OutEdgeIt {
    585       friend class UndirGraphWrapper<Graph>;
    586       bool out_or_in; //true iff out
    587       typename Graph::OutEdgeIt out;
    588       typename Graph::InEdgeIt in;
     581    /// \bug Why cant an edge say that it is forward or not???
     582    /// By this, a pointer to the graph have to be stored
     583    /// The implementation
     584    template <typename T>
     585    class EdgeMap {
     586    protected:
     587      const UndirGraphWrapperBase<_Graph>* g;
     588      template <typename TT> friend class EdgeMap;
     589      typename _Graph::template EdgeMap<T> forward_map, backward_map;
    589590    public:
    590       OutEdgeIt() { }
    591       OutEdgeIt(const Invalid& i) : Edge(i) { }
    592       OutEdgeIt(const UndirGraphWrapper<Graph>& _G, const Node& _n) {
    593         out_or_in=true; _G.graph->first(out, _n);
    594         if (!(_G.graph->valid(out))) { out_or_in=false; _G.graph->first(in, _n);        }
    595       }
    596       operator Edge() const {
    597         if (out_or_in) return Edge(out); else return Edge(in);
     591      typedef T Value;
     592      typedef Edge Key;
     593     
     594      EdgeMap(const UndirGraphWrapperBase<_Graph>& _g) : g(&_g),
     595        forward_map(*(g->graph)), backward_map(*(g->graph)) { }
     596
     597      EdgeMap(const UndirGraphWrapperBase<_Graph>& _g, T a) : g(&_g),
     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];
    598612      }
    599613    };
    600 
    601     typedef OutEdgeIt InEdgeIt;
    602 
    603     using GraphWrapper<Graph>::first;
    604     OutEdgeIt& first(OutEdgeIt& i, const Node& p) const {
    605       i=OutEdgeIt(*this, p); return i;
    606     }
    607 
    608     using GraphWrapper<Graph>::next;
    609 
    610     OutEdgeIt& next(OutEdgeIt& e) const {
    611       if (e.out_or_in) {
    612         typename Graph::Node n=this->graph->source(e.out);
    613         this->graph->next(e.out);
    614         if (!this->graph->valid(e.out)) {
    615           e.out_or_in=false; this->graph->first(e.in, n); }
    616       } else {
    617         this->graph->next(e.in);
    618       }
    619       return e;
    620     }
    621 
    622     Node aNode(const OutEdgeIt& e) const {
    623       if (e.out_or_in) return this->graph->source(e); else
    624         return this->graph->target(e); }
    625     Node bNode(const OutEdgeIt& e) const {
    626       if (e.out_or_in) return this->graph->target(e); else
    627         return this->graph->source(e); }
    628 
    629     //    KEEP_MAPS(Parent, UndirGraphWrapper);
    630 
    631   };
    632  
    633 //   /// \brief An undirected graph template.
    634 //   ///
    635 //   ///\warning Graph wrappers are in even more experimental state than the other
    636 //   ///parts of the lib. Use them at your own risk.
    637 //   ///
    638 //   /// An undirected graph template.
    639 //   /// This class works as an undirected graph and a directed graph of
    640 //   /// class \c Graph is used for the physical storage.
    641 //   /// \ingroup graphs
    642   template<typename Graph>
    643   class UndirGraph : public UndirGraphWrapper<Graph> {
    644     typedef UndirGraphWrapper<Graph> Parent;
    645   protected:
    646     Graph gr;
    647   public:
    648     UndirGraph() : UndirGraphWrapper<Graph>() {
    649       Parent::setGraph(gr);
    650     }
    651 
    652     //    KEEP_MAPS(Parent, UndirGraph);
     614       
     615    template <typename T>
     616    class UndirEdgeMap {
     617      template <typename TT> friend class UndirEdgeMap;
     618      typename _Graph::template EdgeMap<T> map;
     619    public:
     620      typedef T Value;
     621      typedef UndirEdge Key;
     622     
     623      UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g) :
     624        map(*(g.graph)) { }
     625
     626      UndirEdgeMap(const UndirGraphWrapperBase<_Graph>& g, T a) :
     627        map(*(g.graph), a) { }
     628     
     629      void set(UndirEdge e, T a) {
     630        map.set(e, a);
     631      }
     632
     633      T operator[](UndirEdge e) const {
     634        return map[e];
     635      }
     636    };
     637     
     638  };
     639
     640  /// \brief An undirected graph is made from a directed graph by a wrapper
     641  ///
     642  /// Undocumented, untested!!!
     643  /// If somebody knows nice demo application, let's polulate it.
     644  ///
     645  /// \author Marton Makai
     646  template<typename _Graph>
     647  class UndirGraphWrapper :
     648    public IterableUndirGraphExtender<
     649    UndirGraphWrapperBase<_Graph> > {
     650  public:
     651    typedef _Graph Graph;
     652    typedef IterableUndirGraphExtender<
     653      UndirGraphWrapperBase<_Graph> > Parent;
     654  protected:
     655    UndirGraphWrapper() { }
     656  public:
     657    UndirGraphWrapper(_Graph& _graph) {
     658      setGraph(_graph);
     659    }
    653660  };
    654661
  • src/test/graph_wrapper_test.cc

    r1359 r1383  
    2020#include<lemon/smart_graph.h>
    2121#include<lemon/concept/graph.h>
     22#include<lemon/concept/undir_graph.h>
    2223
    2324#include<lemon/list_graph.h>
     
    6364    checkConcept<StaticGraph, ErasingFirstGraphWrapper<Graph,
    6465      Graph::NodeMap<Graph::Edge> > >();
     66
     67    /// \bug why does not compile with StaticGraph
     68    checkConcept<BaseIterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
     69    checkConcept<IterableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
     70    checkConcept<MappableUndirGraphConcept, UndirGraphWrapper<ListGraph> >();
    6571  }
    6672  std::cout << __FILE__ ": All tests passed.\n";
Note: See TracChangeset for help on using the changeset viewer.