COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 627:6cc21a9c9fda in lemon-0.x


Ignore:
Timestamp:
05/13/04 10:20:39 (20 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@818
Message:
 
Location:
src/work/deba
Files:
1 added
1 deleted
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/deba/main.cpp

    r595 r627  
    88
    99int main() {
    10         ListGraph g;
    11         for (int i = 0; i < 3; ++i) {
    12                 ListGraph::Node node = g.addNode();
    13         }
    14         ListGraph::NodeMapFactory::Map<int> map(g, g.node_maps);
    15         for (int i = 0; i < 10; ++i) {
    16                 ListGraph::Node node = g.addNode();
    17                 map[node] = rand()%100;
    18         }
    19         for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
    20                 cout << map[it] << endl;
    21         }
    22         return 0;
     10  ListGraph g;
     11  for (int i = 0; i < 10; ++i) {
     12    ListGraph::Node node = g.addNode();
     13  }
     14  ListGraph::NodeMapFactory::Map<int> map(g, g.node_maps);
     15  for (int i = 0; i < 10; ++i) {
     16    ListGraph::Node node = g.addNode();
     17    map[node] = rand()%100;
     18  }
     19  for (ListGraph::NodeIt it(g); g.valid(it); g.next(it)) {
     20    cout << map[it] << endl;
     21  }
     22  return 0;
    2323}
    2424

  • src/work/deba/map_registry.h

    r595 r627  
    66using namespace std;
    77
     8/**
     9    Registry class to register edge or node maps in the graph. The
     10    registry helps you to implement an observer pattern. If you add
     11    or erase an edge or node you must notify all the maps about the
     12    event.
     13*/
    814
    915namespace hugo {
    10         template <typename G, typename K, typename KIt>
    11         class MapRegistry;
     16
     17  template <typename G, typename K, typename KIt>
     18  class MapRegistry {
     19  public:
     20    typedef G Graph;
     21    typedef K Key;
     22    typedef KIt KeyIt;
     23       
     24
     25
     26    class MapBase {
     27    public:
     28      typedef G Graph;
     29      typedef MapRegistry<G, K, KIt> Registry;
     30      typedef K Key;
     31      typedef KIt KeyIt;
     32       
     33      friend class Registry;
     34               
     35      /**
     36          Default constructor.
     37      */       
     38               
     39      MapBase() : graph(0), registry(0) {}
     40
     41      /**
     42          Simple constructor to register into a graph registry.
     43      */
     44       
     45      MapBase(Graph& g, Registry& r) : graph(&g), registry(0) {
     46        r.attach(*this);
     47      }
     48
     49      /**
     50          Copy constructor with registering into the map.
     51      */       
     52       
     53      MapBase(const MapBase& copy) : registry(0), graph(copy.graph) {
     54        if (copy.registry) {
     55          copy.registry->attach(*this);
     56        }
     57      }
     58       
     59      /**
     60          Assign operator.
     61      */       
     62
     63      const MapBase& operator=(const MapBase& copy) {
     64        if (registry) {
     65          registry->detach(*this);
     66        }
     67        graph = copy.graph;
     68        if (copy.registry) {
     69          copy.registry->attach(*this);
     70        }
     71      }
     72       
     73
     74      /**
     75          Destructor.
     76      */               
     77
     78      virtual ~MapBase() {
     79        if (registry) {
     80          registry->detach(*this);
     81        }
     82      }
     83       
     84    protected:
     85               
     86      Graph* graph;
     87      Registry* registry;
     88
     89      int registry_index;
     90       
     91      /**
     92         Helper function to implement constructors in the subclasses.
     93      */
     94       
     95      virtual void init() {
     96        for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
     97          add(it);
     98        }
     99      }
     100       
     101      /**
     102         Helper function to implement the destructor in the subclasses.
     103      */
     104       
     105      virtual void destroy() {
     106        for (KeyIt it(*graph); graph->valid(it); graph->next(it)) {
     107          erase(it);
     108        }
     109      }
     110       
     111      /**
     112          The add member function should be overloaded in the subclasses.
     113          \e Add extends the map with the new node.
     114      */
     115       
     116      virtual void add(const Key&) = 0;
     117      /**
     118          The erase member function should be overloaded in the subclasses.
     119          \e Erase removes the node from the map.
     120      */
     121       
     122      virtual void erase(const Key&) = 0;
     123       
     124      /**
     125         Exception class to throw at unsupported operation.
     126      */
     127       
     128      class NotSupportedOperationException {};
     129
     130    };
     131       
     132  protected:
     133       
     134    typedef std::vector<MapBase*> Container;
     135    Container container;
     136
     137               
     138    public:
     139       
     140    MapRegistry() {}
     141       
     142    MapRegistry(const MapRegistry&) {}
     143               
     144    MapRegistry& operator=(const MapRegistry&) {
     145      for (it = container.begin(); it != container.end(); ++it) {
     146        (*it)->destroy();
     147        (*it)->graph = 0;
     148        (*it)->registry = 0;
     149      }
     150    }
     151                               
     152    ~MapRegistry() {
     153      typename Container::iterator it;
     154      for (it = container.begin(); it != container.end(); ++it) {
     155        (*it)->destroy();
     156        (*it)->registry = 0;
     157        (*it)->graph = 0;
     158      }
     159    }
     160       
     161       
     162    public:
     163       
     164    void attach(MapBase& map) {
     165      if (map.registry) {
     166        map.registry->detach(map);
     167      }
     168      container.push_back(&map);
     169      map.registry = this;
     170      map.registry_index = container.size()-1;
     171    }
     172       
     173    void detach(MapBase& map) {
     174      container.back()->registry_index = map.registry_index;
     175      container[map.registry_index] = container.back();
     176      container.pop_back();
     177      map.registry = 0;
     178      map.graph = 0;
     179    }
     180       
     181               
     182    virtual void add(Key& key) {
     183      typename Container::iterator it;
     184      for (it = container.begin(); it != container.end(); ++it) {
     185        (*it)->add(key);
     186      }
     187    }   
     188               
     189    virtual void erase(Key& key) {
     190      typename Container::iterator it;
     191      for (it = container.begin(); it != container.end(); ++it) {
     192        (*it)->erase(key);
     193      }
     194    }
     195
     196  };
     197
    12198}
    13199
    14 #include "map_base.h"
    15 
    16 namespace hugo {
    17 
    18         template <typename G, typename K, typename KIt>
    19         class MapRegistry {
    20         public:
    21                 typedef G Graph;
    22                 typedef K Key;
    23                 typedef KIt KeyIt;
    24        
    25                 typedef MapBase<Graph, Key, KIt> Map;
    26                 friend class Base;
    27        
    28         protected:
    29        
    30                 typedef std::vector<Map*> Container;
    31           Container container;
    32 
    33                
    34         public:
    35        
    36                 MapRegistry() {}
    37        
    38                 MapRegistry(const MapRegistry&) {}
    39                
    40                 MapRegistry& operator=(const MapRegistry&) {
    41                         for (it = container.begin(); it != container.end(); ++it) {
    42                                 (*it)->destroy();
    43                                 (*it)->graph = 0;
    44                                 (*it)->registry = 0;
    45                         }
    46                 }
    47                                
    48                 ~MapRegistry() {
    49                         typename Container::iterator it;
    50                         for (it = container.begin(); it != container.end(); ++it) {
    51                                 (*it)->destroy();
    52                                 (*it)->registry = 0;
    53                                 (*it)->graph = 0;
    54                         }
    55                 }
    56        
    57        
    58         public:
    59        
    60                 void attach(Map& map) {
    61                         if (map.registry) {
    62                                 map.registry->detach(map);
    63                         }
    64                         container.push_back(&map);
    65                         map.registry = this;
    66                         map.registry_index = container.size()-1;
    67                 }
    68        
    69                 void detach(Map& map) {
    70                         container.back()->registry_index = map.registry_index;
    71                         container[map.registry_index] = container.back();
    72                         container.pop_back();
    73                         map.registry = 0;
    74                         map.graph = 0;
    75                 }
    76        
    77                
    78                 virtual void add(Key& key) {
    79                         typename Container::iterator it;
    80                         for (it = container.begin(); it != container.end(); ++it) {
    81                                 (*it)->add(key);
    82                         }
    83                 }       
    84                
    85                 virtual void erase(Key& key) {
    86                         typename Container::iterator it;
    87                         for (it = container.begin(); it != container.end(); ++it) {
    88                                 (*it)->erase(key);
    89                         }
    90                 }
    91 
    92         };
    93 
    94 }
    95 
    96200#endif

  • src/work/deba/test_graph.h

    r595 r627  
    3131    class SymEdgeIt;
    3232   
    33 //    template <typename T> class NodeMap;
    34 //    template <typename T> class EdgeMap;
     33    //    template <typename T> class NodeMap;
     34    //    template <typename T> class EdgeMap;
    3535  private:
    36 //    template <typename T> friend class NodeMap;
    37  //   template <typename T> friend class EdgeMap;
     36    //    template <typename T> friend class NodeMap;
     37    //   template <typename T> friend class EdgeMap;
    3838 
    3939  private:
    4040
    4141 
    42         public:
     42  public:
    4343       
    44                 typedef MapBase<ListGraph, Node, NodeIt> NodeMapBase;
    45                 typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
    46                 typedef VectorMapFactory<ListGraph, Node, NodeIt> NodeMapFactory;
    47                 NodeMapRegistry node_maps;
    48 
    49 
    50 
    51                 typedef MapBase<ListGraph, Edge, EdgeIt> EdgeMapBase;
    52                 typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
    53                 typedef VectorMapFactory<ListGraph, Edge, EdgeIt> EdgeMapFactory;
    54                 EdgeMapRegistry edge_maps;
     44    typedef MapRegistry<ListGraph, Node, NodeIt> NodeMapRegistry;
     45    typedef VectorMapFactory<NodeMapRegistry> NodeMapFactory;
     46    NodeMapRegistry node_maps;
     47
     48
     49
     50    typedef MapRegistry<ListGraph, Edge, EdgeIt> EdgeMapRegistry;
     51    typedef VectorMapFactory<EdgeMapRegistry> EdgeMapFactory;
     52    EdgeMapRegistry edge_maps;
    5553 
    5654
    … …  
    303301
    304302    Node addNode() {
    305                         Node n = _add_node();
    306                         node_maps.add(n);
    307                         return n;
    308                 }
     303      Node n = _add_node();
     304      node_maps.add(n);
     305      return n;
     306    }
    309307    Edge addEdge(Node u, Node v) {
    310                         Edge e = _add_edge(u.node, v.node);
    311                         edge_maps.add(e);
     308      Edge e = _add_edge(u.node, v.node);
     309      edge_maps.add(e);
    312310      return e;
    313311    }
    314312
    315313    void erase(Node i) {
    316                         node_maps.erase(i);
     314      node_maps.erase(i);
    317315      while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
    318316      while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
    … …  
    321319 
    322320    void erase(Edge e) {
    323                         edge_maps.erase(e);
    324                         _delete_edge(e.edge);
    325                 }
     321      edge_maps.erase(e);
     322      _delete_edge(e.edge);
     323    }
    326324
    327325    void clear() {
    … …  
    511509  };
    512510
    513 //   template< typename T >
    514 //   T ListGraph::first() const {
    515 //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;
    516 //     return T();
    517 //   }
    518 
    519 //   template<>
    520 //   ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {
    521 //     return firstNode();
    522 //   }
    523 
    524 //   template<>
    525 //   ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {
    526 //     return firstEdge();
    527 //   }
    528 
    529 //   template< typename T >
    530 //   T ListGraph::first(ListGraph::Node v) const {
    531 //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;
    532 //     return T();
    533 //   }
    534 
    535 //   template<>
    536 //   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {
    537 //     return firstOutEdge(v);
    538 //   }
    539 
    540 //   template<>
    541 //   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {
    542 //     return firstInEdge(v);
    543 //   }
    544 
    545 //   template<>
    546 //   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {
    547 //     return firstSymEdge(v);
    548 //   }
     511  //   template< typename T >
     512  //   T ListGraph::first() const {
     513  //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;
     514  //     return T();
     515  //   }
     516
     517  //   template<>
     518  //   ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {
     519  //     return firstNode();
     520  //   }
     521
     522  //   template<>
     523  //   ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {
     524  //     return firstEdge();
     525  //   }
     526
     527  //   template< typename T >
     528  //   T ListGraph::first(ListGraph::Node v) const {
     529  //     std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;
     530  //     return T();
     531  //   }
     532
     533  //   template<>
     534  //   ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {
     535  //     return firstOutEdge(v);
     536  //   }
     537
     538  //   template<>
     539  //   ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {
     540  //     return firstInEdge(v);
     541  //   }
     542
     543  //   template<>
     544  //   ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {
     545  //     return firstSymEdge(v);
     546  //   }
    549547
    550548

  • src/work/deba/vector_map_factory.h

    r595 r627  
    44#include <vector>
    55
    6 #include "map_base.h"
     6#include "map_registry.h"
    77
    88namespace hugo {
    99       
    10         template <typename G, typename K, typename KIt>
    11         class VectorMapFactory {
     10  template <typename MapRegistry>
     11  class VectorMapFactory {
     12  public:
     13               
     14    typedef typename MapRegistry::Graph Graph;
     15    typedef typename MapRegistry::Key Key;
     16    typedef typename MapRegistry::KeyIt KeyIt;
     17
     18    typedef typename MapRegistry::MapBase MapBase;
     19               
     20    template <typename V>
     21      class Map : public MapBase {
     22      public:
     23      typedef V Value;
     24       
     25      Map() {}
     26                       
     27      Map(Graph& g, MapRegistry& r) : MapBase(g, r) {
     28        init();
     29      }
     30                       
     31                                               
     32      virtual ~Map() {
     33        destroy();
     34      }
    1235       
    1336       
    14         public:
     37      Value& operator[](const Key& key) {
     38        int id = graph->id(key);
     39        return container[id];
     40      }
    1541               
    16                 typedef G Graph;
    17                 typedef K Key;
    18                 typedef KIt KeyIt;
     42      const Value& operator[](const Key& key) const {
     43        int id = graph->id(key);
     44        return container[id];
     45      }
     46       
     47      const Value& get(const Key& key) const {
     48        int id = graph->id(key);
     49        return container[id];
     50      }
    1951               
    20                 template <typename V>
    21                 class Map : public MapBase<G, K, KIt> {
    22                 public:
    23                         typedef V Value;
     52      void set(const Key& key, const Value& val) {
     53        int id = graph->id(key);
     54        container[id] = val;
     55      }
     56               
     57      void add(const Key& key) {
     58        int id = graph->id(key);
     59        if (id >= container.size()) {
     60          container.resize(id + 1);
     61        }
     62      }
     63               
     64      void erase(const Key& key) {}
    2465       
    25                         Map() {}
    26                        
    27                         Map(Graph& g, MapRegistry<G, K, KIt>& r)
    28                                 : MapBase<G, K, KIt>(g, r) {
    29                                 init();
    30                         }
    31                                
    32                         virtual ~Map() {
    33                                 destroy();
    34                         }
    35        
    36        
    37                         Value& operator[](const K& key) {
    38                                 int id = graph->id(key);
    39                                 return container[id];
    40                         }
     66      private:
     67      typedef std::vector<Value> Container;
    4168               
    42                         const Value& operator[](const K& key) const {
    43                                 int id = graph->id(key);
    44                                 return container[id];
    45                         }
    46        
    47                         const Value& get(const K& key) const {
    48                                 int id = graph->id(key);
    49                                 return container[id];
    50                         }
     69      Container container;
     70    };
    5171               
    52                         void set(const K& key, const Value& val) {
    53                                 int id = graph->id(key);
    54                                 container[id] = val;
    55                         }
    56                
    57                         void add(const K& key) {
    58                                 int id = graph->id(key);
    59                                 if (id >= container.size()) {
    60                                         container.resize(id + 1);
    61                                 }
    62                         }
    63                
    64                         void erase(const K& key) {}
    65        
    66                 private:
    67                         typedef std::vector<Value> Container;
    68                
    69                         Container container;
    70                 };
    71                
    72         };
     72  };
    7373}
    7474
Note: See TracChangeset for help on using the changeset viewer.