1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/deba/bin_heap.h Fri Jul 09 07:33:12 2004 +0000
1.3 @@ -0,0 +1,246 @@
1.4 +// -*- C++ -*- //
1.5 +
1.6 +/* FIXME: Copyright ...
1.7 + *
1.8 + * This implementation is heavily based on STL's heap functions and
1.9 + * the similar class by Alpar Juttner in IKTA...
1.10 + */
1.11 +
1.12 +/******
1.13 + *
1.14 + * BinHeap<ItemType, PrioType, ItemIntMap, [PrioCompare]>
1.15 + *
1.16 + * Ez az osztaly item-prioritas parok tarolasara alkalmas binaris kupacot
1.17 + * valosit meg.
1.18 + * A kupacban legfolul mindig az a par talalhato, amiben a prioritas a
1.19 + * legkisebb. (Gondolj a Dijkstra pont-tavolsag kupacara; igazabol ahhoz
1.20 + * lett keszitve...)
1.21 + *
1.22 + * Megjegyzes: a kupacos temakorokben a prioritast kulcsnak szoktak nevezni,
1.23 + * de mivel ez zavaro tud lenni a property-map-es kulcs-ertek szohasznalata
1.24 + * miatt, megprobaltunk valami semleges elnevezeseket kitalalni.
1.25 + *
1.26 + * A hasznalatahoz szukseg van egy irhato/olvashato property_map-re, ami
1.27 + * az itemekhez egy int-et tud tarolni (ezzel tudom megkeresni az illeto
1.28 + * elemet a kupacban a csokkentes es hasonlo muveletekhez).
1.29 + * A map-re csak referenciat tarol, ugy hogy a kupac elete folyan a map-nek
1.30 + * is elnie kell. (???)
1.31 + *
1.32 + * Ketfele modon hasznalhato:
1.33 + * Lusta mod:
1.34 + * set(Item, Prio) metodussal pakolunk a kupacba,
1.35 + * aztan o majd eldonti, hogy ez az elem mar benne van-e es ha igen, akkor
1.36 + * csokkentettunk-e rajta, vagy noveltunk.
1.37 + * Ehhez nagyon fontos, hogy az atadott property map inicializalva legyen
1.38 + * minden szobajovo kulcs ertekre, -1 -es ertekkel!
1.39 + * Es ilyen esetben a kulcsokrol lekerdezheto az allapotuk a state metodussal:
1.40 + * (nem jart meg a kupacban PRE_HEAP=-1, epp a kupacban van IN_HEAP=0,
1.41 + * mar kikerult a kupacbol POST_HEAP=-2).
1.42 + * Szoval ebben a modban a kupac nagyjabol hasznalhato property_map-kent, csak
1.43 + * meg meg tudja mondani a "legkisebb" prioritasu elemet. De csak nagyjabol,
1.44 + * hiszen a kupacbol kikerult elemeknek elvesz az ertekuk...
1.45 + *
1.46 + * Kozvetlen mod:
1.47 + * push(Item, Prio) metodussal belerakunk a kupacba (ha az illeto kulcs mar
1.48 + * benn volt, akkor gaz).
1.49 + * increase/decrease(Item i, Prio new_prio) metodusokkal lehet
1.50 + * novelni/csokkenteni az illeto elemhez tartozo prioritast. (Ha nem volt
1.51 + * megbenne a kupacban az illeto elem, vagy nem abba az iranyba valtoztattad
1.52 + * az erteket, amerre mondtad -- gaz).
1.53 + *
1.54 + * Termeszetesen a fenti ket modot ertelemszeruen lehet keverni.
1.55 + * Ja es mindig nagyon gaz, ha belepiszkalsz a map-be, amit a kupac
1.56 + * hasznal. :-))
1.57 + *
1.58 + *
1.59 + * Bocs, most faradt vagyok, majd egyszer leforditom. (Misi)
1.60 + *
1.61 + */
1.62 +
1.63 +
1.64 +#ifndef HUGO_BIN_HEAP_H
1.65 +#define HUGO_BIN_HEAP_H
1.66 +
1.67 +///\ingroup auxdat
1.68 +///\file
1.69 +///\brief Binary Heap implementation.
1.70 +
1.71 +#include <vector>
1.72 +#include <utility>
1.73 +#include <functional>
1.74 +
1.75 +namespace hugo {
1.76 +
1.77 + /// \addtogroup auxdat
1.78 + /// @{
1.79 +
1.80 + /// A Binary Heap implementation.
1.81 + template <typename Item, typename Prio, typename ItemIntMap,
1.82 + typename Compare = std::less<Prio> >
1.83 + class BinHeap {
1.84 +
1.85 + public:
1.86 + typedef Item ItemType;
1.87 + // FIXME: stl-ben nem ezt hivjak value_type -nak, hanem a kovetkezot...
1.88 + typedef Prio PrioType;
1.89 + typedef std::pair<ItemType,PrioType> PairType;
1.90 + typedef ItemIntMap ItemIntMapType;
1.91 + typedef Compare PrioCompare;
1.92 +
1.93 + /**
1.94 + * Each Item element have a state associated to it. It may be "in heap",
1.95 + * "pre heap" or "post heap". The later two are indifferent from the
1.96 + * heap's point of view, but may be useful to the user.
1.97 + *
1.98 + * The ItemIntMap _should_ be initialized in such way, that it maps
1.99 + * PRE_HEAP (-1) to any element to be put in the heap...
1.100 + */
1.101 + ///\todo it is used nowhere
1.102 + ///
1.103 + enum state_enum {
1.104 + IN_HEAP = 0,
1.105 + PRE_HEAP = -1,
1.106 + POST_HEAP = -2
1.107 + };
1.108 +
1.109 + private:
1.110 + std::vector<PairType> data;
1.111 + Compare comp;
1.112 + // FIXME: jo ez igy???
1.113 + ItemIntMap &iim;
1.114 +
1.115 + public:
1.116 + BinHeap(ItemIntMap &_iim) : iim(_iim) {}
1.117 + BinHeap(ItemIntMap &_iim, const Compare &_comp) : comp(_comp), iim(_iim) {}
1.118 +
1.119 +
1.120 + int size() const { return data.size(); }
1.121 + bool empty() const { return data.empty(); }
1.122 +
1.123 + private:
1.124 + static int parent(int i) { return (i-1)/2; }
1.125 + static int second_child(int i) { return 2*i+2; }
1.126 + bool less(const PairType &p1, const PairType &p2) const {
1.127 + return comp(p1.second, p2.second);
1.128 + }
1.129 +
1.130 + int bubble_up(int hole, PairType p);
1.131 + int bubble_down(int hole, PairType p, int length);
1.132 +
1.133 + void move(const PairType &p, int i) {
1.134 + data[i] = p;
1.135 + iim.set(p.first, i);
1.136 + }
1.137 +
1.138 + void rmidx(int h) {
1.139 + int n = data.size()-1;
1.140 + if( h>=0 && h<=n ) {
1.141 + iim.set(data[h].first, POST_HEAP);
1.142 + if ( h<n ) {
1.143 + bubble_down(h, data[n], n);
1.144 + }
1.145 + data.pop_back();
1.146 + }
1.147 + }
1.148 +
1.149 + public:
1.150 + void push(const PairType &p) {
1.151 + int n = data.size();
1.152 + data.resize(n+1);
1.153 + bubble_up(n, p);
1.154 + }
1.155 + void push(const Item &i, const Prio &p) { push(PairType(i,p)); }
1.156 +
1.157 + Item top() const {
1.158 + return data[0].first;
1.159 + }
1.160 + /// Returns the prio of the top element of the heap.
1.161 + Prio prio() const {
1.162 + return data[0].second;
1.163 + }
1.164 +
1.165 + void pop() {
1.166 + rmidx(0);
1.167 + }
1.168 +
1.169 + void erase(const Item &i) {
1.170 + rmidx(iim[i]);
1.171 + }
1.172 +
1.173 + Prio operator[](const Item &i) const {
1.174 + int idx = iim[i];
1.175 + return data[idx].second;
1.176 + }
1.177 +
1.178 + void set(const Item &i, const Prio &p) {
1.179 + int idx = iim[i];
1.180 + if( idx < 0 ) {
1.181 + push(i,p);
1.182 + }
1.183 + else if( comp(p, data[idx].second) ) {
1.184 + bubble_up(idx, PairType(i,p));
1.185 + }
1.186 + else {
1.187 + bubble_down(idx, PairType(i,p), data.size());
1.188 + }
1.189 + }
1.190 +
1.191 + void decrease(const Item &i, const Prio &p) {
1.192 + int idx = iim[i];
1.193 + bubble_up(idx, PairType(i,p));
1.194 + }
1.195 + void increase(const Item &i, const Prio &p) {
1.196 + int idx = iim[i];
1.197 + bubble_down(idx, PairType(i,p), data.size());
1.198 + }
1.199 +
1.200 + state_enum state(const Item &i) const {
1.201 + int s = iim[i];
1.202 + if( s>=0 )
1.203 + s=0;
1.204 + return state_enum(s);
1.205 + }
1.206 +
1.207 + }; // class BinHeap
1.208 +
1.209 +
1.210 + template <typename K, typename V, typename M, typename C>
1.211 + int BinHeap<K,V,M,C>::bubble_up(int hole, PairType p) {
1.212 + int par = parent(hole);
1.213 + while( hole>0 && less(p,data[par]) ) {
1.214 + move(data[par],hole);
1.215 + hole = par;
1.216 + par = parent(hole);
1.217 + }
1.218 + move(p, hole);
1.219 + return hole;
1.220 + }
1.221 +
1.222 + template <typename K, typename V, typename M, typename C>
1.223 + int BinHeap<K,V,M,C>::bubble_down(int hole, PairType p, int length) {
1.224 + int child = second_child(hole);
1.225 + while(child < length) {
1.226 + if( less(data[child-1], data[child]) ) {
1.227 + --child;
1.228 + }
1.229 + if( !less(data[child], p) )
1.230 + goto ok;
1.231 + move(data[child], hole);
1.232 + hole = child;
1.233 + child = second_child(hole);
1.234 + }
1.235 + child--;
1.236 + if( child<length && less(data[child], p) ) {
1.237 + move(data[child], hole);
1.238 + hole=child;
1.239 + }
1.240 + ok:
1.241 + move(p, hole);
1.242 + return hole;
1.243 + }
1.244 +
1.245 + ///@}
1.246 +
1.247 +} // namespace hugo
1.248 +
1.249 +#endif // BIN_HEAP_HH
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/deba/dijkstra.h Fri Jul 09 07:33:12 2004 +0000
2.3 @@ -0,0 +1,329 @@
2.4 +// -*- C++ -*-
2.5 +#ifndef HUGO_DIJKSTRA_H
2.6 +#define HUGO_DIJKSTRA_H
2.7 +
2.8 +///\ingroup galgs
2.9 +///\file
2.10 +///\brief Dijkstra algorithm.
2.11 +
2.12 +#include <hugo/bin_heap.h>
2.13 +#include <hugo/invalid.h>
2.14 +
2.15 +namespace hugo {
2.16 +
2.17 +/// \addtogroup galgs
2.18 +/// @{
2.19 +
2.20 + ///%Dijkstra algorithm class.
2.21 +
2.22 + ///This class provides an efficient implementation of %Dijkstra algorithm.
2.23 + ///The edge lengths are passed to the algorithm using a
2.24 + ///\ref ReadMapSkeleton "readable map",
2.25 + ///so it is easy to change it to any kind of length.
2.26 + ///
2.27 + ///The type of the length is determined by the \c ValueType of the length map.
2.28 + ///
2.29 + ///It is also possible to change the underlying priority heap.
2.30 + ///
2.31 + ///\param GR The graph type the algorithm runs on.
2.32 + ///\param LM This read-only
2.33 + ///EdgeMap
2.34 + ///determines the
2.35 + ///lengths of the edges. It is read once for each edge, so the map
2.36 + ///may involve in relatively time consuming process to compute the edge
2.37 + ///length if it is necessary. The default map type is
2.38 + ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
2.39 + ///\param Heap The heap type used by the %Dijkstra
2.40 + ///algorithm. The default
2.41 + ///is using \ref BinHeap "binary heap".
2.42 + ///
2.43 + ///\author Jacint Szabo and Alpar Juttner
2.44 + ///\todo We need a typedef-names should be standardized. (-:
2.45 +
2.46 +#ifdef DOXYGEN
2.47 + template <typename GR,
2.48 + typename LM,
2.49 + typename Heap>
2.50 +#else
2.51 + template <typename GR,
2.52 + typename LM=typename GR::template EdgeMap<int>,
2.53 + template <class,class,class,class> class Heap = BinHeap >
2.54 +#endif
2.55 + class Dijkstra{
2.56 + public:
2.57 + ///The type of the underlying graph.
2.58 + typedef GR Graph;
2.59 + typedef typename Graph::Node Node;
2.60 + typedef typename Graph::NodeIt NodeIt;
2.61 + typedef typename Graph::Edge Edge;
2.62 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.63 +
2.64 + ///The type of the length of the edges.
2.65 + typedef typename LM::ValueType ValueType;
2.66 + ///The type of the map that stores the edge lengths.
2.67 + typedef LM LengthMap;
2.68 + ///\brief The type of the map that stores the last
2.69 + ///edges of the shortest paths.
2.70 + typedef typename Graph::template NodeMap<Edge> PredMap;
2.71 + ///\brief The type of the map that stores the last but one
2.72 + ///nodes of the shortest paths.
2.73 + typedef typename Graph::template NodeMap<Node> PredNodeMap;
2.74 + ///The type of the map that stores the dists of the nodes.
2.75 + typedef typename Graph::template NodeMap<ValueType> DistMap;
2.76 +
2.77 + private:
2.78 + const Graph *G;
2.79 + const LM *length;
2.80 + // bool local_length;
2.81 + PredMap *predecessor;
2.82 + bool local_predecessor;
2.83 + PredNodeMap *pred_node;
2.84 + bool local_pred_node;
2.85 + DistMap *distance;
2.86 + bool local_distance;
2.87 +
2.88 + ///Initialize maps
2.89 +
2.90 + ///\todo Error if \c G or are \c NULL. What about \c length?
2.91 + ///\todo Better memory allocation (instead of new).
2.92 + void init_maps()
2.93 + {
2.94 +// if(!length) {
2.95 +// local_length = true;
2.96 +// length = new LM(G);
2.97 +// }
2.98 + if(!predecessor) {
2.99 + local_predecessor = true;
2.100 + predecessor = new PredMap(*G);
2.101 + }
2.102 + if(!pred_node) {
2.103 + local_pred_node = true;
2.104 + pred_node = new PredNodeMap(*G);
2.105 + }
2.106 + if(!distance) {
2.107 + local_distance = true;
2.108 + distance = new DistMap(*G);
2.109 + }
2.110 + }
2.111 +
2.112 + public :
2.113 +
2.114 + Dijkstra(const Graph& _G, const LM& _length) :
2.115 + G(&_G), length(&_length),
2.116 + predecessor(NULL), pred_node(NULL), distance(NULL),
2.117 + local_predecessor(false), local_pred_node(false), local_distance(false)
2.118 + { }
2.119 +
2.120 + ~Dijkstra()
2.121 + {
2.122 + // if(local_length) delete length;
2.123 + if(local_predecessor) delete predecessor;
2.124 + if(local_pred_node) delete pred_node;
2.125 + if(local_distance) delete distance;
2.126 + }
2.127 +
2.128 + ///Sets the graph the algorithm will run on.
2.129 +
2.130 + ///Sets the graph the algorithm will run on.
2.131 + ///\return <tt> (*this) </tt>
2.132 + Dijkstra &setGraph(const Graph &_G)
2.133 + {
2.134 + G = &_G;
2.135 + return *this;
2.136 + }
2.137 + ///Sets the length map.
2.138 +
2.139 + ///Sets the length map.
2.140 + ///\return <tt> (*this) </tt>
2.141 + Dijkstra &setLengthMap(const LM &m)
2.142 + {
2.143 +// if(local_length) {
2.144 +// delete length;
2.145 +// local_length=false;
2.146 +// }
2.147 + length = &m;
2.148 + return *this;
2.149 + }
2.150 +
2.151 + ///Sets the map storing the predecessor edges.
2.152 +
2.153 + ///Sets the map storing the predecessor edges.
2.154 + ///If you don't use this function before calling \ref run(),
2.155 + ///it will allocate one. The destuctor deallocates this
2.156 + ///automatically allocated map, of course.
2.157 + ///\return <tt> (*this) </tt>
2.158 + Dijkstra &setPredMap(PredMap &m)
2.159 + {
2.160 + if(local_predecessor) {
2.161 + delete predecessor;
2.162 + local_predecessor=false;
2.163 + }
2.164 + predecessor = &m;
2.165 + return *this;
2.166 + }
2.167 +
2.168 + ///Sets the map storing the predecessor nodes.
2.169 +
2.170 + ///Sets the map storing the predecessor nodes.
2.171 + ///If you don't use this function before calling \ref run(),
2.172 + ///it will allocate one. The destuctor deallocates this
2.173 + ///automatically allocated map, of course.
2.174 + ///\return <tt> (*this) </tt>
2.175 + Dijkstra &setPredNodeMap(PredNodeMap &m)
2.176 + {
2.177 + if(local_pred_node) {
2.178 + delete pred_node;
2.179 + local_pred_node=false;
2.180 + }
2.181 + pred_node = &m;
2.182 + return *this;
2.183 + }
2.184 +
2.185 + ///Sets the map storing the distances calculated by the algorithm.
2.186 +
2.187 + ///Sets the map storing the distances calculated by the algorithm.
2.188 + ///If you don't use this function before calling \ref run(),
2.189 + ///it will allocate one. The destuctor deallocates this
2.190 + ///automatically allocated map, of course.
2.191 + ///\return <tt> (*this) </tt>
2.192 + Dijkstra &setDistMap(DistMap &m)
2.193 + {
2.194 + if(local_distance) {
2.195 + delete distance;
2.196 + local_distance=false;
2.197 + }
2.198 + distance = &m;
2.199 + return *this;
2.200 + }
2.201 +
2.202 + ///Runs %Dijkstra algorithm from node \c s.
2.203 +
2.204 + ///This method runs the %Dijkstra algorithm from a root node \c s
2.205 + ///in order to
2.206 + ///compute the
2.207 + ///shortest path to each node. The algorithm computes
2.208 + ///- The shortest path tree.
2.209 + ///- The distance of each node from the root.
2.210 +
2.211 + void run(Node s) {
2.212 +
2.213 + init_maps();
2.214 +
2.215 + for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
2.216 + predecessor->set(u,INVALID);
2.217 + pred_node->set(u,INVALID);
2.218 + }
2.219 +
2.220 + typename GR::template NodeMap<int> heap_map(*G,-1);
2.221 +
2.222 + typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
2.223 + std::less<ValueType> >
2.224 + HeapType;
2.225 +
2.226 + HeapType heap(heap_map);
2.227 +
2.228 + heap.push(s,0);
2.229 +
2.230 + while ( !heap.empty() ) {
2.231 +
2.232 + Node v=heap.top();
2.233 + ValueType oldvalue=heap[v];
2.234 + heap.pop();
2.235 + distance->set(v, oldvalue);
2.236 +
2.237 +
2.238 + for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
2.239 + Node w=G->bNode(e);
2.240 +
2.241 + switch(heap.state(w)) {
2.242 + case HeapType::PRE_HEAP:
2.243 + heap.push(w,oldvalue+(*length)[e]);
2.244 + predecessor->set(w,e);
2.245 + pred_node->set(w,v);
2.246 + break;
2.247 + case HeapType::IN_HEAP:
2.248 + if ( oldvalue+(*length)[e] < heap[w] ) {
2.249 + heap.decrease(w, oldvalue+(*length)[e]);
2.250 + predecessor->set(w,e);
2.251 + pred_node->set(w,v);
2.252 + }
2.253 + break;
2.254 + case HeapType::POST_HEAP:
2.255 + break;
2.256 + }
2.257 + }
2.258 + }
2.259 + }
2.260 +
2.261 + ///The distance of a node from the root.
2.262 +
2.263 + ///Returns the distance of a node from the root.
2.264 + ///\pre \ref run() must be called before using this function.
2.265 + ///\warning If node \c v in unreachable from the root the return value
2.266 + ///of this funcion is undefined.
2.267 + ValueType dist(Node v) const { return (*distance)[v]; }
2.268 +
2.269 + ///Returns the 'previous edge' of the shortest path tree.
2.270 +
2.271 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
2.272 + ///i.e. it returns the last edge from a shortest path from the root to \c
2.273 + ///v. It is \ref INVALID
2.274 + ///if \c v is unreachable from the root or if \c v=s. The
2.275 + ///shortest path tree used here is equal to the shortest path tree used in
2.276 + ///\ref predNode(Node v). \pre \ref run() must be called before using
2.277 + ///this function.
2.278 + Edge pred(Node v) const { return (*predecessor)[v]; }
2.279 +
2.280 + ///Returns the 'previous node' of the shortest path tree.
2.281 +
2.282 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
2.283 + ///i.e. it returns the last but one node from a shortest path from the
2.284 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
2.285 + ///\c v=s. The shortest path tree used here is equal to the shortest path
2.286 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
2.287 + ///using this function.
2.288 + Node predNode(Node v) const { return (*pred_node)[v]; }
2.289 +
2.290 + ///Returns a reference to the NodeMap of distances.
2.291 +
2.292 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
2.293 + ///be called before using this function.
2.294 + const DistMap &distMap() const { return *distance;}
2.295 +
2.296 + ///Returns a reference to the shortest path tree map.
2.297 +
2.298 + ///Returns a reference to the NodeMap of the edges of the
2.299 + ///shortest path tree.
2.300 + ///\pre \ref run() must be called before using this function.
2.301 + const PredMap &predMap() const { return *predecessor;}
2.302 +
2.303 + ///Returns a reference to the map of nodes of shortest paths.
2.304 +
2.305 + ///Returns a reference to the NodeMap of the last but one nodes of the
2.306 + ///shortest path tree.
2.307 + ///\pre \ref run() must be called before using this function.
2.308 + const PredNodeMap &predNodeMap() const { return *pred_node;}
2.309 +
2.310 + ///Checks if a node is reachable from the root.
2.311 +
2.312 + ///Returns \c true if \c v is reachable from the root.
2.313 + ///\warning the root node is reported to be unreached!
2.314 + ///\todo Is this what we want?
2.315 + ///\pre \ref run() must be called before using this function.
2.316 + ///
2.317 + bool reached(Node v) { return G->valid((*predecessor)[v]); }
2.318 +
2.319 + };
2.320 +
2.321 +
2.322 + // **********************************************************************
2.323 + // IMPLEMENTATIONS
2.324 + // **********************************************************************
2.325 +
2.326 +/// @}
2.327 +
2.328 +} //END OF NAMESPACE HUGO
2.329 +
2.330 +#endif
2.331 +
2.332 +
3.1 --- a/src/work/deba/invalid.h Tue Jul 06 13:57:01 2004 +0000
3.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
3.3 @@ -1,33 +0,0 @@
3.4 -// -*- mode:C++ -*-
3.5 -
3.6 -#ifndef HUGO_INVALID_H
3.7 -#define HUGO_INVALID_H
3.8 -
3.9 -///\file
3.10 -///\brief Definition of INVALID.
3.11 -
3.12 -namespace hugo {
3.13 -
3.14 - /// Dummy type to make it easier to make invalid iterators.
3.15 -
3.16 - /// See \ref INVALID, how to use it.
3.17 -
3.18 - struct Invalid {};
3.19 -
3.20 - /// Invalid iterators.
3.21 -
3.22 - /// \ref Invalid is a global type that converts to each iterator
3.23 - /// in such a way that the value of the target iterator will be invalid.
3.24 -
3.25 - // It is also used to convert the \c INVALID constant to the
3.26 - // node iterator that makes is possible to write
3.27 -
3.28 - //extern Invalid INVALID;
3.29 -
3.30 - //const Invalid &INVALID = *(Invalid *)0;
3.31 - const Invalid INVALID = Invalid();
3.32 -
3.33 -};
3.34 -
3.35 -#endif
3.36 -
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/deba/list_graph.h Fri Jul 09 07:33:12 2004 +0000
4.3 @@ -0,0 +1,1305 @@
4.4 +// -*- mode:C++ -*-
4.5 +
4.6 +#ifndef HUGO_LIST_GRAPH_H
4.7 +#define HUGO_LIST_GRAPH_H
4.8 +
4.9 +///\ingroup graphs
4.10 +///\file
4.11 +///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
4.12 +
4.13 +#include <vector>
4.14 +#include <climits>
4.15 +
4.16 +#include "invalid.h"
4.17 +
4.18 +#include "vector_map_factory.h"
4.19 +#include "map_registry.h"
4.20 +
4.21 +#include "map_defines.h"
4.22 +
4.23 +namespace hugo {
4.24 +
4.25 +/// \addtogroup graphs
4.26 +/// @{
4.27 +
4.28 + ///A list graph class.
4.29 +
4.30 + ///This is a simple and fast erasable graph implementation.
4.31 + ///
4.32 + ///It conforms to the graph interface documented under
4.33 + ///the description of \ref GraphSkeleton.
4.34 + ///\sa \ref GraphSkeleton.
4.35 + class ListGraph {
4.36 +
4.37 + //Nodes are double linked.
4.38 + //The free nodes are only single linked using the "next" field.
4.39 + struct NodeT
4.40 + {
4.41 + int first_in,first_out;
4.42 + int prev, next;
4.43 + // NodeT() {}
4.44 + };
4.45 + //Edges are double linked.
4.46 + //The free edges are only single linked using the "next_in" field.
4.47 + struct EdgeT
4.48 + {
4.49 + int head, tail;
4.50 + int prev_in, prev_out;
4.51 + int next_in, next_out;
4.52 + //FIXME: is this necessary?
4.53 + // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
4.54 + };
4.55 +
4.56 + std::vector<NodeT> nodes;
4.57 + //The first node
4.58 + int first_node;
4.59 + //The first free node
4.60 + int first_free_node;
4.61 + std::vector<EdgeT> edges;
4.62 + //The first free edge
4.63 + int first_free_edge;
4.64 +
4.65 + protected:
4.66 +
4.67 + public:
4.68 +
4.69 + class Node;
4.70 + class Edge;
4.71 +
4.72 + typedef ListGraph Graph;
4.73 +
4.74 + public:
4.75 +
4.76 + class NodeIt;
4.77 + class EdgeIt;
4.78 + class OutEdgeIt;
4.79 + class InEdgeIt;
4.80 +
4.81 + CREATE_MAP_REGISTRIES;
4.82 + CREATE_MAPS(VectorMapFactory);
4.83 +
4.84 + public:
4.85 +
4.86 + ListGraph() : nodes(), first_node(-1),
4.87 + first_free_node(-1), edges(), first_free_edge(-1) {}
4.88 + ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
4.89 + first_free_node(_g.first_free_node),
4.90 + edges(_g.edges),
4.91 + first_free_edge(_g.first_free_edge) {}
4.92 +
4.93 +
4.94 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
4.95 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
4.96 +
4.97 + ///Set the expected number of edges
4.98 +
4.99 + ///With this function, it is possible to set the expected number of edges.
4.100 + ///The use of this fasten the building of the graph and makes
4.101 + ///it possible to avoid the superfluous memory allocation.
4.102 + void reserveEdge(int n) { edges.reserve(n); };
4.103 +
4.104 + ///\bug This function does something different than
4.105 + ///its name would suggests...
4.106 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
4.107 + ///\bug This function does something different than
4.108 + ///its name would suggests...
4.109 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
4.110 +
4.111 + Node tail(Edge e) const { return edges[e.n].tail; }
4.112 + Node head(Edge e) const { return edges[e.n].head; }
4.113 +
4.114 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
4.115 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
4.116 +
4.117 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
4.118 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
4.119 +
4.120 + NodeIt& first(NodeIt& v) const {
4.121 + v=NodeIt(*this); return v; }
4.122 + EdgeIt& first(EdgeIt& e) const {
4.123 + e=EdgeIt(*this); return e; }
4.124 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
4.125 + e=OutEdgeIt(*this,v); return e; }
4.126 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
4.127 + e=InEdgeIt(*this,v); return e; }
4.128 +
4.129 +// template< typename It >
4.130 +// It first() const { It e; first(e); return e; }
4.131 +
4.132 +// template< typename It >
4.133 +// It first(Node v) const { It e; first(e,v); return e; }
4.134 +
4.135 + bool valid(Edge e) const { return e.n!=-1; }
4.136 + bool valid(Node n) const { return n.n!=-1; }
4.137 +
4.138 + void setInvalid(Edge &e) { e.n=-1; }
4.139 + void setInvalid(Node &n) { n.n=-1; }
4.140 +
4.141 + template <typename It> It getNext(It it) const
4.142 + { It tmp(it); return next(tmp); }
4.143 +
4.144 + NodeIt& next(NodeIt& it) const {
4.145 + it.n=nodes[it.n].next;
4.146 + return it;
4.147 + }
4.148 + OutEdgeIt& next(OutEdgeIt& it) const
4.149 + { it.n=edges[it.n].next_out; return it; }
4.150 + InEdgeIt& next(InEdgeIt& it) const
4.151 + { it.n=edges[it.n].next_in; return it; }
4.152 + EdgeIt& next(EdgeIt& it) const {
4.153 + if(edges[it.n].next_in!=-1) {
4.154 + it.n=edges[it.n].next_in;
4.155 + }
4.156 + else {
4.157 + int n;
4.158 + for(n=nodes[edges[it.n].head].next;
4.159 + n!=-1 && nodes[n].first_in == -1;
4.160 + n = nodes[n].next) ;
4.161 + it.n = (n==-1)?-1:nodes[n].first_in;
4.162 + }
4.163 + return it;
4.164 + }
4.165 +
4.166 + int id(Node v) const { return v.n; }
4.167 + int id(Edge e) const { return e.n; }
4.168 +
4.169 + /// Adds a new node to the graph.
4.170 +
4.171 + /// \todo It adds the nodes in a reversed order.
4.172 + /// (i.e. the lastly added node becomes the first.)
4.173 + Node addNode() {
4.174 + int n;
4.175 +
4.176 + if(first_free_node==-1)
4.177 + {
4.178 + n = nodes.size();
4.179 + nodes.push_back(NodeT());
4.180 + }
4.181 + else {
4.182 + n = first_free_node;
4.183 + first_free_node = nodes[n].next;
4.184 + }
4.185 +
4.186 + nodes[n].next = first_node;
4.187 + if(first_node != -1) nodes[first_node].prev = n;
4.188 + first_node = n;
4.189 + nodes[n].prev = -1;
4.190 +
4.191 + nodes[n].first_in = nodes[n].first_out = -1;
4.192 +
4.193 + Node nn; nn.n=n;
4.194 +
4.195 + //Update dynamic maps
4.196 + node_maps.add(nn);
4.197 +
4.198 + return nn;
4.199 + }
4.200 +
4.201 + Edge addEdge(Node u, Node v) {
4.202 + int n;
4.203 +
4.204 + if(first_free_edge==-1)
4.205 + {
4.206 + n = edges.size();
4.207 + edges.push_back(EdgeT());
4.208 + }
4.209 + else {
4.210 + n = first_free_edge;
4.211 + first_free_edge = edges[n].next_in;
4.212 + }
4.213 +
4.214 + edges[n].tail = u.n; edges[n].head = v.n;
4.215 +
4.216 + edges[n].next_out = nodes[u.n].first_out;
4.217 + if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
4.218 + edges[n].next_in = nodes[v.n].first_in;
4.219 + if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
4.220 + edges[n].prev_in = edges[n].prev_out = -1;
4.221 +
4.222 + nodes[u.n].first_out = nodes[v.n].first_in = n;
4.223 +
4.224 + Edge e; e.n=n;
4.225 +
4.226 + //Update dynamic maps
4.227 + edge_maps.add(e);
4.228 +
4.229 + return e;
4.230 + }
4.231 +
4.232 + private:
4.233 + void eraseEdge(int n) {
4.234 +
4.235 + if(edges[n].next_in!=-1)
4.236 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
4.237 + if(edges[n].prev_in!=-1)
4.238 + edges[edges[n].prev_in].next_in = edges[n].next_in;
4.239 + else nodes[edges[n].head].first_in = edges[n].next_in;
4.240 +
4.241 + if(edges[n].next_out!=-1)
4.242 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
4.243 + if(edges[n].prev_out!=-1)
4.244 + edges[edges[n].prev_out].next_out = edges[n].next_out;
4.245 + else nodes[edges[n].tail].first_out = edges[n].next_out;
4.246 +
4.247 + edges[n].next_in = first_free_edge;
4.248 + first_free_edge = n;
4.249 +
4.250 + //Update dynamic maps
4.251 + Edge e; e.n=n;
4.252 + }
4.253 +
4.254 + public:
4.255 +
4.256 + void erase(Node nn) {
4.257 + int n=nn.n;
4.258 +
4.259 + int m;
4.260 + while((m=nodes[n].first_in)!=-1) eraseEdge(m);
4.261 + while((m=nodes[n].first_out)!=-1) eraseEdge(m);
4.262 +
4.263 + if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
4.264 + if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
4.265 + else first_node = nodes[n].next;
4.266 +
4.267 + nodes[n].next = first_free_node;
4.268 + first_free_node = n;
4.269 +
4.270 + //Update dynamic maps
4.271 + node_maps.erase(nn);
4.272 + }
4.273 +
4.274 + void erase(Edge e) {
4.275 + edge_maps.erase(e);
4.276 + eraseEdge(e.n);
4.277 + }
4.278 +
4.279 + ///\bug Dynamic maps must be updated!
4.280 + ///
4.281 + void clear() {
4.282 + nodes.clear();edges.clear();
4.283 + first_node=first_free_node=first_free_edge=-1;
4.284 + }
4.285 +
4.286 + class Node {
4.287 + friend class ListGraph;
4.288 + template <typename T> friend class NodeMap;
4.289 +
4.290 + friend class Edge;
4.291 + friend class OutEdgeIt;
4.292 + friend class InEdgeIt;
4.293 + friend class SymEdge;
4.294 +
4.295 + protected:
4.296 + int n;
4.297 + friend int ListGraph::id(Node v) const;
4.298 + Node(int nn) {n=nn;}
4.299 + public:
4.300 + Node() {}
4.301 + Node (Invalid) { n=-1; }
4.302 + bool operator==(const Node i) const {return n==i.n;}
4.303 + bool operator!=(const Node i) const {return n!=i.n;}
4.304 + bool operator<(const Node i) const {return n<i.n;}
4.305 + };
4.306 +
4.307 + class NodeIt : public Node {
4.308 + friend class ListGraph;
4.309 + public:
4.310 + NodeIt() : Node() { }
4.311 + NodeIt(Invalid i) : Node(i) { }
4.312 + NodeIt(const ListGraph& G) : Node(G.first_node) { }
4.313 + ///\todo Undocumented conversion Node -\> NodeIt.
4.314 + NodeIt(const ListGraph& G, const Node &n) : Node(n) { }
4.315 + };
4.316 +
4.317 + class Edge {
4.318 + friend class ListGraph;
4.319 + template <typename T> friend class EdgeMap;
4.320 +
4.321 + //template <typename T> friend class SymListGraph::SymEdgeMap;
4.322 + //friend Edge SymListGraph::opposite(Edge) const;
4.323 +
4.324 + friend class Node;
4.325 + friend class NodeIt;
4.326 + protected:
4.327 + int n;
4.328 + friend int ListGraph::id(Edge e) const;
4.329 +
4.330 + Edge(int nn) {n=nn;}
4.331 + public:
4.332 + Edge() { }
4.333 + Edge (Invalid) { n=-1; }
4.334 + bool operator==(const Edge i) const {return n==i.n;}
4.335 + bool operator!=(const Edge i) const {return n!=i.n;}
4.336 + bool operator<(const Edge i) const {return n<i.n;}
4.337 + ///\bug This is a workaround until somebody tells me how to
4.338 + ///make class \c SymListGraph::SymEdgeMap friend of Edge
4.339 + int &idref() {return n;}
4.340 + const int &idref() const {return n;}
4.341 + };
4.342 +
4.343 + class EdgeIt : public Edge {
4.344 + friend class ListGraph;
4.345 + public:
4.346 + EdgeIt(const ListGraph& G) : Edge() {
4.347 + int m;
4.348 + for(m=G.first_node;
4.349 + m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
4.350 + n = (m==-1)?-1:G.nodes[m].first_in;
4.351 + }
4.352 + EdgeIt (Invalid i) : Edge(i) { }
4.353 + EdgeIt() : Edge() { }
4.354 + ///\bug This is a workaround until somebody tells me how to
4.355 + ///make class \c SymListGraph::SymEdgeMap friend of Edge
4.356 + int &idref() {return n;}
4.357 + };
4.358 +
4.359 + class OutEdgeIt : public Edge {
4.360 + friend class ListGraph;
4.361 + public:
4.362 + OutEdgeIt() : Edge() { }
4.363 + OutEdgeIt (Invalid i) : Edge(i) { }
4.364 +
4.365 + OutEdgeIt(const ListGraph& G,const Node v)
4.366 + : Edge(G.nodes[v.n].first_out) {}
4.367 + };
4.368 +
4.369 + class InEdgeIt : public Edge {
4.370 + friend class ListGraph;
4.371 + public:
4.372 + InEdgeIt() : Edge() { }
4.373 + InEdgeIt (Invalid i) : Edge(i) { }
4.374 + InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in) {}
4.375 + };
4.376 +
4.377 + };
4.378 +
4.379 + ///Graph for bidirectional edges.
4.380 +
4.381 + ///The purpose of this graph structure is to handle graphs
4.382 + ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
4.383 + ///of oppositely directed edges.
4.384 + ///There is a new edge map type called
4.385 + ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
4.386 + ///that complements this
4.387 + ///feature by
4.388 + ///storing shared values for the edge pairs. The usual
4.389 + ///\ref GraphSkeleton::EdgeMap "EdgeMap"
4.390 + ///can be used
4.391 + ///as well.
4.392 + ///
4.393 + ///The oppositely directed edge can also be obtained easily
4.394 + ///using \ref opposite.
4.395 + ///
4.396 + ///Here erase(Edge) deletes a pair of edges.
4.397 + ///
4.398 + ///\todo this date structure need some reconsiderations. Maybe it
4.399 + ///should be implemented independently from ListGraph.
4.400 +
4.401 + };
4.402 +
4.403 +
4.404 + ///A graph class containing only nodes.
4.405 +
4.406 + ///This class implements a graph structure without edges.
4.407 + ///The most useful application of this class is to be the node set of an
4.408 + ///\ref EdgeSet class.
4.409 + ///
4.410 + ///It conforms to the graph interface documented under
4.411 + ///the description of \ref GraphSkeleton with the exception that you cannot
4.412 + ///add (or delete) edges. The usual edge iterators are exists, but they are
4.413 + ///always \ref INVALID.
4.414 + ///\sa \ref GraphSkeleton
4.415 + ///\sa \ref EdgeSet
4.416 + class NodeSet {
4.417 +
4.418 + //Nodes are double linked.
4.419 + //The free nodes are only single linked using the "next" field.
4.420 + struct NodeT
4.421 + {
4.422 + int first_in,first_out;
4.423 + int prev, next;
4.424 + // NodeT() {}
4.425 + };
4.426 +
4.427 + std::vector<NodeT> nodes;
4.428 + //The first node
4.429 + int first_node;
4.430 + //The first free node
4.431 + int first_free_node;
4.432 +
4.433 + protected:
4.434 +
4.435 + template <typename Key> class DynMapBase
4.436 + {
4.437 + protected:
4.438 + const NodeSet* G;
4.439 + public:
4.440 + virtual void add(const Key k) = 0;
4.441 + virtual void erase(const Key k) = 0;
4.442 + DynMapBase(const NodeSet &_G) : G(&_G) {}
4.443 + virtual ~DynMapBase() {}
4.444 + friend class NodeSet;
4.445 + };
4.446 +
4.447 + public:
4.448 + template <typename T> class EdgeMap;
4.449 + template <typename T> class NodeMap;
4.450 +
4.451 + class Node;
4.452 + class Edge;
4.453 +
4.454 + // protected:
4.455 + // HELPME:
4.456 + protected:
4.457 + ///\bug It must be public because of SymEdgeMap.
4.458 + ///
4.459 + mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
4.460 + //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
4.461 +
4.462 + public:
4.463 +
4.464 + class NodeIt;
4.465 + class EdgeIt;
4.466 + class OutEdgeIt;
4.467 + class InEdgeIt;
4.468 +
4.469 + template <typename T> class NodeMap;
4.470 + template <typename T> class EdgeMap;
4.471 +
4.472 + public:
4.473 +
4.474 + ///Default constructor
4.475 + NodeSet() : nodes(), first_node(-1),
4.476 + first_free_node(-1) {}
4.477 + ///Copy constructor
4.478 + NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
4.479 + first_free_node(_g.first_free_node) {}
4.480 +
4.481 + ~NodeSet()
4.482 + {
4.483 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.484 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
4.485 + //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
4.486 + // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
4.487 + }
4.488 +
4.489 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
4.490 + int edgeNum() const { return 0; } //FIXME: What is this?
4.491 +
4.492 + ///\bug This function does something different than
4.493 + ///its name would suggests...
4.494 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
4.495 + ///\bug This function does something different than
4.496 + ///its name would suggests...
4.497 + int maxEdgeId() const { return 0; } //FIXME: What is this?
4.498 +
4.499 + Node tail(Edge e) const { return INVALID; }
4.500 + Node head(Edge e) const { return INVALID; }
4.501 +
4.502 + Node aNode(OutEdgeIt e) const { return INVALID; }
4.503 + Node aNode(InEdgeIt e) const { return INVALID; }
4.504 +
4.505 + Node bNode(OutEdgeIt e) const { return INVALID; }
4.506 + Node bNode(InEdgeIt e) const { return INVALID; }
4.507 +
4.508 + NodeIt& first(NodeIt& v) const {
4.509 + v=NodeIt(*this); return v; }
4.510 + EdgeIt& first(EdgeIt& e) const {
4.511 + e=EdgeIt(*this); return e; }
4.512 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
4.513 + e=OutEdgeIt(*this,v); return e; }
4.514 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
4.515 + e=InEdgeIt(*this,v); return e; }
4.516 +
4.517 +// template< typename It >
4.518 +// It first() const { It e; first(e); return e; }
4.519 +
4.520 +// template< typename It >
4.521 +// It first(Node v) const { It e; first(e,v); return e; }
4.522 +
4.523 + bool valid(Edge e) const { return false; }
4.524 + bool valid(Node n) const { return n.n!=-1; }
4.525 +
4.526 + void setInvalid(Edge &e) { }
4.527 + void setInvalid(Node &n) { n.n=-1; }
4.528 +
4.529 + template <typename It> It getNext(It it) const
4.530 + { It tmp(it); return next(tmp); }
4.531 +
4.532 + NodeIt& next(NodeIt& it) const {
4.533 + it.n=nodes[it.n].next;
4.534 + return it;
4.535 + }
4.536 + OutEdgeIt& next(OutEdgeIt& it) const { return it; }
4.537 + InEdgeIt& next(InEdgeIt& it) const { return it; }
4.538 + EdgeIt& next(EdgeIt& it) const { return it; }
4.539 +
4.540 + int id(Node v) const { return v.n; }
4.541 + int id(Edge e) const { return -1; }
4.542 +
4.543 + /// Adds a new node to the graph.
4.544 +
4.545 + /// \todo It adds the nodes in a reversed order.
4.546 + /// (i.e. the lastly added node becomes the first.)
4.547 + Node addNode() {
4.548 + int n;
4.549 +
4.550 + if(first_free_node==-1)
4.551 + {
4.552 + n = nodes.size();
4.553 + nodes.push_back(NodeT());
4.554 + }
4.555 + else {
4.556 + n = first_free_node;
4.557 + first_free_node = nodes[n].next;
4.558 + }
4.559 +
4.560 + nodes[n].next = first_node;
4.561 + if(first_node != -1) nodes[first_node].prev = n;
4.562 + first_node = n;
4.563 + nodes[n].prev = -1;
4.564 +
4.565 + nodes[n].first_in = nodes[n].first_out = -1;
4.566 +
4.567 + Node nn; nn.n=n;
4.568 +
4.569 + //Update dynamic maps
4.570 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.571 + i!=dyn_node_maps.end(); ++i) (**i).add(nn);
4.572 +
4.573 + return nn;
4.574 + }
4.575 +
4.576 + void erase(Node nn) {
4.577 + int n=nn.n;
4.578 +
4.579 + if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
4.580 + if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
4.581 + else first_node = nodes[n].next;
4.582 +
4.583 + nodes[n].next = first_free_node;
4.584 + first_free_node = n;
4.585 +
4.586 + //Update dynamic maps
4.587 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.588 + i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
4.589 + }
4.590 +
4.591 + ///\bug Dynamic maps must be updated!
4.592 + ///
4.593 + void clear() {
4.594 + nodes.clear();
4.595 + first_node = first_free_node = -1;
4.596 + }
4.597 +
4.598 + class Node {
4.599 + friend class NodeSet;
4.600 + template <typename T> friend class NodeMap;
4.601 +
4.602 + friend class Edge;
4.603 + friend class OutEdgeIt;
4.604 + friend class InEdgeIt;
4.605 +
4.606 + protected:
4.607 + int n;
4.608 + friend int NodeSet::id(Node v) const;
4.609 + Node(int nn) {n=nn;}
4.610 + public:
4.611 + Node() {}
4.612 + Node (Invalid i) { n=-1; }
4.613 + bool operator==(const Node i) const {return n==i.n;}
4.614 + bool operator!=(const Node i) const {return n!=i.n;}
4.615 + bool operator<(const Node i) const {return n<i.n;}
4.616 + };
4.617 +
4.618 + class NodeIt : public Node {
4.619 + friend class NodeSet;
4.620 + public:
4.621 + NodeIt() : Node() { }
4.622 + NodeIt(Invalid i) : Node(i) { }
4.623 + NodeIt(const NodeSet& G) : Node(G.first_node) { }
4.624 + ///\todo Undocumented conversion Node -\> NodeIt.
4.625 + NodeIt(const NodeSet& G, const Node &n) : Node(n) { }
4.626 +
4.627 + };
4.628 +
4.629 + class Edge {
4.630 + //friend class NodeSet;
4.631 + //template <typename T> friend class EdgeMap;
4.632 +
4.633 + //template <typename T> friend class SymNodeSet::SymEdgeMap;
4.634 + //friend Edge SymNodeSet::opposite(Edge) const;
4.635 +
4.636 + // friend class Node;
4.637 + // friend class NodeIt;
4.638 + protected:
4.639 + //friend int NodeSet::id(Edge e) const;
4.640 + // Edge(int nn) {}
4.641 + public:
4.642 + Edge() { }
4.643 + Edge (Invalid) { }
4.644 + bool operator==(const Edge i) const {return true;}
4.645 + bool operator!=(const Edge i) const {return false;}
4.646 + bool operator<(const Edge i) const {return false;}
4.647 + ///\bug This is a workaround until somebody tells me how to
4.648 + ///make class \c SymNodeSet::SymEdgeMap friend of Edge
4.649 + // int idref() {return -1;}
4.650 + // int idref() const {return -1;}
4.651 + };
4.652 +
4.653 + class EdgeIt : public Edge {
4.654 + //friend class NodeSet;
4.655 + public:
4.656 + EdgeIt(const NodeSet& G) : Edge() { }
4.657 + EdgeIt (Invalid i) : Edge(i) { }
4.658 + EdgeIt() : Edge() { }
4.659 + ///\bug This is a workaround until somebody tells me how to
4.660 + ///make class \c SymNodeSet::SymEdgeMap friend of Edge
4.661 + // int idref() {return -1;}
4.662 + };
4.663 +
4.664 + class OutEdgeIt : public Edge {
4.665 + friend class NodeSet;
4.666 + public:
4.667 + OutEdgeIt() : Edge() { }
4.668 + OutEdgeIt (Invalid i) : Edge(i) { }
4.669 + OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
4.670 + };
4.671 +
4.672 + class InEdgeIt : public Edge {
4.673 + friend class NodeSet;
4.674 + public:
4.675 + InEdgeIt() : Edge() { }
4.676 + InEdgeIt (Invalid i) : Edge(i) { }
4.677 + InEdgeIt(const NodeSet& G,Node v) :Edge() {}
4.678 + };
4.679 +
4.680 + template <typename T> class NodeMap : public DynMapBase<Node>
4.681 + {
4.682 + std::vector<T> container;
4.683 +
4.684 + public:
4.685 + typedef T ValueType;
4.686 + typedef Node KeyType;
4.687 +
4.688 + NodeMap(const NodeSet &_G) :
4.689 + DynMapBase<Node>(_G), container(_G.maxNodeId())
4.690 + {
4.691 + G->dyn_node_maps.push_back(this);
4.692 + }
4.693 + NodeMap(const NodeSet &_G,const T &t) :
4.694 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
4.695 + {
4.696 + G->dyn_node_maps.push_back(this);
4.697 + }
4.698 +
4.699 + NodeMap(const NodeMap<T> &m) :
4.700 + DynMapBase<Node>(*m.G), container(m.container)
4.701 + {
4.702 + G->dyn_node_maps.push_back(this);
4.703 + }
4.704 +
4.705 + template<typename TT> friend class NodeMap;
4.706 +
4.707 + ///\todo It can copy between different types.
4.708 + ///
4.709 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
4.710 + DynMapBase<Node>(*m.G), container(m.container.size())
4.711 + {
4.712 + G->dyn_node_maps.push_back(this);
4.713 + typename std::vector<TT>::const_iterator i;
4.714 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.715 + i!=m.container.end();
4.716 + i++)
4.717 + container.push_back(*i);
4.718 + }
4.719 + ~NodeMap()
4.720 + {
4.721 + if(G) {
4.722 + std::vector<DynMapBase<Node>* >::iterator i;
4.723 + for(i=G->dyn_node_maps.begin();
4.724 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
4.725 + //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
4.726 + //A better way to do that: (Is this really important?)
4.727 + if(*i==this) {
4.728 + *i=G->dyn_node_maps.back();
4.729 + G->dyn_node_maps.pop_back();
4.730 + }
4.731 + }
4.732 + }
4.733 +
4.734 + void add(const Node k)
4.735 + {
4.736 + if(k.n>=int(container.size())) container.resize(k.n+1);
4.737 + }
4.738 +
4.739 + void erase(const Node) { }
4.740 +
4.741 + void set(Node n, T a) { container[n.n]=a; }
4.742 + //'T& operator[](Node n)' would be wrong here
4.743 + typename std::vector<T>::reference
4.744 + operator[](Node n) { return container[n.n]; }
4.745 + //'const T& operator[](Node n)' would be wrong here
4.746 + typename std::vector<T>::const_reference
4.747 + operator[](Node n) const { return container[n.n]; }
4.748 +
4.749 + ///\warning There is no safety check at all!
4.750 + ///Using operator = between maps attached to different graph may
4.751 + ///cause serious problem.
4.752 + ///\todo Is this really so?
4.753 + ///\todo It can copy between different types.
4.754 + const NodeMap<T>& operator=(const NodeMap<T> &m)
4.755 + {
4.756 + container = m.container;
4.757 + return *this;
4.758 + }
4.759 + template<typename TT>
4.760 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
4.761 + {
4.762 + std::copy(m.container.begin(), m.container.end(), container.begin());
4.763 + return *this;
4.764 + }
4.765 +
4.766 + void update() {} //Useless for Dynamic Maps
4.767 + void update(T a) {} //Useless for Dynamic Maps
4.768 + };
4.769 +
4.770 + template <typename T> class EdgeMap
4.771 + {
4.772 + public:
4.773 + typedef T ValueType;
4.774 + typedef Edge KeyType;
4.775 +
4.776 + EdgeMap(const NodeSet &) { }
4.777 + EdgeMap(const NodeSet &,const T &) { }
4.778 + EdgeMap(const EdgeMap<T> &) { }
4.779 + // template<typename TT> friend class EdgeMap;
4.780 +
4.781 + ///\todo It can copy between different types.
4.782 + ///
4.783 + template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
4.784 + ~EdgeMap() { }
4.785 +
4.786 + void add(const Edge ) { }
4.787 + void erase(const Edge) { }
4.788 +
4.789 + void set(Edge, T) { }
4.790 + //T get(Edge n) const { return container[n.n]; }
4.791 + ValueType &operator[](Edge) { return *((T*)(NULL)); }
4.792 + const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
4.793 +
4.794 + const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
4.795 +
4.796 + template<typename TT>
4.797 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
4.798 +
4.799 + void update() {}
4.800 + void update(T a) {}
4.801 + };
4.802 + };
4.803 +
4.804 +
4.805 +
4.806 + ///Graph structure using a node set of another graph.
4.807 +
4.808 + ///This structure can be used to establish another graph over a node set
4.809 + /// of an existing one. The node iterator will go through the nodes of the
4.810 + /// original graph, and the NodeMap's of both graphs will convert to
4.811 + /// each other.
4.812 + ///
4.813 + ///\warning Adding or deleting nodes from the graph is not safe if an
4.814 + ///\ref EdgeSet is currently attached to it!
4.815 + ///
4.816 + ///\todo Make it possible to add/delete edges from the base graph
4.817 + ///(and from \ref EdgeSet, as well)
4.818 + ///
4.819 + ///\param GG The type of the graph which shares its node set with this class.
4.820 + ///Its interface must conform with \ref GraphSkeleton.
4.821 + ///
4.822 + ///It conforms to the graph interface documented under
4.823 + ///the description of \ref GraphSkeleton.
4.824 + ///\sa \ref GraphSkeleton.
4.825 + ///\sa \ref NodeSet.
4.826 + template<typename GG>
4.827 + class EdgeSet {
4.828 +
4.829 + typedef GG NodeGraphType;
4.830 +
4.831 + NodeGraphType &G;
4.832 +
4.833 + public:
4.834 + class Node;
4.835 + int id(Node v) const;
4.836 +
4.837 + class Node : public NodeGraphType::Node {
4.838 + friend class EdgeSet;
4.839 + // template <typename T> friend class NodeMap;
4.840 +
4.841 + friend class Edge;
4.842 + friend class OutEdgeIt;
4.843 + friend class InEdgeIt;
4.844 + friend class SymEdge;
4.845 +
4.846 + public:
4.847 + friend int EdgeSet::id(Node v) const;
4.848 + // Node(int nn) {n=nn;}
4.849 + public:
4.850 + Node() : NodeGraphType::Node() {}
4.851 + Node (Invalid i) : NodeGraphType::Node(i) {}
4.852 + Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
4.853 + };
4.854 +
4.855 + class NodeIt : public NodeGraphType::NodeIt {
4.856 + friend class EdgeSet;
4.857 + public:
4.858 + NodeIt() : NodeGraphType::NodeIt() { }
4.859 + NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
4.860 + NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
4.861 + NodeIt(const typename NodeGraphType::NodeIt &n)
4.862 + : NodeGraphType::NodeIt(n) {}
4.863 + ///\todo Undocumented conversion Node -\> NodeIt.
4.864 + NodeIt(const EdgeSet& _G, const Node &n)
4.865 + : NodeGraphType::NodeIt(_G.G,n) { }
4.866 +
4.867 + operator Node() { return Node(*this);}
4.868 + };
4.869 +
4.870 + private:
4.871 + //Edges are double linked.
4.872 + //The free edges are only single linked using the "next_in" field.
4.873 + struct NodeT
4.874 + {
4.875 + int first_in,first_out;
4.876 + NodeT() : first_in(-1), first_out(-1) { }
4.877 + };
4.878 +
4.879 + struct EdgeT
4.880 + {
4.881 + Node head, tail;
4.882 + int prev_in, prev_out;
4.883 + int next_in, next_out;
4.884 + };
4.885 +
4.886 +
4.887 + typename NodeGraphType::template NodeMap<NodeT> nodes;
4.888 +
4.889 + std::vector<EdgeT> edges;
4.890 + //The first free edge
4.891 + int first_free_edge;
4.892 +
4.893 + protected:
4.894 +
4.895 + template <typename Key> class DynMapBase
4.896 + {
4.897 + protected:
4.898 + const EdgeSet* G;
4.899 + public:
4.900 + virtual void add(const Key k) = 0;
4.901 + virtual void erase(const Key k) = 0;
4.902 + DynMapBase(const EdgeSet &_G) : G(&_G) {}
4.903 + virtual ~DynMapBase() {}
4.904 + friend class EdgeSet;
4.905 + };
4.906 +
4.907 + public:
4.908 + //template <typename T> class NodeMap;
4.909 + template <typename T> class EdgeMap;
4.910 +
4.911 + class Node;
4.912 + class Edge;
4.913 +
4.914 + // protected:
4.915 + // HELPME:
4.916 + protected:
4.917 + // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
4.918 + ///\bug It must be public because of SymEdgeMap.
4.919 + ///
4.920 + mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
4.921 +
4.922 + public:
4.923 +
4.924 + class NodeIt;
4.925 + class EdgeIt;
4.926 + class OutEdgeIt;
4.927 + class InEdgeIt;
4.928 +
4.929 + template <typename T> class NodeMap;
4.930 + template <typename T> class EdgeMap;
4.931 +
4.932 + public:
4.933 +
4.934 + ///Constructor
4.935 +
4.936 + ///Construates a new graph based on the nodeset of an existing one.
4.937 + ///\param _G the base graph.
4.938 + ///\todo It looks like a copy constructor, but it isn't.
4.939 + EdgeSet(NodeGraphType &_G) : G(_G),
4.940 + nodes(_G), edges(),
4.941 + first_free_edge(-1) { }
4.942 + ///Copy constructor
4.943 +
4.944 + ///Makes a copy of an EdgeSet.
4.945 + ///It will be based on the same graph.
4.946 + EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
4.947 + first_free_edge(_g.first_free_edge) { }
4.948 +
4.949 + ~EdgeSet()
4.950 + {
4.951 + // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
4.952 + // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
4.953 + for(typename std::vector<DynMapBase<Edge> * >::iterator
4.954 + i=dyn_edge_maps.begin();
4.955 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
4.956 + }
4.957 +
4.958 + int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
4.959 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
4.960 +
4.961 + ///\bug This function does something different than
4.962 + ///its name would suggests...
4.963 + int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
4.964 + ///\bug This function does something different than
4.965 + ///its name would suggests...
4.966 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
4.967 +
4.968 + Node tail(Edge e) const { return edges[e.n].tail; }
4.969 + Node head(Edge e) const { return edges[e.n].head; }
4.970 +
4.971 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
4.972 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
4.973 +
4.974 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
4.975 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
4.976 +
4.977 + NodeIt& first(NodeIt& v) const {
4.978 + v=NodeIt(*this); return v; }
4.979 + EdgeIt& first(EdgeIt& e) const {
4.980 + e=EdgeIt(*this); return e; }
4.981 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
4.982 + e=OutEdgeIt(*this,v); return e; }
4.983 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
4.984 + e=InEdgeIt(*this,v); return e; }
4.985 +
4.986 +// template< typename It >
4.987 +// It first() const { It e; first(e); return e; }
4.988 +
4.989 +// template< typename It >
4.990 +// It first(Node v) const { It e; first(e,v); return e; }
4.991 +
4.992 + bool valid(Edge e) const { return e.n!=-1; }
4.993 + bool valid(Node n) const { return G.valid(n); }
4.994 +
4.995 + void setInvalid(Edge &e) { e.n=-1; }
4.996 + void setInvalid(Node &n) { G.setInvalid(n); }
4.997 +
4.998 + template <typename It> It getNext(It it) const
4.999 + { It tmp(it); return next(tmp); }
4.1000 +
4.1001 + NodeIt& next(NodeIt& it) const { G.next(it); return it; }
4.1002 + OutEdgeIt& next(OutEdgeIt& it) const
4.1003 + { it.n=edges[it.n].next_out; return it; }
4.1004 + InEdgeIt& next(InEdgeIt& it) const
4.1005 + { it.n=edges[it.n].next_in; return it; }
4.1006 + EdgeIt& next(EdgeIt& it) const {
4.1007 + if(edges[it.n].next_in!=-1) {
4.1008 + it.n=edges[it.n].next_in;
4.1009 + }
4.1010 + else {
4.1011 + NodeIt n(*this,edges[it.n].head);
4.1012 + for(n=next(n);
4.1013 + valid(n) && nodes[n].first_in == -1;
4.1014 + next(n)) ;
4.1015 + it.n = (valid(n))?-1:nodes[n].first_in;
4.1016 + }
4.1017 + return it;
4.1018 + }
4.1019 +
4.1020 + int id(Edge e) const { return e.n; }
4.1021 +
4.1022 + /// Adds a new node to the graph.
4.1023 + Node addNode() { return G.addNode(); }
4.1024 +
4.1025 + Edge addEdge(Node u, Node v) {
4.1026 + int n;
4.1027 +
4.1028 + if(first_free_edge==-1)
4.1029 + {
4.1030 + n = edges.size();
4.1031 + edges.push_back(EdgeT());
4.1032 + }
4.1033 + else {
4.1034 + n = first_free_edge;
4.1035 + first_free_edge = edges[n].next_in;
4.1036 + }
4.1037 +
4.1038 + edges[n].tail = u; edges[n].head = v;
4.1039 +
4.1040 + edges[n].next_out = nodes[u].first_out;
4.1041 + if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
4.1042 + edges[n].next_in = nodes[v].first_in;
4.1043 + if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
4.1044 + edges[n].prev_in = edges[n].prev_out = -1;
4.1045 +
4.1046 + nodes[u].first_out = nodes[v].first_in = n;
4.1047 +
4.1048 + Edge e; e.n=n;
4.1049 +
4.1050 + //Update dynamic maps
4.1051 + for(typename std::vector<DynMapBase<Edge> * >::iterator
4.1052 + i=dyn_edge_maps.begin();
4.1053 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
4.1054 +
4.1055 + return e;
4.1056 + }
4.1057 +
4.1058 + private:
4.1059 + void eraseEdge(int n) {
4.1060 +
4.1061 + if(edges[n].next_in!=-1)
4.1062 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
4.1063 + if(edges[n].prev_in!=-1)
4.1064 + edges[edges[n].prev_in].next_in = edges[n].next_in;
4.1065 + else nodes[edges[n].head].first_in = edges[n].next_in;
4.1066 +
4.1067 + if(edges[n].next_out!=-1)
4.1068 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
4.1069 + if(edges[n].prev_out!=-1)
4.1070 + edges[edges[n].prev_out].next_out = edges[n].next_out;
4.1071 + else nodes[edges[n].tail].first_out = edges[n].next_out;
4.1072 +
4.1073 + edges[n].next_in = first_free_edge;
4.1074 + first_free_edge = -1;
4.1075 +
4.1076 + //Update dynamic maps
4.1077 + Edge e; e.n=n;
4.1078 + for(typename std::vector<DynMapBase<Edge> * >::iterator
4.1079 + i=dyn_edge_maps.begin();
4.1080 + i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
4.1081 + }
4.1082 +
4.1083 + public:
4.1084 +
4.1085 +// void erase(Node nn) {
4.1086 +// int n=nn.n;
4.1087 +// int m;
4.1088 +// while((m=nodes[n].first_in)!=-1) eraseEdge(m);
4.1089 +// while((m=nodes[n].first_out)!=-1) eraseEdge(m);
4.1090 +// }
4.1091 +
4.1092 + void erase(Edge e) { eraseEdge(e.n); }
4.1093 +
4.1094 + ///Clear all edges. (Doesn't clear the nodes!)
4.1095 + void clear() {
4.1096 + edges.clear();
4.1097 + first_free_edge=-1;
4.1098 + }
4.1099 +
4.1100 +
4.1101 +// //\bug Dynamic maps must be updated!
4.1102 +// //
4.1103 +// void clear() {
4.1104 +// nodes.clear();edges.clear();
4.1105 +// first_node=first_free_node=first_free_edge=-1;
4.1106 +// }
4.1107 +
4.1108 + public:
4.1109 + template <typename T> class EdgeMap;
4.1110 +
4.1111 + ///
4.1112 + class Edge {
4.1113 + public:
4.1114 + friend class EdgeSet;
4.1115 + template <typename T> friend class EdgeMap;
4.1116 +
4.1117 + friend class Node;
4.1118 + friend class NodeIt;
4.1119 + public:
4.1120 + ///\bug It shoud be at least protected
4.1121 + ///
4.1122 + int n;
4.1123 + protected:
4.1124 + friend int EdgeSet::id(Edge e) const;
4.1125 +
4.1126 + Edge(int nn) {n=nn;}
4.1127 + public:
4.1128 + Edge() { }
4.1129 + Edge (Invalid) { n=-1; }
4.1130 + bool operator==(const Edge i) const {return n==i.n;}
4.1131 + bool operator!=(const Edge i) const {return n!=i.n;}
4.1132 + bool operator<(const Edge i) const {return n<i.n;}
4.1133 + ///\bug This is a workaround until somebody tells me how to
4.1134 + ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
4.1135 + int &idref() {return n;}
4.1136 + const int &idref() const {return n;}
4.1137 + };
4.1138 +
4.1139 + class EdgeIt : public Edge {
4.1140 + friend class EdgeSet;
4.1141 + template <typename T> friend class EdgeMap;
4.1142 +
4.1143 +
4.1144 + public:
4.1145 + EdgeIt(const EdgeSet& G) : Edge() {
4.1146 + // typename NodeGraphType::Node m;
4.1147 + NodeIt m;
4.1148 + for(G.first(m);
4.1149 + G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
4.1150 + //AJJAJ! This is a non sense!!!!!!!
4.1151 + this->n = G.valid(m)?-1:G.nodes[m].first_in;
4.1152 + }
4.1153 + EdgeIt (Invalid i) : Edge(i) { }
4.1154 + EdgeIt() : Edge() { }
4.1155 + ///\bug This is a workaround until somebody tells me how to
4.1156 + ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
4.1157 + int &idref() {return this->n;}
4.1158 + };
4.1159 +
4.1160 + class OutEdgeIt : public Edge {
4.1161 + friend class EdgeSet;
4.1162 + public:
4.1163 + OutEdgeIt() : Edge() { }
4.1164 + OutEdgeIt (Invalid i) : Edge(i) { }
4.1165 +
4.1166 + OutEdgeIt(const EdgeSet& G,const Node v) : Edge(G.nodes[v].first_out) { }
4.1167 + };
4.1168 +
4.1169 + class InEdgeIt : public Edge {
4.1170 + friend class EdgeSet;
4.1171 + public:
4.1172 + InEdgeIt() : Edge() { }
4.1173 + InEdgeIt (Invalid i) : Edge(i) { }
4.1174 + InEdgeIt(const EdgeSet& G,Node v) :Edge(G.nodes[v].first_in) { }
4.1175 + };
4.1176 +
4.1177 + template <typename T> class NodeMap :
4.1178 + public NodeGraphType::template NodeMap<T>
4.1179 + {
4.1180 + //This is a must, the constructors need it.
4.1181 + typedef typename NodeGraphType::template NodeMap<T> ParentNodeMap;
4.1182 + public:
4.1183 + NodeMap(const EdgeSet &_G) : ParentNodeMap(_G.G) { }
4.1184 + NodeMap(const EdgeSet &_G,const T &t) : ParentNodeMap(_G.G,t) { }
4.1185 + //It is unnecessary
4.1186 + NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
4.1187 + ParentNodeMap(m) { }
4.1188 +
4.1189 + ///\todo It can copy between different types.
4.1190 + ///
4.1191 + template<typename TT>
4.1192 + NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
4.1193 + : ParentNodeMap(m) { }
4.1194 + };
4.1195 +
4.1196 + ///
4.1197 + template <typename T> class EdgeMap : public DynMapBase<Edge>
4.1198 + {
4.1199 + protected:
4.1200 + public:
4.1201 + ///\bug It should be at least protected
4.1202 + ///
4.1203 + std::vector<T> container;
4.1204 +
4.1205 + public:
4.1206 + typedef T ValueType;
4.1207 + typedef Edge KeyType;
4.1208 +
4.1209 + EdgeMap(const EdgeSet &_G) :
4.1210 + DynMapBase<Edge>(_G), container(_G.maxEdgeId())
4.1211 + {
4.1212 + //FIXME: What if there are empty Id's?
4.1213 + //FIXME: Can I use 'this' in a constructor?
4.1214 + G->dyn_edge_maps.push_back(this);
4.1215 + }
4.1216 + EdgeMap(const EdgeSet &_G,const T &t) :
4.1217 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
4.1218 + {
4.1219 + G->dyn_edge_maps.push_back(this);
4.1220 + }
4.1221 + EdgeMap(const EdgeMap<T> &m) :
4.1222 + DynMapBase<Edge>(*m.G), container(m.container)
4.1223 + {
4.1224 + G->dyn_edge_maps.push_back(this);
4.1225 + }
4.1226 +
4.1227 + template<typename TT> friend class EdgeMap;
4.1228 +
4.1229 + ///\todo It can copy between different types.
4.1230 + ///
4.1231 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
4.1232 + DynMapBase<Edge>(*m.G), container(m.container.size())
4.1233 + {
4.1234 + G->dyn_edge_maps.push_back(this);
4.1235 + typename std::vector<TT>::const_iterator i;
4.1236 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
4.1237 + i!=m.container.end();
4.1238 + i++)
4.1239 + container.push_back(*i);
4.1240 + }
4.1241 + ~EdgeMap()
4.1242 + {
4.1243 + if(G) {
4.1244 + typename std::vector<DynMapBase<Edge>* >::iterator i;
4.1245 + for(i=G->dyn_edge_maps.begin();
4.1246 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
4.1247 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
4.1248 + //A better way to do that: (Is this really important?)
4.1249 + if(*i==this) {
4.1250 + *i=G->dyn_edge_maps.back();
4.1251 + G->dyn_edge_maps.pop_back();
4.1252 + }
4.1253 + }
4.1254 + }
4.1255 +
4.1256 + void add(const Edge k)
4.1257 + {
4.1258 + if(k.n>=int(container.size())) container.resize(k.n+1);
4.1259 + }
4.1260 + void erase(const Edge) { }
4.1261 +
4.1262 + ///\bug This doesn't work. Why?
4.1263 + /// void set(Edge n, T a) { container[n.n]=a; }
4.1264 + void set(Edge n, T a) { container[G->id(n)]=a; }
4.1265 + //T get(Edge n) const { return container[n.n]; }
4.1266 + typename std::vector<T>::reference
4.1267 + ///\bug This doesn't work. Why?
4.1268 + /// operator[](Edge n) { return container[n.n]; }
4.1269 + operator[](Edge n) { return container[G->id(n)]; }
4.1270 + typename std::vector<T>::const_reference
4.1271 + ///\bug This doesn't work. Why?
4.1272 + /// operator[](Edge n) const { return container[n.n]; }
4.1273 + operator[](Edge n) const { return container[G->id(n)]; }
4.1274 +
4.1275 + ///\warning There is no safety check at all!
4.1276 + ///Using operator = between maps attached to different graph may
4.1277 + ///cause serious problem.
4.1278 + ///\todo Is this really so?
4.1279 + ///\todo It can copy between different types.
4.1280 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
4.1281 + {
4.1282 + container = m.container;
4.1283 + return *this;
4.1284 + }
4.1285 +
4.1286 + template<typename TT> friend class EdgeMap;
4.1287 +
4.1288 + template<typename TT>
4.1289 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
4.1290 + {
4.1291 + std::copy(m.container.begin(), m.container.end(), container.begin());
4.1292 + return *this;
4.1293 + }
4.1294 +
4.1295 + void update() {} //Useless for DynMaps
4.1296 + void update(T a) {} //Useless for DynMaps
4.1297 + };
4.1298 +
4.1299 + };
4.1300 +
4.1301 + template<typename GG>
4.1302 + inline int EdgeSet<GG>::id(Node v) const { return G.id(v); }
4.1303 +
4.1304 +/// @}
4.1305 +
4.1306 +} //namespace hugo
4.1307 +
4.1308 +#endif //HUGO_LIST_GRAPH_H
5.1 --- a/src/work/deba/main.cpp Tue Jul 06 13:57:01 2004 +0000
5.2 +++ b/src/work/deba/main.cpp Fri Jul 09 07:33:12 2004 +0000
5.3 @@ -1,6 +1,6 @@
5.4 #include <iostream>
5.5 #include <cstdlib>
5.6 -#include "test_graph.h"
5.7 +#include "list_graph.h"
5.8
5.9 using namespace std;
5.10 using namespace hugo;
6.1 --- a/src/work/deba/test_graph.h Tue Jul 06 13:57:01 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,539 +0,0 @@
6.4 -// -*- c++ -*-
6.5 -#ifndef HUGO_LIST_GRAPH_H
6.6 -#define HUGO_LIST_GRAPH_H
6.7 -
6.8 -#include <iostream>
6.9 -#include <vector>
6.10 -
6.11 -#include "invalid.h"
6.12 -
6.13 -#include "map_registry.h"
6.14 -#include "array_map_factory.h"
6.15 -
6.16 -#include "map_defines.h"
6.17 -
6.18 -namespace hugo {
6.19 -
6.20 - template <typename It>
6.21 - int count(It it) {
6.22 - int i=0;
6.23 - for( ; it.valid(); ++it) { ++i; }
6.24 - return i;
6.25 - }
6.26 -
6.27 - class ListGraph {
6.28 - class node_item;
6.29 - class edge_item;
6.30 - public:
6.31 - class Node;
6.32 - class NodeIt;
6.33 - class Edge;
6.34 - class EdgeIt;
6.35 - class OutEdgeIt;
6.36 - class InEdgeIt;
6.37 - class SymEdgeIt;
6.38 -
6.39 - typedef ListGraph Graph;
6.40 -
6.41 - CREATE_MAP_REGISTRIES;
6.42 - CREATE_MAPS(ArrayMapFactory);
6.43 -
6.44 - private:
6.45 -
6.46 - int node_id;
6.47 - int edge_id;
6.48 - int _node_num;
6.49 - int _edge_num;
6.50 -
6.51 - node_item* _first_node;
6.52 - node_item* _last_node;
6.53 -
6.54 - class node_item {
6.55 - friend class ListGraph;
6.56 - template <typename T> friend class NodeMap;
6.57 -
6.58 - friend class Node;
6.59 - friend class NodeIt;
6.60 - friend class Edge;
6.61 - friend class EdgeIt;
6.62 - friend class OutEdgeIt;
6.63 - friend class InEdgeIt;
6.64 - friend class SymEdgeIt;
6.65 - friend std::ostream& operator<<(std::ostream& os, const Node& i);
6.66 - friend std::ostream& operator<<(std::ostream& os, const Edge& i);
6.67 - //ListGraph* G;
6.68 - int id;
6.69 - edge_item* _first_out_edge;
6.70 - edge_item* _last_out_edge;
6.71 - edge_item* _first_in_edge;
6.72 - edge_item* _last_in_edge;
6.73 - node_item* _next_node;
6.74 - node_item* _prev_node;
6.75 - public:
6.76 - node_item() { }
6.77 - };
6.78 -
6.79 - class edge_item {
6.80 - friend class ListGraph;
6.81 - template <typename T> friend class EdgeMap;
6.82 -
6.83 - friend class Node;
6.84 - friend class NodeIt;
6.85 - friend class Edge;
6.86 - friend class EdgeIt;
6.87 - friend class OutEdgeIt;
6.88 - friend class InEdgeIt;
6.89 - friend class SymEdgeIt;
6.90 - friend std::ostream& operator<<(std::ostream& os, const Edge& i);
6.91 - //ListGraph* G;
6.92 - int id;
6.93 - node_item* _tail;
6.94 - node_item* _head;
6.95 - edge_item* _next_out;
6.96 - edge_item* _prev_out;
6.97 - edge_item* _next_in;
6.98 - edge_item* _prev_in;
6.99 - public:
6.100 - edge_item() { }
6.101 - };
6.102 -
6.103 - node_item* _add_node() {
6.104 - node_item* p=new node_item;
6.105 - p->id=node_id++;
6.106 - p->_first_out_edge=0;
6.107 - p->_last_out_edge=0;
6.108 - p->_first_in_edge=0;
6.109 - p->_last_in_edge=0;
6.110 - p->_prev_node=_last_node;
6.111 - p->_next_node=0;
6.112 - if (_last_node) _last_node->_next_node=p;
6.113 - _last_node=p;
6.114 - if (!_first_node) _first_node=p;
6.115 -
6.116 - ++_node_num;
6.117 - return p;
6.118 - }
6.119 -
6.120 - edge_item* _add_edge(node_item* _tail, node_item* _head) {
6.121 - edge_item* e=new edge_item;
6.122 - e->id=edge_id++;
6.123 - e->_tail=_tail;
6.124 - e->_head=_head;
6.125 -
6.126 - e->_prev_out=_tail->_last_out_edge;
6.127 - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
6.128 - _tail->_last_out_edge=e;
6.129 - if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
6.130 - e->_next_out=0;
6.131 -
6.132 - e->_prev_in=_head->_last_in_edge;
6.133 - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
6.134 - _head->_last_in_edge=e;
6.135 - if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
6.136 - e->_next_in=0;
6.137 -
6.138 - ++_edge_num;
6.139 - return e;
6.140 - }
6.141 -
6.142 - //deletes a node which has no out edge and no in edge
6.143 - void _delete_node(node_item* v) {
6.144 - if (v->_next_node) (v->_next_node)->_prev_node=v->_prev_node; else
6.145 - _last_node=v->_prev_node;
6.146 - if (v->_prev_node) (v->_prev_node)->_next_node=v->_next_node; else
6.147 - _first_node=v->_next_node;
6.148 -
6.149 - delete v;
6.150 - --_node_num;
6.151 - }
6.152 -
6.153 - void _delete_edge(edge_item* e) {
6.154 - if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
6.155 - (e->_tail)->_last_out_edge=e->_prev_out;
6.156 - if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
6.157 - (e->_tail)->_first_out_edge=e->_next_out;
6.158 - if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
6.159 - (e->_head)->_last_in_edge=e->_prev_in;
6.160 - if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
6.161 - (e->_head)->_first_in_edge=e->_next_in;
6.162 -
6.163 - delete e;
6.164 - --_edge_num;
6.165 - }
6.166 -
6.167 - void _set_tail(edge_item* e, node_item* _tail) {
6.168 - if (e->_next_out) (e->_next_out)->_prev_out=e->_prev_out; else
6.169 - (e->_tail)->_last_out_edge=e->_prev_out;
6.170 - if (e->_prev_out) (e->_prev_out)->_next_out=e->_next_out; else
6.171 - (e->_tail)->_first_out_edge=e->_next_out;
6.172 -
6.173 - e->_tail=_tail;
6.174 -
6.175 - e->_prev_out=_tail->_last_out_edge;
6.176 - if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
6.177 - _tail->_last_out_edge=e;
6.178 - if (!_tail->_first_out_edge) _tail->_first_out_edge=e;
6.179 - e->_next_out=0;
6.180 - }
6.181 -
6.182 - void _set_head(edge_item* e, node_item* _head) {
6.183 - if (e->_next_in) (e->_next_in)->_prev_in=e->_prev_in; else
6.184 - (e->_head)->_last_in_edge=e->_prev_in;
6.185 - if (e->_prev_in) (e->_prev_in)->_next_in=e->_next_in; else
6.186 - (e->_head)->_first_in_edge=e->_next_in;
6.187 -
6.188 - e->_head=_head;
6.189 -
6.190 - e->_prev_in=_head->_last_in_edge;
6.191 - if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
6.192 - _head->_last_in_edge=e;
6.193 - if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
6.194 - e->_next_in=0;
6.195 - }
6.196 -
6.197 - public:
6.198 -
6.199 - /* default constructor */
6.200 -
6.201 - ListGraph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0){ }
6.202 -
6.203 - ~ListGraph() {
6.204 - while (first<NodeIt>().valid()) erase(first<NodeIt>());
6.205 - }
6.206 -
6.207 - int nodeNum() const { return _node_num; }
6.208 - int edgeNum() const { return _edge_num; }
6.209 -
6.210 - /* functions to construct iterators from the graph, or from each other */
6.211 -
6.212 - //NodeIt firstNode() const { return NodeIt(*this); }
6.213 - //EdgeIt firstEdge() const { return EdgeIt(*this); }
6.214 -
6.215 - //OutEdgeIt firstOutEdge(const Node v) const { return OutEdgeIt(v); }
6.216 - //InEdgeIt firstInEdge(const Node v) const { return InEdgeIt(v); }
6.217 - //SymEdgeIt firstSymEdge(const Node v) const { return SymEdgeIt(v); }
6.218 - Node tail(Edge e) const { return e.tailNode(); }
6.219 - Node head(Edge e) const { return e.headNode(); }
6.220 -
6.221 - Node aNode(const OutEdgeIt& e) const { return e.aNode(); }
6.222 - Node aNode(const InEdgeIt& e) const { return e.aNode(); }
6.223 - Node aNode(const SymEdgeIt& e) const { return e.aNode(); }
6.224 -
6.225 - Node bNode(const OutEdgeIt& e) const { return e.bNode(); }
6.226 - Node bNode(const InEdgeIt& e) const { return e.bNode(); }
6.227 - Node bNode(const SymEdgeIt& e) const { return e.bNode(); }
6.228 -
6.229 - //Node invalid_node() { return Node(); }
6.230 - //Edge invalid_edge() { return Edge(); }
6.231 - //OutEdgeIt invalid_out_edge() { return OutEdgeIt(); }
6.232 - //InEdgeIt invalid_in_edge() { return InEdgeIt(); }
6.233 - //SymEdgeIt invalid_sym_edge() { return SymEdgeIt(); }
6.234 -
6.235 - /* same methods in other style */
6.236 - /* for experimental purpose */
6.237 -
6.238 - NodeIt& /*getF*/first(NodeIt& v) const {
6.239 - v=NodeIt(*this); return v; }
6.240 - EdgeIt& /*getF*/first(EdgeIt& e) const {
6.241 - e=EdgeIt(*this); return e; }
6.242 - OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
6.243 - e=OutEdgeIt(*this, v); return e; }
6.244 - InEdgeIt& /*getF*/first(InEdgeIt& e, Node v) const {
6.245 - e=InEdgeIt(*this, v); return e; }
6.246 - SymEdgeIt& /*getF*/first(SymEdgeIt& e, Node v) const {
6.247 - e=SymEdgeIt(*this, v); return e; }
6.248 - //void getTail(Node& n, const Edge& e) const { n=tail(e); }
6.249 - //void getHead(Node& n, const Edge& e) const { n=head(e); }
6.250 -
6.251 - //void getANode(Node& n, const OutEdgeIt& e) const { n=e.aNode(); }
6.252 - //void getANode(Node& n, const InEdgeIt& e) const { n=e.aNode(); }
6.253 - //void getANode(Node& n, const SymEdgeIt& e) const { n=e.aNode(); }
6.254 - //void getBNode(Node& n, const OutEdgeIt& e) const { n=e.bNode(); }
6.255 - //void getBNode(Node& n, const InEdgeIt& e) const { n=e.bNode(); }
6.256 - //void getBNode(Node& n, const SymEdgeIt& e) const { n=e.bNode(); }
6.257 - //void get_invalid(Node& n) { n=Node(); }
6.258 - //void get_invalid(Edge& e) { e=Edge(); }
6.259 - //void get_invalid(OutEdgeIt& e) { e=OutEdgeIt(); }
6.260 - //void get_invalid(InEdgeIt& e) { e=InEdgeIt(); }
6.261 - //void get_invalid(SymEdgeIt& e) { e=SymEdgeIt(); }
6.262 -
6.263 - template< typename It >
6.264 - It first() const {
6.265 - It e;
6.266 - /*getF*/first(e);
6.267 - return e;
6.268 - }
6.269 -
6.270 - template< typename It >
6.271 - It first(Node v) const {
6.272 - It e;
6.273 - /*getF*/first(e, v);
6.274 - return e;
6.275 - }
6.276 -
6.277 - bool valid(Node n) const { return n.valid(); }
6.278 - bool valid(Edge e) const { return e.valid(); }
6.279 -
6.280 - template <typename It> It getNext(It it) const {
6.281 - It tmp(it); return next(tmp); }
6.282 - template <typename It> It& next(It& it) const { return ++it; }
6.283 -
6.284 -
6.285 - /* for getting id's of graph objects */
6.286 - /* these are important for the implementation of property vectors */
6.287 -
6.288 - int id(Node v) const { return v.node->id; }
6.289 - int id(Edge e) const { return e.edge->id; }
6.290 -
6.291 - /* adding nodes and edges */
6.292 -
6.293 - Node addNode() {
6.294 - Node n = _add_node();
6.295 - node_maps.add(n);
6.296 - return n;
6.297 - }
6.298 - Edge addEdge(Node u, Node v) {
6.299 - Edge e = _add_edge(u.node, v.node);
6.300 - edge_maps.add(e);
6.301 - return e;
6.302 - }
6.303 -
6.304 - void erase(Node i) {
6.305 - node_maps.erase(i);
6.306 - while (first<OutEdgeIt>(i).valid()) erase(first<OutEdgeIt>(i));
6.307 - while (first<InEdgeIt>(i).valid()) erase(first<InEdgeIt>(i));
6.308 - _delete_node(i.node);
6.309 - }
6.310 -
6.311 - void erase(Edge e) {
6.312 - edge_maps.erase(e);
6.313 - _delete_edge(e.edge);
6.314 - }
6.315 -
6.316 - void clear() {
6.317 - while (first<NodeIt>().valid()) erase(first<NodeIt>());
6.318 - }
6.319 -
6.320 - void setTail(Edge e, Node tail) {
6.321 - _set_tail(e.edge, tail.node);
6.322 - }
6.323 -
6.324 - void setHead(Edge e, Node head) {
6.325 - _set_head(e.edge, head.node);
6.326 - }
6.327 -
6.328 - /* stream operations, for testing purpose */
6.329 -
6.330 - friend std::ostream& operator<<(std::ostream& os, const Node& i) {
6.331 - os << i.node->id; return os;
6.332 - }
6.333 - friend std::ostream& operator<<(std::ostream& os, const Edge& i) {
6.334 - os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")";
6.335 - return os;
6.336 - }
6.337 -
6.338 - class Node {
6.339 - friend class ListGraph;
6.340 - template <typename T> friend class NodeMap;
6.341 -
6.342 - friend class Edge;
6.343 - friend class OutEdgeIt;
6.344 - friend class InEdgeIt;
6.345 - friend class SymEdgeIt;
6.346 - //public: //FIXME: It is required by op= of NodeIt
6.347 - protected:
6.348 - node_item* node;
6.349 - protected:
6.350 - friend int ListGraph::id(Node v) const;
6.351 - public:
6.352 - Node() /*: node(0)*/ { }
6.353 - Node(const Invalid&) : node(0) { }
6.354 - protected:
6.355 - Node(node_item* _node) : node(_node) { }
6.356 - bool valid() const { return (node); }
6.357 - public:
6.358 - //void makeInvalid() { node=0; }
6.359 - friend bool operator==(Node u, Node v) { return v.node==u.node; }
6.360 - friend bool operator!=(Node u, Node v) { return v.node!=u.node; }
6.361 - friend std::ostream& operator<<(std::ostream& os, const Node& i);
6.362 - };
6.363 -
6.364 - class NodeIt : public Node {
6.365 - friend class ListGraph;
6.366 - //protected:
6.367 - public: //for everybody but marci
6.368 - NodeIt(const ListGraph& G) : Node(G._first_node) { }
6.369 - public:
6.370 - NodeIt() : Node() { }
6.371 - NodeIt(const Invalid& i) : Node(i) { }
6.372 - protected:
6.373 - NodeIt(node_item* v) : Node(v) { }
6.374 - NodeIt& operator++() { node=node->_next_node; return *this; }
6.375 - //FIXME::
6.376 - // NodeIt& operator=(const Node& e)
6.377 - // { node=e.node; return *this; }
6.378 - };
6.379 -
6.380 - class Edge {
6.381 - friend class ListGraph;
6.382 - template <typename T> friend class EdgeMap;
6.383 -
6.384 - friend class Node;
6.385 - friend class NodeIt;
6.386 - protected:
6.387 - edge_item* edge;
6.388 - friend int ListGraph::id(Edge e) const;
6.389 - public:
6.390 - Edge() /*: edge(0)*/ { }
6.391 - Edge(const Invalid&) : edge(0) { }
6.392 - //Edge() { }
6.393 - protected:
6.394 - Edge(edge_item* _edge) : edge(_edge) { }
6.395 - bool valid() const { return (edge); }
6.396 - public:
6.397 - //void makeInvalid() { edge=0; }
6.398 - friend bool operator==(Edge u, Edge v) { return v.edge==u.edge; }
6.399 - friend bool operator!=(Edge u, Edge v) { return v.edge!=u.edge; }
6.400 - protected:
6.401 - Node tailNode() const { return Node(edge->_tail); }
6.402 - Node headNode() const { return Node(edge->_head); }
6.403 - public:
6.404 - friend std::ostream& operator<<(std::ostream& os, const Edge& i);
6.405 - };
6.406 -
6.407 - class EdgeIt : public Edge {
6.408 - friend class ListGraph;
6.409 - //protected:
6.410 - public: //for alpar
6.411 - EdgeIt(const ListGraph& G) {
6.412 - node_item* v=G._first_node;
6.413 - if (v) edge=v->_first_out_edge; else edge=0;
6.414 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
6.415 - }
6.416 - public:
6.417 - EdgeIt() : Edge() { }
6.418 - EdgeIt(const Invalid& i) : Edge(i) { }
6.419 - protected:
6.420 - EdgeIt(edge_item* _e) : Edge(_e) { }
6.421 - EdgeIt& operator++() {
6.422 - node_item* v=edge->_tail;
6.423 - edge=edge->_next_out;
6.424 - while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
6.425 - return *this;
6.426 - }
6.427 - };
6.428 -
6.429 - class OutEdgeIt : public Edge {
6.430 - friend class ListGraph;
6.431 - //node_item* v;
6.432 - //protected:
6.433 - protected: //for alpar
6.434 - OutEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
6.435 - public:
6.436 - OutEdgeIt() : Edge()/*, v(0)*/ { }
6.437 - OutEdgeIt(const Invalid& i) : Edge(i) { }
6.438 - OutEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_out_edge; }
6.439 - protected:
6.440 - OutEdgeIt& operator++() { edge=edge->_next_out; return *this; }
6.441 - protected:
6.442 - Node aNode() const { return Node(edge->_tail); }
6.443 - Node bNode() const { return Node(edge->_head); }
6.444 - };
6.445 -
6.446 - class InEdgeIt : public Edge {
6.447 - friend class ListGraph;
6.448 - //node_item* v;
6.449 - //protected:
6.450 - protected: //for alpar
6.451 - InEdgeIt(const Node& _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
6.452 - public:
6.453 - InEdgeIt() : Edge()/*, v(0)*/ { }
6.454 - InEdgeIt(const Invalid& i) : Edge(i) { }
6.455 - InEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ { edge=_v.node->_first_in_edge; }
6.456 - protected:
6.457 - InEdgeIt& operator++() { edge=edge->_next_in; return *this; }
6.458 - protected:
6.459 - Node aNode() const { return Node(edge->_head); }
6.460 - Node bNode() const { return Node(edge->_tail); }
6.461 - };
6.462 -
6.463 - class SymEdgeIt : public Edge {
6.464 - friend class ListGraph;
6.465 - bool out_or_in; //1 iff out, 0 iff in
6.466 - //node_item* v;
6.467 - //protected:
6.468 - public: //for alpar
6.469 - SymEdgeIt(const Node& _v) /*: v(_v.node)*/ {
6.470 - out_or_in=1;
6.471 - edge=_v.node->_first_out_edge;
6.472 - if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
6.473 - }
6.474 - public:
6.475 - SymEdgeIt() : Edge() /*, v(0)*/ { }
6.476 - SymEdgeIt(const Invalid& i) : Edge(i) { }
6.477 - SymEdgeIt(const ListGraph&, Node _v) /*: v(_v.node)*/ {
6.478 - out_or_in=1;
6.479 - edge=_v.node->_first_out_edge;
6.480 - if (!edge) { edge=_v.node->_first_in_edge; out_or_in=0; }
6.481 - }
6.482 - protected:
6.483 - SymEdgeIt& operator++() {
6.484 - if (out_or_in) {
6.485 - node_item* v=edge->_tail;
6.486 - edge=edge->_next_out;
6.487 - if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
6.488 - } else {
6.489 - edge=edge->_next_in;
6.490 - }
6.491 - return *this;
6.492 - }
6.493 - protected:
6.494 - Node aNode() const {
6.495 - return (out_or_in) ? Node(edge->_tail) : Node(edge->_head); }
6.496 - Node bNode() const {
6.497 - return (out_or_in) ? Node(edge->_head) : Node(edge->_tail); }
6.498 - };
6.499 -
6.500 - };
6.501 -
6.502 - // template< typename T >
6.503 - // T ListGraph::first() const {
6.504 - // std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>();" << std::endl;
6.505 - // return T();
6.506 - // }
6.507 -
6.508 - // template<>
6.509 - // ListGraph::NodeIt ListGraph::first<ListGraph::NodeIt>() const {
6.510 - // return firstNode();
6.511 - // }
6.512 -
6.513 - // template<>
6.514 - // ListGraph::EdgeIt ListGraph::first<ListGraph::EdgeIt>() const {
6.515 - // return firstEdge();
6.516 - // }
6.517 -
6.518 - // template< typename T >
6.519 - // T ListGraph::first(ListGraph::Node v) const {
6.520 - // std::cerr << "Invalid use of template<typemane T> T ListGraph::first<T>(ListGRaph::Node);" << std::endl;
6.521 - // return T();
6.522 - // }
6.523 -
6.524 - // template<>
6.525 - // ListGraph::OutEdgeIt ListGraph::first<ListGraph::OutEdgeIt>(const ListGraph::Node v) const {
6.526 - // return firstOutEdge(v);
6.527 - // }
6.528 -
6.529 - // template<>
6.530 - // ListGraph::InEdgeIt ListGraph::first<ListGraph::InEdgeIt>(const ListGraph::Node v) const {
6.531 - // return firstInEdge(v);
6.532 - // }
6.533 -
6.534 - // template<>
6.535 - // ListGraph::SymEdgeIt ListGraph::first<ListGraph::SymEdgeIt>(const ListGraph::Node v) const {
6.536 - // return firstSymEdge(v);
6.537 - // }
6.538 -
6.539 -
6.540 -} //namespace hugo
6.541 -
6.542 -#endif //HUGO_LIST_GRAPH_H
7.1 --- a/src/work/deba/vector_map_factory.h Tue Jul 06 13:57:01 2004 +0000
7.2 +++ b/src/work/deba/vector_map_factory.h Fri Jul 09 07:33:12 2004 +0000
7.3 @@ -3,25 +3,25 @@
7.4
7.5 #include <vector>
7.6
7.7 -#include "map_registry.h"
7.8 -
7.9 namespace hugo {
7.10
7.11 template <typename MapRegistry>
7.12 - class VectorMapFactory {
7.13 - public:
7.14 + class VectorMapFactory {
7.15 + public:
7.16
7.17 typedef typename MapRegistry::Graph Graph;
7.18 typedef typename MapRegistry::Key Key;
7.19 typedef typename MapRegistry::KeyIt KeyIt;
7.20
7.21 typedef typename MapRegistry::MapBase MapBase;
7.22 +
7.23
7.24 template <typename V>
7.25 class Map : public MapBase {
7.26 public:
7.27 typedef V Value;
7.28
7.29 + typedef std::vector<Value> Container;
7.30 Map() {}
7.31
7.32 Map(Graph& g, MapRegistry& r) : MapBase(g, r) {
7.33 @@ -34,21 +34,16 @@
7.34 }
7.35
7.36
7.37 - Value& operator[](const Key& key) {
7.38 + typename Container::reference operator[](const Key& key) {
7.39 int id = graph->id(key);
7.40 return container[id];
7.41 }
7.42
7.43 - const Value& operator[](const Key& key) const {
7.44 + typename Container::const_reference operator[](const Key& key) const {
7.45 int id = graph->id(key);
7.46 return container[id];
7.47 }
7.48
7.49 - const Value& get(const Key& key) const {
7.50 - int id = graph->id(key);
7.51 - return container[id];
7.52 - }
7.53 -
7.54 void set(const Key& key, const Value& val) {
7.55 int id = graph->id(key);
7.56 container[id] = val;
7.57 @@ -63,11 +58,37 @@
7.58
7.59 void erase(const Key& key) {}
7.60
7.61 + class const_iterator {
7.62 +
7.63 + private:
7.64 +
7.65 + };
7.66 +
7.67 + class iterator {
7.68 + public:
7.69 + iterator() {}
7.70 +
7.71 + std::pair<const Key&, Value&> operator*() {
7.72 + return std::pair<const Key&, Value&>(static_cast<Key&>(it), map[it]);
7.73 + }
7.74 +
7.75 + iterator& operator++() { ++it; return *this; }
7.76 + iterator operator++(int) { iterator tmp(it); ++it; return tmp; }
7.77 + private:
7.78 + Map& map;
7.79 + KeyIt it;
7.80 + };
7.81 +
7.82 private:
7.83 typedef std::vector<Value> Container;
7.84
7.85 Container container;
7.86 +
7.87 +
7.88 };
7.89 +
7.90 +
7.91 +
7.92
7.93 };
7.94 }