COIN-OR::LEMON - Graph Library

Changeset 946:c94ef40a22ce in lemon-0.x


Ignore:
Timestamp:
10/28/04 00:38:50 (19 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

Location:
src
Files:
15 added
1 deleted
20 edited

Legend:

Unmodified
Added
Removed
  • src/benchmark/hcube.cc

    r921 r946  
    6767   
    6868    //  for(EdgeIt e(G);G.valid(e);G.next(e)) map[e]=P();
    69     Edge te;
    70     for(int i=0;i<dim*(1<<dim);i++) {
    71       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
    72       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
    73       map[te]=P();
    74     }
     69
     70    ///\todo It must have been commented out because of
     71    ///setToId
     72//     Edge te;
     73//     for(int i=0;i<dim*(1<<dim);i++) {
     74//       te.setToId(((long long int)(i)*93505)%(dim*(1<<dim)));
     75//       //    map[Edge(((long long int)(i)*2987)%(dim*(1<<dim)))]=P();
     76//       map[te]=P();
     77//     }
    7578   
    7679//     for(int i=0;i<(1<<dim);i++) {
  • src/lemon/Makefile.am

    r937 r946  
    1111        full_graph.h                                                    \
    1212        graph_wrapper.h                                                 \
     13        graph_utils.h                                                   \
    1314        invalid.h                                                       \
    1415        kruskal.h                                                       \
    1516        list_graph.h                                                    \
    16         map_defines.h                                                   \
    1717        map_iterator.h                                                  \
    18         map_registry.h                                                  \
    19         map_bits.h                                                      \
     18        alteration_observer_registry.h                                  \
    2019        maps.h                                                          \
    2120        min_cost_flow.h                                                 \
     
    2726        unionfind.h                                                     \
    2827        vector_map.h                                                    \
    29         xy.h
     28        xy.h                                                            \
     29        concept_check.h                                                 \
     30        map_defines.h                                                   \
     31        map_bits.h                                                      \
     32        iterable_graph_extender.h                                       \
     33        idmappable_graph_extender.h                                     \
     34        extendable_graph_extender.h                                     \
     35        clearable_graph_extender.h                                      \
     36        erasable_graph_extender.h
    3037
    3138noinst_HEADERS =                                                        \
    3239        skeletons/graph.h                                               \
     40        skeletons/graph_component.h                                     \
    3341        skeletons/sym_graph.h                                           \
    3442        skeletons/maps.h                                                \
  • src/lemon/array_map.h

    r921 r946  
    2121
    2222#include <lemon/map_iterator.h>
    23 #include <lemon/map_bits.h>
    2423
    2524///\ingroup graphmaps
     
    4342   */
    4443
    45   template <typename MapRegistry, typename Value>
    46   class ArrayMap : public MapRegistry::MapBase {
    47 
    48     template <typename MR, typename V> friend class ArrayMap;
    49                
     44  template <typename _Graph,
     45            typename _Item,
     46            typename _ItemIt,
     47            typename _IdMap,
     48            typename _Value>
     49  class ArrayMap : public AlterationObserverRegistry<_Item>::ObserverBase {
     50
    5051  public:
    5152               
    5253    /// The graph type of the maps.
    53     typedef typename MapRegistry::Graph Graph;
     54    typedef _Graph Graph;
    5455    /// The key type of the maps.
    55     typedef typename MapRegistry::KeyType KeyType;
     56    typedef _Item KeyType;
     57
     58    typedef AlterationObserverRegistry<_Item> Registry;
     59
     60  private:
    5661    /// The iterator to iterate on the keys.
    57     typedef typename MapRegistry::KeyIt KeyIt;
     62    typedef _ItemIt KeyIt;
     63
     64    typedef _IdMap IdMap;
     65
     66    typedef _Value Value;
    5867
    5968    /// The MapBase of the Map which imlements the core regisitry function.
    60     typedef typename MapRegistry::MapBase MapBase;
     69    typedef typename Registry::ObserverBase Parent;
    6170               
    6271   
     
    7887
    7988
     89  private:
    8090    typedef std::allocator<Value> Allocator;
    8191
    82        
     92
     93  public:
     94
    8395    /** Graph and Registry initialized map constructor.
    8496     */
    85     ArrayMap(const Graph& g, MapRegistry& r) : MapBase(g, r) {
     97    ArrayMap(const Graph& _g, Registry& _r) : graph(&_g) {
     98      attach(_r);
    8699      allocate_memory();
    87       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    88         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     100      for (KeyIt it(*graph); it != INVALID; ++it) {
     101        int id = IdMap(*graph)[it];
    89102        allocator.construct(&(values[id]), Value());
    90103      }                                                         
    91104    }
    92105
    93     /** Constructor to use default value to initialize the map.
    94      */
    95     ArrayMap(const Graph& g, MapRegistry& r, const Value& v)
    96       : MapBase(g, r) {
     106    /// Constructor to use default value to initialize the map.
     107
     108    /// It constrates a map and initialize all of the the map.
     109
     110    ArrayMap(const Graph& _g, Registry& _r, const Value& _v) : graph(&_g) {
     111      attach(_r);
    97112      allocate_memory();
    98       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    99         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    100         allocator.construct(&(values[id]), v);
     113      for (KeyIt it(*graph); it != INVALID; ++it) {
     114        int id = IdMap(*graph)[it];
     115        allocator.construct(&(values[id]), _v);
    101116      }                                                         
    102117    }
     
    104119    /** Constructor to copy a map of the same map type.
    105120     */
    106     ArrayMap(const ArrayMap& copy) : MapBase(copy) {
     121    ArrayMap(const ArrayMap& copy) {
     122      if (copy.attached()) {
     123        attach(*copy.getRegistry());
     124      }
    107125      capacity = copy.capacity;
    108126      if (capacity == 0) return;
    109127      values = allocator.allocate(capacity);
    110       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    111         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    112         allocator.construct(&(values[id]), copy.values[id]);
    113       }
    114     }
    115 
    116     /** Constructor to copy a map of an other map type.
    117      */
    118     template <typename TT>
    119     ArrayMap(const ArrayMap<MapRegistry, TT>& copy)
    120       : MapBase(copy) {
    121       capacity = copy.capacity;
    122       if (capacity == 0) return;
    123       values = allocator.allocate(capacity);
    124       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    125         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     128      for (KeyIt it(*graph); it != INVALID; ++it) {
     129        int id = IdMap(*graph)[it];
    126130        allocator.construct(&(values[id]), copy.values[id]);
    127131      }
     
    133137      if (&copy == this) return *this;
    134138     
    135       if (MapBase::getGraph() != copy.getGraph()) {
    136         if (capacity != 0) {
    137           MapBase::destroy();
    138           allocator.deallocate(values, capacity);
     139      if (graph != copy.graph) {
     140        if (attached()) {
     141          clear();
     142          detach();
    139143        }
    140 
    141         MapBase::operator=(copy);
     144        if (copy.attached()) {
     145          attach(*copy.getRegistry());
     146        }
    142147        capacity = copy.capacity;
    143148        if (capacity == 0) return *this;
     
    145150      }
    146151
    147       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    148         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     152      for (KeyIt it(*graph); it != INVALID; ++it) {
     153        int id = IdMap(*graph)[it];
    149154        allocator.construct(&(values[id]), copy.values[id]);
    150155      }
     
    153158    }
    154159
    155     /** Assign operator to copy a map of an other map type.
    156      */
    157     template <typename TT>
    158     ArrayMap& operator=(const ArrayMap<MapRegistry, TT>& copy) {
    159 
    160       if (MapBase::getGraph() != copy.getGraph()) {
    161         if (capacity != 0) {
    162           MapBase::destroy();
    163           allocator.deallocate(values, capacity);
    164         }
    165 
    166         MapBase::operator=(copy);
    167 
    168         capacity = copy.capacity;
    169         if (capacity == 0) return *this;
    170         values = allocator.allocate(capacity);
    171       }
    172 
    173       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    174         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    175         allocator.construct(&(values[id]), copy.values[id]);
    176       }
    177 
    178       return *this;
    179     }
    180                                
    181160    /** The destructor of the map.
    182161     */
    183     virtual ~ArrayMap() {
    184       if (capacity != 0) {
    185         MapBase::destroy();
    186         allocator.deallocate(values, capacity);
     162    virtual ~ArrayMap() {     
     163      if (attached()) {
     164        clear();
     165        detach();
    187166      }
    188167    }
     
    194173     */
    195174    ReferenceType operator[](const KeyType& key) {
    196       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     175      int id = IdMap(*graph)[key];
    197176      return values[id];
    198177    }
     
    203182     */
    204183    ConstReferenceType operator[](const KeyType& key) const {
    205       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     184      int id = IdMap(*graph)[key];
    206185      return values[id];
    207186    }
     
    211190     */
    212191    void set(const KeyType& key, const ValueType& val) {
    213       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    214       values[id] = val;
     192      (*this)[key] = val;
    215193    }
    216194               
     
    218196     */
    219197    void add(const KeyType& key) {
    220       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     198      int id = IdMap(*graph)[key];
    221199      if (id >= capacity) {
    222200        int new_capacity = (capacity == 0 ? 1 : capacity);
     
    224202          new_capacity <<= 1;
    225203        }
    226         Value* new_values = allocator.allocate(new_capacity);;
    227         for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    228           int jd = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
     204        Value* new_values = allocator.allocate(new_capacity);
     205        for (KeyIt it(*graph); it != INVALID; ++it) {
     206          int jd = IdMap(*graph)[it];
    229207          if (id != jd) {
    230208            allocator.construct(&(new_values[jd]), values[jd]);
     
    242220     */
    243221    void erase(const KeyType& key) {
    244       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     222      int id = IdMap(*graph)[key];
    245223      allocator.destroy(&(values[id]));
    246224    }
    247225
    248     /** Clear the data structure.
    249      */
     226    void build() {
     227      allocate_memory();
     228      for (KeyIt it(*graph); it != INVALID; ++it) {
     229        int id = IdMap(*graph)[it];
     230        allocator.construct(&(values[id]), Value());
     231      }                                                         
     232    }
     233
    250234    void clear() {     
    251235      if (capacity != 0) {
    252         MapBase::destroy();
     236        for (KeyIt it(*graph); it != INVALID; ++it) {
     237          int id = IdMap(*graph)[it];
     238          allocator.destroy(&(values[id]));
     239        }                                                               
    253240        allocator.deallocate(values, capacity);
    254241        capacity = 0;
     
    256243    }
    257244
    258     /// The stl compatible pair iterator of the map.
    259     typedef MapIterator<ArrayMap> Iterator;
    260     /// The stl compatible const pair iterator of the map.
    261     typedef MapConstIterator<ArrayMap> ConstIterator;
    262 
    263     /** Returns the begin iterator of the map.
    264      */
    265     Iterator begin() {
    266       return Iterator(*this, KeyIt(*MapBase::getGraph()));
    267     }
    268 
    269     /** Returns the end iterator of the map.
    270      */
    271     Iterator end() {
    272       return Iterator(*this, INVALID);
    273     }
    274 
    275     /** Returns the begin ConstIterator of the map.
    276      */
    277     ConstIterator begin() const {
    278       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
    279     }
    280 
    281     /** Returns the end const_iterator of the map.
    282      */
    283     ConstIterator end() const {
    284       return ConstIterator(*this, INVALID);
    285     }
    286 
    287     /// The KeySet of the Map.
    288     typedef MapConstKeySet<ArrayMap> ConstKeySet;
    289 
    290     /// KeySet getter function.
    291     ConstKeySet keySet() const {
    292       return ConstKeySet(*this);
    293     }
    294 
    295     /// The ConstValueSet of the Map.
    296     typedef MapConstValueSet<ArrayMap> ConstValueSet;
    297 
    298     /// ConstValueSet getter function.
    299     ConstValueSet valueSet() const {
    300       return ConstValueSet(*this);
    301     }
    302 
    303     /// The ValueSet of the Map.
    304     typedef MapValueSet<ArrayMap> ValueSet;
    305 
    306     /// ValueSet getter function.
    307     ValueSet valueSet() {
    308       return ValueSet(*this);
    309     }
     245//     /// The stl compatible pair iterator of the map.
     246//     typedef MapIterator<ArrayMap> Iterator;
     247//     /// The stl compatible const pair iterator of the map.
     248//     typedef MapConstIterator<ArrayMap> ConstIterator;
     249
     250//     /** Returns the begin iterator of the map.
     251//      */
     252//     Iterator begin() {
     253//       return Iterator(*this, KeyIt(*MapBase::getGraph()));
     254//     }
     255
     256//     /** Returns the end iterator of the map.
     257//      */
     258//     Iterator end() {
     259//       return Iterator(*this, INVALID);
     260//     }
     261
     262//     /** Returns the begin ConstIterator of the map.
     263//      */
     264//     ConstIterator begin() const {
     265//       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
     266//     }
     267
     268//     /** Returns the end const_iterator of the map.
     269//      */
     270//     ConstIterator end() const {
     271//       return ConstIterator(*this, INVALID);
     272//     }
     273
     274//     /// The KeySet of the Map.
     275//     typedef MapConstKeySet<ArrayMap> ConstKeySet;
     276
     277//     /// KeySet getter function.
     278//     ConstKeySet keySet() const {
     279//       return ConstKeySet(*this);
     280//     }
     281
     282//     /// The ConstValueSet of the Map.
     283//     typedef MapConstValueSet<ArrayMap> ConstValueSet;
     284
     285//     /// ConstValueSet getter function.
     286//     ConstValueSet valueSet() const {
     287//       return ConstValueSet(*this);
     288//     }
     289
     290//     /// The ValueSet of the Map.
     291//     typedef MapValueSet<ArrayMap> ValueSet;
     292
     293//     /// ValueSet getter function.
     294//     ValueSet valueSet() {
     295//       return ValueSet(*this);
     296//     }
    310297
    311298  private:
    312299     
    313300    void allocate_memory() {
    314       int max_id = KeyInfo<Graph, KeyIt>::maxId(*MapBase::getGraph());
     301      int max_id = IdMap(*graph).maxId();
    315302      if (max_id == -1) {
    316303        capacity = 0;
     
    325312    }     
    326313
     314    const Graph* graph;
    327315    int capacity;
    328316    Value* values;
     
    330318
    331319  public:
    332     // STL  compatibility typedefs.
    333     typedef Iterator iterator;
    334     typedef ConstIterator const_iterator;
    335     typedef typename Iterator::PairValueType value_type;
    336     typedef typename Iterator::KeyType key_type;
    337     typedef typename Iterator::ValueType data_type;
    338     typedef typename Iterator::PairReferenceType reference;
    339     typedef typename Iterator::PairPointerType pointer;
    340     typedef typename ConstIterator::PairReferenceType const_reference;
    341     typedef typename ConstIterator::PairPointerType const_pointer;
    342     typedef int difference_type;               
     320//     // STL  compatibility typedefs.
     321//     typedef Iterator iterator;
     322//     typedef ConstIterator const_iterator;
     323//     typedef typename Iterator::PairValueType value_type;
     324//     typedef typename Iterator::KeyType key_type;
     325//     typedef typename Iterator::ValueType data_type;
     326//     typedef typename Iterator::PairReferenceType reference;
     327//     typedef typename Iterator::PairPointerType pointer;
     328//     typedef typename ConstIterator::PairReferenceType const_reference;
     329//     typedef typename ConstIterator::PairPointerType const_pointer;
     330//     typedef int difference_type;             
    343331  };           
    344332
     333  template <typename _Base>
     334  class ArrayMappableGraphExtender : public _Base {
     335  public:
     336
     337    typedef ArrayMappableGraphExtender<_Base> Graph;
     338    typedef _Base Parent;
     339
     340    typedef typename Parent::Node Node;
     341    typedef typename Parent::NodeIt NodeIt;
     342    typedef typename Parent::NodeIdMap NodeIdMap;
     343    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
     344
     345    typedef typename Parent::Edge Edge;
     346    typedef typename Parent::EdgeIt EdgeIt;
     347    typedef typename Parent::EdgeIdMap EdgeIdMap;
     348    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
     349
     350   
     351
     352    template <typename _Value>
     353    class NodeMap : public ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
     354    public:
     355      typedef ArrayMappableGraphExtender<_Base> Graph;
     356
     357      typedef typename Graph::Node Node;
     358      typedef typename Graph::NodeIt NodeIt;
     359      typedef typename Graph::NodeIdMap NodeIdMap;
     360
     361      typedef ArrayMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
     362
     363      typedef typename Parent::Graph Graph;
     364      typedef typename Parent::Value Value;
     365
     366      NodeMap(const Graph& g)
     367        : Parent(g, g.getNodeObserverRegistry()) {}
     368      NodeMap(const Graph& g, const Value& v)
     369        : Parent(g, g.getNodeObserverRegistry(), v) {}
     370
     371    };
     372
     373    template <typename _Value>
     374    class EdgeMap : public ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
     375    public:
     376      typedef ArrayMappableGraphExtender<_Base> Graph;
     377
     378      typedef typename Graph::Edge Edge;
     379      typedef typename Graph::EdgeIt EdgeIt;
     380      typedef typename Graph::EdgeIdMap EdgeIdMap;
     381
     382      typedef ArrayMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
     383
     384      typedef typename Parent::Graph Graph;
     385      typedef typename Parent::Value Value;
     386
     387      EdgeMap(const Graph& g)
     388        : Parent(g, g.getEdgeObserverRegistry()) {}
     389      EdgeMap(const Graph& g, const Value& v)
     390        : Parent(g, g.getEdgeObserverRegistry(), v) {}
     391
     392    };
     393   
     394  };
     395
    345396/// @}
    346397
  • src/lemon/bfs.h

    r921 r946  
    196196      }
    197197     
    198       int N=G->nodeNum();
     198      int N = countNodes(*G);
    199199      std::vector<typename Graph::Node> Q(N);
    200200      int Qh=0;
  • src/lemon/default_map.h

    r937 r946  
    2424///\ingroup graphmaps
    2525///\file
    26 ///\brief Graph maps that construates and destruates
     26///\brief Graph maps that construct and destruct
    2727///their elements dynamically.
    2828
     
    4242
    4343
    44   /** Macro to implement the DefaultMap.
    45    */
    46 #define DEFAULT_MAP_BODY(DynMap, Value) \
    47 { \
    48 \
    49 public: \
    50 \
    51 typedef DynMap<MapRegistry, Value> Parent; \
    52 \
    53 typedef typename MapRegistry::Graph Graph; \
    54 \
    55 DefaultMap(const Graph& g, MapRegistry& r) : Parent(g, r) {} \
    56 DefaultMap(const Graph& g, MapRegistry& r, const Value& v) \
    57   : Parent(g, r, v) {} \
    58 DefaultMap(const DefaultMap& copy) \
    59   : Parent(static_cast<const Parent&>(copy)) {} \
    60 template <typename TT> \
    61 DefaultMap(const DefaultMap<MapRegistry, TT>& copy) \
    62   : Parent(*copy.getGraph()) { \
    63   if (Parent::getGraph()) { \
    64     for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
    65       Parent::operator[](it) = copy[it]; \
    66     } \
    67   } \
    68 } \
    69 DefaultMap& operator=(const DefaultMap& copy) { \
    70   Parent::operator=(static_cast<const Parent&>(copy)); \
    71   return *this; \
    72 } \
    73 template <typename TT> \
    74 DefaultMap& operator=(const DefaultMap<MapRegistry, TT>& copy) { \
    75   if (Parent::getGraph() != copy.getGraph()) { \
    76     Parent::clear(); \
    77     Parent::MapBase::operator=(copy); \
    78     Parent::construct(); \
    79   } \
    80   if (Parent::getGraph()) { \
    81     for (typename Parent::KeyIt it(*Parent::getGraph()); it!=INVALID; ++it) {\
    82       Parent::operator[](it) = copy[it]; \
    83     } \
    84   } \
    85   return *this; \
    86 } \
    87 };
    88 
    89 
    90   template <typename MapRegistry, typename Type>
    91   class DefaultMap : public ArrayMap<MapRegistry, Type>
    92   DEFAULT_MAP_BODY(ArrayMap, Type);
    93 
    94   template <typename MapRegistry>
    95   class DefaultMap<MapRegistry, bool>
    96     : public VectorMap<MapRegistry, bool>
    97   DEFAULT_MAP_BODY(VectorMap, bool);
    98 
    99   template <typename MapRegistry>
    100   class DefaultMap<MapRegistry, char>
    101     : public VectorMap<MapRegistry, char>
    102   DEFAULT_MAP_BODY(VectorMap, char);
    103 
    104   template <typename MapRegistry>
    105   class DefaultMap<MapRegistry, int>
    106     : public VectorMap<MapRegistry, int>
    107   DEFAULT_MAP_BODY(VectorMap, int);
    108 
    109   template <typename MapRegistry>
    110   class DefaultMap<MapRegistry, short>
    111     : public VectorMap<MapRegistry, short>
    112   DEFAULT_MAP_BODY(VectorMap, short);
    113 
    114   template <typename MapRegistry>
    115   class DefaultMap<MapRegistry, long>
    116     : public VectorMap<MapRegistry, long>
    117   DEFAULT_MAP_BODY(VectorMap, long);
    118 
    119   template <typename MapRegistry>
    120   class DefaultMap<MapRegistry, float>
    121     : public VectorMap<MapRegistry, float>
    122   DEFAULT_MAP_BODY(VectorMap, float);
    123 
    124   template <typename MapRegistry>
    125   class DefaultMap<MapRegistry, double>
    126     : public VectorMap<MapRegistry, double>
    127   DEFAULT_MAP_BODY(VectorMap, double);
    128 
    129   template <typename MapRegistry>
    130   class DefaultMap<MapRegistry, long double>
    131     : public VectorMap<MapRegistry, long double>
    132   DEFAULT_MAP_BODY(VectorMap, long double);
    133 
    134   template <typename MapRegistry, typename Type>
    135   class DefaultMap<MapRegistry, Type*>
    136     : public VectorMap<MapRegistry, Type*>
    137   DEFAULT_MAP_BODY(VectorMap, Type*);
     44
     45  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap, typename _Value>
     46  struct DefaultMapSelector {
     47    typedef ArrayMap<_Graph, _Item, _ItemIt, _IdMap, _Value> Map;
     48  };
     49
     50  // bool
     51  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     52  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, bool> {
     53    typedef VectorMap<_Graph, _Item, _IdMap, bool> Map;
     54  };
     55
     56  // char
     57  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     58  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, char> {
     59    typedef VectorMap<_Graph, _Item, _IdMap, char> Map;
     60  };
     61
     62  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     63  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed char> {
     64    typedef VectorMap<_Graph, _Item, _IdMap, signed char> Map;
     65  };
     66
     67  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     68  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned char> {
     69    typedef VectorMap<_Graph, _Item, _IdMap, unsigned char> Map;
     70  };
     71
     72
     73  // int
     74  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     75  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed int> {
     76    typedef VectorMap<_Graph, _Item, _IdMap, signed int> Map;
     77  };
     78
     79  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     80  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned int> {
     81    typedef VectorMap<_Graph, _Item, _IdMap, unsigned int> Map;
     82  };
     83
     84
     85  // short
     86  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     87  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed short> {
     88    typedef VectorMap<_Graph, _Item, _IdMap, signed short> Map;
     89  };
     90
     91  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     92  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned short> {
     93    typedef VectorMap<_Graph, _Item, _IdMap, unsigned short> Map;
     94  };
     95
     96
     97  // long
     98  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     99  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, signed long> {
     100    typedef VectorMap<_Graph, _Item, _IdMap, signed long> Map;
     101  };
     102
     103  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     104  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, unsigned long> {
     105    typedef VectorMap<_Graph, _Item, _IdMap, unsigned long> Map;
     106  };
     107
     108  // \todo handling long long type
     109
     110
     111  // float
     112  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     113  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, float> {
     114    typedef VectorMap<_Graph, _Item, _IdMap, float> Map;
     115  };
     116
     117
     118  // double
     119  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     120  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, double> {
     121    typedef VectorMap<_Graph, _Item, _IdMap,  double> Map;
     122  };
     123
     124
     125  // long double
     126  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap>
     127  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, long double> {
     128    typedef VectorMap<_Graph, _Item, _IdMap, long double> Map;
     129  };
     130
     131
     132  // pointer
     133  template <typename _Graph, typename _Item, typename _ItemIt, typename _IdMap, typename _Ptr>
     134  struct DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Ptr*> {
     135    typedef VectorMap<_Graph, _Item, _IdMap, _Ptr*> Map;
     136  };
     137
     138
     139
     140  template <typename _Graph,
     141            typename _Item,
     142            typename _ItemIt,
     143            typename _IdMap,
     144            typename _Value>
     145  class DefaultMap : public DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map {
     146  public:
     147    typedef typename DefaultMapSelector<_Graph, _Item, _ItemIt, _IdMap, _Value>::Map Parent;
     148    typedef DefaultMap<_Graph, _Item, _ItemIt, _IdMap, bool> Map;
     149   
     150    typedef typename Parent::Graph Graph;
     151    typedef typename Parent::Registry Registry;
     152    typedef typename Parent::ValueType ValueType;
     153
     154    DefaultMap(const Graph& _g, Registry& _r) : Parent(_g, _r) {}
     155    DefaultMap(const Graph& _g, Registry& _r, const ValueType& _v) : Parent(_g, _r, _v) {}
     156  };
     157
     158
     159
     160  template <typename _Base>
     161  class DefaultMappableGraphExtender : public _Base {
     162  public:
     163
     164    typedef DefaultMappableGraphExtender<_Base> Graph;
     165    typedef _Base Parent;
     166
     167    typedef typename Parent::Node Node;
     168    typedef typename Parent::NodeIt NodeIt;
     169    typedef typename Parent::NodeIdMap NodeIdMap;
     170    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
     171
     172    typedef typename Parent::Edge Edge;
     173    typedef typename Parent::EdgeIt EdgeIt;
     174    typedef typename Parent::EdgeIdMap EdgeIdMap;
     175    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
     176
     177   
     178
     179    template <typename _Value>
     180    class NodeMap : public DefaultMap<Graph, Node, NodeIt, NodeIdMap, _Value> {
     181    public:
     182      typedef DefaultMappableGraphExtender<_Base> Graph;
     183
     184      typedef typename Graph::Node Node;
     185      typedef typename Graph::NodeIt NodeIt;
     186      typedef typename Graph::NodeIdMap NodeIdMap;
     187
     188      typedef DefaultMap<Graph, Node, NodeIt, NodeIdMap, _Value> Parent;
     189
     190      typedef typename Parent::Graph Graph;
     191      typedef typename Parent::ValueType ValueType;
     192
     193      NodeMap(const Graph& g)
     194        : Parent(g, g.getNodeObserverRegistry()) {}
     195      NodeMap(const Graph& g, const ValueType& v)
     196        : Parent(g, g.getNodeObserverRegistry(), v) {}
     197
     198    };
     199
     200    template <typename _Value>
     201    class EdgeMap : public DefaultMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> {
     202    public:
     203      typedef DefaultMappableGraphExtender<_Base> Graph;
     204
     205      typedef typename Graph::Edge Edge;
     206      typedef typename Graph::EdgeIt EdgeIt;
     207      typedef typename Graph::EdgeIdMap EdgeIdMap;
     208
     209      typedef DefaultMap<Graph, Edge, EdgeIt, EdgeIdMap, _Value> Parent;
     210
     211      typedef typename Parent::Graph Graph;
     212      typedef typename Parent::ValueType ValueType;
     213
     214      EdgeMap(const Graph& g)
     215        : Parent(g, g.getEdgeObserverRegistry()) {}
     216      EdgeMap(const Graph& g, const ValueType& v)
     217        : Parent(g, g.getEdgeObserverRegistry(), v) {}
     218
     219    };
     220   
     221  };
     222
    138223
    139224}
  • src/lemon/dfs.h

    r921 r946  
    2424///\todo Revise Manual.
    2525
    26 #include <lemon/bin_heap.h>
     26#include <lemon/graph_utils.h>
    2727#include <lemon/invalid.h>
    2828
     
    194194      }
    195195     
    196       int N=G->nodeNum();
     196      int N = countNodes(*G);
    197197      std::vector<typename Graph::OutEdgeIt> Q(N);
    198198
    199199      int Qh=0;
    200200     
    201       G->first(Q[Qh],s);
     201      Q[Qh] = OutEdgeIt(*G, s);
    202202      distance->set(s, 0);
    203203
     
    210210            predecessor->set(m,e);
    211211            pred_node->set(m,n);
    212             G->first(Q[++Qh],m);
     212            Q[++Qh] = OutEdgeIt(*G, m);
    213213            distance->set(m,Qh);
    214214            n=m;
  • src/lemon/full_graph.h

    r921 r946  
    1818#define LEMON_FULL_GRAPH_H
    1919
     20
     21#include <lemon/idmappable_graph_extender.h>
     22
     23#include <lemon/iterable_graph_extender.h>
     24
     25#include <lemon/alteration_observer_registry.h>
     26#include <lemon/default_map.h>
     27
    2028///\ingroup graphs
    2129///\file
    2230///\brief FullGraph and SymFullGraph classes.
    2331
    24 #include <vector>
    25 #include <climits>
    2632
    2733#include <lemon/invalid.h>
    28 
    29 #include <lemon/map_registry.h>
    30 #include <lemon/array_map.h>
    31 
    32 #include <lemon/map_defines.h>
    3334
    3435namespace lemon {
     
    4950  ///
    5051  ///\author Alpar Juttner
    51   class FullGraph {
     52  class FullGraphBase {
    5253    int NodeNum;
    5354    int EdgeNum;
    5455  public:
    5556
    56     typedef FullGraph Graph;
     57    typedef FullGraphBase Graph;
    5758
    5859    class Node;
    5960    class Edge;
    6061
    61     class NodeIt;
    62     class EdgeIt;
    63     class OutEdgeIt;
    64     class InEdgeIt;
    65    
    66 
    67     // Create map registries.
    68     CREATE_MAP_REGISTRIES;
    69     // Create node and edge maps.
    70     CREATE_MAPS(ArrayMap);
    71    
    7262  public:
    7363
     64    FullGraphBase() {}
     65
     66
    7467    ///Creates a full graph with \c n nodes.
    75     FullGraph(int n) : NodeNum(n), EdgeNum(NodeNum*NodeNum) { }
    76     ///
    77     FullGraph(const FullGraph &_g)
    78       : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
     68    void construct(int n) { NodeNum = n; EdgeNum = n * n; }
     69    ///
     70    //    FullGraphBase(const FullGraphBase &_g)
     71    //      : NodeNum(_g.nodeNum()), EdgeNum(NodeNum*NodeNum) { }
    7972   
    8073    ///Number of nodes.
     
    9487    int maxEdgeId() const { return EdgeNum-1; }
    9588
    96     Node tail(Edge e) const { return e.n%NodeNum; }
    97     Node head(Edge e) const { return e.n/NodeNum; }
    98 
    99     NodeIt& first(NodeIt& v) const {
    100       v=NodeIt(*this); return v; }
    101     EdgeIt& first(EdgeIt& e) const {
    102       e=EdgeIt(*this); return e; }
    103     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    104       e=OutEdgeIt(*this,v); return e; }
    105     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    106       e=InEdgeIt(*this,v); return e; }
     89    Node tail(Edge e) const { return e.id % NodeNum; }
     90    Node head(Edge e) const { return e.id / NodeNum; }
     91
    10792
    10893    /// Node ID.
     
    11499    /// The ID of the \ref INVALID node is -1.
    115100    ///\return The ID of the node \c v.
    116     static int id(Node v) { return v.n; }
     101
     102    static int id(Node v) { return v.id; }
    117103    /// Edge ID.
    118104   
     
    123109    /// The ID of the \ref INVALID edge is -1.
    124110    ///\return The ID of the edge \c e.
    125     static int id(Edge e) { return e.n; }
     111    static int id(Edge e) { return e.id; }
    126112
    127113    /// Finds an edge between two nodes.
     
    135121    Edge findEdge(Node u,Node v, Edge prev = INVALID)
    136122    {
    137       return prev.n == -1 ? Edge(*this, u.n, v.n) : INVALID;
     123      return prev.id == -1 ? Edge(*this, u.id, v.id) : INVALID;
    138124    }
    139125   
    140126     
    141127    class Node {
    142       friend class FullGraph;
    143       template <typename T> friend class NodeMap;
    144 
    145       friend class Edge;
    146       friend class OutEdgeIt;
    147       friend class InEdgeIt;
    148       friend class SymEdge;
     128      friend class FullGraphBase;
    149129
    150130    protected:
    151       int n;
    152       friend int FullGraph::id(Node v);
    153       Node(int nn) {n=nn;}
     131      int id;
     132      Node(int _id) { id = _id;}
    154133    public:
    155134      Node() {}
    156       Node (Invalid) { n=-1; }
    157       bool operator==(const Node i) const {return n==i.n;}
    158       bool operator!=(const Node i) const {return n!=i.n;}
    159       bool operator<(const Node i) const {return n<i.n;}
     135      Node (Invalid) { id = -1; }
     136      bool operator==(const Node node) const {return id == node.id;}
     137      bool operator!=(const Node node) const {return id != node.id;}
     138      bool operator<(const Node node) const {return id < node.id;}
    160139    };
    161140   
    162     class NodeIt : public Node {
    163       const FullGraph *G;
    164       friend class FullGraph;
    165     public:
    166       NodeIt() : Node() { }
    167       NodeIt(const FullGraph& _G,Node n) : Node(n), G(&_G) { }
    168       NodeIt(Invalid i) : Node(i) { }
    169       NodeIt(const FullGraph& _G) : Node(_G.NodeNum?0:-1), G(&_G) { }
    170       ///\todo Undocumented conversion Node -\> NodeIt.
    171       NodeIt& operator++() { n=(n+2)%(G->NodeNum+1)-1;return *this; }
    172     };
     141
    173142
    174143    class Edge {
    175       friend class FullGraph;
    176       template <typename T> friend class EdgeMap;
     144      friend class FullGraphBase;
    177145     
    178       friend class Node;
    179       friend class NodeIt;
    180146    protected:
    181       int n; //NodeNum*head+tail;
    182       friend int FullGraph::id(Edge e);
    183 
    184       Edge(int nn) : n(nn) {}
    185       Edge(const FullGraph &G, int tail, int head) : n(G.NodeNum*head+tail) {}
     147      int id;  // NodeNum * head + tail;
     148
     149      Edge(int _id) : id(_id) {}
     150
     151      Edge(const FullGraphBase& _graph, int tail, int head)
     152        : id(_graph.NodeNum * head+tail) {}
    186153    public:
    187154      Edge() { }
    188       Edge (Invalid) { n=-1; }
    189       bool operator==(const Edge i) const {return n==i.n;}
    190       bool operator!=(const Edge i) const {return n!=i.n;}
    191       bool operator<(const Edge i) const {return n<i.n;}
    192       ///\bug This is a workaround until somebody tells me how to
    193       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
    194       int &idref() {return n;}
    195       const int &idref() const {return n;}
     155      Edge (Invalid) { id = -1; }
     156      bool operator==(const Edge edge) const {return id == edge.id;}
     157      bool operator!=(const Edge edge) const {return id != edge.id;}
     158      bool operator<(const Edge edge) const {return id < edge.id;}
    196159    };
    197    
    198     class EdgeIt : public Edge {
    199       friend class FullGraph;
    200     public:
    201       EdgeIt(const FullGraph& _G) : Edge(_G.EdgeNum-1) { }
    202       EdgeIt(const FullGraph&, Edge e) : Edge(e) { }
    203       EdgeIt (Invalid i) : Edge(i) { }
    204       EdgeIt() : Edge() { }
    205       EdgeIt& operator++() { --n; return *this; }
    206 
    207       ///\bug This is a workaround until somebody tells me how to
    208       ///make class \c SymFullGraph::SymEdgeMap friend of Edge
    209       int &idref() {return n;}
    210     };
    211    
    212     class OutEdgeIt : public Edge {
    213       const FullGraph *G;
    214       friend class FullGraph;
    215     public:
    216       OutEdgeIt() : Edge() { }
    217       OutEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
    218       OutEdgeIt (Invalid i) : Edge(i) { }
    219 
    220       OutEdgeIt(const FullGraph& _G,const Node v) : Edge(v.n), G(&_G) {}
    221      
    222       OutEdgeIt& operator++()
    223       { n+=G->NodeNum; if(n>=G->EdgeNum) n=-1; return *this; }
    224 
    225     };
    226    
    227     class InEdgeIt : public Edge {
    228       const FullGraph *G;
    229       friend class FullGraph;
    230     public:
    231       InEdgeIt() : Edge() { }
    232       InEdgeIt(const FullGraph& _G, Edge e) : Edge(e), G(&_G) { }
    233       InEdgeIt (Invalid i) : Edge(i) { }
    234       InEdgeIt(const FullGraph& _G,Node v) : Edge(v.n*_G.NodeNum), G(&_G) {}
    235       InEdgeIt& operator++()
    236       { if(!((++n)%G->NodeNum)) n=-1; return *this; }
    237     };
     160
     161    void first(Node& node) const {
     162      node.id = NodeNum-1;
     163    }
     164
     165    static void next(Node& node) {
     166      --node.id;
     167    }
     168
     169    void first(Edge& edge) const {
     170      edge.id = EdgeNum-1;
     171    }
     172
     173    static void next(Edge& edge) {
     174      --edge.id;
     175    }
     176
     177    void firstOut(Edge& edge, const Node& node) const {
     178      edge.id = EdgeNum + node.id - NodeNum;
     179    }
     180
     181    void nextOut(Edge& edge) const {
     182      edge.id -= NodeNum;
     183      if (edge.id < 0) edge.id = -1;
     184    }
     185
     186    void firstIn(Edge& edge, const Node& node) const {
     187      edge.id = node.id * NodeNum;
     188    }
     189   
     190    void nextIn(Edge& edge) const {
     191      ++edge.id;
     192      if (edge.id % NodeNum == 0) edge.id = -1;
     193    }
    238194
    239195  };
    240196
     197
     198  typedef AlterableGraphExtender<FullGraphBase> AlterableFullGraphBase;
     199  typedef IterableGraphExtender<AlterableFullGraphBase> IterableFullGraphBase;
     200  typedef IdMappableGraphExtender<IterableFullGraphBase> IdMappableFullGraphBase;
     201  typedef DefaultMappableGraphExtender<IdMappableFullGraphBase> MappableFullGraphBase;
     202
     203  class FullGraph : public MappableFullGraphBase {
     204  public:
     205
     206    FullGraph(int n) { construct(n); }
     207  };
     208
     209  template <>
     210  int countNodes<FullGraph>(const FullGraph& graph) {
     211    return graph.nodeNum();
     212  }
     213
     214  template <>
     215  int countEdges<FullGraph>(const FullGraph& graph) {
     216    return graph.edgeNum();
     217  }
     218
    241219  /// @} 
    242220
  • src/lemon/list_graph.h

    r937 r946  
    1 /* -*- C++ -*-
    2  * src/lemon/list_graph.h - Part of LEMON, a generic C++ optimization library
    3  *
    4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Combinatorial Optimization Research Group, EGRES).
    6  *
    7  * Permission to use, modify and distribute this software is granted
    8  * provided that this copyright notice appears in all copies. For
    9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
     1// -*- c++ -*-
    162
    173#ifndef LEMON_LIST_GRAPH_H
    184#define LEMON_LIST_GRAPH_H
    195
    20 ///\ingroup graphs
    21 ///\file
    22 ///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
    23 
    24 #include <vector>
    25 #include <climits>
    26 
    27 #include <lemon/invalid.h>
    28 
    29 #include <lemon/map_registry.h>
    30 #include <lemon/array_map.h>
    31 
    32 #include <lemon/map_defines.h>
     6#include <lemon/erasable_graph_extender.h>
     7#include <lemon/clearable_graph_extender.h>
     8#include <lemon/extendable_graph_extender.h>
     9
     10#include <lemon/idmappable_graph_extender.h>
     11
     12#include <lemon/iterable_graph_extender.h>
     13
     14#include <lemon/alteration_observer_registry.h>
     15
     16#include <lemon/default_map.h>
    3317
    3418
    3519namespace lemon {
    3620
    37 /// \addtogroup graphs
    38 /// @{
    39 
    40   ///A list graph class.
    41 
    42   ///This is a simple and fast erasable graph implementation.
    43   ///
    44   ///It conforms to the
    45   ///\ref skeleton::ErasableGraph "ErasableGraph" concept.
    46   ///\sa skeleton::ErasableGraph.
    47   class ListGraph {
    48 
    49     //Nodes are double linked.
    50     //The free nodes are only single linked using the "next" field.
    51     struct NodeT
    52     {
     21  class ListGraphBase {
     22
     23    struct NodeT {
    5324      int first_in,first_out;
    5425      int prev, next;
    5526    };
    56     //Edges are double linked.
    57     //The free edges are only single linked using the "next_in" field.
    58     struct EdgeT
    59     {
     27 
     28    struct EdgeT {
    6029      int head, tail;
    6130      int prev_in, prev_out;
     
    6433
    6534    std::vector<NodeT> nodes;
    66     //The first node
     35
    6736    int first_node;
    68     //The first free node
     37
    6938    int first_free_node;
     39
    7040    std::vector<EdgeT> edges;
    71     //The first free edge
     41
    7242    int first_free_edge;
    7343   
    7444  public:
    7545   
    76     typedef ListGraph Graph;
    77    
    78     class Node;
    79     class Edge;
    80 
    81    
    82   public:
    83 
    84     class NodeIt;
    85     class EdgeIt;
    86     class OutEdgeIt;
    87     class InEdgeIt;
    88 
    89     // Create map registries.
    90     CREATE_MAP_REGISTRIES;
    91     // Create node and edge maps.
    92     CREATE_MAPS(ArrayMap);
    93 
    94   public:
    95 
    96     ListGraph()
     46    typedef ListGraphBase Graph;
     47   
     48    class Node {
     49      friend class Graph;
     50    protected:
     51
     52      int id;
     53      Node(int pid) { id = pid;}
     54
     55    public:
     56      Node() {}
     57      Node (Invalid) { id = -1; }
     58      bool operator==(const Node& node) const {return id == node.id;}
     59      bool operator!=(const Node& node) const {return id != node.id;}
     60      bool operator<(const Node& node) const {return id < node.id;}
     61    };
     62
     63    class Edge {
     64      friend class Graph;
     65    protected:
     66
     67      int id;
     68      Edge(int pid) { id = pid;}
     69
     70    public:
     71      Edge() {}
     72      Edge (Invalid) { id = -1; }
     73      bool operator==(const Edge& edge) const {return id == edge.id;}
     74      bool operator!=(const Edge& edge) const {return id != edge.id;}
     75      bool operator<(const Edge& edge) const {return id < edge.id;}
     76    };
     77
     78
     79
     80    ListGraphBase()
    9781      : nodes(), first_node(-1),
    9882        first_free_node(-1), edges(), first_free_edge(-1) {}
    9983
    100     ListGraph(const ListGraph &_g)
    101       : nodes(_g.nodes), first_node(_g.first_node),
    102         first_free_node(_g.first_free_node), edges(_g.edges),
    103         first_free_edge(_g.first_free_edge) {}
    104    
    105     /// \bug In the vector can be hole if a node is erased from the graph.
    106     ///Number of nodes.
    107     int nodeNum() const { return nodes.size(); }
    108     ///Number of edges.
    109     int edgeNum() const { return edges.size(); }
    110 
    111     ///Set the expected maximum number of edges.
    112 
    113     ///With this function, it is possible to set the expected number of edges.
    114     ///The use of this fasten the building of the graph and makes
     84   
    11585    ///it possible to avoid the superfluous memory allocation.
    11686    void reserveEdge(int n) { edges.reserve(n); };
     
    12191    ///\sa id(Node)
    12292    int maxNodeId() const { return nodes.size()-1; }
     93
    12394    /// Maximum edge ID.
    12495   
     
    12798    int maxEdgeId() const { return edges.size()-1; }
    12899
    129     Node tail(Edge e) const { return edges[e.n].tail; }
    130     Node head(Edge e) const { return edges[e.n].head; }
    131 
    132     NodeIt& first(NodeIt& v) const {
    133       v=NodeIt(*this); return v; }
    134     EdgeIt& first(EdgeIt& e) const {
    135       e=EdgeIt(*this); return e; }
    136     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    137       e=OutEdgeIt(*this,v); return e; }
    138     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    139       e=InEdgeIt(*this,v); return e; }
    140 
    141     /// Node ID.
    142    
    143     /// The ID of a valid Node is a nonnegative integer not greater than
    144     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    145     /// and the greatest node ID can be actually less then \ref maxNodeId().
    146     ///
    147     /// The ID of the \ref INVALID node is -1.
    148     ///\return The ID of the node \c v.
    149     static int id(Node v) { return v.n; }
    150     /// Edge ID.
    151    
    152     /// The ID of a valid Edge is a nonnegative integer not greater than
    153     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    154     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    155     ///
    156     /// The ID of the \ref INVALID edge is -1.
    157     ///\return The ID of the edge \c e.
    158     static int id(Edge e) { return e.n; }
     100    Node tail(Edge e) const { return edges[e.id].tail; }
     101    Node head(Edge e) const { return edges[e.id].head; }
     102
     103
     104    void first(Node& node) const {
     105      node.id = first_node;
     106    }
     107
     108    void next(Node& node) const {
     109      node.id = nodes[node.id].next;
     110    }
     111
     112
     113    void first(Edge& e) const {
     114      int n;
     115      for(n = first_node;
     116          n!=-1 && nodes[n].first_in == -1;
     117          n = nodes[n].next);
     118      e.id = (n == -1) ? -1 : nodes[n].first_in;
     119    }
     120
     121    void next(Edge& edge) const {
     122      if (edges[edge.id].next_in != -1) {
     123        edge.id = edges[edge.id].next_in;
     124      } else {
     125        int n;
     126        for(n = nodes[edges[edge.id].head].next;
     127          n!=-1 && nodes[n].first_in == -1;
     128          n = nodes[n].next);
     129        edge.id = (n == -1) ? -1 : nodes[n].first_in;
     130      }     
     131    }
     132
     133    void firstOut(Edge &e, const Node& v) const {
     134      e.id = nodes[v.id].first_out;
     135    }
     136    void nextOut(Edge &e) const {
     137      e.id=edges[e.id].next_out;
     138    }
     139
     140    void firstIn(Edge &e, const Node& v) const {
     141      e.id = nodes[v.id].first_in;
     142    }
     143    void nextIn(Edge &e) const {
     144      e.id=edges[e.id].next_in;
     145    }
     146
     147   
     148    static int id(Node v) { return v.id; }
     149    static int id(Edge e) { return e.id; }
    159150
    160151    /// Adds a new node to the graph.
     
    162153    /// \warning It adds the new node to the front of the list.
    163154    /// (i.e. the lastly added node becomes the first.)
    164     Node addNode() {
     155    Node addNode() {     
    165156      int n;
    166157     
    167       if(first_free_node==-1)
    168         {
    169           n = nodes.size();
    170           nodes.push_back(NodeT());
    171         }
    172       else {
     158      if(first_free_node==-1) {
     159        n = nodes.size();
     160        nodes.push_back(NodeT());
     161      } else {
    173162        n = first_free_node;
    174163        first_free_node = nodes[n].next;
     
    182171      nodes[n].first_in = nodes[n].first_out = -1;
    183172     
    184       Node nn; nn.n=n;
    185 
    186       //Update dynamic maps
    187       node_maps.add(nn);
    188 
    189       return nn;
     173      return Node(n);
    190174    }
    191175   
    192176    Edge addEdge(Node u, Node v) {
    193       int n;
    194      
    195       if(first_free_edge==-1)
    196         {
    197           n = edges.size();
    198           edges.push_back(EdgeT());
    199         }
    200       else {
     177      int n;     
     178
     179      if (first_free_edge == -1) {
     180        n = edges.size();
     181        edges.push_back(EdgeT());
     182      } else {
    201183        n = first_free_edge;
    202184        first_free_edge = edges[n].next_in;
    203185      }
    204186     
    205       edges[n].tail = u.n; edges[n].head = v.n;
    206 
    207       edges[n].next_out = nodes[u.n].first_out;
    208       if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
    209       edges[n].next_in = nodes[v.n].first_in;
    210       if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
     187      edges[n].tail = u.id;
     188      edges[n].head = v.id;
     189
     190      edges[n].next_out = nodes[u.id].first_out;
     191      if(nodes[u.id].first_out != -1) {
     192        edges[nodes[u.id].first_out].prev_out = n;
     193      }
     194     
     195      edges[n].next_in = nodes[v.id].first_in;
     196      if(nodes[v.id].first_in != -1) {
     197        edges[nodes[v.id].first_in].prev_in = n;
     198      }
     199     
    211200      edges[n].prev_in = edges[n].prev_out = -1;
    212201       
    213       nodes[u.n].first_out = nodes[v.n].first_in = n;
    214 
    215       Edge e; e.n=n;
    216 
    217       //Update dynamic maps
    218       edge_maps.add(e);
    219 
    220       return e;
    221     }
    222    
    223     /// Finds an edge between two nodes.
    224 
    225     /// Finds an edge from node \c u to node \c v.
    226     ///
    227     /// If \c prev is \ref INVALID (this is the default value), then
    228     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    229     /// the next edge from \c u to \c v after \c prev.
    230     /// \return The found edge or INVALID if there is no such an edge.
    231     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    232     {
    233       int e = (prev.n==-1)? nodes[u.n].first_out : edges[prev.n].next_out;
    234       while(e!=-1 && edges[e].tail!=v.n) e = edges[e].next_out;
    235       prev.n=e;
    236       return prev;
    237     }
    238    
    239   private:
    240     void eraseEdge(int n) {
    241      
    242       if(edges[n].next_in!=-1)
     202      nodes[u.id].first_out = nodes[v.id].first_in = n;
     203
     204      return Edge(n);
     205    }
     206   
     207    void erase(const Node& node) {
     208      int n = node.id;
     209     
     210      if(nodes[n].next != -1) {
     211        nodes[nodes[n].next].prev = nodes[n].prev;
     212      }
     213     
     214      if(nodes[n].prev != -1) {
     215        nodes[nodes[n].prev].next = nodes[n].next;
     216      } else {
     217        first_node = nodes[n].next;
     218      }
     219     
     220      nodes[n].next = first_free_node;
     221      first_free_node = n;
     222
     223    }
     224   
     225    void erase(const Edge& edge) {
     226      int n = edge.id;
     227     
     228      if(edges[n].next_in!=-1) {
    243229        edges[edges[n].next_in].prev_in = edges[n].prev_in;
    244       if(edges[n].prev_in!=-1)
     230      }
     231
     232      if(edges[n].prev_in!=-1) {
    245233        edges[edges[n].prev_in].next_in = edges[n].next_in;
    246       else nodes[edges[n].head].first_in = edges[n].next_in;
    247      
    248       if(edges[n].next_out!=-1)
     234      } else {
     235        nodes[edges[n].head].first_in = edges[n].next_in;
     236      }
     237
     238     
     239      if(edges[n].next_out!=-1) {
    249240        edges[edges[n].next_out].prev_out = edges[n].prev_out;
    250       if(edges[n].prev_out!=-1)
     241      }
     242
     243      if(edges[n].prev_out!=-1) {
    251244        edges[edges[n].prev_out].next_out = edges[n].next_out;
    252       else nodes[edges[n].tail].first_out = edges[n].next_out;
     245      } else {
     246        nodes[edges[n].tail].first_out = edges[n].next_out;
     247      }
    253248     
    254249      edges[n].next_in = first_free_edge;
    255250      first_free_edge = n;     
    256251
    257       //Update dynamic maps
    258       Edge e; e.n=n;
    259       edge_maps.erase(e);
    260 
    261     }
    262      
    263   public:
    264 
    265     void erase(Node nn) {
    266       int n=nn.n;
    267      
    268       int m;
    269       while((m=nodes[n].first_in)!=-1) eraseEdge(m);
    270       while((m=nodes[n].first_out)!=-1) eraseEdge(m);
    271 
    272       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
    273       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
    274       else first_node = nodes[n].next;
    275      
    276       nodes[n].next = first_free_node;
    277       first_free_node = n;
    278 
    279       //Update dynamic maps
    280       node_maps.erase(nn);
    281 
    282     }
    283    
    284     void erase(Edge e) { eraseEdge(e.n); }
     252    }
    285253
    286254    void clear() {
    287       edge_maps.clear();
    288255      edges.clear();
    289       node_maps.clear();
    290256      nodes.clear();
    291       first_node=first_free_node=first_free_edge=-1;
    292     }
    293 
    294     class Node {
    295       friend class ListGraph;
    296       template <typename T> friend class NodeMap;
    297        
    298       friend class Edge;
    299       friend class OutEdgeIt;
    300       friend class InEdgeIt;
    301       friend class SymEdge;
    302 
    303     protected:
    304       int n;
    305       friend int ListGraph::id(Node v);
    306       Node(int nn) {n=nn;}
    307     public:
    308       Node() {}
    309       Node (Invalid) { n=-1; }
    310       bool operator==(const Node i) const {return n==i.n;}
    311       bool operator!=(const Node i) const {return n!=i.n;}
    312       bool operator<(const Node i) const {return n<i.n;}
    313       //      ///Validity check
    314       //      operator bool() { return n!=-1; }
    315     };
    316    
    317     class NodeIt : public Node {
    318       const ListGraph *G;
    319       friend class ListGraph;
    320     public:
    321       NodeIt() : Node() { }
    322       NodeIt(Invalid i) : Node(i) { }
    323       NodeIt(const ListGraph& _G) : Node(_G.first_node), G(&_G) { }
    324       NodeIt(const ListGraph& _G,Node n) : Node(n), G(&_G) { }
    325       NodeIt &operator++() {
    326         n=G->nodes[n].next;
    327         return *this;
    328       }
    329       //      ///Validity check
    330       //      operator bool() { return Node::operator bool(); }     
    331     };
    332 
    333     class Edge {
    334       friend class ListGraph;
    335       template <typename T> friend class EdgeMap;
    336 
    337       friend class SymListGraph;
    338      
    339       friend class Node;
    340       friend class NodeIt;
    341     protected:
    342       int n;
    343       friend int ListGraph::id(Edge e);
    344 
    345     public:
    346       /// An Edge with id \c n.
    347 
    348       /// \bug It should be
    349       /// obtained by a member function of the Graph.
    350       Edge(int nn) {n=nn;}
    351 
    352       Edge() { }
    353       Edge (Invalid) { n=-1; }
    354       bool operator==(const Edge i) const {return n==i.n;}
    355       bool operator!=(const Edge i) const {return n!=i.n;}
    356       bool operator<(const Edge i) const {return n<i.n;}
    357       //      ///Validity check
    358       //      operator bool() { return n!=-1; }
    359    };
    360    
    361     class EdgeIt : public Edge {
    362       const ListGraph *G;
    363       friend class ListGraph;
    364     public:
    365       EdgeIt(const ListGraph& _G) : Edge(), G(&_G) {
    366         int m;
    367         for(m=_G.first_node;
    368             m!=-1 && _G.nodes[m].first_in == -1; m = _G.nodes[m].next);
    369         n = (m==-1)?-1:_G.nodes[m].first_in;
    370       }
    371       EdgeIt (Invalid i) : Edge(i) { }
    372       EdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    373       EdgeIt() : Edge() { }
    374       EdgeIt &operator++() {
    375         if(G->edges[n].next_in!=-1) n=G->edges[n].next_in;
    376         else {
    377           int nn;
    378           for(nn=G->nodes[G->edges[n].head].next;
    379               nn!=-1 && G->nodes[nn].first_in == -1;
    380               nn = G->nodes[nn].next) ;
    381           n = (nn==-1)?-1:G->nodes[nn].first_in;
    382         }
    383         return *this;
    384       }
    385       //      ///Validity check
    386       //      operator bool() { return Edge::operator bool(); }     
    387     };
    388    
    389     class OutEdgeIt : public Edge {
    390       const ListGraph *G;
    391       friend class ListGraph;
    392     public:
    393       OutEdgeIt() : Edge() { }
    394       OutEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    395       OutEdgeIt (Invalid i) : Edge(i) { }
    396 
    397       OutEdgeIt(const ListGraph& _G,const Node v)
    398         : Edge(_G.nodes[v.n].first_out), G(&_G) {}
    399       OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
    400       //      ///Validity check
    401       //      operator bool() { return Edge::operator bool(); }     
    402     };
    403    
    404     class InEdgeIt : public Edge {
    405       const ListGraph *G;
    406       friend class ListGraph;
    407     public:
    408       InEdgeIt() : Edge() { }
    409       InEdgeIt(const ListGraph& _G, Edge e) : Edge(e), G(&_G) { }
    410       InEdgeIt (Invalid i) : Edge(i) { }
    411       InEdgeIt(const ListGraph& _G,Node v)
    412         : Edge(_G.nodes[v.n].first_in), G(&_G) { }
    413       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
    414       //      ///Validity check
    415       //      operator bool() { return Edge::operator bool(); }     
    416     };
     257      first_node = first_free_node = first_free_edge = -1;
     258    }
     259
    417260  };
    418261
    419   ///Graph for bidirectional edges.
    420 
    421   ///The purpose of this graph structure is to handle graphs
    422   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
    423   ///of oppositely directed edges.
    424   ///There is a new edge map type called
    425   ///\ref lemon::SymListGraph::SymEdgeMap "SymEdgeMap"
    426   ///that complements this
    427   ///feature by
    428   ///storing shared values for the edge pairs. The usual
    429   ///\ref lemon::skeleton::StaticGraph::EdgeMap "EdgeMap"
    430   ///can be used
    431   ///as well.
    432   ///
    433   ///The oppositely directed edge can also be obtained easily
    434   ///using \ref lemon::SymListGraph::opposite() "opposite()" member function.
    435   ///
    436   ///Here erase(Edge) deletes a pair of edges.
    437   ///
    438   ///\todo this date structure need some reconsiderations. Maybe it
    439   ///should be implemented independently from ListGraph.
    440   /* 
    441   class SymListGraph : public ListGraph
    442   {
    443   public:
    444 
    445     typedef SymListGraph Graph;
    446 
    447     // Create symmetric map registry.
    448     CREATE_SYM_EDGE_MAP_REGISTRY;
    449     // Create symmetric edge map.
    450     CREATE_SYM_EDGE_MAP(ArrayMap);
    451 
    452     SymListGraph() : ListGraph() { }
    453     SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
    454     ///Adds a pair of oppositely directed edges to the graph.
    455     Edge addEdge(Node u, Node v)
    456     {
    457       Edge e = ListGraph::addEdge(u,v);
    458       Edge f = ListGraph::addEdge(v,u);
    459       sym_edge_maps.add(e);
    460       sym_edge_maps.add(f);
    461      
    462       return e;
    463     }
    464 
    465     void erase(Node n) { ListGraph::erase(n);}
    466     ///The oppositely directed edge.
    467 
    468     ///Returns the oppositely directed
    469     ///pair of the edge \c e.
    470     static Edge opposite(Edge e)
    471     {
    472       Edge f;
    473       f.n = e.n - 2*(e.n%2) + 1;
    474       return f;
    475     }
    476    
    477     ///Removes a pair of oppositely directed edges to the graph.
    478     void erase(Edge e) {
    479       Edge f = opposite(e);
    480       sym_edge_maps.erase(e);
    481       sym_edge_maps.erase(f);
    482       ListGraph::erase(f);
    483       ListGraph::erase(e);
    484     }   
    485     };*/
    486 
    487   class SymListGraph : public ListGraph {
    488     typedef ListGraph Parent;
    489   public:
    490 
    491     typedef SymListGraph Graph;
    492 
    493     typedef ListGraph::Node Node;
    494     typedef ListGraph::NodeIt NodeIt;
    495 
    496     class SymEdge;
    497     class SymEdgeIt;
    498 
    499     class Edge;
    500     class EdgeIt;
    501     class OutEdgeIt;
    502     class InEdgeIt;
    503 
    504     template <typename Value>
    505     class NodeMap : public Parent::NodeMap<Value> {     
    506     public:
    507       NodeMap(const SymListGraph& g)
    508         : SymListGraph::Parent::NodeMap<Value>(g) {}
    509       NodeMap(const SymListGraph& g, Value v)
    510         : SymListGraph::Parent::NodeMap<Value>(g, v) {}
    511       template<typename TT>
    512       NodeMap(const NodeMap<TT>& copy)
    513         : SymListGraph::Parent::NodeMap<Value>(copy) { }           
    514     };
    515 
    516     template <typename Value>
    517     class SymEdgeMap : public Parent::EdgeMap<Value> {
    518     public:
    519       typedef SymEdge KeyType;
    520 
    521       SymEdgeMap(const SymListGraph& g)
    522         : SymListGraph::Parent::EdgeMap<Value>(g) {}
    523       SymEdgeMap(const SymListGraph& g, Value v)
    524         : SymListGraph::Parent::EdgeMap<Value>(g, v) {}
    525       template<typename TT>
    526       SymEdgeMap(const SymEdgeMap<TT>& copy)
    527         : SymListGraph::Parent::EdgeMap<Value>(copy) { }
    528      
    529     };
    530 
    531     // Create edge map registry.
    532     CREATE_EDGE_MAP_REGISTRY;
    533     // Create edge maps.
    534     CREATE_EDGE_MAP(ArrayMap);
    535 
    536     class Edge {
    537       friend class SymListGraph;
    538       friend class SymListGraph::EdgeIt;
    539       friend class SymListGraph::OutEdgeIt;
    540       friend class SymListGraph::InEdgeIt;
    541      
    542     protected:
    543       int id;
    544 
    545       Edge(int pid) { id = pid; }
    546 
    547     public:
    548       /// An Edge with id \c n.
    549 
    550       Edge() { }
    551       Edge (Invalid) { id = -1; }
    552 
    553       operator SymEdge(){ return SymEdge(id >> 1);}
    554      
    555       bool operator==(const Edge i) const {return id == i.id;}
    556       bool operator!=(const Edge i) const {return id != i.id;}
    557       bool operator<(const Edge i) const {return id < i.id;}
    558       //      ///Validity check
    559       //      operator bool() { return n!=-1; }
    560     };
    561 
    562     class SymEdge : public ListGraph::Edge {
    563       friend class SymListGraph;
    564       friend class SymListGraph::Edge;
    565       typedef ListGraph::Edge Parent;
    566 
    567     protected:     
    568       SymEdge(int pid) : Parent(pid) {}
    569     public:
    570 
    571       SymEdge() { }
    572       SymEdge(const ListGraph::Edge& i) : Parent(i) {}
    573       SymEdge (Invalid) : Parent(INVALID) {}
    574 
    575     };
    576 
    577     class OutEdgeIt {
    578       Parent::OutEdgeIt out;
    579       Parent::InEdgeIt in;     
    580     public:
    581       OutEdgeIt() {}
    582       OutEdgeIt(const SymListGraph& g, Edge e) {
    583         if ((e.id & 1) == 0) { 
    584           out = Parent::OutEdgeIt(g, SymEdge(e));
    585           in = Parent::InEdgeIt(g, g.tail(e));
    586         } else {
    587           out = Parent::OutEdgeIt(INVALID);
    588           in = Parent::InEdgeIt(g, SymEdge(e));
    589         }
    590       }
    591       OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    592 
    593       OutEdgeIt(const SymListGraph& g, const Node v)
    594         : out(g, v), in(g, v) {}
    595       OutEdgeIt &operator++() {
    596         if (out != INVALID) {
    597           ++out;
    598         } else {
    599           ++in;
    600         }
    601         return *this;
    602       }
    603 
    604       operator Edge() const {
    605         if (out == INVALID && in == INVALID) return INVALID;
    606         return out != INVALID ? forward(out) : backward(in);
    607       }
    608 
    609       bool operator==(const Edge i) const {return Edge(*this) == i;}
    610       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    611       bool operator<(const Edge i) const {return Edge(*this) < i;}
    612     };
    613 
    614     class InEdgeIt {
    615       Parent::OutEdgeIt out;
    616       Parent::InEdgeIt in;     
    617     public:
    618       InEdgeIt() {}
    619       InEdgeIt(const SymListGraph& g, Edge e) {
    620         if ((e.id & 1) == 0) { 
    621           out = Parent::OutEdgeIt(g, SymEdge(e));
    622           in = Parent::InEdgeIt(g, g.tail(e));
    623         } else {
    624           out = Parent::OutEdgeIt(INVALID);
    625           in = Parent::InEdgeIt(g, SymEdge(e));
    626         }
    627       }
    628       InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    629 
    630       InEdgeIt(const SymListGraph& g, const Node v)
    631         : out(g, v), in(g, v) {}
    632 
    633       InEdgeIt &operator++() {
    634         if (out != INVALID) {
    635           ++out;
    636         } else {
    637           ++in;
    638         }
    639         return *this;
    640       }
    641 
    642       operator Edge() const {
    643         if (out == INVALID && in == INVALID) return INVALID;
    644         return out != INVALID ? backward(out) : forward(in);
    645       }
    646 
    647       bool operator==(const Edge i) const {return Edge(*this) == i;}
    648       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    649       bool operator<(const Edge i) const {return Edge(*this) < i;}
    650     };
    651 
    652     class SymEdgeIt : public Parent::EdgeIt {
    653 
    654     public:
    655       SymEdgeIt() {}
    656 
    657       SymEdgeIt(const SymListGraph& g)
    658         : SymListGraph::Parent::EdgeIt(g) {}
    659 
    660       SymEdgeIt(const SymListGraph& g, SymEdge e)
    661         : SymListGraph::Parent::EdgeIt(g, e) {}
    662 
    663       SymEdgeIt(Invalid i)
    664         : SymListGraph::Parent::EdgeIt(INVALID) {}
    665 
    666       SymEdgeIt& operator++() {
    667         SymListGraph::Parent::EdgeIt::operator++();
    668         return *this;
    669       }
    670 
    671       operator SymEdge() const {
    672         return SymEdge
    673           (static_cast<const SymListGraph::Parent::EdgeIt&>(*this));
    674       }
    675       bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
    676       bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
    677       bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
    678     };
    679 
    680     class EdgeIt {
    681       SymEdgeIt it;
    682       bool fw;
    683     public:
    684       EdgeIt(const SymListGraph& g) : it(g), fw(true) {}
    685       EdgeIt (Invalid i) : it(i) { }
    686       EdgeIt(const SymListGraph& g, Edge e)
    687         : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
    688       EdgeIt() { }
    689       EdgeIt& operator++() {
    690         fw = !fw;
    691         if (fw) ++it;
    692         return *this;
    693       }
    694       operator Edge() const {
    695         if (it == INVALID) return INVALID;
    696         return fw ? forward(it) : backward(it);
    697       }
    698       bool operator==(const Edge i) const {return Edge(*this) == i;}
    699       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    700       bool operator<(const Edge i) const {return Edge(*this) < i;}
    701 
    702     };
    703 
    704     ///Number of nodes.
    705     int nodeNum() const { return Parent::nodeNum(); }
    706     ///Number of edges.
    707     int edgeNum() const { return 2*Parent::edgeNum(); }
    708     ///Number of symmetric edges.
    709     int symEdgeNum() const { return Parent::edgeNum(); }
    710 
    711     ///Set the expected maximum number of edges.
    712 
    713     ///With this function, it is possible to set the expected number of edges.
    714     ///The use of this fasten the building of the graph and makes
    715     ///it possible to avoid the superfluous memory allocation.
    716     void reserveSymEdge(int n) { Parent::reserveEdge(n); };
    717    
    718     /// Maximum node ID.
    719    
    720     /// Maximum node ID.
    721     ///\sa id(Node)
    722     int maxNodeId() const { return Parent::maxNodeId(); }
    723     /// Maximum edge ID.
    724    
    725     /// Maximum edge ID.
    726     ///\sa id(Edge)
    727     int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
    728     /// Maximum symmetric edge ID.
    729    
    730     /// Maximum symmetric edge ID.
    731     ///\sa id(SymEdge)
    732     int maxSymEdgeId() const { return Parent::maxEdgeId(); }
    733 
    734 
    735     Node tail(Edge e) const {
    736       return (e.id & 1) == 0 ?
    737         Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
    738     }
    739 
    740     Node head(Edge e) const {
    741       return (e.id & 1) == 0 ?
    742         Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
    743     }
    744 
    745     Node tail(SymEdge e) const {
    746       return Parent::tail(e);
    747     }
    748 
    749     Node head(SymEdge e) const {
    750       return Parent::head(e);
    751     }
    752 
    753     NodeIt& first(NodeIt& v) const {
    754       v=NodeIt(*this); return v; }
    755     EdgeIt& first(EdgeIt& e) const {
    756       e=EdgeIt(*this); return e; }
    757     SymEdgeIt& first(SymEdgeIt& e) const {
    758       e=SymEdgeIt(*this); return e; }
    759     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    760       e=OutEdgeIt(*this,v); return e; }
    761     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    762       e=InEdgeIt(*this,v); return e; }
    763 
    764     /// Node ID.
    765    
    766     /// The ID of a valid Node is a nonnegative integer not greater than
    767     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    768     /// and the greatest node ID can be actually less then \ref maxNodeId().
    769     ///
    770     /// The ID of the \ref INVALID node is -1.
    771     ///\return The ID of the node \c v.
    772     static int id(Node v) { return Parent::id(v); }
    773     /// Edge ID.
    774    
    775     /// The ID of a valid Edge is a nonnegative integer not greater than
    776     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    777     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    778     ///
    779     /// The ID of the \ref INVALID edge is -1.
    780     ///\return The ID of the edge \c e.
    781     static int id(Edge e) { return e.id; }
    782 
    783     /// The ID of a valid SymEdge is a nonnegative integer not greater than
    784     /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
    785     /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
    786     ///
    787     /// The ID of the \ref INVALID symmetric edge is -1.
    788     ///\return The ID of the edge \c e.
    789     static int id(SymEdge e) { return Parent::id(e); }
    790 
    791     /// Adds a new node to the graph.
    792 
    793     /// \warning It adds the new node to the front of the list.
    794     /// (i.e. the lastly added node becomes the first.)
    795     Node addNode() {
    796       return Parent::addNode();
    797     }
    798    
    799     SymEdge addEdge(Node u, Node v) {
    800       SymEdge se = Parent::addEdge(u, v);
    801       edge_maps.add(forward(se));
    802       edge_maps.add(backward(se));
    803       return se;
    804     }
    805    
    806     /// Finds an edge between two nodes.
    807 
    808     /// Finds an edge from node \c u to node \c v.
    809     ///
    810     /// If \c prev is \ref INVALID (this is the default value), then
    811     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    812     /// the next edge from \c u to \c v after \c prev.
    813     /// \return The found edge or INVALID if there is no such an edge.
    814     Edge findEdge(Node u, Node v, Edge prev = INVALID)
    815     {     
    816       if (prev == INVALID || id(prev) & 1 == 0) {
    817         SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    818         if (se != INVALID) return forward(se);
    819       } else {
    820         SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    821         if (se != INVALID) return backward(se);
    822       }
    823       return INVALID;
    824     }
    825 
    826 //     /// Finds an symmetric edge between two nodes.
    827 
    828 //     /// Finds an symmetric edge from node \c u to node \c v.
    829 //     ///
    830 //     /// If \c prev is \ref INVALID (this is the default value), then
    831 //     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    832 //     /// the next edge from \c u to \c v after \c prev.
    833 //     /// \return The found edge or INVALID if there is no such an edge.
    834 
    835 //     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
    836 //     {     
    837 //       if (prev == INVALID || id(prev) & 1 == 0) {
    838 //      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    839 //      if (se != INVALID) return se;
    840 //       } else {
    841 //      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    842 //      if (se != INVALID) return se;   
    843 //       }
    844 //       return INVALID;
    845 //     }
    846    
    847   public:
    848 
    849     void erase(Node n) {     
    850       for (OutEdgeIt it(*this, n); it != INVALID; ++it) {
    851         edge_maps.erase(it);
    852         edge_maps.erase(opposite(it));
    853       }
    854       Parent::erase(n);
    855     }
    856    
    857     void erase(SymEdge e) {
    858       edge_maps.erase(forward(e));
    859       edge_maps.erase(backward(e));
    860       Parent::erase(e);
    861     };
    862 
    863     void clear() {
    864       edge_maps.clear();
    865       Parent::clear();
    866     }
    867 
    868     static Edge opposite(Edge e) {
    869       return Edge(id(e) ^ 1);
    870     }
    871 
    872     static Edge forward(SymEdge e) {
    873       return Edge(id(e) << 1);
    874     }
    875 
    876     static Edge backward(SymEdge e) {
    877       return Edge((id(e) << 1) | 1);
    878     }
    879 
    880   };
    881 
    882   ///A graph class containing only nodes.
    883 
    884   ///This class implements a graph structure without edges.
    885   ///The most useful application of this class is to be the node set of an
    886   ///\ref EdgeSet class.
    887   ///
    888   ///It conforms to
    889   ///the \ref skeleton::ExtendableGraph "ExtendableGraph" concept
    890   ///with the exception that you cannot
    891   ///add (or delete) edges. The usual edge iterators are exists, but they are
    892   ///always \ref INVALID.
    893   ///\sa skeleton::ExtendableGraph
    894   ///\sa EdgeSet
    895   class NodeSet {
    896 
    897     //Nodes are double linked.
    898     //The free nodes are only single linked using the "next" field.
    899     struct NodeT
    900     {
    901       int first_in,first_out;
    902       int prev, next;
    903       //      NodeT() {}
    904     };
    905 
    906     std::vector<NodeT> nodes;
    907     //The first node
    908     int first_node;
    909     //The first free node
    910     int first_free_node;
    911    
    912   public:
    913 
    914     typedef NodeSet Graph;
    915    
    916     class Node;
    917     class Edge;
    918 
    919   public:
    920 
    921     class NodeIt;
    922     class EdgeIt;
    923     class OutEdgeIt;
    924     class InEdgeIt;
    925    
    926     // Create node map registry.
    927     CREATE_NODE_MAP_REGISTRY;
    928     // Create node maps.
    929     CREATE_NODE_MAP(ArrayMap);
    930 
    931     /// Creating empty map structure for edges.
    932     template <typename Value>
    933     class EdgeMap {
    934     public:
    935       EdgeMap(const Graph&) {}
    936       EdgeMap(const Graph&, const Value&) {}
    937 
    938       EdgeMap(const EdgeMap&) {}
    939       template <typename CMap> EdgeMap(const CMap&) {}
    940 
    941       EdgeMap& operator=(const EdgeMap&) {}
    942       template <typename CMap> EdgeMap& operator=(const CMap&) {}
    943      
    944       class ConstIterator {
    945       public:
    946         bool operator==(const ConstIterator&) {return true;}
    947         bool operator!=(const ConstIterator&) {return false;}
    948       };
    949 
    950       typedef ConstIterator Iterator;
    951      
    952       Iterator begin() { return Iterator();}
    953       Iterator end() { return Iterator();}
    954 
    955       ConstIterator begin() const { return ConstIterator();}
    956       ConstIterator end() const { return ConstIterator();}
    957 
    958     };
    959    
    960   public:
    961 
    962     ///Default constructor
    963     NodeSet()
    964       : nodes(), first_node(-1), first_free_node(-1) {}
    965     ///Copy constructor
    966     NodeSet(const NodeSet &_g)
    967       : nodes(_g.nodes), first_node(_g.first_node),
    968         first_free_node(_g.first_free_node) {}
    969    
    970     ///Number of nodes.
    971     int nodeNum() const { return nodes.size(); }
    972     ///Number of edges.
    973     int edgeNum() const { return 0; }
    974 
    975     /// Maximum node ID.
    976    
    977     /// Maximum node ID.
    978     ///\sa id(Node)
    979     int maxNodeId() const { return nodes.size()-1; }
    980     /// Maximum edge ID.
    981    
    982     /// Maximum edge ID.
    983     ///\sa id(Edge)
    984     int maxEdgeId() const { return 0; }
    985 
    986     Node tail(Edge e) const { return INVALID; }
    987     Node head(Edge e) const { return INVALID; }
    988 
    989     NodeIt& first(NodeIt& v) const {
    990       v=NodeIt(*this); return v; }
    991     EdgeIt& first(EdgeIt& e) const {
    992       e=EdgeIt(*this); return e; }
    993     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    994       e=OutEdgeIt(*this,v); return e; }
    995     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    996       e=InEdgeIt(*this,v); return e; }
    997 
    998     /// Node ID.
    999    
    1000     /// The ID of a valid Node is a nonnegative integer not greater than
    1001     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    1002     /// and the greatest node ID can be actually less then \ref maxNodeId().
    1003     ///
    1004     /// The ID of the \ref INVALID node is -1.
    1005     ///\return The ID of the node \c v.
    1006     static int id(Node v) { return v.n; }
    1007     /// Edge ID.
    1008    
    1009     /// The ID of a valid Edge is a nonnegative integer not greater than
    1010     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    1011     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    1012     ///
    1013     /// The ID of the \ref INVALID edge is -1.
    1014     ///\return The ID of the edge \c e.
    1015     static int id(Edge e) { return -1; }
    1016 
    1017     /// Adds a new node to the graph.
    1018 
    1019     /// \warning It adds the new node to the front of the list.
    1020     /// (i.e. the lastly added node becomes the first.)
    1021     Node addNode() {
    1022       int n;
    1023      
    1024       if(first_free_node==-1)
    1025         {
    1026           n = nodes.size();
    1027           nodes.push_back(NodeT());
    1028         }
    1029       else {
    1030         n = first_free_node;
    1031         first_free_node = nodes[n].next;
    1032       }
    1033      
    1034       nodes[n].next = first_node;
    1035       if(first_node != -1) nodes[first_node].prev = n;
    1036       first_node = n;
    1037       nodes[n].prev = -1;
    1038      
    1039       nodes[n].first_in = nodes[n].first_out = -1;
    1040      
    1041       Node nn; nn.n=n;
    1042 
    1043       //Update dynamic maps
    1044       node_maps.add(nn);
    1045 
    1046       return nn;
    1047     }
    1048    
    1049     void erase(Node nn) {
    1050       int n=nn.n;
    1051      
    1052       if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
    1053       if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
    1054       else first_node = nodes[n].next;
    1055      
    1056       nodes[n].next = first_free_node;
    1057       first_free_node = n;
    1058 
    1059       //Update dynamic maps
    1060       node_maps.erase(nn);
    1061     }
    1062    
    1063        
    1064     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    1065     {
    1066       return INVALID;
    1067     }
    1068    
    1069     void clear() {
    1070       node_maps.clear();
    1071       nodes.clear();
    1072       first_node = first_free_node = -1;
    1073     }
    1074 
    1075     class Node {
    1076       friend class NodeSet;
    1077       template <typename T> friend class NodeMap;
    1078      
    1079       friend class Edge;
    1080       friend class OutEdgeIt;
    1081       friend class InEdgeIt;
    1082 
    1083     protected:
    1084       int n;
    1085       friend int NodeSet::id(Node v);
    1086       Node(int nn) {n=nn;}
    1087     public:
    1088       Node() {}
    1089       Node (Invalid i) { n=-1; }
    1090       bool operator==(const Node i) const {return n==i.n;}
    1091       bool operator!=(const Node i) const {return n!=i.n;}
    1092       bool operator<(const Node i) const {return n<i.n;}
    1093     };
    1094    
    1095     class NodeIt : public Node {
    1096       const NodeSet *G;
    1097       friend class NodeSet;
    1098     public:
    1099       NodeIt() : Node() { }
    1100       NodeIt(const NodeSet& _G,Node n) : Node(n), G(&_G) { }
    1101       NodeIt(Invalid i) : Node(i) { }
    1102       NodeIt(const NodeSet& _G) : Node(_G.first_node), G(&_G) { }
    1103       NodeIt &operator++() {
    1104         n=G->nodes[n].next;
    1105         return *this;
    1106       }
    1107     };
    1108 
    1109     class Edge {
    1110     public:
    1111       Edge() { }
    1112       Edge (Invalid) { }
    1113       bool operator==(const Edge i) const {return true;}
    1114       bool operator!=(const Edge i) const {return false;}
    1115       bool operator<(const Edge i) const {return false;}
    1116     };
    1117    
    1118     class EdgeIt : public Edge {
    1119     public:
    1120       EdgeIt(const NodeSet& G) : Edge() { }
    1121       EdgeIt(const NodeSet&, Edge) : Edge() { }
    1122       EdgeIt (Invalid i) : Edge(i) { }
    1123       EdgeIt() : Edge() { }
    1124       EdgeIt operator++() { return INVALID; }
    1125     };
    1126    
    1127     class OutEdgeIt : public Edge {
    1128       friend class NodeSet;
    1129     public:
    1130       OutEdgeIt() : Edge() { }
    1131       OutEdgeIt(const NodeSet&, Edge) : Edge() { }
    1132       OutEdgeIt (Invalid i) : Edge(i) { }
    1133       OutEdgeIt(const NodeSet& G,const Node v)  : Edge() {}
    1134       OutEdgeIt operator++() { return INVALID; }
    1135     };
    1136    
    1137     class InEdgeIt : public Edge {
    1138       friend class NodeSet;
    1139     public:
    1140       InEdgeIt() : Edge() { }
    1141       InEdgeIt(const NodeSet&, Edge) : Edge() { }
    1142       InEdgeIt (Invalid i) : Edge(i) { }
    1143       InEdgeIt(const NodeSet& G,Node v) :Edge() {}
    1144       InEdgeIt operator++() { return INVALID; }
    1145     };
    1146 
    1147   };
    1148 
    1149 
    1150 
    1151   ///Graph structure using a node set of another graph.
    1152 
    1153   ///This structure can be used to establish another graph over a node set
    1154   /// of an existing one. The node iterator will go through the nodes of the
    1155   /// original graph, and the NodeMap's of both graphs will convert to
    1156   /// each other.
    1157   ///
    1158   ///\warning Adding or deleting nodes from the graph is not safe if an
    1159   ///\ref EdgeSet is currently attached to it!
    1160   ///
    1161   ///\todo Make it possible to add/delete edges from the base graph
    1162   ///(and from \ref EdgeSet, as well)
    1163   ///
    1164   ///\param GG The type of the graph which shares its node set with this class.
    1165   ///Its interface must conform to the
    1166   ///\ref skeleton::StaticGraph "StaticGraph" concept.
    1167   ///
    1168   ///It conforms to the
    1169   ///\ref skeleton::ExtendableGraph "ExtendableGraph" concept.
    1170   ///\sa skeleton::ExtendableGraph.
    1171   ///\sa NodeSet.
    1172   template<typename GG>
    1173   class EdgeSet {
    1174 
    1175     typedef GG NodeGraphType;
    1176 
    1177     NodeGraphType &G;
    1178 
    1179   public:
    1180 
    1181     class Node;
    1182     class Edge;
    1183     class OutEdgeIt;
    1184     class InEdgeIt;
    1185     class SymEdge;
    1186 
    1187     typedef EdgeSet Graph;
    1188 
    1189     int id(Node v) const;
    1190 
    1191     class Node : public NodeGraphType::Node {
    1192       friend class EdgeSet;
    1193      
    1194       friend class Edge;
    1195       friend class OutEdgeIt;
    1196       friend class InEdgeIt;
    1197       friend class SymEdge;
    1198 
    1199     public:
    1200       friend int EdgeSet::id(Node v) const;
    1201     public:
    1202       Node() : NodeGraphType::Node() {}
    1203       Node (Invalid i) : NodeGraphType::Node(i) {}
    1204       Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
    1205     };
    1206    
    1207     class NodeIt : public NodeGraphType::NodeIt {
    1208       friend class EdgeSet;
    1209     public:
    1210       NodeIt() : NodeGraphType::NodeIt() { }
    1211       NodeIt(const EdgeSet& _G,Node n) : NodeGraphType::NodeIt(_G.G,n) { }
    1212       NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
    1213       NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
    1214       NodeIt(const typename NodeGraphType::NodeIt &n)
    1215         : NodeGraphType::NodeIt(n) {}
    1216 
    1217       operator Node() { return Node(*this);}
    1218       NodeIt &operator++()
    1219       { this->NodeGraphType::NodeIt::operator++(); return *this;}
    1220     };
    1221 
    1222   private:
    1223     //Edges are double linked.
    1224     //The free edges are only single linked using the "next_in" field.
    1225     struct NodeT
    1226     {
    1227       int first_in,first_out;
    1228       NodeT() : first_in(-1), first_out(-1) { }
    1229     };
    1230 
    1231     struct EdgeT
    1232     {
    1233       Node head, tail;
    1234       int prev_in, prev_out;
    1235       int next_in, next_out;
    1236     };
    1237 
    1238    
    1239     typename NodeGraphType::template NodeMap<NodeT> nodes;
    1240    
    1241     std::vector<EdgeT> edges;
    1242     //The first free edge
    1243     int first_free_edge;
    1244    
    1245   public:
    1246    
    1247     class Node;
    1248     class Edge;
    1249 
    1250     class NodeIt;
    1251     class EdgeIt;
    1252     class OutEdgeIt;
    1253     class InEdgeIt;
    1254 
    1255 
    1256     // Create edge map registry.
    1257     CREATE_EDGE_MAP_REGISTRY;
    1258     // Create edge maps.
    1259     CREATE_EDGE_MAP(ArrayMap);
    1260 
    1261     // Import node maps from the NodeGraphType.
    1262     IMPORT_NODE_MAP(NodeGraphType, graph.G, EdgeSet, graph);
    1263    
    1264    
    1265   public:
    1266 
    1267     ///Constructor
    1268    
    1269     ///Construates a new graph based on the nodeset of an existing one.
    1270     ///\param _G the base graph.
    1271     explicit EdgeSet(NodeGraphType &_G)
    1272       : G(_G), nodes(_G), edges(),
    1273         first_free_edge(-1) {}
    1274     ///Copy constructor
    1275 
    1276     ///Makes a copy of an EdgeSet.
    1277     ///It will be based on the same graph.
    1278     explicit EdgeSet(const EdgeSet &_g)
    1279       : G(_g.G), nodes(_g.G), edges(_g.edges),
    1280         first_free_edge(_g.first_free_edge) {}
    1281    
    1282     ///Number of nodes.
    1283     int nodeNum() const { return G.nodeNum(); }
    1284     ///Number of edges.
    1285     int edgeNum() const { return edges.size(); }
    1286 
    1287     /// Maximum node ID.
    1288    
    1289     /// Maximum node ID.
    1290     ///\sa id(Node)
    1291     int maxNodeId() const { return G.maxNodeId(); }
    1292     /// Maximum edge ID.
    1293    
    1294     /// Maximum edge ID.
    1295     ///\sa id(Edge)
    1296     int maxEdgeId() const { return edges.size()-1; }
    1297 
    1298     Node tail(Edge e) const { return edges[e.n].tail; }
    1299     Node head(Edge e) const { return edges[e.n].head; }
    1300 
    1301     NodeIt& first(NodeIt& v) const {
    1302       v=NodeIt(*this); return v; }
    1303     EdgeIt& first(EdgeIt& e) const {
    1304       e=EdgeIt(*this); return e; }
    1305     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    1306       e=OutEdgeIt(*this,v); return e; }
    1307     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    1308       e=InEdgeIt(*this,v); return e; }
    1309 
    1310     /// Node ID.
    1311    
    1312     /// The ID of a valid Node is a nonnegative integer not greater than
    1313     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    1314     /// and the greatest node ID can be actually less then \ref maxNodeId().
    1315     ///
    1316     /// The ID of the \ref INVALID node is -1.
    1317     ///\return The ID of the node \c v.
    1318     int id(Node v) { return G.id(v); }
    1319     /// Edge ID.
    1320    
    1321     /// The ID of a valid Edge is a nonnegative integer not greater than
    1322     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    1323     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    1324     ///
    1325     /// The ID of the \ref INVALID edge is -1.
    1326     ///\return The ID of the edge \c e.
    1327     static int id(Edge e) { return e.n; }
    1328 
    1329     /// Adds a new node to the graph.
    1330     Node addNode() { return G.addNode(); }
    1331    
    1332     Edge addEdge(Node u, Node v) {
    1333       int n;
    1334      
    1335       if(first_free_edge==-1)
    1336         {
    1337           n = edges.size();
    1338           edges.push_back(EdgeT());
    1339         }
    1340       else {
    1341         n = first_free_edge;
    1342         first_free_edge = edges[n].next_in;
    1343       }
    1344      
    1345       edges[n].tail = u; edges[n].head = v;
    1346 
    1347       edges[n].next_out = nodes[u].first_out;
    1348       if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
    1349       edges[n].next_in = nodes[v].first_in;
    1350       if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
    1351       edges[n].prev_in = edges[n].prev_out = -1;
    1352        
    1353       nodes[u].first_out = nodes[v].first_in = n;
    1354 
    1355       Edge e; e.n=n;
    1356 
    1357       //Update dynamic maps
    1358       edge_maps.add(e);
    1359 
    1360       return e;
    1361     }
    1362 
    1363     /// Finds an edge between two nodes.
    1364 
    1365     /// Finds an edge from node \c u to node \c v.
    1366     ///
    1367     /// If \c prev is \ref INVALID (this is the default value), then
    1368     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    1369     /// the next edge from \c u to \c v after \c prev.
    1370     /// \return The found edge or INVALID if there is no such an edge.
    1371     Edge findEdge(Node u,Node v, Edge prev = INVALID)
    1372     {
    1373       int e = (prev.n==-1)? nodes[u].first_out : edges[prev.n].next_out;
    1374       while(e!=-1 && edges[e].tail!=v) e = edges[e].next_out;
    1375       prev.n=e;
    1376       return prev;
    1377     }
    1378    
    1379   private:
    1380     void eraseEdge(int n) {
    1381      
    1382       if(edges[n].next_in!=-1)
    1383         edges[edges[n].next_in].prev_in = edges[n].prev_in;
    1384       if(edges[n].prev_in!=-1)
    1385         edges[edges[n].prev_in].next_in = edges[n].next_in;
    1386       else nodes[edges[n].head].first_in = edges[n].next_in;
    1387      
    1388       if(edges[n].next_out!=-1)
    1389         edges[edges[n].next_out].prev_out = edges[n].prev_out;
    1390       if(edges[n].prev_out!=-1)
    1391         edges[edges[n].prev_out].next_out = edges[n].next_out;
    1392       else nodes[edges[n].tail].first_out = edges[n].next_out;
    1393      
    1394       edges[n].next_in = first_free_edge;
    1395       first_free_edge = -1;     
    1396 
    1397       //Update dynamic maps
    1398       Edge e; e.n = n;
    1399       edge_maps.erase(e);
    1400     }
    1401      
    1402   public:
    1403 
    1404     void erase(Edge e) { eraseEdge(e.n); }
    1405 
    1406     ///Clear all edges. (Doesn't clear the nodes!)
    1407     void clear() {
    1408       edge_maps.clear();
    1409       edges.clear();
    1410       first_free_edge=-1;
    1411     }
    1412 
    1413 
    1414     class Edge {
    1415     public:
    1416       friend class EdgeSet;
    1417       template <typename T> friend class EdgeMap;
    1418 
    1419       friend class Node;
    1420       friend class NodeIt;
    1421     protected:
    1422       int n;
    1423       friend int EdgeSet::id(Edge e) const;
    1424 
    1425       Edge(int nn) {n=nn;}
    1426     public:
    1427       Edge() { }
    1428       Edge (Invalid) { n=-1; }
    1429       bool operator==(const Edge i) const {return n==i.n;}
    1430       bool operator!=(const Edge i) const {return n!=i.n;}
    1431       bool operator<(const Edge i) const {return n<i.n;}
    1432     };
    1433    
    1434     class EdgeIt : public Edge {
    1435       friend class EdgeSet;
    1436       template <typename T> friend class EdgeMap;
    1437    
    1438       const EdgeSet *G;
    1439     public:
    1440       EdgeIt(const EdgeSet& _G) : Edge(), G(&_G) {
    1441         NodeIt m;
    1442         for(G->first(m);
    1443             m!=INVALID && G->nodes[m].first_in == -1;  ++m);
    1444         ///\bug AJJAJ! This is a non sense!!!!!!!
    1445         this->n = m!=INVALID?-1:G->nodes[m].first_in;
    1446       }
    1447       EdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    1448       EdgeIt (Invalid i) : Edge(i) { }
    1449       EdgeIt() : Edge() { }
    1450       ///.
    1451      
    1452       ///\bug UNIMPLEMENTED!!!!!
    1453       //
    1454       EdgeIt &operator++() {
    1455         return *this;
    1456       }
    1457     };
    1458    
    1459     class OutEdgeIt : public Edge {
    1460       const EdgeSet *G;
    1461       friend class EdgeSet;
    1462     public:
    1463       OutEdgeIt() : Edge() { }
    1464       OutEdgeIt (Invalid i) : Edge(i) { }
    1465       OutEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    1466 
    1467       OutEdgeIt(const EdgeSet& _G,const Node v) :
    1468         Edge(_G.nodes[v].first_out), G(&_G) { }
    1469       OutEdgeIt &operator++() {
    1470         Edge::n = G->edges[Edge::n].next_out;
    1471         return *this;
    1472       }
    1473     };
    1474    
    1475     class InEdgeIt : public Edge {
    1476       const EdgeSet *G;
    1477       friend class EdgeSet;
    1478     public:
    1479       InEdgeIt() : Edge() { }
    1480       InEdgeIt (Invalid i) : Edge(i) { }
    1481       InEdgeIt(const EdgeSet& _G, Edge e) : Edge(e), G(&_G) { }
    1482       InEdgeIt(const EdgeSet& _G,Node v)
    1483         : Edge(_G.nodes[v].first_in), G(&_G) { }
    1484       InEdgeIt &operator++() {
    1485         Edge::n = G->edges[Edge::n].next_in;
    1486         return *this;
    1487       }
    1488     };
    1489    
    1490   };
    1491 
    1492   template<typename GG>
    1493   inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
    1494 
    1495 /// @} 
    1496 
    1497 } //namespace lemon
    1498 
    1499 #endif //LEMON_LIST_GRAPH_H
     262  typedef AlterableGraphExtender<ListGraphBase> AlterableListGraphBase;
     263  typedef IterableGraphExtender<AlterableListGraphBase> IterableListGraphBase;
     264  typedef IdMappableGraphExtender<IterableListGraphBase> IdMappableListGraphBase;
     265  typedef DefaultMappableGraphExtender<IdMappableListGraphBase> MappableListGraphBase;
     266  typedef ExtendableGraphExtender<MappableListGraphBase> ExtendableListGraphBase;
     267  typedef ClearableGraphExtender<ExtendableListGraphBase> ClearableListGraphBase;
     268  typedef ErasableGraphExtender<ClearableListGraphBase> ErasableListGraphBase;
     269
     270  typedef ErasableListGraphBase ListGraph;
     271
     272}
     273
     274
     275 
     276
     277#endif
  • src/lemon/preflow.h

    r921 r946  
    141141              const CapMap& _capacity, FlowMap& _flow) :
    142142        g(&_G), s(_s), t(_t), capacity(&_capacity),
    143         flow(&_flow), n(_G.nodeNum()), level(_G), excess(_G,0),
     143        flow(&_flow), n(countNodes(_G)), level(_G), excess(_G,0),
    144144        flow_prop(NO_FLOW), status(AFTER_NOTHING) { }
    145145
  • src/lemon/skeletons/graph.h

    r938 r946  
    2424#include <lemon/invalid.h>
    2525#include <lemon/skeletons/maps.h>
     26#include <lemon/concept_check.h>
     27#include <lemon/skeletons/graph_component.h>
    2628
    2729namespace lemon {
     
    3133    /// @{
    3234
    33     /// An empty static graph class.
     35//     /// An empty static graph class.
    3436 
    35     /// This class provides all the common features of a graph structure,
    36     /// however completely without implementations and real data structures
    37     /// behind the interface.
    38     /// All graph algorithms should compile with this class, but it will not
    39     /// run properly, of course.
    40     ///
    41     /// It can be used for checking the interface compatibility,
    42     /// or it can serve as a skeleton of a new graph structure.
    43     ///
    44     /// Also, you will find here the full documentation of a certain graph
    45     /// feature, the documentation of a real graph imlementation
    46     /// like @ref ListGraph or
    47     /// @ref SmartGraph will just refer to this structure.
    48     ///
    49     /// \todo A pages describing the concept of concept description would
    50     /// be nice.
    51     class StaticGraph
    52     {
     37//     /// This class provides all the common features of a graph structure,
     38//     /// however completely without implementations and real data structures
     39//     /// behind the interface.
     40//     /// All graph algorithms should compile with this class, but it will not
     41//     /// run properly, of course.
     42//     ///
     43//     /// It can be used for checking the interface compatibility,
     44//     /// or it can serve as a skeleton of a new graph structure.
     45//     ///
     46//     /// Also, you will find here the full documentation of a certain graph
     47//     /// feature, the documentation of a real graph imlementation
     48//     /// like @ref ListGraph or
     49//     /// @ref SmartGraph will just refer to this structure.
     50//     ///
     51//     /// \todo A pages describing the concept of concept description would
     52//     /// be nice.
     53//     class StaticGraph
     54//     {
     55//     public:
     56//       /// Defalult constructor.
     57
     58//       /// Defalult constructor.
     59//       ///
     60//       StaticGraph() { }
     61//       ///Copy consructor.
     62
     63// //       ///\todo It is not clear, what we expect from a copy constructor.
     64// //       ///E.g. How to assign the nodes/edges to each other? What about maps?
     65// //       StaticGraph(const StaticGraph& g) { }
     66
     67//       /// The base type of node iterators,
     68//       /// or in other words, the trivial node iterator.
     69
     70//       /// This is the base type of each node iterator,
     71//       /// thus each kind of node iterator converts to this.
     72//       /// More precisely each kind of node iterator should be inherited
     73//       /// from the trivial node iterator.
     74//       class Node {
     75//       public:
     76//      /// Default constructor
     77
     78//      /// @warning The default constructor sets the iterator
     79//      /// to an undefined value.
     80//      Node() { }
     81//      /// Copy constructor.
     82
     83//      /// Copy constructor.
     84//      ///
     85//      Node(const Node&) { }
     86
     87//      /// Invalid constructor \& conversion.
     88
     89//      /// This constructor initializes the iterator to be invalid.
     90//      /// \sa Invalid for more details.
     91//      Node(Invalid) { }
     92//      /// Equality operator
     93
     94//      /// Two iterators are equal if and only if they point to the
     95//      /// same object or both are invalid.
     96//      bool operator==(Node) const { return true; }
     97
     98//      /// Inequality operator
     99       
     100//      /// \sa operator==(Node n)
     101//      ///
     102//      bool operator!=(Node) const { return true; }
     103
     104//      ///Comparison operator.
     105
     106//      ///This is a strict ordering between the nodes.
     107//      ///
     108//      ///This ordering can be different from the order in which NodeIt
     109//      ///goes through the nodes.
     110//      ///\todo Possibly we don't need it.
     111//      bool operator<(Node) const { return true; }
     112//       };
     113   
     114//       /// This iterator goes through each node.
     115
     116//       /// This iterator goes through each node.
     117//       /// Its usage is quite simple, for example you can count the number
     118//       /// of nodes in graph \c g of type \c Graph like this:
     119//       /// \code
     120//       /// int count=0;
     121//       /// for (Graph::NodeIt n(g); n!=INVALID ++n) ++count;
     122//       /// \endcode
     123//       class NodeIt : public Node {
     124//       public:
     125//      /// Default constructor
     126
     127//      /// @warning The default constructor sets the iterator
     128//      /// to an undefined value.
     129//      NodeIt() { }
     130//      /// Copy constructor.
     131       
     132//      /// Copy constructor.
     133//      ///
     134//      NodeIt(const NodeIt&) { }
     135//      /// Invalid constructor \& conversion.
     136
     137//      /// Initialize the iterator to be invalid.
     138//      /// \sa Invalid for more details.
     139//      NodeIt(Invalid) { }
     140//      /// Sets the iterator to the first node.
     141
     142//      /// Sets the iterator to the first node of \c g.
     143//      ///
     144//      NodeIt(const StaticGraph& g) { }
     145//      /// Node -> NodeIt conversion.
     146
     147//      /// Sets the iterator to the node of \c g pointed by the trivial
     148//      /// iterator n.
     149//      /// This feature necessitates that each time we
     150//      /// iterate the edge-set, the iteration order is the same.
     151//      NodeIt(const StaticGraph& g, const Node& n) { }
     152//      /// Next node.
     153
     154//      /// Assign the iterator to the next node.
     155//      ///
     156//      NodeIt& operator++() { return *this; }
     157//       };
     158   
     159   
     160//       /// The base type of the edge iterators.
     161
     162//       /// The base type of the edge iterators.
     163//       ///
     164//       class Edge {
     165//       public:
     166//      /// Default constructor
     167
     168//      /// @warning The default constructor sets the iterator
     169//      /// to an undefined value.
     170//      Edge() { }
     171//      /// Copy constructor.
     172
     173//      /// Copy constructor.
     174//      ///
     175//      Edge(const Edge&) { }
     176//      /// Initialize the iterator to be invalid.
     177
     178//      /// Initialize the iterator to be invalid.
     179//      ///
     180//      Edge(Invalid) { }
     181//      /// Equality operator
     182
     183//      /// Two iterators are equal if and only if they point to the
     184//      /// same object or both are invalid.
     185//      bool operator==(Edge) const { return true; }
     186//      /// Inequality operator
     187
     188//      /// \sa operator==(Node n)
     189//      ///
     190//      bool operator!=(Edge) const { return true; }
     191//      ///Comparison operator.
     192
     193//      ///This is a strict ordering between the nodes.
     194//      ///
     195//      ///This ordering can be different from the order in which NodeIt
     196//      ///goes through the nodes.
     197//      ///\todo Possibly we don't need it.
     198//      bool operator<(Edge) const { return true; }
     199//       };
     200   
     201//       /// This iterator goes trough the outgoing edges of a node.
     202
     203//       /// This iterator goes trough the \e outgoing edges of a certain node
     204//       /// of a graph.
     205//       /// Its usage is quite simple, for example you can count the number
     206//       /// of outgoing edges of a node \c n
     207//       /// in graph \c g of type \c Graph as follows.
     208//       /// \code
     209//       /// int count=0;
     210//       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     211//       /// \endcode
     212   
     213//       class OutEdgeIt : public Edge {
     214//       public:
     215//      /// Default constructor
     216
     217//      /// @warning The default constructor sets the iterator
     218//      /// to an undefined value.
     219//      OutEdgeIt() { }
     220//      /// Copy constructor.
     221
     222//      /// Copy constructor.
     223//      ///
     224//      OutEdgeIt(const OutEdgeIt&) { }
     225//      /// Initialize the iterator to be invalid.
     226
     227//      /// Initialize the iterator to be invalid.
     228//      ///
     229//      OutEdgeIt(Invalid) { }
     230//      /// This constructor sets the iterator to first outgoing edge.
     231   
     232//      /// This constructor set the iterator to the first outgoing edge of
     233//      /// node
     234//      ///@param n the node
     235//      ///@param g the graph
     236//      OutEdgeIt(const StaticGraph& g, const Node& n) { }
     237//      /// Edge -> OutEdgeIt conversion
     238
     239//      /// Sets the iterator to the value of the trivial iterator \c e.
     240//      /// This feature necessitates that each time we
     241//      /// iterate the edge-set, the iteration order is the same.
     242//      OutEdgeIt(const StaticGraph& g, const Edge& e) { }
     243//      ///Next outgoing edge
     244       
     245//      /// Assign the iterator to the next
     246//      /// outgoing edge of the corresponding node.
     247//      OutEdgeIt& operator++() { return *this; }
     248//       };
     249
     250//       /// This iterator goes trough the incoming edges of a node.
     251
     252//       /// This iterator goes trough the \e incoming edges of a certain node
     253//       /// of a graph.
     254//       /// Its usage is quite simple, for example you can count the number
     255//       /// of outgoing edges of a node \c n
     256//       /// in graph \c g of type \c Graph as follows.
     257//       /// \code
     258//       /// int count=0;
     259//       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
     260//       /// \endcode
     261
     262//       class InEdgeIt : public Edge {
     263//       public:
     264//      /// Default constructor
     265
     266//      /// @warning The default constructor sets the iterator
     267//      /// to an undefined value.
     268//      InEdgeIt() { }
     269//      /// Copy constructor.
     270
     271//      /// Copy constructor.
     272//      ///
     273//      InEdgeIt(const InEdgeIt&) { }
     274//      /// Initialize the iterator to be invalid.
     275
     276//      /// Initialize the iterator to be invalid.
     277//      ///
     278//      InEdgeIt(Invalid) { }
     279//      /// This constructor sets the iterator to first incoming edge.
     280   
     281//      /// This constructor set the iterator to the first incoming edge of
     282//      /// node
     283//      ///@param n the node
     284//      ///@param g the graph
     285//      InEdgeIt(const StaticGraph& g, const Node& n) { }
     286//      /// Edge -> InEdgeIt conversion
     287
     288//      /// Sets the iterator to the value of the trivial iterator \c e.
     289//      /// This feature necessitates that each time we
     290//      /// iterate the edge-set, the iteration order is the same.
     291//      InEdgeIt(const StaticGraph& g, const Edge& n) { }
     292//      /// Next incoming edge
     293
     294//      /// Assign the iterator to the next inedge of the corresponding node.
     295//      ///
     296//      InEdgeIt& operator++() { return *this; }
     297//       };
     298//       /// This iterator goes through each edge.
     299
     300//       /// This iterator goes through each edge of a graph.
     301//       /// Its usage is quite simple, for example you can count the number
     302//       /// of edges in a graph \c g of type \c Graph as follows:
     303//       /// \code
     304//       /// int count=0;
     305//       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
     306//       /// \endcode
     307//       class EdgeIt : public Edge {
     308//       public:
     309//      /// Default constructor
     310
     311//      /// @warning The default constructor sets the iterator
     312//      /// to an undefined value.
     313//      EdgeIt() { }
     314//      /// Copy constructor.
     315
     316//      /// Copy constructor.
     317//      ///
     318//      EdgeIt(const EdgeIt&) { }
     319//      /// Initialize the iterator to be invalid.
     320
     321//      /// Initialize the iterator to be invalid.
     322//      ///
     323//      EdgeIt(Invalid) { }
     324//      /// This constructor sets the iterator to first edge.
     325   
     326//      /// This constructor set the iterator to the first edge of
     327//      /// node
     328//      ///@param g the graph
     329//      EdgeIt(const StaticGraph& g) { }
     330//      /// Edge -> EdgeIt conversion
     331
     332//      /// Sets the iterator to the value of the trivial iterator \c e.
     333//      /// This feature necessitates that each time we
     334//      /// iterate the edge-set, the iteration order is the same.
     335//      EdgeIt(const StaticGraph&, const Edge&) { }
     336//      ///Next edge
     337       
     338//      /// Assign the iterator to the next
     339//      /// edge of the corresponding node.
     340//      EdgeIt& operator++() { return *this; }
     341//       };
     342
     343//       /// First node of the graph.
     344
     345//       /// \retval i the first node.
     346//       /// \return the first node.
     347//       ///
     348//       NodeIt& first(NodeIt& i) const { return i; }
     349
     350//       /// The first incoming edge.
     351
     352//       /// The first incoming edge.
     353//       ///
     354//       InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
     355//       /// The first outgoing edge.
     356
     357//       /// The first outgoing edge.
     358//       ///
     359//       OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
     360//       /// The first edge of the Graph.
     361
     362//       /// The first edge of the Graph.
     363//       ///
     364//       EdgeIt& first(EdgeIt& i) const { return i; }
     365
     366//       ///Gives back the head node of an edge.
     367
     368//       ///Gives back the head node of an edge.
     369//       ///
     370//       Node head(Edge) const { return INVALID; }
     371//       ///Gives back the tail node of an edge.
     372
     373//       ///Gives back the tail node of an edge.
     374//       ///
     375//       Node tail(Edge) const { return INVALID; }
     376 
     377//       ///Gives back the \e id of a node.
     378
     379//       ///\warning Not all graph structures provide this feature.
     380//       ///
     381//       ///\todo Should each graph provide \c id?
     382//       int id(const Node&) const { return 0; }
     383//       ///Gives back the \e id of an edge.
     384
     385//       ///\warning Not all graph structures provide this feature.
     386//       ///
     387//       ///\todo Should each graph provide \c id?
     388//       int id(const Edge&) const { return 0; }
     389
     390//       ///\e
     391     
     392//       ///\todo Should it be in the concept?
     393//       ///
     394//       int nodeNum() const { return 0; }
     395//       ///\e
     396
     397//       ///\todo Should it be in the concept?
     398//       ///
     399//       int edgeNum() const { return 0; }
     400
     401
     402//       ///Reference map of the nodes to type \c T.
     403
     404//       /// \ingroup skeletons
     405//       ///Reference map of the nodes to type \c T.
     406//       /// \sa Reference
     407//       /// \warning Making maps that can handle bool type (NodeMap<bool>)
     408//       /// needs some extra attention!
     409//       template<class T> class NodeMap : public ReferenceMap< Node, T >
     410//       {
     411//       public:
     412
     413//      ///\e
     414//      NodeMap(const StaticGraph&) { }
     415//      ///\e
     416//      NodeMap(const StaticGraph&, T) { }
     417
     418//      ///Copy constructor
     419//      template<typename TT> NodeMap(const NodeMap<TT>&) { }
     420//      ///Assignment operator
     421//      template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
     422//      { return *this; }
     423//       };
     424
     425//       ///Reference map of the edges to type \c T.
     426
     427//       /// \ingroup skeletons
     428//       ///Reference map of the edges to type \c T.
     429//       /// \sa Reference
     430//       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
     431//       /// needs some extra attention!
     432//       template<class T> class EdgeMap
     433//      : public ReferenceMap<Edge,T>
     434//       {
     435//       public:
     436
     437//      ///\e
     438//      EdgeMap(const StaticGraph&) { }
     439//      ///\e
     440//      EdgeMap(const StaticGraph&, T) { }
     441   
     442//      ///Copy constructor
     443//      template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
     444//      ///Assignment operator
     445//      template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
     446//      { return *this; }
     447//       };
     448//     };
     449
     450//     struct DummyType {
     451//       int value;
     452//       DummyType() {}
     453//       DummyType(int p) : value(p) {}
     454//       DummyType& operator=(int p) { value = p; return *this;}
     455//     };
     456   
     457//     ///\brief Checks whether \c G meets the
     458//     ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
     459//     template<class Graph> void checkCompileStaticGraph(Graph &G)
     460//     {
     461//       typedef typename Graph::Node Node;
     462//       typedef typename Graph::NodeIt NodeIt;
     463//       typedef typename Graph::Edge Edge;
     464//       typedef typename Graph::EdgeIt EdgeIt;
     465//       typedef typename Graph::InEdgeIt InEdgeIt;
     466//       typedef typename Graph::OutEdgeIt OutEdgeIt;
     467 
     468//       {
     469//      Node i; Node j(i); Node k(INVALID);
     470//      i=j;
     471//      bool b; b=true;
     472//      b=(i==INVALID); b=(i!=INVALID);
     473//      b=(i==j); b=(i!=j); b=(i<j);
     474//       }
     475//       {
     476//      NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
     477//      i=j;
     478//      j=G.first(i);
     479//      j=++i;
     480//      bool b; b=true;
     481//      b=(i==INVALID); b=(i!=INVALID);
     482//      Node n(i);
     483//      n=i;
     484//      b=(i==j); b=(i!=j); b=(i<j);
     485//      //Node ->NodeIt conversion
     486//      NodeIt ni(G,n);
     487//       }
     488//       {
     489//      Edge i; Edge j(i); Edge k(INVALID);
     490//      i=j;
     491//      bool b; b=true;
     492//      b=(i==INVALID); b=(i!=INVALID);
     493//      b=(i==j); b=(i!=j); b=(i<j);
     494//       }
     495//       {
     496//      EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
     497//      i=j;
     498//      j=G.first(i);
     499//      j=++i;
     500//      bool b; b=true;
     501//      b=(i==INVALID); b=(i!=INVALID);
     502//      Edge e(i);
     503//      e=i;
     504//      b=(i==j); b=(i!=j); b=(i<j);
     505//      //Edge ->EdgeIt conversion
     506//      EdgeIt ei(G,e);
     507//       }
     508//       {
     509//      Node n;
     510//      InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
     511//      i=j;
     512//      j=G.first(i,n);
     513//      j=++i;
     514//      bool b; b=true;
     515//      b=(i==INVALID); b=(i!=INVALID);
     516//      Edge e(i);
     517//      e=i;
     518//      b=(i==j); b=(i!=j); b=(i<j);
     519//      //Edge ->InEdgeIt conversion
     520//      InEdgeIt ei(G,e);
     521//       }
     522//       {
     523//      Node n;
     524//      OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
     525//      i=j;
     526//      j=G.first(i,n);
     527//      j=++i;
     528//      bool b; b=true;
     529//      b=(i==INVALID); b=(i!=INVALID);
     530//      Edge e(i);
     531//      e=i;
     532//      b=(i==j); b=(i!=j); b=(i<j);
     533//      //Edge ->OutEdgeIt conversion
     534//      OutEdgeIt ei(G,e);
     535//       }
     536//       {
     537//      Node n,m;
     538//      n=m=INVALID;
     539//      Edge e;
     540//      e=INVALID;
     541//      n=G.tail(e);
     542//      n=G.head(e);
     543//       }
     544//       // id tests
     545//       { Node n; int i=G.id(n); i=i; }
     546//       { Edge e; int i=G.id(e); i=i; }
     547//       //NodeMap tests
     548//       {
     549//      Node k;
     550//      typename Graph::template NodeMap<int> m(G);
     551//      //Const map
     552//      typename Graph::template NodeMap<int> const &cm = m;
     553//      //Inicialize with default value
     554//      typename Graph::template NodeMap<int> mdef(G,12);
     555//      //Copy
     556//      typename Graph::template NodeMap<int> mm(cm);
     557//      //Copy from another type
     558//      typename Graph::template NodeMap<double> dm(cm);
     559//      //Copy to more complex type
     560//      typename Graph::template NodeMap<DummyType> em(cm);
     561//      int v;
     562//      v=m[k]; m[k]=v; m.set(k,v);
     563//      v=cm[k];
     564   
     565//      m=cm; 
     566//      dm=cm; //Copy from another type 
     567//      em=cm; //Copy to more complex type
     568//      {
     569//        //Check the typedef's
     570//        typename Graph::template NodeMap<int>::ValueType val;
     571//        val=1;
     572//        typename Graph::template NodeMap<int>::KeyType key;
     573//        key = typename Graph::NodeIt(G);
     574//      }
     575//       } 
     576//       { //bool NodeMap
     577//      Node k;
     578//      typename Graph::template NodeMap<bool> m(G);
     579//      typename Graph::template NodeMap<bool> const &cm = m;  //Const map
     580//      //Inicialize with default value
     581//      typename Graph::template NodeMap<bool> mdef(G,12);
     582//      typename Graph::template NodeMap<bool> mm(cm);   //Copy
     583//      typename Graph::template NodeMap<int> dm(cm); //Copy from another type
     584//      bool v;
     585//      v=m[k]; m[k]=v; m.set(k,v);
     586//      v=cm[k];
     587   
     588//      m=cm; 
     589//      dm=cm; //Copy from another type
     590//      m=dm; //Copy to another type
     591
     592//      {
     593//        //Check the typedef's
     594//        typename Graph::template NodeMap<bool>::ValueType val;
     595//        val=true;
     596//        typename Graph::template NodeMap<bool>::KeyType key;
     597//        key= typename Graph::NodeIt(G);
     598//      }
     599//       }
     600//       //EdgeMap tests
     601//       {
     602//      Edge k;
     603//      typename Graph::template EdgeMap<int> m(G);
     604//      typename Graph::template EdgeMap<int> const &cm = m;  //Const map
     605//      //Inicialize with default value
     606//      typename Graph::template EdgeMap<int> mdef(G,12);
     607//      typename Graph::template EdgeMap<int> mm(cm);   //Copy
     608//      typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
     609//      int v;
     610//      v=m[k]; m[k]=v; m.set(k,v);
     611//      v=cm[k];
     612   
     613//      m=cm; 
     614//      dm=cm; //Copy from another type
     615//      {
     616//        //Check the typedef's
     617//        typename Graph::template EdgeMap<int>::ValueType val;
     618//        val=1;
     619//        typename Graph::template EdgeMap<int>::KeyType key;
     620//        key= typename Graph::EdgeIt(G);
     621//      }
     622//       } 
     623//       { //bool EdgeMap
     624//      Edge k;
     625//      typename Graph::template EdgeMap<bool> m(G);
     626//      typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
     627//      //Inicialize with default value
     628//      typename Graph::template EdgeMap<bool> mdef(G,12);
     629//      typename Graph::template EdgeMap<bool> mm(cm);   //Copy
     630//      typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
     631//      bool v;
     632//      v=m[k]; m[k]=v; m.set(k,v);
     633//      v=cm[k];
     634   
     635//      m=cm; 
     636//      dm=cm; //Copy from another type
     637//      m=dm; //Copy to another type
     638//      {
     639//        //Check the typedef's
     640//        typename Graph::template EdgeMap<bool>::ValueType val;
     641//        val=true;
     642//        typename Graph::template EdgeMap<bool>::KeyType key;
     643//        key= typename Graph::EdgeIt(G);
     644//      }
     645//       }
     646//     }
     647   
     648//     /// An empty non-static graph class.
     649   
     650//     /// This class provides everything that \ref StaticGraph
     651//     /// with additional functionality which enables to build a
     652//     /// graph from scratch.
     653//     class ExtendableGraph : public StaticGraph
     654//     {
     655//     public:
     656//       /// Defalult constructor.
     657
     658//       /// Defalult constructor.
     659//       ///
     660//       ExtendableGraph() { }
     661//       ///Add a new node to the graph.
     662
     663//       /// \return the new node.
     664//       ///
     665//       Node addNode() { return INVALID; }
     666//       ///Add a new edge to the graph.
     667
     668//       ///Add a new edge to the graph with tail node \c t
     669//       ///and head node \c h.
     670//       ///\return the new edge.
     671//       Edge addEdge(Node h, Node t) { return INVALID; }
     672   
     673//       /// Resets the graph.
     674
     675//       /// This function deletes all edges and nodes of the graph.
     676//       /// It also frees the memory allocated to store them.
     677//       /// \todo It might belong to \ref ErasableGraph.
     678//       void clear() { }
     679//     };
     680
     681   
     682//     ///\brief Checks whether \c G meets the
     683//     ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
     684//     template<class Graph> void checkCompileExtendableGraph(Graph &G)
     685//     {
     686//       checkCompileStaticGraph(G);
     687
     688//       typedef typename Graph::Node Node;
     689//       typedef typename Graph::NodeIt NodeIt;
     690//       typedef typename Graph::Edge Edge;
     691//       typedef typename Graph::EdgeIt EdgeIt;
     692//       typedef typename Graph::InEdgeIt InEdgeIt;
     693//       typedef typename Graph::OutEdgeIt OutEdgeIt;
     694 
     695//       Node n,m;
     696//       n=G.addNode();
     697//       m=G.addNode();
     698//       Edge e;
     699//       e=G.addEdge(n,m);
     700 
     701//       //  G.clear();
     702//     }
     703
     704
     705//     /// An empty erasable graph class.
     706 
     707//     /// This class is an extension of \ref ExtendableGraph. It also makes it
     708//     /// possible to erase edges or nodes.
     709//     class ErasableGraph : public ExtendableGraph
     710//     {
     711//     public:
     712//       /// Defalult constructor.
     713
     714//       /// Defalult constructor.
     715//       ///
     716//       ErasableGraph() { }
     717//       /// Deletes a node.
     718
     719//       /// Deletes node \c n node.
     720//       ///
     721//       void erase(Node n) { }
     722//       /// Deletes an edge.
     723
     724//       /// Deletes edge \c e edge.
     725//       ///
     726//       void erase(Edge e) { }
     727//     };
     728   
     729//     template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
     730//     {
     731//       typename Graph::Edge e;
     732//       G.erase(e);
     733//     }
     734
     735//     template<class Graph> void checkCompileGraphEraseNode(Graph &G)
     736//     {
     737//       typename Graph::Node n;
     738//       G.erase(n);
     739//     }
     740
     741//     ///\brief Checks whether \c G meets the
     742//     ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
     743//     template<class Graph> void checkCompileErasableGraph(Graph &G)
     744//     {
     745//       checkCompileExtendableGraph(G);
     746//       checkCompileGraphEraseNode(G);
     747//       checkCompileGraphEraseEdge(G);
     748//     }
     749
     750//     ///Checks whether a graph has findEdge() member function.
     751   
     752//     ///\todo findEdge() might be a global function.
     753//     ///
     754//     template<class Graph> void checkCompileGraphFindEdge(Graph &G)
     755//     {
     756//       typedef typename Graph::NodeIt Node;
     757//       typedef typename Graph::NodeIt NodeIt;
     758
     759//       G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
     760//       G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
     761//     }
     762
     763
     764
     765    /************* New GraphBase stuff **************/
     766
     767
     768    /// \bug The nodes and edges are not allowed to inherit from the
     769    /// same baseclass.
     770
     771    class BaseGraphItem {
    53772    public:
    54       /// Defalult constructor.
    55 
    56       /// Defalult constructor.
    57       ///
    58       StaticGraph() { }
    59       ///Copy consructor.
    60 
    61 //       ///\todo It is not clear, what we expect from a copy constructor.
    62 //       ///E.g. How to assign the nodes/edges to each other? What about maps?
    63 //       StaticGraph(const StaticGraph& g) { }
    64 
    65       /// The base type of node iterators,
    66       /// or in other words, the trivial node iterator.
    67 
    68       /// This is the base type of each node iterator,
    69       /// thus each kind of node iterator converts to this.
    70       /// More precisely each kind of node iterator should be inherited
    71       /// from the trivial node iterator.
    72       class Node {
    73       public:
    74         /// Default constructor
    75 
    76         /// @warning The default constructor sets the iterator
    77         /// to an undefined value.
    78         Node() { }
    79         /// Copy constructor.
    80 
    81         /// Copy constructor.
    82         ///
    83         Node(const Node&) { }
    84 
    85         /// Invalid constructor \& conversion.
    86 
    87         /// This constructor initializes the iterator to be invalid.
    88         /// \sa Invalid for more details.
    89         Node(Invalid) { }
    90         /// Equality operator
    91 
    92         /// Two iterators are equal if and only if they point to the
    93         /// same object or both are invalid.
    94         bool operator==(Node) const { return true; }
    95 
    96         /// Inequality operator
     773      BaseGraphItem() {}
     774      BaseGraphItem(Invalid) {}
     775
     776      // We explicitely list these:
     777      BaseGraphItem(BaseGraphItem const&) {}
     778      BaseGraphItem& operator=(BaseGraphItem const&) { return *this; }
     779
     780      bool operator==(BaseGraphItem) const { return false; }
     781      bool operator!=(BaseGraphItem) const { return false; }
     782
     783      // Technical requirement. Do we really need this?
     784      bool operator<(BaseGraphItem) const { return false; }
     785    };
     786
     787
     788    /// A minimal GraphBase concept
     789
     790    /// This class describes a minimal concept which can be extended to a
     791    /// full-featured graph with \ref GraphFactory.
     792    class GraphBase {
     793    public:
     794
     795      GraphBase() {}
     796
     797
     798      /// \bug Nodes and Edges are comparable each other
     799     
     800      class Node : public BaseGraphItem {};
     801      class Edge : public BaseGraphItem {};
     802
     803      // Graph operation
     804      void firstNode(Node &n) const { }
     805      void firstEdge(Edge &e) const { }
     806
     807      void firstOutEdge(Edge &e, Node) const { }
     808      void firstInEdge(Edge &e, Node) const { }
     809
     810      void nextNode(Node &n) const { }
     811      void nextEdge(Edge &e) const { }
     812
     813
     814      // Question: isn't it reasonable if this methods have a Node
     815      // parameter? Like this:
     816      // Edge& nextOut(Edge &e, Node) const { return e; }
     817      void nextOutEdge(Edge &e) const { }
     818      void nextInEdge(Edge &e) const { }
     819
     820      Node head(Edge) const { return Node(); }
     821      Node tail(Edge) const { return Node(); }
     822     
     823
     824      // Do we need id, nodeNum, edgeNum and co. in this basic graphbase
     825      // concept?
     826
     827
     828      // Maps.
     829      //
     830      // We need a special slimer concept which does not provide maps (it
     831      // wouldn't be strictly slimer, cause for map-factory id() & friends
     832      // a required...)
     833
     834      template<typename T>
     835      class NodeMap : public GraphMap<Node, T, GraphBase> {};
     836
     837      template<typename T>
     838      class EdgeMap : public GraphMap<Edge, T, GraphBase> {};
     839    };
     840
     841
     842
     843    /**************** Concept checking classes ****************/
     844
     845    template<typename BGI>
     846    struct BaseGraphItemConcept {
     847      void constraints() {
     848        BGI i1;
     849        BGI i2 = i1;
     850        BGI i3 = INVALID;
    97851       
    98         /// \sa operator==(Node n)
    99         ///
    100         bool operator!=(Node) const { return true; }
    101 
    102         ///Comparison operator.
    103 
    104         ///This is a strict ordering between the nodes.
    105         ///
    106         ///This ordering can be different from the order in which NodeIt
    107         ///goes through the nodes.
    108         ///\todo Possibly we don't need it.
    109         bool operator<(Node) const { return true; }
    110       };
    111    
    112       /// This iterator goes through each node.
    113 
    114       /// This iterator goes through each node.
    115       /// Its usage is quite simple, for example you can count the number
    116       /// of nodes in graph \c g of type \c Graph like this:
    117       /// \code
    118       /// int count=0;
    119       /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
    120       /// \endcode
    121       class NodeIt : public Node {
    122       public:
    123         /// Default constructor
    124 
    125         /// @warning The default constructor sets the iterator
    126         /// to an undefined value.
    127         NodeIt() { }
    128         /// Copy constructor.
    129        
    130         /// Copy constructor.
    131         ///
    132         NodeIt(const NodeIt&) { }
    133         /// Invalid constructor \& conversion.
    134 
    135         /// Initialize the iterator to be invalid.
    136         /// \sa Invalid for more details.
    137         NodeIt(Invalid) { }
    138         /// Sets the iterator to the first node.
    139 
    140         /// Sets the iterator to the first node of \c g.
    141         ///
    142         NodeIt(const StaticGraph& g) { }
    143         /// Node -> NodeIt conversion.
    144 
    145         /// Sets the iterator to the node of \c g pointed by the trivial
    146         /// iterator n.
    147         /// This feature necessitates that each time we
    148         /// iterate the edge-set, the iteration order is the same.
    149         NodeIt(const StaticGraph& g, const Node& n) { }
    150         /// Next node.
    151 
    152         /// Assign the iterator to the next node.
    153         ///
    154         NodeIt& operator++() { return *this; }
    155       };
    156    
    157    
    158       /// The base type of the edge iterators.
    159 
    160       /// The base type of the edge iterators.
    161       ///
    162       class Edge {
    163       public:
    164         /// Default constructor
    165 
    166         /// @warning The default constructor sets the iterator
    167         /// to an undefined value.
    168         Edge() { }
    169         /// Copy constructor.
    170 
    171         /// Copy constructor.
    172         ///
    173         Edge(const Edge&) { }
    174         /// Initialize the iterator to be invalid.
    175 
    176         /// Initialize the iterator to be invalid.
    177         ///
    178         Edge(Invalid) { }
    179         /// Equality operator
    180 
    181         /// Two iterators are equal if and only if they point to the
    182         /// same object or both are invalid.
    183         bool operator==(Edge) const { return true; }
    184         /// Inequality operator
    185 
    186         /// \sa operator==(Node n)
    187         ///
    188         bool operator!=(Edge) const { return true; }
    189         ///Comparison operator.
    190 
    191         ///This is a strict ordering between the nodes.
    192         ///
    193         ///This ordering can be different from the order in which NodeIt
    194         ///goes through the nodes.
    195         ///\todo Possibly we don't need it.
    196         bool operator<(Edge) const { return true; }
    197       };
    198    
    199       /// This iterator goes trough the outgoing edges of a node.
    200 
    201       /// This iterator goes trough the \e outgoing edges of a certain node
    202       /// of a graph.
    203       /// Its usage is quite simple, for example you can count the number
    204       /// of outgoing edges of a node \c n
    205       /// in graph \c g of type \c Graph as follows.
    206       /// \code
    207       /// int count=0;
    208       /// for (Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    209       /// \endcode
    210    
    211       class OutEdgeIt : public Edge {
    212       public:
    213         /// Default constructor
    214 
    215         /// @warning The default constructor sets the iterator
    216         /// to an undefined value.
    217         OutEdgeIt() { }
    218         /// Copy constructor.
    219 
    220         /// Copy constructor.
    221         ///
    222         OutEdgeIt(const OutEdgeIt&) { }
    223         /// Initialize the iterator to be invalid.
    224 
    225         /// Initialize the iterator to be invalid.
    226         ///
    227         OutEdgeIt(Invalid) { }
    228         /// This constructor sets the iterator to first outgoing edge.
    229    
    230         /// This constructor set the iterator to the first outgoing edge of
    231         /// node
    232         ///@param n the node
    233         ///@param g the graph
    234         OutEdgeIt(const StaticGraph& g, const Node& n) { }
    235         /// Edge -> OutEdgeIt conversion
    236 
    237         /// Sets the iterator to the value of the trivial iterator \c e.
    238         /// This feature necessitates that each time we
    239         /// iterate the edge-set, the iteration order is the same.
    240         OutEdgeIt(const StaticGraph& g, const Edge& e) { }
    241         ///Next outgoing edge
    242        
    243         /// Assign the iterator to the next
    244         /// outgoing edge of the corresponding node.
    245         OutEdgeIt& operator++() { return *this; }
    246       };
    247 
    248       /// This iterator goes trough the incoming edges of a node.
    249 
    250       /// This iterator goes trough the \e incoming edges of a certain node
    251       /// of a graph.
    252       /// Its usage is quite simple, for example you can count the number
    253       /// of outgoing edges of a node \c n
    254       /// in graph \c g of type \c Graph as follows.
    255       /// \code
    256       /// int count=0;
    257       /// for(Graph::InEdgeIt e(g, n); e!=INVALID; ++e) ++count;
    258       /// \endcode
    259 
    260       class InEdgeIt : public Edge {
    261       public:
    262         /// Default constructor
    263 
    264         /// @warning The default constructor sets the iterator
    265         /// to an undefined value.
    266         InEdgeIt() { }
    267         /// Copy constructor.
    268 
    269         /// Copy constructor.
    270         ///
    271         InEdgeIt(const InEdgeIt&) { }
    272         /// Initialize the iterator to be invalid.
    273 
    274         /// Initialize the iterator to be invalid.
    275         ///
    276         InEdgeIt(Invalid) { }
    277         /// This constructor sets the iterator to first incoming edge.
    278    
    279         /// This constructor set the iterator to the first incoming edge of
    280         /// node
    281         ///@param n the node
    282         ///@param g the graph
    283         InEdgeIt(const StaticGraph& g, const Node& n) { }
    284         /// Edge -> InEdgeIt conversion
    285 
    286         /// Sets the iterator to the value of the trivial iterator \c e.
    287         /// This feature necessitates that each time we
    288         /// iterate the edge-set, the iteration order is the same.
    289         InEdgeIt(const StaticGraph& g, const Edge& n) { }
    290         /// Next incoming edge
    291 
    292         /// Assign the iterator to the next inedge of the corresponding node.
    293         ///
    294         InEdgeIt& operator++() { return *this; }
    295       };
    296       /// This iterator goes through each edge.
    297 
    298       /// This iterator goes through each edge of a graph.
    299       /// Its usage is quite simple, for example you can count the number
    300       /// of edges in a graph \c g of type \c Graph as follows:
    301       /// \code
    302       /// int count=0;
    303       /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
    304       /// \endcode
    305       class EdgeIt : public Edge {
    306       public:
    307         /// Default constructor
    308 
    309         /// @warning The default constructor sets the iterator
    310         /// to an undefined value.
    311         EdgeIt() { }
    312         /// Copy constructor.
    313 
    314         /// Copy constructor.
    315         ///
    316         EdgeIt(const EdgeIt&) { }
    317         /// Initialize the iterator to be invalid.
    318 
    319         /// Initialize the iterator to be invalid.
    320         ///
    321         EdgeIt(Invalid) { }
    322         /// This constructor sets the iterator to first edge.
    323    
    324         /// This constructor set the iterator to the first edge of
    325         /// node
    326         ///@param g the graph
    327         EdgeIt(const StaticGraph& g) { }
    328         /// Edge -> EdgeIt conversion
    329 
    330         /// Sets the iterator to the value of the trivial iterator \c e.
    331         /// This feature necessitates that each time we
    332         /// iterate the edge-set, the iteration order is the same.
    333         EdgeIt(const StaticGraph&, const Edge&) { }
    334         ///Next edge
    335        
    336         /// Assign the iterator to the next
    337         /// edge of the corresponding node.
    338         EdgeIt& operator++() { return *this; }
    339       };
    340 
    341       /// First node of the graph.
    342 
    343       /// \retval i the first node.
    344       /// \return the first node.
    345       ///
    346       NodeIt& first(NodeIt& i) const { return i; }
    347 
    348       /// The first incoming edge.
    349 
    350       /// The first incoming edge.
    351       ///
    352       InEdgeIt& first(InEdgeIt &i, Node) const { return i; }
    353       /// The first outgoing edge.
    354 
    355       /// The first outgoing edge.
    356       ///
    357       OutEdgeIt& first(OutEdgeIt& i, Node) const { return i; }
    358       /// The first edge of the Graph.
    359 
    360       /// The first edge of the Graph.
    361       ///
    362       EdgeIt& first(EdgeIt& i) const { return i; }
    363 
    364       ///Gives back the head node of an edge.
    365 
    366       ///Gives back the head node of an edge.
    367       ///
    368       Node head(Edge) const { return INVALID; }
    369       ///Gives back the tail node of an edge.
    370 
    371       ///Gives back the tail node of an edge.
    372       ///
    373       Node tail(Edge) const { return INVALID; }
    374  
    375       ///Gives back the \e id of a node.
    376 
    377       ///\warning Not all graph structures provide this feature.
    378       ///
    379       ///\todo Should each graph provide \c id?
    380       int id(const Node&) const { return 0; }
    381       ///Gives back the \e id of an edge.
    382 
    383       ///\warning Not all graph structures provide this feature.
    384       ///
    385       ///\todo Should each graph provide \c id?
    386       int id(const Edge&) const { return 0; }
    387 
    388       ///\e
    389      
    390       ///\todo Should it be in the concept?
    391       ///
    392       int nodeNum() const { return 0; }
    393       ///\e
    394 
    395       ///\todo Should it be in the concept?
    396       ///
    397       int edgeNum() const { return 0; }
    398 
    399 
    400       ///Reference map of the nodes to type \c T.
    401 
    402       /// \ingroup skeletons
    403       ///Reference map of the nodes to type \c T.
    404       /// \sa Reference
    405       /// \warning Making maps that can handle bool type (NodeMap<bool>)
    406       /// needs some extra attention!
    407       template<class T> class NodeMap : public ReferenceMap< Node, T >
    408       {
    409       public:
    410 
    411         ///\e
    412         NodeMap(const StaticGraph&) { }
    413         ///\e
    414         NodeMap(const StaticGraph&, T) { }
    415 
    416         ///Copy constructor
    417         template<typename TT> NodeMap(const NodeMap<TT>&) { }
    418         ///Assignment operator
    419         template<typename TT> NodeMap& operator=(const NodeMap<TT>&)
    420         { return *this; }
    421       };
    422 
    423       ///Reference map of the edges to type \c T.
    424 
    425       /// \ingroup skeletons
    426       ///Reference map of the edges to type \c T.
    427       /// \sa Reference
    428       /// \warning Making maps that can handle bool type (EdgeMap<bool>)
    429       /// needs some extra attention!
    430       template<class T> class EdgeMap
    431         : public ReferenceMap<Edge,T>
    432       {
    433       public:
    434 
    435         ///\e
    436         EdgeMap(const StaticGraph&) { }
    437         ///\e
    438         EdgeMap(const StaticGraph&, T) { }
    439    
    440         ///Copy constructor
    441         template<typename TT> EdgeMap(const EdgeMap<TT>&) { }
    442         ///Assignment operator
    443         template<typename TT> EdgeMap &operator=(const EdgeMap<TT>&)
    444         { return *this; }
    445       };
    446     };
    447 
    448     struct DummyType {
    449       int value;
    450       DummyType() {}
    451       DummyType(int p) : value(p) {}
    452       DummyType& operator=(int p) { value = p; return *this;}
    453     };
    454    
    455     ///\brief Checks whether \c G meets the
    456     ///\ref lemon::skeleton::StaticGraph "StaticGraph" concept
    457     template<class Graph> void checkCompileStaticGraph(Graph &G)
    458     {
    459       typedef typename Graph::Node Node;
    460       typedef typename Graph::NodeIt NodeIt;
    461       typedef typename Graph::Edge Edge;
    462       typedef typename Graph::EdgeIt EdgeIt;
    463       typedef typename Graph::InEdgeIt InEdgeIt;
    464       typedef typename Graph::OutEdgeIt OutEdgeIt;
    465  
    466       {
    467         Node i; Node j(i); Node k(INVALID);
    468         i=j;
    469         bool b; b=true;
    470         b=(i==INVALID); b=(i!=INVALID);
    471         b=(i==j); b=(i!=j); b=(i<j);
    472       }
    473       {
    474         NodeIt i; NodeIt j(i); NodeIt k(INVALID); NodeIt l(G);
    475         i=j;
    476         j=G.first(i);
    477         j=++i;
    478         bool b; b=true;
    479         b=(i==INVALID); b=(i!=INVALID);
    480         Node n(i);
    481         n=i;
    482         b=(i==j); b=(i!=j); b=(i<j);
    483         //Node ->NodeIt conversion
    484         NodeIt ni(G,n);
    485       }
    486       {
    487         Edge i; Edge j(i); Edge k(INVALID);
    488         i=j;
    489         bool b; b=true;
    490         b=(i==INVALID); b=(i!=INVALID);
    491         b=(i==j); b=(i!=j); b=(i<j);
    492       }
    493       {
    494         EdgeIt i; EdgeIt j(i); EdgeIt k(INVALID); EdgeIt l(G);
    495         i=j;
    496         j=G.first(i);
    497         j=++i;
    498         bool b; b=true;
    499         b=(i==INVALID); b=(i!=INVALID);
    500         Edge e(i);
    501         e=i;
    502         b=(i==j); b=(i!=j); b=(i<j);
    503         //Edge ->EdgeIt conversion
    504         EdgeIt ei(G,e);
    505       }
    506       {
    507         Node n;
    508         InEdgeIt i; InEdgeIt j(i); InEdgeIt k(INVALID); InEdgeIt l(G,n);
    509         i=j;
    510         j=G.first(i,n);
    511         j=++i;
    512         bool b; b=true;
    513         b=(i==INVALID); b=(i!=INVALID);
    514         Edge e(i);
    515         e=i;
    516         b=(i==j); b=(i!=j); b=(i<j);
    517         //Edge ->InEdgeIt conversion
    518         InEdgeIt ei(G,e);
    519       }
    520       {
    521         Node n;
    522         OutEdgeIt i; OutEdgeIt j(i); OutEdgeIt k(INVALID); OutEdgeIt l(G,n);
    523         i=j;
    524         j=G.first(i,n);
    525         j=++i;
    526         bool b; b=true;
    527         b=(i==INVALID); b=(i!=INVALID);
    528         Edge e(i);
    529         e=i;
    530         b=(i==j); b=(i!=j); b=(i<j);
    531         //Edge ->OutEdgeIt conversion
    532         OutEdgeIt ei(G,e);
    533       }
    534       {
    535         Node n,m;
    536         n=m=INVALID;
    537         Edge e;
    538         e=INVALID;
    539         n=G.tail(e);
    540         n=G.head(e);
    541       }
    542       // id tests
    543       { Node n; int i=G.id(n); i=i; }
    544       { Edge e; int i=G.id(e); i=i; }
    545       //NodeMap tests
    546       {
    547         Node k;
    548         typename Graph::template NodeMap<int> m(G);
    549         //Const map
    550         typename Graph::template NodeMap<int> const &cm = m;
    551         //Inicialize with default value
    552         typename Graph::template NodeMap<int> mdef(G,12);
    553         //Copy
    554         typename Graph::template NodeMap<int> mm(cm);
    555         //Copy from another type
    556         typename Graph::template NodeMap<double> dm(cm);
    557         //Copy to more complex type
    558         typename Graph::template NodeMap<DummyType> em(cm);
    559         int v;
    560         v=m[k]; m[k]=v; m.set(k,v);
    561         v=cm[k];
    562    
    563         m=cm; 
    564         dm=cm; //Copy from another type 
    565         em=cm; //Copy to more complex type
    566         {
    567           //Check the typedef's
    568           typename Graph::template NodeMap<int>::ValueType val;
    569           val=1;
    570           typename Graph::template NodeMap<int>::KeyType key;
    571           key = typename Graph::NodeIt(G);
    572         }
    573       } 
    574       { //bool NodeMap
    575         Node k;
    576         typename Graph::template NodeMap<bool> m(G);
    577         typename Graph::template NodeMap<bool> const &cm = m;  //Const map
    578         //Inicialize with default value
    579         typename Graph::template NodeMap<bool> mdef(G,12);
    580         typename Graph::template NodeMap<bool> mm(cm);   //Copy
    581         typename Graph::template NodeMap<int> dm(cm); //Copy from another type
    582         bool v;
    583         v=m[k]; m[k]=v; m.set(k,v);
    584         v=cm[k];
    585    
    586         m=cm; 
    587         dm=cm; //Copy from another type
    588         m=dm; //Copy to another type
    589 
    590         {
    591           //Check the typedef's
    592           typename Graph::template NodeMap<bool>::ValueType val;
    593           val=true;
    594           typename Graph::template NodeMap<bool>::KeyType key;
    595           key= typename Graph::NodeIt(G);
     852        i1 = i3;
     853        if( i1 == i3 ) {
     854          if ( i2 != i3 && i3 < i2 )
     855            return;
    596856        }
    597857      }
    598       //EdgeMap tests
    599       {
    600         Edge k;
    601         typename Graph::template EdgeMap<int> m(G);
    602         typename Graph::template EdgeMap<int> const &cm = m;  //Const map
    603         //Inicialize with default value
    604         typename Graph::template EdgeMap<int> mdef(G,12);
    605         typename Graph::template EdgeMap<int> mm(cm);   //Copy
    606         typename Graph::template EdgeMap<double> dm(cm);//Copy from another type
    607         int v;
    608         v=m[k]; m[k]=v; m.set(k,v);
    609         v=cm[k];
    610    
    611         m=cm; 
    612         dm=cm; //Copy from another type
    613         {
    614           //Check the typedef's
    615           typename Graph::template EdgeMap<int>::ValueType val;
    616           val=1;
    617           typename Graph::template EdgeMap<int>::KeyType key;
    618           key= typename Graph::EdgeIt(G);
    619         }
    620       } 
    621       { //bool EdgeMap
    622         Edge k;
    623         typename Graph::template EdgeMap<bool> m(G);
    624         typename Graph::template EdgeMap<bool> const &cm = m;  //Const map
    625         //Inicialize with default value
    626         typename Graph::template EdgeMap<bool> mdef(G,12);
    627         typename Graph::template EdgeMap<bool> mm(cm);   //Copy
    628         typename Graph::template EdgeMap<int> dm(cm); //Copy from another type
    629         bool v;
    630         v=m[k]; m[k]=v; m.set(k,v);
    631         v=cm[k];
    632    
    633         m=cm; 
    634         dm=cm; //Copy from another type
    635         m=dm; //Copy to another type
    636         {
    637           //Check the typedef's
    638           typename Graph::template EdgeMap<bool>::ValueType val;
    639           val=true;
    640           typename Graph::template EdgeMap<bool>::KeyType key;
    641           key= typename Graph::EdgeIt(G);
    642         }
     858    };
     859
     860   
     861   
     862    class StaticGraph
     863      :  virtual public BaseGraphComponent, public IterableGraphComponent, public MappableGraphComponent {
     864    public:
     865      typedef BaseGraphComponent::Node Node;
     866      typedef BaseGraphComponent::Edge Edge;
     867    };
     868
     869    template <typename Graph>
     870    struct StaticGraphConcept {
     871      void constraints() {
     872        function_requires<BaseGraphComponentConcept<Graph> >();
     873        function_requires<IterableGraphComponentConcept<Graph> >();
     874        function_requires<MappableGraphComponentConcept<Graph> >();
    643875      }
    644     }
    645    
    646     /// An empty non-static graph class.
    647    
    648     /// This class provides everything that \ref StaticGraph
    649     /// with additional functionality which enables to build a
    650     /// graph from scratch.
    651     class ExtendableGraph : public StaticGraph
    652     {
     876      Graph& graph;
     877    };
     878
     879    class ExtendableGraph
     880      :  virtual public BaseGraphComponent, public StaticGraph, public ExtendableGraphComponent, public ClearableGraphComponent {
    653881    public:
    654       /// Defalult constructor.
    655 
    656       /// Defalult constructor.
    657       ///
    658       ExtendableGraph() { }
    659       ///Add a new node to the graph.
    660 
    661       /// \return the new node.
    662       ///
    663       Node addNode() { return INVALID; }
    664       ///Add a new edge to the graph.
    665 
    666       ///Add a new edge to the graph with tail node \c t
    667       ///and head node \c h.
    668       ///\return the new edge.
    669       Edge addEdge(Node h, Node t) { return INVALID; }
    670    
    671       /// Resets the graph.
    672 
    673       /// This function deletes all edges and nodes of the graph.
    674       /// It also frees the memory allocated to store them.
    675       /// \todo It might belong to \ref ErasableGraph.
    676       void clear() { }
     882      typedef BaseGraphComponent::Node Node;
     883      typedef BaseGraphComponent::Edge Edge;
    677884    };
    678885
    679    
    680     ///\brief Checks whether \c G meets the
    681     ///\ref lemon::skeleton::ExtendableGraph "ExtendableGraph" concept
    682     template<class Graph> void checkCompileExtendableGraph(Graph &G)
    683     {
    684       checkCompileStaticGraph(G);
    685 
    686       typedef typename Graph::Node Node;
    687       typedef typename Graph::NodeIt NodeIt;
    688       typedef typename Graph::Edge Edge;
    689       typedef typename Graph::EdgeIt EdgeIt;
    690       typedef typename Graph::InEdgeIt InEdgeIt;
    691       typedef typename Graph::OutEdgeIt OutEdgeIt;
    692  
    693       Node n,m;
    694       n=G.addNode();
    695       m=G.addNode();
    696       Edge e;
    697       e=G.addEdge(n,m);
    698  
    699       //  G.clear();
    700     }
    701 
    702 
    703     /// An empty erasable graph class.
    704  
    705     /// This class is an extension of \ref ExtendableGraph. It also makes it
    706     /// possible to erase edges or nodes.
    707     class ErasableGraph : public ExtendableGraph
    708     {
     886    template <typename Graph>
     887    struct ExtendableGraphConcept {
     888      void constraints() {
     889        function_requires<StaticGraphConcept<Graph> >();
     890        function_requires<ExtendableGraphComponentConcept<Graph> >();
     891        function_requires<ClearableGraphComponentConcept<Graph> >();
     892      }
     893      Graph& graph;
     894    };
     895
     896    class ErasableGraph
     897      :  virtual public BaseGraphComponent, public ExtendableGraph, public ErasableGraphComponent {
    709898    public:
    710       /// Defalult constructor.
    711 
    712       /// Defalult constructor.
    713       ///
    714       ErasableGraph() { }
    715       /// Deletes a node.
    716 
    717       /// Deletes node \c n node.
    718       ///
    719       void erase(Node n) { }
    720       /// Deletes an edge.
    721 
    722       /// Deletes edge \c e edge.
    723       ///
    724       void erase(Edge e) { }
     899      typedef BaseGraphComponent::Node Node;
     900      typedef BaseGraphComponent::Edge Edge;
    725901    };
    726    
    727     template<class Graph> void checkCompileGraphEraseEdge(Graph &G)
    728     {
    729       typename Graph::Edge e;
    730       G.erase(e);
    731     }
    732 
    733     template<class Graph> void checkCompileGraphEraseNode(Graph &G)
    734     {
    735       typename Graph::Node n;
    736       G.erase(n);
    737     }
    738 
    739     ///\brief Checks whether \c G meets the
    740     ///\ref lemon::skeleton::EresableGraph "EresableGraph" concept
    741     template<class Graph> void checkCompileErasableGraph(Graph &G)
    742     {
    743       checkCompileExtendableGraph(G);
    744       checkCompileGraphEraseNode(G);
    745       checkCompileGraphEraseEdge(G);
    746     }
    747 
    748     ///Checks whether a graph has findEdge() member function.
    749    
    750     ///\todo findEdge() might be a global function.
    751     ///
    752     template<class Graph> void checkCompileGraphFindEdge(Graph &G)
    753     {
    754       typedef typename Graph::NodeIt Node;
    755       typedef typename Graph::NodeIt NodeIt;
    756 
    757       G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
    758       G.findEdge(Node(),Node(),G.findEdge(Node(),Node())); 
    759     }
    760  
     902
     903    template <typename Graph>
     904    struct ErasableGraphConcept {
     905      void constraints() {
     906        function_requires<ExtendableGraphConcept<Graph> >();
     907        function_requires<ErasableGraphComponentConcept<Graph> >();
     908      }
     909      Graph& graph;
     910    };
     911
    761912    // @}
    762913  } //namespace skeleton 
  • src/lemon/skeletons/maps.h

    r921 r946  
    1717#ifndef LEMON_MAPSKELETON_H
    1818#define LEMON_MAPSKELETON_H
     19
     20#include <lemon/concept_check.h>
    1921
    2022///\ingroup skeletons
     
    114116    };
    115117
     118
     119    template<typename Item, typename T, typename Graph>
     120    class GraphMap : public ReadWriteMap<Item, T> {
     121      // I really, really don't like the idea that every graph should have
     122      // reference maps! --klao
     123
     124    private:
     125      // We state explicitly that graph maps have no default constructor?
     126      GraphMap();
     127
     128    public:
     129      explicit GraphMap(Graph const&) {}
     130      // value for initializing
     131      GraphMap(Graph const&, T) {}
     132
     133      // this probably should be required:
     134      GraphMap(GraphMap const&) {}
     135      GraphMap& operator=(GraphMap const&) { return *this; }
     136
     137      // but this is a absolute no-op! We should provide a more generic
     138      // graph-map-copy operation.
     139      //
     140      // template<typename TT>
     141      // GraphMap(GraphMap<TT> const&);
     142      //
     143      // template<typename TT>
     144      // GraphMap& operator=(const GraphMap<TT>&);
     145    };
     146
     147
     148    /****************  Concept-checking classes  ****************/
     149
     150    template<typename ReadMap>
     151    struct ReadMapConcept {
     152      typedef typename ReadMap::KeyType KeyType;
     153      typedef typename ReadMap::ValueType ValueType;
     154
     155      void constraints() {
     156        // No constraints for constructor.
     157
     158        // What are the requirement for the ValueType?
     159        // CopyConstructible? Assignable? None of these?
     160        ValueType v = m[k];
     161        v = m[k];
     162
     163        // FIXME:
     164        ignore_unused_variable_warning(v);
     165      }
     166
     167      ReadMap m;
     168      KeyType k;
     169    };
     170
     171    template<typename WriteMap>
     172    struct WriteMapConcept {
     173      typedef typename WriteMap::KeyType KeyType;
     174      typedef typename WriteMap::ValueType ValueType;
     175
     176      void constraints() {
     177        // No constraints for constructor.
     178
     179        m.set(k, v);
     180      }
     181
     182      WriteMap m;
     183      KeyType k;
     184      ValueType v;
     185    };
     186
     187    template<typename ReadWriteMap>
     188    struct ReadWriteMapConcept {
     189      void constraints() {
     190        function_requires< ReadMapConcept<ReadWriteMap> >();
     191        function_requires< WriteMapConcept<ReadWriteMap> >();
     192      }
     193    };
     194
     195    template<typename ReferenceMap>
     196    struct ReferenceMapConcept {
     197      typedef typename ReferenceMap::KeyType KeyType;
     198      typedef typename ReferenceMap::ValueType ValueType;
     199      typedef typename ReferenceMap::ReferenceType ReferenceType;
     200
     201      // What for is this?
     202      typedef typename ReferenceMap::ConstReferenceType ConstReferenceType;
     203
     204      void constraints() {
     205        function_requires< ReadWriteMapConcept<ReferenceMap> >();
     206
     207        m[k] = v;
     208        // Or should we require real reference?
     209        // Like this:
     210        // ValueType &vv = m[k];
     211        // ignore_unused_variable_warning(vv);
     212      }
     213
     214      ReferenceMap m;
     215      KeyType k;
     216      ValueType v;
     217    };
     218
     219    /// \todo GraphMapConceptCheck
     220
     221    template<typename GraphMap, typename Graph>
     222    struct GraphMapConcept {
     223      void constraints() {
     224        function_requires< ReadWriteMapConcept<GraphMap> >();
     225        // Construction with a graph parameter
     226        GraphMap a(g);
     227        // Ctor with a graph and a default value parameter
     228        GraphMap a2(g,t);
     229        // Copy ctor. Do we need it?
     230        GraphMap b=c;
     231        // Copy operator. Do we need it?
     232        a=b;
     233
     234        ignore_unused_variable_warning(a2);
     235      }
     236      const GraphMap &c;
     237      const Graph &g;
     238      const typename GraphMap::ValueType &t;
     239    };
     240   
     241
    116242    // @}
    117243
  • src/lemon/smart_graph.h

    r937 r946  
    2323
    2424#include <vector>
    25 #include <climits>
    2625
    2726#include <lemon/invalid.h>
    2827
    29 
    30 #include <lemon/array_map.h>
    31 
    32 #include <lemon/map_registry.h>
    33 
    34 #include <lemon/map_defines.h>
     28#include <lemon/erasable_graph_extender.h>
     29#include <lemon/clearable_graph_extender.h>
     30#include <lemon/extendable_graph_extender.h>
     31
     32#include <lemon/idmappable_graph_extender.h>
     33
     34#include <lemon/iterable_graph_extender.h>
     35
     36#include <lemon/alteration_observer_registry.h>
     37#include <lemon/default_map.h>
     38
     39
     40#include <lemon/graph_utils.h>
     41
    3542
    3643namespace lemon {
    3744
    38 /// \addtogroup graphs
    39 /// @{
    40 //  class SymSmartGraph;
     45  /// \addtogroup graphs
     46  /// @{
    4147
    4248  ///A smart graph class.
     
    5763  ///
    5864  ///\author Alpar Juttner
    59   class SmartGraph {
     65  class SmartGraphBase {
    6066
    6167    struct NodeT
     
    7884  public:
    7985
    80     typedef SmartGraph Graph;
     86    typedef SmartGraphBase Graph;
    8187
    8288    class Node;
    8389    class Edge;
    8490
    85     class NodeIt;
    86     class EdgeIt;
    87     class OutEdgeIt;
    88     class InEdgeIt;
    89    
    90     // Create map registries.
    91     CREATE_MAP_REGISTRIES;
    92     // Create node and edge maps.
    93     CREATE_MAPS(ArrayMap);
    9491   
    9592  public:
    9693
    97     SmartGraph() : nodes(), edges() { }
    98     SmartGraph(const SmartGraph &_g) : nodes(_g.nodes), edges(_g.edges) { }
     94    SmartGraphBase() : nodes(), edges() { }
     95    SmartGraphBase(const SmartGraphBase &_g) : nodes(_g.nodes), edges(_g.edges) { }
    9996   
    10097    ///Number of nodes.
     
    116113    Node tail(Edge e) const { return edges[e.n].tail; }
    117114    Node head(Edge e) const { return edges[e.n].head; }
    118 
    119     NodeIt& first(NodeIt& v) const {
    120       v=NodeIt(*this); return v; }
    121     EdgeIt& first(EdgeIt& e) const {
    122       e=EdgeIt(*this); return e; }
    123     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    124       e=OutEdgeIt(*this,v); return e; }
    125     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    126       e=InEdgeIt(*this,v); return e; }
    127115
    128116    /// Node ID.
     
    148136      Node n; n.n=nodes.size();
    149137      nodes.push_back(NodeT()); //FIXME: Hmmm...
    150 
    151      
    152       node_maps.add(n);
    153138      return n;
    154139    }
     
    160145      edges[e.n].next_in=nodes[v.n].first_in;
    161146      nodes[u.n].first_out=nodes[v.n].first_in=e.n;
    162 
    163       edge_maps.add(e);
    164147
    165148      return e;
     
    183166   
    184167    void clear() {
    185       edge_maps.clear();
    186168      edges.clear();
    187       node_maps.clear();
    188169      nodes.clear();
    189170    }
    190171
     172
    191173    class Node {
    192       friend class SmartGraph;
    193       template <typename T> friend class NodeMap;
    194      
    195       friend class Edge;
    196       friend class OutEdgeIt;
    197       friend class InEdgeIt;
    198       friend class SymEdge;
     174      friend class SmartGraphBase;
    199175
    200176    protected:
    201177      int n;
    202       friend int SmartGraph::id(Node v);
    203178      Node(int nn) {n=nn;}
    204179    public:
     
    208183      bool operator!=(const Node i) const {return n!=i.n;}
    209184      bool operator<(const Node i) const {return n<i.n;}
    210       //      ///Validity check
    211       //      operator bool() { return n!=-1; }
    212     };
    213    
    214     class NodeIt : public Node {
    215       const SmartGraph *G;
    216       friend class SmartGraph;
    217     public:
    218       NodeIt() : Node() { }
    219       NodeIt(const SmartGraph& _G,Node n) : Node(n), G(&_G) { }
    220       NodeIt(Invalid i) : Node(i) { }
    221       NodeIt(const SmartGraph& _G) : Node(_G.nodes.size()?0:-1), G(&_G) { }
    222       NodeIt &operator++() {
    223         n=(n+2)%(G->nodes.size()+1)-1;
    224         return *this;
    225       }
    226 //       ///Validity check
    227 //       operator bool() { return Node::operator bool(); }     
    228     };
     185    };
     186   
    229187
    230188    class Edge {
    231       friend class SmartGraph;
    232       template <typename T> friend class EdgeMap;
    233 
    234       friend class SymSmartGraph;
    235      
    236       friend class Node;
    237       friend class NodeIt;
     189      friend class SmartGraphBase;
     190
    238191    protected:
    239192      int n;
    240       friend int SmartGraph::id(Edge e);
    241193      Edge(int nn) {n=nn;}
    242194    public:
    243       /// An Edge with id \c n.
    244 
    245195      Edge() { }
    246196      Edge (Invalid) { n=-1; }
     
    248198      bool operator!=(const Edge i) const {return n!=i.n;}
    249199      bool operator<(const Edge i) const {return n<i.n;}
    250 //       ///Validity check
    251 //       operator bool() { return n!=-1; }
    252 
    253       ///Set the edge to that have ID \c ID.
    254       void setToId(int id) { n=id; }
    255    };
    256    
    257     class EdgeIt : public Edge {
    258       const SmartGraph *G;
    259       friend class SmartGraph;
    260     public:
    261       EdgeIt(const SmartGraph& _G) : Edge(_G.edges.size()-1), G(&_G) { }
    262       EdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    263       EdgeIt (Invalid i) : Edge(i) { }
    264       EdgeIt() : Edge() { }
    265       EdgeIt &operator++() { --n; return *this; }
    266 //       ///Validity check
    267 //       operator bool() { return Edge::operator bool(); }     
    268     };
    269    
    270     class OutEdgeIt : public Edge {
    271       const SmartGraph *G;
    272       friend class SmartGraph;
    273     public:
    274       OutEdgeIt() : Edge() { }
    275       OutEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    276       OutEdgeIt (Invalid i) : Edge(i) { }
    277 
    278       OutEdgeIt(const SmartGraph& _G,const Node v)
    279         : Edge(_G.nodes[v.n].first_out), G(&_G) {}
    280       OutEdgeIt &operator++() { n=G->edges[n].next_out; return *this; }
    281 //       ///Validity check
    282 //       operator bool() { return Edge::operator bool(); }     
    283     };
    284    
    285     class InEdgeIt : public Edge {
    286       const SmartGraph *G;
    287       friend class SmartGraph;
    288     public:
    289       InEdgeIt() : Edge() { }
    290       InEdgeIt(const SmartGraph& _G, Edge e) : Edge(e), G(&_G) { }
    291       InEdgeIt (Invalid i) : Edge(i) { }
    292       InEdgeIt(const SmartGraph& _G,Node v)
    293         : Edge(_G.nodes[v.n].first_in), G(&_G) { }
    294       InEdgeIt &operator++() { n=G->edges[n].next_in; return *this; }
    295 //       ///Validity check
    296 //       operator bool() { return Edge::operator bool(); }     
    297     };
     200    };
     201
     202    void first(Node& node) const {
     203      node.n = nodes.size() - 1;
     204    }
     205
     206    static void next(Node& node) {
     207      --node.n;
     208    }
     209
     210    void first(Edge& edge) const {
     211      edge.n = edges.size() - 1;
     212    }
     213
     214    static void next(Edge& edge) {
     215      --edge.n;
     216    }
     217
     218    void firstOut(Edge& edge, const Node& node) const {
     219      edge.n = nodes[node.n].first_out;
     220    }
     221
     222    void nextOut(Edge& edge) const {
     223      edge.n = edges[edge.n].next_out;
     224    }
     225
     226    void firstIn(Edge& edge, const Node& node) const {
     227      edge.n = nodes[node.n].first_in;
     228    }
     229   
     230    void nextIn(Edge& edge) const {
     231      edge.n = edges[edge.n].next_in;
     232    }
    298233
    299234  };
    300235
    301 
    302 
    303   class SymSmartGraph : public SmartGraph {
    304     typedef SmartGraph Parent;
    305   public:
    306 
    307     typedef SymSmartGraph Graph;
    308 
    309     typedef SmartGraph::Node Node;
    310     typedef SmartGraph::NodeIt NodeIt;
    311 
    312     class SymEdge;
    313     class SymEdgeIt;
    314 
    315     class Edge;
    316     class EdgeIt;
    317     class OutEdgeIt;
    318     class InEdgeIt;
    319 
    320     template <typename Value>
    321     class NodeMap : public Parent::NodeMap<Value> {     
    322     public:
    323       NodeMap(const SymSmartGraph& g)
    324         : SymSmartGraph::Parent::NodeMap<Value>(g) {}
    325       NodeMap(const SymSmartGraph& g, Value v)
    326         : SymSmartGraph::Parent::NodeMap<Value>(g, v) {}
    327       template<typename TT>
    328       NodeMap(const NodeMap<TT>& copy)
    329         : SymSmartGraph::Parent::NodeMap<Value>(copy) { }           
    330     };
    331 
    332     template <typename Value>
    333     class SymEdgeMap : public Parent::EdgeMap<Value> {
    334     public:
    335       typedef SymEdge KeyType;
    336 
    337       SymEdgeMap(const SymSmartGraph& g)
    338         : SymSmartGraph::Parent::EdgeMap<Value>(g) {}
    339       SymEdgeMap(const SymSmartGraph& g, Value v)
    340         : SymSmartGraph::Parent::EdgeMap<Value>(g, v) {}
    341       template<typename TT>
    342       SymEdgeMap(const SymEdgeMap<TT>& copy)
    343         : SymSmartGraph::Parent::EdgeMap<Value>(copy) { }
    344      
    345     };
    346 
    347     // Create edge map registry.
    348     CREATE_EDGE_MAP_REGISTRY;
    349     // Create edge maps.
    350     CREATE_EDGE_MAP(ArrayMap);
    351 
    352     class Edge {
    353       friend class SymSmartGraph;
    354       friend class SymSmartGraph::EdgeIt;
    355       friend class SymSmartGraph::OutEdgeIt;
    356       friend class SymSmartGraph::InEdgeIt;
    357      
    358     protected:
    359       int id;
    360 
    361       Edge(int pid) { id = pid; }
    362 
    363     public:
    364       /// An Edge with id \c n.
    365 
    366       Edge() { }
    367       Edge (Invalid) { id = -1; }
    368 
    369       operator SymEdge(){ return SymEdge(id >> 1);}
    370      
    371       bool operator==(const Edge i) const {return id == i.id;}
    372       bool operator!=(const Edge i) const {return id != i.id;}
    373       bool operator<(const Edge i) const {return id < i.id;}
    374       //      ///Validity check
    375       //      operator bool() { return n!=-1; }
    376     };
    377 
    378     class SymEdge : public SmartGraph::Edge {
    379       friend class SymSmartGraph;
    380       friend class SymSmartGraph::Edge;
    381       typedef SmartGraph::Edge Parent;
    382 
    383     protected:     
    384       SymEdge(int pid) : Parent(pid) {}
    385     public:
    386 
    387       SymEdge() { }
    388       SymEdge(const SmartGraph::Edge& i) : Parent(i) {}
    389       SymEdge (Invalid) : Parent(INVALID) {}
    390 
    391     };
    392 
    393     class OutEdgeIt {
    394       Parent::OutEdgeIt out;
    395       Parent::InEdgeIt in;     
    396     public:
    397       OutEdgeIt() {}
    398       OutEdgeIt(const SymSmartGraph& g, Edge e) {
    399         if ((e.id & 1) == 0) { 
    400           out = Parent::OutEdgeIt(g, SymEdge(e));
    401           in = Parent::InEdgeIt(g, g.tail(e));
    402         } else {
    403           out = Parent::OutEdgeIt(INVALID);
    404           in = Parent::InEdgeIt(g, SymEdge(e));
    405         }
    406       }
    407       OutEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    408 
    409       OutEdgeIt(const SymSmartGraph& g, const Node v)
    410         : out(g, v), in(g, v) {}
    411       OutEdgeIt &operator++() {
    412         if (out != INVALID) {
    413           ++out;
    414         } else {
    415           ++in;
    416         }
    417         return *this;
    418       }
    419 
    420       operator Edge() const {
    421         if (out == INVALID && in == INVALID) return INVALID;
    422         return out != INVALID ? forward(out) : backward(in);
    423       }
    424 
    425       bool operator==(const Edge i) const {return Edge(*this) == i;}
    426       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    427       bool operator<(const Edge i) const {return Edge(*this) < i;}
    428     };
    429 
    430     class InEdgeIt {
    431       Parent::OutEdgeIt out;
    432       Parent::InEdgeIt in;     
    433     public:
    434       InEdgeIt() {}
    435       InEdgeIt(const SymSmartGraph& g, Edge e) {
    436         if ((e.id & 1) == 0) { 
    437           out = Parent::OutEdgeIt(g, SymEdge(e));
    438           in = Parent::InEdgeIt(g, g.tail(e));
    439         } else {
    440           out = Parent::OutEdgeIt(INVALID);
    441           in = Parent::InEdgeIt(g, SymEdge(e));
    442         }
    443       }
    444       InEdgeIt (Invalid i) : out(INVALID), in(INVALID) { }
    445 
    446       InEdgeIt(const SymSmartGraph& g, const Node v)
    447         : out(g, v), in(g, v) {}
    448 
    449       InEdgeIt &operator++() {
    450         if (out != INVALID) {
    451           ++out;
    452         } else {
    453           ++in;
    454         }
    455         return *this;
    456       }
    457 
    458       operator Edge() const {
    459         if (out == INVALID && in == INVALID) return INVALID;
    460         return out != INVALID ? backward(out) : forward(in);
    461       }
    462 
    463       bool operator==(const Edge i) const {return Edge(*this) == i;}
    464       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    465       bool operator<(const Edge i) const {return Edge(*this) < i;}
    466     };
    467 
    468     class SymEdgeIt : public Parent::EdgeIt {
    469 
    470     public:
    471       SymEdgeIt() {}
    472 
    473       SymEdgeIt(const SymSmartGraph& g)
    474         : SymSmartGraph::Parent::EdgeIt(g) {}
    475 
    476       SymEdgeIt(const SymSmartGraph& g, SymEdge e)
    477         : SymSmartGraph::Parent::EdgeIt(g, e) {}
    478 
    479       SymEdgeIt(Invalid i)
    480         : SymSmartGraph::Parent::EdgeIt(INVALID) {}
    481 
    482       SymEdgeIt& operator++() {
    483         SymSmartGraph::Parent::EdgeIt::operator++();
    484         return *this;
    485       }
    486 
    487       operator SymEdge() const {
    488         return SymEdge
    489           (static_cast<const SymSmartGraph::Parent::EdgeIt&>(*this));
    490       }
    491       bool operator==(const SymEdge i) const {return SymEdge(*this) == i;}
    492       bool operator!=(const SymEdge i) const {return SymEdge(*this) != i;}
    493       bool operator<(const SymEdge i) const {return SymEdge(*this) < i;}
    494     };
    495 
    496     class EdgeIt {
    497       SymEdgeIt it;
    498       bool fw;
    499     public:
    500       EdgeIt(const SymSmartGraph& g) : it(g), fw(true) {}
    501       EdgeIt (Invalid i) : it(i) { }
    502       EdgeIt(const SymSmartGraph& g, Edge e)
    503         : it(g, SymEdge(e)), fw(id(e) & 1 == 0) { }
    504       EdgeIt() { }
    505       EdgeIt& operator++() {
    506         fw = !fw;
    507         if (fw) ++it;
    508         return *this;
    509       }
    510       operator Edge() const {
    511         if (it == INVALID) return INVALID;
    512         return fw ? forward(it) : backward(it);
    513       }
    514       bool operator==(const Edge i) const {return Edge(*this) == i;}
    515       bool operator!=(const Edge i) const {return Edge(*this) != i;}
    516       bool operator<(const Edge i) const {return Edge(*this) < i;}
    517 
    518     };
    519 
    520     ///Number of nodes.
    521     int nodeNum() const { return Parent::nodeNum(); }
    522     ///Number of edges.
    523     int edgeNum() const { return 2*Parent::edgeNum(); }
    524     ///Number of symmetric edges.
    525     int symEdgeNum() const { return Parent::edgeNum(); }
    526 
    527     /// Maximum node ID.
    528    
    529     /// Maximum node ID.
    530     ///\sa id(Node)
    531     int maxNodeId() const { return Parent::maxNodeId(); }
    532     /// Maximum edge ID.
    533    
    534     /// Maximum edge ID.
    535     ///\sa id(Edge)
    536     int maxEdgeId() const { return 2*Parent::maxEdgeId(); }
    537     /// Maximum symmetric edge ID.
    538    
    539     /// Maximum symmetric edge ID.
    540     ///\sa id(SymEdge)
    541     int maxSymEdgeId() const { return Parent::maxEdgeId(); }
    542 
    543 
    544     Node tail(Edge e) const {
    545       return (e.id & 1) == 0 ?
    546         Parent::tail(SymEdge(e)) : Parent::head(SymEdge(e));
    547     }
    548 
    549     Node head(Edge e) const {
    550       return (e.id & 1) == 0 ?
    551         Parent::head(SymEdge(e)) : Parent::tail(SymEdge(e));
    552     }
    553 
    554     Node tail(SymEdge e) const {
    555       return Parent::tail(e);
    556     }
    557 
    558     Node head(SymEdge e) const {
    559       return Parent::head(e);
    560     }
    561 
    562     NodeIt& first(NodeIt& v) const {
    563       v=NodeIt(*this); return v; }
    564     EdgeIt& first(EdgeIt& e) const {
    565       e=EdgeIt(*this); return e; }
    566     SymEdgeIt& first(SymEdgeIt& e) const {
    567       e=SymEdgeIt(*this); return e; }
    568     OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
    569       e=OutEdgeIt(*this,v); return e; }
    570     InEdgeIt& first(InEdgeIt& e, const Node v) const {
    571       e=InEdgeIt(*this,v); return e; }
    572 
    573     /// Node ID.
    574    
    575     /// The ID of a valid Node is a nonnegative integer not greater than
    576     /// \ref maxNodeId(). The range of the ID's is not surely continuous
    577     /// and the greatest node ID can be actually less then \ref maxNodeId().
    578     ///
    579     /// The ID of the \ref INVALID node is -1.
    580     ///\return The ID of the node \c v.
    581     static int id(Node v) { return Parent::id(v); }
    582     /// Edge ID.
    583    
    584     /// The ID of a valid Edge is a nonnegative integer not greater than
    585     /// \ref maxEdgeId(). The range of the ID's is not surely continuous
    586     /// and the greatest edge ID can be actually less then \ref maxEdgeId().
    587     ///
    588     /// The ID of the \ref INVALID edge is -1.
    589     ///\return The ID of the edge \c e.
    590     static int id(Edge e) { return e.id; }
    591 
    592     /// The ID of a valid SymEdge is a nonnegative integer not greater than
    593     /// \ref maxSymEdgeId(). The range of the ID's is not surely continuous
    594     /// and the greatest edge ID can be actually less then \ref maxSymEdgeId().
    595     ///
    596     /// The ID of the \ref INVALID symmetric edge is -1.
    597     ///\return The ID of the edge \c e.
    598     static int id(SymEdge e) { return Parent::id(e); }
    599 
    600     /// Adds a new node to the graph.
    601 
    602     /// \warning It adds the new node to the front of the list.
    603     /// (i.e. the lastly added node becomes the first.)
    604     Node addNode() {
    605       return Parent::addNode();
    606     }
    607    
    608     SymEdge addEdge(Node u, Node v) {
    609       SymEdge se = Parent::addEdge(u, v);
    610       edge_maps.add(forward(se));
    611       edge_maps.add(backward(se));
    612       return se;
    613     }
    614    
    615     /// Finds an edge between two nodes.
    616 
    617     /// Finds an edge from node \c u to node \c v.
    618     ///
    619     /// If \c prev is \ref INVALID (this is the default value), then
    620     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    621     /// the next edge from \c u to \c v after \c prev.
    622     /// \return The found edge or INVALID if there is no such an edge.
    623     Edge findEdge(Node u, Node v, Edge prev = INVALID)
    624     {     
    625       if (prev == INVALID || id(prev) & 1 == 0) {
    626         SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    627         if (se != INVALID) return forward(se);
    628       } else {
    629         SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    630         if (se != INVALID) return backward(se);
    631       }
    632       return INVALID;
    633     }
    634 
    635 //     /// Finds an symmetric edge between two nodes.
    636 
    637 //     /// Finds an symmetric edge from node \c u to node \c v.
    638 //     ///
    639 //     /// If \c prev is \ref INVALID (this is the default value), then
    640 //     /// It finds the first edge from \c u to \c v. Otherwise it looks for
    641 //     /// the next edge from \c u to \c v after \c prev.
    642 //     /// \return The found edge or INVALID if there is no such an edge.
    643 
    644 //     SymEdge findEdge(Node u, Node v, SymEdge prev = INVALID)
    645 //     {     
    646 //       if (prev == INVALID || id(prev) & 1 == 0) {
    647 //      SymEdge se = Parent::findEdge(u, v, SymEdge(prev));
    648 //      if (se != INVALID) return se;
    649 //       } else {
    650 //      SymEdge se = Parent::findEdge(v, u, SymEdge(prev));
    651 //      if (se != INVALID) return se;   
    652 //       }
    653 //       return INVALID;
    654 //     }
    655    
    656   public:
    657 
    658     void clear() {
    659       edge_maps.clear();
    660       Parent::clear();
    661     }
    662 
    663     static Edge opposite(Edge e) {
    664       return Edge(id(e) ^ 1);
    665     }
    666 
    667     static Edge forward(SymEdge e) {
    668       return Edge(id(e) << 1);
    669     }
    670 
    671     static Edge backward(SymEdge e) {
    672       return Edge((id(e) << 1) | 1);
    673     }
    674 
    675   };
    676   ///Graph for bidirectional edges.
    677 
    678   ///The purpose of this graph structure is to handle graphs
    679   ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
    680   ///of oppositely directed edges.
    681   ///There is a new edge map type called
    682   ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap"
    683   ///that complements this
    684   ///feature by
    685   ///storing shared values for the edge pairs. The usual
    686   ///\ref Graph::EdgeMap "EdgeMap"
    687   ///can be used
    688   ///as well.
    689   ///
    690   ///The oppositely directed edge can also be obtained easily
    691   ///using \ref opposite.
    692   ///\warning It shares the similarity with \ref SmartGraph that
    693   ///it is not possible to delete edges or nodes from the graph.
    694   //\sa SmartGraph.
    695 
    696   /*  class SymSmartGraph : public SmartGraph
    697   {
    698   public:
    699     typedef SymSmartGraph Graph;
    700 
    701     // Create symmetric map registry.
    702     CREATE_SYM_EDGE_MAP_REGISTRY;
    703     // Create symmetric edge map.
    704     CREATE_SYM_EDGE_MAP(ArrayMap);
    705 
    706 
    707     SymSmartGraph() : SmartGraph() { }
    708     SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { }
    709     ///Adds a pair of oppositely directed edges to the graph.
    710     Edge addEdge(Node u, Node v)
    711     {
    712       Edge e = SmartGraph::addEdge(u,v);
    713       Edge f = SmartGraph::addEdge(v,u);
    714       sym_edge_maps.add(e);
    715       sym_edge_maps.add(f);
    716       return e;
    717     }
    718 
    719     ///The oppositely directed edge.
    720 
    721     ///Returns the oppositely directed
    722     ///pair of the edge \c e.
    723     static Edge opposite(Edge e)
    724     {
    725       Edge f;
    726       f.n = e.n - 2*(e.n%2) + 1;
    727       return f;
    728     }
    729    
    730 
    731     };*/
    732  
     236  typedef AlterableGraphExtender<SmartGraphBase> AlterableSmartGraphBase;
     237  typedef IterableGraphExtender<AlterableSmartGraphBase> IterableSmartGraphBase;
     238  typedef IdMappableGraphExtender<IterableSmartGraphBase> IdMappableSmartGraphBase;
     239  typedef DefaultMappableGraphExtender<IdMappableSmartGraphBase> MappableSmartGraphBase;
     240  typedef ExtendableGraphExtender<MappableSmartGraphBase> ExtendableSmartGraphBase;
     241  typedef ClearableGraphExtender<ExtendableSmartGraphBase> ClearableSmartGraphBase;
     242
     243  typedef ClearableSmartGraphBase SmartGraph;
     244
     245
     246  template <>
     247  int countNodes<SmartGraph>(const SmartGraph& graph) {
     248    return graph.nodeNum();
     249  }
     250
     251  template <>
     252  int countEdges<SmartGraph>(const SmartGraph& graph) {
     253    return graph.edgeNum();
     254  }
     255
    733256  /// @} 
    734257} //namespace lemon
  • src/lemon/suurballe.h

    r941 r946  
    126126      for (int j=0; j<i; ++j){
    127127        Node n=s;
    128         OutEdgeIt e;
    129128
    130129        while (n!=t){
    131130
    132 
    133           G.first(e,n);
     131          OutEdgeIt e(G, n);
    134132         
    135133          while (!reversed[e]){
  • src/lemon/vector_map.h

    r937 r946  
    1919
    2020#include <vector>
    21 
    22 #include <lemon/map_iterator.h>
    23 #include <lemon/map_bits.h>
     21#include <algorithm>
     22
     23#include <lemon/alteration_observer_registry.h>
    2424
    2525///\ingroup graphmaps
     
    3232  /// @{
    3333 
    34   /** The VectorMap template class is graph map structure what
    35    *  automatically updates the map when a key is added to or erased from
    36    *  the map. This map factory uses the allocators to implement
    37    *  the container functionality. This map factory
    38    *  uses the std::vector to implement the container function.
    39    *
    40    *  \param MapRegistry The MapRegistry that the maps will belong to.
    41    *  \param Value The value type of the map.
    42    *
    43    *  \author Balazs Dezso
    44    */
    45        
    46   template <typename MapRegistry, typename Value>
    47   class VectorMap : public MapRegistry::MapBase {
    48     template <typename MR, typename T> friend class VectorMap;
     34  /// The VectorMap template class is graph map structure what
     35  /// automatically updates the map when a key is added to or erased from
     36  /// the map. This map factory uses the allocators to implement
     37  /// the container functionality. This map factory
     38  /// uses the std::vector to implement the container function.
     39  ///
     40  /// \param Registry The AlterationObserverRegistry that will notify this map.
     41  /// \param IdMap The IdMap type of the graph items.
     42  /// \param Value The value type of the map.
     43  ///
     44  /// \author Balazs Dezso
     45       
     46
     47  template <typename _Graph,
     48            typename _Item,
     49            typename _IdMap,
     50            typename _Value>
     51  class VectorMap : public AlterationObserverRegistry<_Item>::ObserverBase {
    4952  public:
    5053               
    51     /// The graph type of the maps.
    52     typedef typename MapRegistry::Graph Graph;
    53     /// The key type of the maps.
    54     typedef typename MapRegistry::KeyType KeyType;
    55     /// The iterator to iterate on the keys.
    56     typedef typename MapRegistry::KeyIt KeyIt;
     54    /// The graph type of the map.
     55    typedef _Graph Graph;
     56    /// The key type of the map.
     57    typedef _Item KeyType;
     58    /// The id map type of the map.
     59    typedef _IdMap IdMap;
     60    /// The registry type of the map.
     61    typedef AlterationObserverRegistry<_Item> Registry;
     62    /// The value type of the map.
     63    typedef _Value Value;
    5764
    5865    /// The map type.
    5966    typedef VectorMap Map;
    60     /// The MapBase of the Map which implements the core regisitry function.
    61     typedef typename MapRegistry::MapBase MapBase;
     67    /// The base class of the map.
     68    typedef typename Registry::ObserverBase Parent;
    6269
    6370  private:
     
    6774
    6875  public:
    69 
    7076
    7177    /// The value type of the map.
     
    8389    typedef typename Container::const_pointer ConstPointerType;
    8490
    85     /// Constructor to attach the new map into a registry.
    86 
    87     /** Constructor to attach the new map into a registry.
    88      *  It adds all the nodes or edges of the graph to the map.
     91    /// Constructor to attach the new map into the registry.
     92
     93    /// It construates a map and attachs it into the registry.
     94    /// It adds all the items of the graph to the map.
     95     
     96    VectorMap(const Graph& _g, Registry& _r) : graph(&_g) {
     97      attach(_r);
     98      build();
     99    }
     100
     101    /// Constructor uses given value to initialize the map.
     102
     103    /// It construates a map uses a given value to initialize the map.
     104    /// It adds all the items of the graph to the map.
     105     
     106    VectorMap(const Graph& g, Registry& r, const Value& v) : graph(&g) {
     107      attach(r);
     108      container.resize(IdMap(*graph).maxId() + 1, v);
     109    }
     110
     111    VectorMap(const VectorMap& copy) : graph(copy.getGraph()) {
     112      if (copy.attached()) {
     113        attach(*copy.getRegistry());
     114        container = copy.container;
     115      }
     116    }
     117
     118
     119    /** Assign operator to copy a map of the same map type.
    89120     */
    90     VectorMap(const Graph& g, MapRegistry& r)
    91       : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1) {}
    92 
    93     /// Constructor uses given value to initialize the map.
    94 
    95     /** Constructor uses given value to initialize the map.
    96      *  It adds all the nodes or edges of the graph to the map.
    97      */
    98     VectorMap(const Graph& g, MapRegistry& r, const Value& v)
    99       : MapBase(g, r), container(KeyInfo<Graph, KeyIt>::maxId(g)+1, v) {}
    100 
    101     /// Assign operator to copy a map of an other map type.
    102 
    103     /** Assign operator to copy a map of an other map type.
    104      *  This map's value type must be assignable by the other
    105      *  map type's value type.
    106      */
    107     template <typename TT>
    108     VectorMap(const VectorMap<MapRegistry, TT>& c)
    109       : MapBase(c), container(c.container.size()) {
    110       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    111         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    112         container[id] = c.container[id];
    113       }
    114     }
    115 
    116     /// Assign operator to copy a map of an other map type.
    117 
    118     /** Assign operator to copy a map of an other map type.
    119      *  This map's value type must be assignable by the other
    120      *  map type's value type.
    121      */
    122     template <typename TT>
    123     VectorMap& operator=(const VectorMap<MapRegistry, TT>& c) {
    124       if (MapBase::getGraph() != c.getGraph()) {
    125         MapBase::operator=(c);
    126         container.resize(c.container.size());
    127       }
    128       for (KeyIt it(*MapBase::getGraph()); it != INVALID; ++it) {
    129         int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), it);
    130         container[id] = c.container[id];
    131       }
     121    VectorMap& operator=(const VectorMap& copy) {
     122      if (&copy == this) return *this;
     123     
     124      if (graph != copy.graph) {
     125        if (attached()) {
     126          detach();
     127        }
     128        if (copy.attached()) {
     129          attach(*copy.getRegistry());
     130        }
     131      }
     132      container = copy.container;
     133
    132134      return *this;
    133135    }
    134136
     137
     138    virtual ~VectorMap() {
     139      if (attached()) {
     140        detach();
     141      }
     142    }
     143
     144    const Graph* getGraph() const {
     145      return graph;
     146    }
     147
    135148    /// The subcript operator.
    136149
    137     /**
    138      * The subscript operator. The map can be subscripted by the
    139      * actual keys of the graph.
    140      */
     150    /// The subscript operator. The map can be subscripted by the
     151    /// actual items of the graph.
     152     
    141153    ReferenceType operator[](const KeyType& key) {
    142       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    143       return container[id];
     154      return container[IdMap(*graph)[key]];
    144155    }
    145156               
    146157    /// The const subcript operator.
    147158
    148     /**
    149      * The const subscript operator. The map can be subscripted by the
    150      * actual keys of the graph.
    151      */
     159    /// The const subscript operator. The map can be subscripted by the
     160    /// actual items of the graph.
     161     
    152162    ConstReferenceType operator[](const KeyType& key) const {
    153       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    154       return container[id];
    155     }
    156 
    157     ///Setter function of the map.
    158 
    159     /** Setter function of the map. Equivalent with map[key] = val.
    160      *  This is a compatibility feature with the not dereferable maps.
    161      */
    162     void set(const KeyType& key, const ValueType& val) {
    163       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
    164       container[id] = val;
    165     }
     163      return container[IdMap(*graph)[key]];
     164    }
     165
     166
     167    /// The setter function of the map.
     168
     169    /// It the same as operator[](key) = value expression.
     170    ///
     171     
     172    void set(const KeyType& key, const ValueType& value) {
     173      (*this)[key] = value;
     174    }
     175
    166176    /// Adds a new key to the map.
    167177               
    168     /** Adds a new key to the map. It called by the map registry
    169      *  and it overrides the \ref MapRegistry::MapBase MapBase's
    170      *  add() member function.
    171      */
     178    /// It adds a new key to the map. It called by the observer registry
     179    /// and it overrides the add() member function of the observer base.
     180     
    172181    void add(const KeyType& key) {
    173       int id = KeyInfo<Graph, KeyIt>::id(*MapBase::getGraph(), key);
     182      int id = IdMap(*graph)[key];
    174183      if (id >= (int)container.size()) {
    175184        container.resize(id + 1);
     
    179188    /// Erases a key from the map.
    180189               
    181     /** Erase a key from the map. It called by the map registry
    182      *  and it overrides the \ref MapRegistry::MapBase MapBase's
    183      *  erase() member function.
    184      */
     190    /// Erase a key from the map. It called by the observer registry
     191    /// and it overrides the erase() member function of the observer base.     
    185192    void erase(const KeyType& key) {}
    186193
    187     /// Makes empty the map.
    188 
    189     /** Makes empty the map. It called by the map registry
    190      *  and it overrides the \ref MapRegistry::MapBase MapBase's
    191      *  clear() member function.
    192      */
    193 
     194    /// Buildes the map.
     195               
     196    /// It buildes the map. It called by the observer registry
     197    /// and it overrides the build() member function of the observer base.
     198
     199    void build() {
     200      container.resize(IdMap(*graph).maxId() + 1);
     201    }
     202
     203    /// Clear the map.
     204
     205    /// It erase all items from the map. It called by the observer registry
     206    /// and it overrides the clear() member function of the observer base.     
    194207    void clear() {
    195208      container.clear();
    196209    }
    197210
    198     /// The stl compatible pair iterator of the map.
    199     typedef MapIterator<VectorMap> Iterator;
    200     /// The stl compatible const pair iterator of the map.
    201     typedef MapConstIterator<VectorMap> ConstIterator;
    202 
    203     /** Returns the begin iterator of the map.
    204      */
    205     Iterator begin() {
    206       return Iterator(*this, KeyIt(*MapBase::getGraph()));
    207     }
    208 
    209     /** Returns the end iterator of the map.
    210      */
    211     Iterator end() {
    212       return Iterator(*this, INVALID);
    213     }
    214 
    215     /** Returns the begin ConstIterator of the map.
    216      */
    217     ConstIterator begin() const {
    218       return ConstIterator(*this, KeyIt(*MapBase::getGraph()));
    219     }
    220 
    221     /** Returns the end const_iterator of the map.
    222      */
    223     ConstIterator end() const {
    224       return ConstIterator(*this, INVALID);
    225     }
    226 
    227     /// The KeySet of the Map.
    228     typedef MapConstKeySet<VectorMap> ConstKeySet;
    229 
    230     /// KeySet getter function.
    231     ConstKeySet keySet() const {
    232       return ConstKeySet(*this);
    233     }
    234 
    235     /// The ConstValueSet of the Map.
    236     typedef MapConstValueSet<VectorMap> ConstValueSet;
    237 
    238     /// ConstValueSet getter function.
    239     ConstValueSet valueSet() const {
    240       return ConstValueSet(*this);
    241     }
    242 
    243     /// The ValueSet of the Map.
    244     typedef MapValueSet<VectorMap> ValueSet;
    245 
    246     /// ValueSet getter function.
    247     ValueSet valueSet() {
    248       return ValueSet(*this);
    249     }
    250 
    251 
    252211  private:
    253212               
    254213    Container container;
    255 
     214    const Graph *graph;
     215
     216  };
     217
     218
     219  template <typename _Base>
     220  class VectorMappableGraphExtender : public _Base {
    256221  public:
    257     // STL  compatibility typedefs.
    258     typedef Iterator iterator;
    259     typedef ConstIterator const_iterator;
    260     typedef typename Iterator::PairValueType value_type;
    261     typedef typename Iterator::KeyType key_type;
    262     typedef typename Iterator::ValueType data_type;
    263     typedef typename Iterator::PairReferenceType reference;
    264     typedef typename Iterator::PairPointerType pointer;
    265     typedef typename ConstIterator::PairReferenceType const_reference;
    266     typedef typename ConstIterator::PairPointerType const_pointer;
    267     typedef int difference_type;               
     222
     223    typedef VectorMappableGraphExtender<_Base> Graph;
     224    typedef _Base Parent;
     225
     226    typedef typename Parent::Node Node;
     227    typedef typename Parent::NodeIt NodeIt;
     228    typedef typename Parent::NodeIdMap NodeIdMap;
     229    typedef typename Parent::NodeObserverRegistry NodeObserverRegistry;
     230
     231    typedef typename Parent::Edge Edge;
     232    typedef typename Parent::EdgeIt EdgeIt;
     233    typedef typename Parent::EdgeIdMap EdgeIdMap;
     234    typedef typename Parent::EdgeObserverRegistry EdgeObserverRegistry;
     235
     236   
     237
     238    template <typename _Value>
     239    class NodeMap : public VectorMap<Graph, Node, NodeIdMap, _Value> {
     240    public:
     241      typedef VectorMappableGraphExtender<_Base> Graph;
     242
     243      typedef typename Graph::Node Node;
     244      typedef typename Graph::NodeIdMap NodeIdMap;
     245
     246      typedef VectorMap<Graph, Node, NodeIdMap, _Value> Parent;
     247
     248      typedef typename Parent::Graph Graph;
     249      typedef typename Parent::Value Value;
     250
     251      NodeMap(const Graph& g)
     252        : Parent(g, g.getNodeObserverRegistry()) {}
     253      NodeMap(const Graph& g, const Value& v)
     254        : Parent(g, g.getNodeObserverRegistry(), v) {}
     255
     256    };
     257
     258    template <typename _Value>
     259    class EdgeMap : public VectorMap<Graph, Edge, EdgeIdMap, _Value> {
     260    public:
     261      typedef VectorMappableGraphExtender<_Base> Graph;
     262
     263      typedef typename Graph::Edge Edge;
     264      typedef typename Graph::EdgeIdMap EdgeIdMap;
     265
     266      typedef VectorMap<Graph, Edge, EdgeIdMap, _Value> Parent;
     267
     268      typedef typename Parent::Graph Graph;
     269      typedef typename Parent::Value Value;
     270
     271      EdgeMap(const Graph& g)
     272        : Parent(g, g.getEdgeObserverRegistry()) {}
     273      EdgeMap(const Graph& g, const Value& v)
     274        : Parent(g, g.getEdgeObserverRegistry(), v) {}
     275
     276    };
     277   
    268278  };
    269279 
  • src/test/Makefile.am

    r938 r946  
    33EXTRA_DIST = preflow_graph.dim #input file for preflow_test.cc
    44
    5 noinst_HEADERS = test_tools.h graph_test.h sym_graph_test.h
     5noinst_HEADERS = \
     6        test_tools.h \
     7        graph_test.h \
     8        sym_graph_test.h \
     9        map_test.h \
     10        graph_utils_test.h
    611
    712check_PROGRAMS = \
     
    1015        dijkstra_test \
    1116        graph_test \
    12         sym_graph_test \
    13         graph_wrapper_test \
     17        graph_utils_test \
    1418        kruskal_test \
    1519        min_cost_flow_test \
     20        new_graph_test \
    1621        suurballe_test \
    1722        path_test \
     
    2126        time_measure_test \
    2227        unionfind_test \
     28        graph_wrapper_test \
    2329        xy_test
    2430
     
    3036dijkstra_test_SOURCES = dijkstra_test.cc
    3137graph_test_SOURCES = graph_test.cc
    32 sym_graph_test_SOURCES = sym_graph_test.cc
     38graph_utils_test_SOURCES = graph_utils_test.cc
    3339graph_wrapper_test_SOURCES = graph_wrapper_test.cc
    3440kruskal_test_SOURCES = kruskal_test.cc
    3541min_cost_flow_test_SOURCES = min_cost_flow_test.cc
     42new_graph_test_SOURCES = new_graph_test.cc
    3643suurballe_test_SOURCES = suurballe_test.cc
    3744path_test_SOURCES = path_test.cc
  • src/test/graph_test.cc

    r938 r946  
    1 /* -*- C++ -*-
    2  * src/test/graph_test.cc - Part of LEMON, a generic C++ optimization library
    3  *
    4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Combinatorial Optimization Research Group, EGRES).
    6  *
    7  * Permission to use, modify and distribute this software is granted
    8  * provided that this copyright notice appears in all copies. For
    9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
     1// -*- c++ -*-
    162
    17 #include<iostream>
    18 #include<lemon/smart_graph.h>
    19 #include<lemon/skeletons/graph.h>
    20 #include<lemon/list_graph.h>
    21 #include<lemon/full_graph.h>
     3#include <iostream>
     4#include <vector>
    225
    23 #include"test_tools.h"
    24 #include"graph_test.h"
     6#include <lemon/skeletons/graph.h>
     7#include <lemon/list_graph.h>
     8#include <lemon/smart_graph.h>
     9#include <lemon/full_graph.h>
    2510
    26 /**
    27 \file
    28 This test makes consistency checks of list graph structures.
     11#include "test_tools.h"
     12#include "graph_test.h"
     13#include "map_test.h"
    2914
    30 G.addNode(), G.addEdge(), G.tail(), G.head()
    31 
    32 \todo Checks for empty graphs and isolated points.
    33 conversion.
    34 */
    3515
    3616using namespace lemon;
    37 
    38 template<class Graph> void bidirPetersen(Graph &G)
    39 {
    40   typedef typename Graph::Edge Edge;
    41   typedef typename Graph::EdgeIt EdgeIt;
    42  
    43   checkGraphEdgeList(G,15);
    44  
    45   std::vector<Edge> ee;
    46  
    47   for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
    48 
    49   for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
    50     G.addEdge(G.head(*p),G.tail(*p));
    51 }
    52 
    53 template<class Graph> void checkPetersen(Graph &G)
    54 {
    55   typedef typename Graph::Node Node;
    56 
    57   typedef typename Graph::EdgeIt EdgeIt;
    58   typedef typename Graph::NodeIt NodeIt;
    59 
    60   checkGraphNodeList(G,10);
    61   checkGraphEdgeList(G,30);
    62 
    63   for(NodeIt n(G);n!=INVALID;++n) {
    64     checkGraphInEdgeList(G,n,3);
    65     checkGraphOutEdgeList(G,n,3);
    66   } 
    67 }
    68 
    69 //Compile Graph
    70 template void lemon::skeleton::checkCompileStaticGraph<skeleton::StaticGraph>
    71 (skeleton::StaticGraph &);
    72 
    73 template
    74 void lemon::skeleton::checkCompileExtendableGraph<skeleton::ExtendableGraph>
    75 (skeleton::ExtendableGraph &);
    76 
    77 template
    78 void lemon::skeleton::checkCompileErasableGraph<skeleton::ErasableGraph>
    79 (skeleton::ErasableGraph &);
    80 
    81 //Compile SmartGraph
    82 template
    83 void lemon::skeleton::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
    84 template
    85 void lemon::skeleton::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
    86 
    87 //Compile SymSmartGraph
    88 //template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
    89 //template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
    90 
    91 //Compile ListGraph
    92 template
    93 void lemon::skeleton::checkCompileExtendableGraph<ListGraph>(ListGraph &);
    94 template
    95 void lemon::skeleton::checkCompileErasableGraph<ListGraph>(ListGraph &);
    96 template
    97 void lemon::skeleton::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
     17using namespace lemon::skeleton;
    9818
    9919
    100 //Compile SymListGraph
    101 //template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
    102 //template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
    103 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
     20int main() {
     21  ///\file
     22  { // checking graph components
     23    function_requires<BaseGraphComponentConcept<BaseGraphComponent> >();
    10424
    105 //Compile FullGraph
    106 template void lemon::skeleton::checkCompileStaticGraph<FullGraph>(FullGraph &);
    107 template
    108 void lemon::skeleton::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
     25    function_requires<BaseIterableGraphComponentConcept<BaseIterableGraphComponent> >();
    10926
    110 //Compile EdgeSet <ListGraph>
    111 template void lemon::skeleton::checkCompileExtendableGraph<EdgeSet <ListGraph> >
    112 (EdgeSet <ListGraph> &);
    113 template void lemon::skeleton::checkCompileGraphEraseEdge<EdgeSet <ListGraph> >
    114 (EdgeSet <ListGraph> &);
    115 template void lemon::skeleton::checkCompileGraphFindEdge<EdgeSet <ListGraph> >
    116 (EdgeSet <ListGraph> &);
     27    function_requires<IDableGraphComponentConcept<IDableGraphComponent> >();
     28    function_requires<MaxIDableGraphComponentConcept<MaxIDableGraphComponent> >();
    11729
    118 //Compile EdgeSet <NodeSet>
    119 template void lemon::skeleton::checkCompileExtendableGraph<EdgeSet <NodeSet> >
    120 (EdgeSet <NodeSet> &);
    121 template void lemon::skeleton::checkCompileGraphEraseEdge<EdgeSet <NodeSet> >
    122 (EdgeSet <NodeSet> &);
    123 template void lemon::skeleton::checkCompileGraphFindEdge<EdgeSet <NodeSet> >
    124 (EdgeSet <NodeSet> &);
     30    function_requires<BaseExtendableGraphComponentConcept<BaseExtendableGraphComponent> >();
     31    function_requires<BaseErasableGraphComponentConcept<BaseErasableGraphComponent> >();
     32    function_requires<BaseClearableGraphComponentConcept<BaseClearableGraphComponent> >();
    12533
     34    function_requires<IterableGraphComponentConcept<IterableGraphComponent> >();
    12635
    127 int main()
    128 {
    129   {
    130     SmartGraph G;
    131     addPetersen(G);
    132     bidirPetersen(G);
    133     checkPetersen(G);
     36    function_requires<IdMappableGraphComponentConcept<IdMappableGraphComponent> >();
     37    function_requires<MappableGraphComponentConcept<MappableGraphComponent> >();
     38
     39    function_requires<ExtendableGraphComponentConcept<ExtendableGraphComponent> >();
     40    function_requires<ErasableGraphComponentConcept<ErasableGraphComponent> >();
     41    function_requires<ClearableGraphComponentConcept<ClearableGraphComponent> >();
    13442  }
    135   {
    136     ListGraph G;
    137     addPetersen(G);
    138     bidirPetersen(G);
    139     checkPetersen(G);
     43  { // checking skeleton graphs
     44    function_requires<StaticGraphConcept<StaticGraph> >();
     45    function_requires<ExtendableGraphConcept<ExtendableGraph> >();
     46    function_requires<ErasableGraphConcept<ErasableGraph> >();
    14047  }
    141   {
    142     //    SymSmartGraph G;
    143     //    addPetersen(G);
    144     //    checkPetersen(G);
     48  { // checking list graph
     49    function_requires<ErasableGraphConcept<ListGraph> >();
     50
     51    checkGraph<ListGraph>();
     52    checkGraphNodeMap<ListGraph>();
     53    checkGraphEdgeMap<ListGraph>();
    14554  }
    146   {
    147     //    SymListGraph G;
    148     //    addPetersen(G);
    149     //    checkPetersen(G);
     55  { // checking smart graph
     56    function_requires<ExtendableGraphConcept<SmartGraph> >();
     57
     58    checkGraph<SmartGraph>();
     59    checkGraphNodeMap<SmartGraph>();
     60    checkGraphEdgeMap<SmartGraph>();
    15061  }
    151 
    152   ///\file
    153   ///\todo map tests.
    154   ///\todo copy constr tests.
     62  { // checking full graph
     63    function_requires<StaticGraphConcept<FullGraph> >();
     64  }
    15565
    15666  std::cout << __FILE__ ": All tests passed.\n";
  • src/test/graph_test.h

    r938 r946  
    2222//! \ingroup misc
    2323//! \file
    24 //! \brief Some utility to test graph classes.
     24//! \brief Some utility and test cases to test graph classes.
    2525namespace lemon {
    2626
    2727  template<class Graph> void checkGraphNodeList(Graph &G, int nn)
    28     {
    29       typename Graph::NodeIt n(G);
    30       for(int i=0;i<nn;i++) {
    31         check(n!=INVALID,"Wrong Node list linking.");
    32         ++n;
    33       }
    34       check(n==INVALID,"Wrong Node list linking.");
     28  {
     29    typename Graph::NodeIt n(G);
     30    for(int i=0;i<nn;i++) {
     31      check(n!=INVALID,"Wrong Node list linking.");
     32      ++n;
    3533    }
     34    check(n==INVALID,"Wrong Node list linking.");
     35  }
    3636
    37   template<class Graph> void checkGraphEdgeList(Graph &G, int nn)
    38     {
    39       typedef typename Graph::EdgeIt EdgeIt;
     37  template<class Graph>
     38  void checkGraphEdgeList(Graph &G, int nn)
     39  {
     40    typedef typename Graph::EdgeIt EdgeIt;
    4041
    41       EdgeIt e(G);
    42       for(int i=0;i<nn;i++) {
    43         check(e!=INVALID,"Wrong Edge list linking.");
    44         ++e;
    45       }
    46       check(e==INVALID,"Wrong Edge list linking.");
     42    EdgeIt e(G);
     43    for(int i=0;i<nn;i++) {
     44      check(e!=INVALID,"Wrong Edge list linking.");
     45      ++e;
    4746    }
     47    check(e==INVALID,"Wrong Edge list linking.");
     48  }
    4849
    49   template<class Graph> void checkGraphOutEdgeList(Graph &G,
    50                                                    typename Graph::Node n,
    51                                                    int nn)
    52     {
    53       typename Graph::OutEdgeIt e(G,n);
    54       for(int i=0;i<nn;i++) {
    55         check(e!=INVALID,"Wrong OutEdge list linking.");
    56         check(n==G.tail(e), "Wrong OutEdge list linking.");
    57         ++e;
    58       }
    59       check(e==INVALID,"Wrong OutEdge list linking.");
     50  template<class Graph>
     51  void checkGraphOutEdgeList(Graph &G, typename Graph::Node n, int nn)
     52  {
     53    typename Graph::OutEdgeIt e(G,n);
     54    for(int i=0;i<nn;i++) {
     55      check(e!=INVALID,"Wrong OutEdge list linking.");
     56      check(n==G.tail(e), "Wrong OutEdge list linking.");
     57      ++e;
    6058    }
     59    check(e==INVALID,"Wrong OutEdge list linking.");
     60  }
    6161
    62   template<class Graph> void checkGraphInEdgeList(Graph &G,
    63                                                   typename Graph::Node n,
    64                                                   int nn)
    65     {
    66       typename Graph::InEdgeIt e(G,n);
    67       for(int i=0;i<nn;i++) {
    68         check(e!=INVALID,"Wrong InEdge list linking.");
    69         check(n==G.head(e), "Wrong InEdge list linking.");
    70         ++e;
    71       }
    72       check(e==INVALID,"Wrong InEdge list linking.");
     62  template<class Graph> void
     63  checkGraphInEdgeList(Graph &G, typename Graph::Node n, int nn)
     64  {
     65    typename Graph::InEdgeIt e(G,n);
     66    for(int i=0;i<nn;i++) {
     67      check(e!=INVALID,"Wrong InEdge list linking.");
     68      check(n==G.head(e), "Wrong InEdge list linking.");
     69      ++e;
    7370    }
     71    check(e==INVALID,"Wrong InEdge list linking.");
     72  }
     73
     74  template <class Graph>
     75  void checkGraph() {
     76    const int num = 5;
     77    Graph G;
     78    addPetersen(G, num);
     79    bidirGraph(G);
     80    checkBidirPetersen(G, num);
     81  }
    7482
    7583  ///\file
  • src/test/graph_wrapper_test.cc

    r938 r946  
    1616
    1717#include<iostream>
     18#include<lemon/concept_check.h>
     19
    1820#include<lemon/smart_graph.h>
    1921#include<lemon/skeletons/graph.h>
     22
    2023#include<lemon/list_graph.h>
    2124#include<lemon/full_graph.h>
     
    3336
    3437using namespace lemon;
     38using namespace lemon::skeleton;
    3539
    3640
    3741typedef SmartGraph Graph;
    3842
    39 //Compile GraphWrapper
    40 typedef GraphWrapper<Graph> GW;
    41 template void lemon::skeleton::checkCompileStaticGraph<GW>(GW &);
    42 
    43 //Compile RevGraphWrapper
    44 typedef RevGraphWrapper<Graph> RevGW;
    45 template void lemon::skeleton::checkCompileStaticGraph<RevGW>(RevGW &);
    46 
    47 //Compile SubGraphWrapper
    48 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>,
    49                         Graph::EdgeMap<bool> > SubGW;
    50 template void lemon::skeleton::checkCompileStaticGraph<SubGW>(SubGW &);
    51 
    52 //Compile NodeSubGraphWrapper
    53 typedef NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > NodeSubGW;
    54 template void lemon::skeleton::checkCompileStaticGraph<NodeSubGW>(NodeSubGW &);
    55 
    56 //Compile EdgeSubGraphWrapper
    57 typedef EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > EdgeSubGW;
    58 template void lemon::skeleton::checkCompileStaticGraph<EdgeSubGW>(EdgeSubGW &);
    59 
    60 //Compile UndirGraphWrapper
    61 /// \bug UndirGraphWrapper cannot pass the StaticGraph test
    62 //typedef UndirGraphWrapper<Graph> UndirGW;
    63 //template void checkCompileStaticGraph<UndirGW>(UndirGW &);
    64 
    65 //Compile UndirGraph
    66 //typedef UndirGraph<Graph> UndirG;
    67 //template void checkCompileStaticGraph<UndirG>(UndirG &);
    68 
    69 //Compile SubBidirGraphWrapper
    70 typedef SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>,
    71                              Graph::EdgeMap<bool> > SubBDGW;
    72 template void lemon::skeleton::checkCompileStaticGraph<SubBDGW>(SubBDGW &);
    73 
    74 //Compile BidirGraphWrapper
    75 typedef BidirGraphWrapper<Graph> BidirGW;
    76 template void lemon::skeleton::checkCompileStaticGraph<BidirGW>(BidirGW &);
    77 
    78 //Compile BidirGraph
    79 typedef BidirGraph<Graph> BidirG;
    80 template void lemon::skeleton::checkCompileStaticGraph<BidirG>(BidirG &);
    81 
    82 //Compile ResGraphWrapper
    83 typedef ResGraphWrapper<Graph, int, Graph::EdgeMap<int>,
    84                         Graph::EdgeMap<int> > ResGW;
    85 template void lemon::skeleton::checkCompileStaticGraph<ResGW>(ResGW &);
    86 
    87 //Compile ErasingFirstGraphWrapper
    88 typedef ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > ErasingFirstGW;
    89 template
    90 void lemon::skeleton::checkCompileStaticGraph<ErasingFirstGW>(ErasingFirstGW &);
    91 
    9243
    9344int main()
    9445{
     46  {
     47    function_requires<StaticGraphConcept<GraphWrapper<Graph> > >();
     48
     49    function_requires<StaticGraphConcept<RevGraphWrapper<Graph> > >();
     50
     51    function_requires<StaticGraphConcept<SubGraphWrapper<Graph, Graph::NodeMap<bool> , Graph::EdgeMap<bool> > > >();
     52    function_requires<StaticGraphConcept<NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > > >();
     53    function_requires<StaticGraphConcept<EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > > >();
     54
     55    function_requires<StaticGraphConcept<SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > > > ();
     56
     57    function_requires<StaticGraphConcept<BidirGraph<Graph> > >();
     58
     59    function_requires<StaticGraphConcept<ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > > >();
     60
     61    function_requires<StaticGraphConcept<ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > > >();
     62  }
    9563  std::cout << __FILE__ ": All tests passed.\n";
    9664
  • src/test/test_tools.h

    r937 r946  
    7171
    7272template<typename Graph>
    73 PetStruct<Graph> addPetersen(Graph &G,int num=5)
     73PetStruct<Graph> addPetersen(Graph &G,int num = 5)
    7474{
    7575  PetStruct<Graph> n;
     
    8282 for(int i=0;i<num;i++) {
    8383   n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
    84    n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
    85    n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
     84   n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num]));
     85   n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num]));
    8686  }
    8787 return n;
     88}
     89
     90/// \brief Adds to the graph the reverse pair of all edge.
     91///
     92/// Adds to the graph the reverse pair of all edge.
     93///
     94template<class Graph> void bidirGraph(Graph &G)
     95{
     96  typedef typename Graph::Edge Edge;
     97  typedef typename Graph::EdgeIt EdgeIt;
     98 
     99  std::vector<Edge> ee;
     100 
     101  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
     102
     103  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
     104    G.addEdge(G.head(*p),G.tail(*p));
     105}
     106
     107
     108/// \brief Checks the bidirectioned Petersen graph.
     109///
     110///  Checks the bidirectioned Petersen graph.
     111///
     112template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
     113{
     114  typedef typename Graph::Node Node;
     115
     116  typedef typename Graph::EdgeIt EdgeIt;
     117  typedef typename Graph::NodeIt NodeIt;
     118
     119  checkGraphNodeList(G, 2 * num);
     120  checkGraphEdgeList(G, 6 * num);
     121
     122  for(NodeIt n(G);n!=INVALID;++n) {
     123    checkGraphInEdgeList(G, n, 3);
     124    checkGraphOutEdgeList(G, n, 3);
     125  } 
    88126}
    89127
  • src/work/klao/TODO

    r486 r946  
     1full_graph.h -t atnez(et)ni!
     2
    13megcsinalni, hogy mukodjon a kereses a doksiban
Note: See TracChangeset for help on using the changeset viewer.