1.1 --- a/doc/Doxyfile Fri May 07 11:57:34 2004 +0000
1.2 +++ b/doc/Doxyfile Fri May 07 13:27:16 2004 +0000
1.3 @@ -396,7 +396,6 @@
1.4 groups.dox \
1.5 ../src/hugo \
1.6 ../src/hugo/skeletons \
1.7 - ../src/work/alpar/list_graph.h \
1.8 ../src/work/athos/minlengthpaths.h \
1.9 ../src/work/klao/path.h \
1.10 ../src/work/jacint/max_flow.h \
2.1 --- a/src/hugo/Makefile.am Fri May 07 11:57:34 2004 +0000
2.2 +++ b/src/hugo/Makefile.am Fri May 07 13:27:16 2004 +0000
2.3 @@ -5,6 +5,7 @@
2.4 error.h \
2.5 fib_heap.h \
2.6 invalid.h \
2.7 + list_graph.h \
2.8 maps.h \
2.9 smart_graph.h \
2.10 time_measure.h \
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/hugo/list_graph.h Fri May 07 13:27:16 2004 +0000
3.3 @@ -0,0 +1,1597 @@
3.4 +// -*- mode:C++ -*-
3.5 +
3.6 +#ifndef HUGO_LIST_GRAPH_H
3.7 +#define HUGO_LIST_GRAPH_H
3.8 +
3.9 +///\ingroup graphs
3.10 +///\file
3.11 +///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
3.12 +
3.13 +#include <vector>
3.14 +#include <limits.h>
3.15 +
3.16 +#include <hugo/invalid.h>
3.17 +
3.18 +namespace hugo {
3.19 +
3.20 +/// \addtogroup graphs
3.21 +/// @{
3.22 +
3.23 + class SymListGraph;
3.24 +
3.25 + ///A list graph class.
3.26 +
3.27 + ///This is a simple and fast erasable graph implementation.
3.28 + ///
3.29 + ///It conforms to the graph interface documented under
3.30 + ///the description of \ref GraphSkeleton.
3.31 + ///\sa \ref GraphSkeleton.
3.32 + class ListGraph {
3.33 +
3.34 + //Nodes are double linked.
3.35 + //The free nodes are only single linked using the "next" field.
3.36 + struct NodeT
3.37 + {
3.38 + int first_in,first_out;
3.39 + int prev, next;
3.40 + // NodeT() {}
3.41 + };
3.42 + //Edges are double linked.
3.43 + //The free edges are only single linked using the "next_in" field.
3.44 + struct EdgeT
3.45 + {
3.46 + int head, tail;
3.47 + int prev_in, prev_out;
3.48 + int next_in, next_out;
3.49 + //FIXME: is this necessary?
3.50 + // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
3.51 + };
3.52 +
3.53 + std::vector<NodeT> nodes;
3.54 + //The first node
3.55 + int first_node;
3.56 + //The first free node
3.57 + int first_free_node;
3.58 + std::vector<EdgeT> edges;
3.59 + //The first free edge
3.60 + int first_free_edge;
3.61 +
3.62 + protected:
3.63 +
3.64 + template <typename Key> class DynMapBase
3.65 + {
3.66 + protected:
3.67 + const ListGraph* G;
3.68 + public:
3.69 + virtual void add(const Key k) = 0;
3.70 + virtual void erase(const Key k) = 0;
3.71 + DynMapBase(const ListGraph &_G) : G(&_G) {}
3.72 + virtual ~DynMapBase() {}
3.73 + friend class ListGraph;
3.74 + };
3.75 +
3.76 + public:
3.77 + template <typename T> class EdgeMap;
3.78 + template <typename T> class NodeMap;
3.79 +
3.80 + class Node;
3.81 + class Edge;
3.82 +
3.83 + // protected:
3.84 + // HELPME:
3.85 + protected:
3.86 + ///\bug It must be public because of SymEdgeMap.
3.87 + ///
3.88 + mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
3.89 + ///\bug It must be public because of SymEdgeMap.
3.90 + ///
3.91 + mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
3.92 +
3.93 + public:
3.94 +
3.95 + class NodeIt;
3.96 + class EdgeIt;
3.97 + class OutEdgeIt;
3.98 + class InEdgeIt;
3.99 +
3.100 + template <typename T> class NodeMap;
3.101 + template <typename T> class EdgeMap;
3.102 +
3.103 + public:
3.104 +
3.105 + ListGraph() : nodes(), first_node(-1),
3.106 + first_free_node(-1), edges(), first_free_edge(-1) {}
3.107 + ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
3.108 + first_free_node(_g.first_free_node),
3.109 + edges(_g.edges),
3.110 + first_free_edge(_g.first_free_edge) {}
3.111 +
3.112 + ~ListGraph()
3.113 + {
3.114 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.115 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
3.116 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
3.117 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
3.118 + }
3.119 +
3.120 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
3.121 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
3.122 +
3.123 + ///\bug This function does something different than
3.124 + ///its name would suggests...
3.125 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
3.126 + ///\bug This function does something different than
3.127 + ///its name would suggests...
3.128 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
3.129 +
3.130 + Node tail(Edge e) const { return edges[e.n].tail; }
3.131 + Node head(Edge e) const { return edges[e.n].head; }
3.132 +
3.133 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
3.134 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
3.135 +
3.136 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
3.137 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
3.138 +
3.139 + NodeIt& first(NodeIt& v) const {
3.140 + v=NodeIt(*this); return v; }
3.141 + EdgeIt& first(EdgeIt& e) const {
3.142 + e=EdgeIt(*this); return e; }
3.143 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
3.144 + e=OutEdgeIt(*this,v); return e; }
3.145 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
3.146 + e=InEdgeIt(*this,v); return e; }
3.147 +
3.148 +// template< typename It >
3.149 +// It first() const { It e; first(e); return e; }
3.150 +
3.151 +// template< typename It >
3.152 +// It first(Node v) const { It e; first(e,v); return e; }
3.153 +
3.154 + bool valid(Edge e) const { return e.n!=-1; }
3.155 + bool valid(Node n) const { return n.n!=-1; }
3.156 +
3.157 + void setInvalid(Edge &e) { e.n=-1; }
3.158 + void setInvalid(Node &n) { n.n=-1; }
3.159 +
3.160 + template <typename It> It getNext(It it) const
3.161 + { It tmp(it); return next(tmp); }
3.162 +
3.163 + NodeIt& next(NodeIt& it) const {
3.164 + it.n=nodes[it.n].next;
3.165 + return it;
3.166 + }
3.167 + OutEdgeIt& next(OutEdgeIt& it) const
3.168 + { it.n=edges[it.n].next_out; return it; }
3.169 + InEdgeIt& next(InEdgeIt& it) const
3.170 + { it.n=edges[it.n].next_in; return it; }
3.171 + EdgeIt& next(EdgeIt& it) const {
3.172 + if(edges[it.n].next_in!=-1) {
3.173 + it.n=edges[it.n].next_in;
3.174 + }
3.175 + else {
3.176 + int n;
3.177 + for(n=nodes[edges[it.n].head].next;
3.178 + n!=-1 && nodes[n].first_in == -1;
3.179 + n = nodes[n].next) ;
3.180 + it.n = (n==-1)?-1:nodes[n].first_in;
3.181 + }
3.182 + return it;
3.183 + }
3.184 +
3.185 + int id(Node v) const { return v.n; }
3.186 + int id(Edge e) const { return e.n; }
3.187 +
3.188 + /// Adds a new node to the graph.
3.189 +
3.190 + /// \todo It adds the nodes in a reversed order.
3.191 + /// (i.e. the lastly added node becomes the first.)
3.192 + Node addNode() {
3.193 + int n;
3.194 +
3.195 + if(first_free_node==-1)
3.196 + {
3.197 + n = nodes.size();
3.198 + nodes.push_back(NodeT());
3.199 + }
3.200 + else {
3.201 + n = first_free_node;
3.202 + first_free_node = nodes[n].next;
3.203 + }
3.204 +
3.205 + nodes[n].next = first_node;
3.206 + if(first_node != -1) nodes[first_node].prev = n;
3.207 + first_node = n;
3.208 + nodes[n].prev = -1;
3.209 +
3.210 + nodes[n].first_in = nodes[n].first_out = -1;
3.211 +
3.212 + Node nn; nn.n=n;
3.213 +
3.214 + //Update dynamic maps
3.215 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.216 + i!=dyn_node_maps.end(); ++i) (**i).add(nn);
3.217 +
3.218 + return nn;
3.219 + }
3.220 +
3.221 + Edge addEdge(Node u, Node v) {
3.222 + int n;
3.223 +
3.224 + if(first_free_edge==-1)
3.225 + {
3.226 + n = edges.size();
3.227 + edges.push_back(EdgeT());
3.228 + }
3.229 + else {
3.230 + n = first_free_edge;
3.231 + first_free_edge = edges[n].next_in;
3.232 + }
3.233 +
3.234 + edges[n].tail = u.n; edges[n].head = v.n;
3.235 +
3.236 + edges[n].next_out = nodes[u.n].first_out;
3.237 + if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
3.238 + edges[n].next_in = nodes[v.n].first_in;
3.239 + if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
3.240 + edges[n].prev_in = edges[n].prev_out = -1;
3.241 +
3.242 + nodes[u.n].first_out = nodes[v.n].first_in = n;
3.243 +
3.244 + Edge e; e.n=n;
3.245 +
3.246 + //Update dynamic maps
3.247 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
3.248 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
3.249 +
3.250 + return e;
3.251 + }
3.252 +
3.253 + private:
3.254 + void eraseEdge(int n) {
3.255 +
3.256 + if(edges[n].next_in!=-1)
3.257 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
3.258 + if(edges[n].prev_in!=-1)
3.259 + edges[edges[n].prev_in].next_in = edges[n].next_in;
3.260 + else nodes[edges[n].head].first_in = edges[n].next_in;
3.261 +
3.262 + if(edges[n].next_out!=-1)
3.263 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
3.264 + if(edges[n].prev_out!=-1)
3.265 + edges[edges[n].prev_out].next_out = edges[n].next_out;
3.266 + else nodes[edges[n].tail].first_out = edges[n].next_out;
3.267 +
3.268 + edges[n].next_in = first_free_edge;
3.269 + first_free_edge = -1;
3.270 +
3.271 + //Update dynamic maps
3.272 + Edge e; e.n=n;
3.273 + for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
3.274 + i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
3.275 + }
3.276 +
3.277 + public:
3.278 +
3.279 + void erase(Node nn) {
3.280 + int n=nn.n;
3.281 +
3.282 + int m;
3.283 + while((m=nodes[n].first_in)!=-1) eraseEdge(m);
3.284 + while((m=nodes[n].first_out)!=-1) eraseEdge(m);
3.285 +
3.286 + if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
3.287 + if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
3.288 + else first_node = nodes[n].next;
3.289 +
3.290 + nodes[n].next = first_free_node;
3.291 + first_free_node = n;
3.292 +
3.293 + //Update dynamic maps
3.294 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.295 + i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
3.296 + }
3.297 +
3.298 + void erase(Edge e) { eraseEdge(e.n); }
3.299 +
3.300 + ///\bug Dynamic maps must be updated!
3.301 + ///
3.302 + void clear() {
3.303 + nodes.clear();edges.clear();
3.304 + first_node=first_free_node=first_free_edge=-1;
3.305 + }
3.306 +
3.307 + class Node {
3.308 + friend class ListGraph;
3.309 + template <typename T> friend class NodeMap;
3.310 +
3.311 + friend class Edge;
3.312 + friend class OutEdgeIt;
3.313 + friend class InEdgeIt;
3.314 + friend class SymEdge;
3.315 +
3.316 + protected:
3.317 + int n;
3.318 + friend int ListGraph::id(Node v) const;
3.319 + Node(int nn) {n=nn;}
3.320 + public:
3.321 + Node() {}
3.322 + Node (Invalid) { n=-1; }
3.323 + bool operator==(const Node i) const {return n==i.n;}
3.324 + bool operator!=(const Node i) const {return n!=i.n;}
3.325 + bool operator<(const Node i) const {return n<i.n;}
3.326 + };
3.327 +
3.328 + class NodeIt : public Node {
3.329 + friend class ListGraph;
3.330 + public:
3.331 + NodeIt() : Node() { }
3.332 + NodeIt(Invalid i) : Node(i) { }
3.333 + NodeIt(const ListGraph& G) : Node(G.first_node) { }
3.334 + };
3.335 +
3.336 + class Edge {
3.337 + friend class ListGraph;
3.338 + template <typename T> friend class EdgeMap;
3.339 +
3.340 + //template <typename T> friend class SymListGraph::SymEdgeMap;
3.341 + //friend Edge SymListGraph::opposite(Edge) const;
3.342 +
3.343 + friend class Node;
3.344 + friend class NodeIt;
3.345 + protected:
3.346 + int n;
3.347 + friend int ListGraph::id(Edge e) const;
3.348 +
3.349 + Edge(int nn) {n=nn;}
3.350 + public:
3.351 + Edge() { }
3.352 + Edge (Invalid) { n=-1; }
3.353 + bool operator==(const Edge i) const {return n==i.n;}
3.354 + bool operator!=(const Edge i) const {return n!=i.n;}
3.355 + bool operator<(const Edge i) const {return n<i.n;}
3.356 + ///\bug This is a workaround until somebody tells me how to
3.357 + ///make class \c SymListGraph::SymEdgeMap friend of Edge
3.358 + int &idref() {return n;}
3.359 + const int &idref() const {return n;}
3.360 + };
3.361 +
3.362 + class EdgeIt : public Edge {
3.363 + friend class ListGraph;
3.364 + public:
3.365 + EdgeIt(const ListGraph& G) : Edge() {
3.366 + int m;
3.367 + for(m=G.first_node;
3.368 + m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
3.369 + n = (m==-1)?-1:G.nodes[m].first_in;
3.370 + }
3.371 + EdgeIt (Invalid i) : Edge(i) { }
3.372 + EdgeIt() : Edge() { }
3.373 + ///\bug This is a workaround until somebody tells me how to
3.374 + ///make class \c SymListGraph::SymEdgeMap friend of Edge
3.375 + int &idref() {return n;}
3.376 + };
3.377 +
3.378 + class OutEdgeIt : public Edge {
3.379 + friend class ListGraph;
3.380 + public:
3.381 + OutEdgeIt() : Edge() { }
3.382 + OutEdgeIt (Invalid i) : Edge(i) { }
3.383 +
3.384 + OutEdgeIt(const ListGraph& G,const Node v)
3.385 + : Edge(G.nodes[v.n].first_out) {}
3.386 + };
3.387 +
3.388 + class InEdgeIt : public Edge {
3.389 + friend class ListGraph;
3.390 + public:
3.391 + InEdgeIt() : Edge() { }
3.392 + InEdgeIt (Invalid i) : Edge(i) { }
3.393 + InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
3.394 + };
3.395 +
3.396 + template <typename T> class NodeMap : public DynMapBase<Node>
3.397 + {
3.398 + std::vector<T> container;
3.399 +
3.400 + public:
3.401 + typedef T ValueType;
3.402 + typedef Node KeyType;
3.403 +
3.404 + NodeMap(const ListGraph &_G) :
3.405 + DynMapBase<Node>(_G), container(_G.maxNodeId())
3.406 + {
3.407 + G->dyn_node_maps.push_back(this);
3.408 + }
3.409 + NodeMap(const ListGraph &_G,const T &t) :
3.410 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
3.411 + {
3.412 + G->dyn_node_maps.push_back(this);
3.413 + }
3.414 +
3.415 + NodeMap(const NodeMap<T> &m) :
3.416 + DynMapBase<Node>(*m.G), container(m.container)
3.417 + {
3.418 + G->dyn_node_maps.push_back(this);
3.419 + }
3.420 +
3.421 + template<typename TT> friend class NodeMap;
3.422 +
3.423 + ///\todo It can copy between different types.
3.424 + ///
3.425 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
3.426 + DynMapBase<Node>(*m.G)
3.427 + {
3.428 + G->dyn_node_maps.push_back(this);
3.429 + typename std::vector<TT>::const_iterator i;
3.430 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.431 + i!=m.container.end();
3.432 + i++)
3.433 + container.push_back(*i);
3.434 + }
3.435 + ~NodeMap()
3.436 + {
3.437 + if(G) {
3.438 + std::vector<DynMapBase<Node>* >::iterator i;
3.439 + for(i=G->dyn_node_maps.begin();
3.440 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
3.441 + //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
3.442 + //A better way to do that: (Is this really important?)
3.443 + if(*i==this) {
3.444 + *i=G->dyn_node_maps.back();
3.445 + G->dyn_node_maps.pop_back();
3.446 + }
3.447 + }
3.448 + }
3.449 +
3.450 + void add(const Node k)
3.451 + {
3.452 + if(k.n>=int(container.size())) container.resize(k.n+1);
3.453 + }
3.454 +
3.455 + void erase(const Node) { }
3.456 +
3.457 + void set(Node n, T a) { container[n.n]=a; }
3.458 + //'T& operator[](Node n)' would be wrong here
3.459 + typename std::vector<T>::reference
3.460 + operator[](Node n) { return container[n.n]; }
3.461 + //'const T& operator[](Node n)' would be wrong here
3.462 + typename std::vector<T>::const_reference
3.463 + operator[](Node n) const { return container[n.n]; }
3.464 +
3.465 + ///\warning There is no safety check at all!
3.466 + ///Using operator = between maps attached to different graph may
3.467 + ///cause serious problem.
3.468 + ///\todo Is this really so?
3.469 + ///\todo It can copy between different types.
3.470 + const NodeMap<T>& operator=(const NodeMap<T> &m)
3.471 + {
3.472 + container = m.container;
3.473 + return *this;
3.474 + }
3.475 + template<typename TT>
3.476 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
3.477 + {
3.478 + std::copy(m.container.begin(), m.container.end(), container.begin());
3.479 + return *this;
3.480 + }
3.481 +
3.482 + void update() {} //Useless for Dynamic Maps
3.483 + void update(T a) {} //Useless for Dynamic Maps
3.484 + };
3.485 +
3.486 + template <typename T> class EdgeMap : public DynMapBase<Edge>
3.487 + {
3.488 + std::vector<T> container;
3.489 +
3.490 + public:
3.491 + typedef T ValueType;
3.492 + typedef Edge KeyType;
3.493 +
3.494 + EdgeMap(const ListGraph &_G) :
3.495 + DynMapBase<Edge>(_G), container(_G.maxEdgeId())
3.496 + {
3.497 + //FIXME: What if there are empty Id's?
3.498 + //FIXME: Can I use 'this' in a constructor?
3.499 + G->dyn_edge_maps.push_back(this);
3.500 + }
3.501 + EdgeMap(const ListGraph &_G,const T &t) :
3.502 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
3.503 + {
3.504 + G->dyn_edge_maps.push_back(this);
3.505 + }
3.506 + EdgeMap(const EdgeMap<T> &m) :
3.507 + DynMapBase<Edge>(*m.G), container(m.container)
3.508 + {
3.509 + G->dyn_edge_maps.push_back(this);
3.510 + }
3.511 +
3.512 + template<typename TT> friend class EdgeMap;
3.513 +
3.514 + ///\todo It can copy between different types.
3.515 + ///
3.516 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
3.517 + DynMapBase<Edge>(*m.G)
3.518 + {
3.519 + G->dyn_edge_maps.push_back(this);
3.520 + typename std::vector<TT>::const_iterator i;
3.521 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.522 + i!=m.container.end();
3.523 + i++)
3.524 + container.push_back(*i);
3.525 + }
3.526 + ~EdgeMap()
3.527 + {
3.528 + if(G) {
3.529 + std::vector<DynMapBase<Edge>* >::iterator i;
3.530 + for(i=G->dyn_edge_maps.begin();
3.531 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
3.532 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
3.533 + //A better way to do that: (Is this really important?)
3.534 + if(*i==this) {
3.535 + *i=G->dyn_edge_maps.back();
3.536 + G->dyn_edge_maps.pop_back();
3.537 + }
3.538 + }
3.539 + }
3.540 +
3.541 + void add(const Edge k)
3.542 + {
3.543 + if(k.n>=int(container.size())) container.resize(k.n+1);
3.544 + }
3.545 + void erase(const Edge) { }
3.546 +
3.547 + void set(Edge n, T a) { container[n.n]=a; }
3.548 + //T get(Edge n) const { return container[n.n]; }
3.549 + typename std::vector<T>::reference
3.550 + operator[](Edge n) { return container[n.n]; }
3.551 + typename std::vector<T>::const_reference
3.552 + operator[](Edge n) const { return container[n.n]; }
3.553 +
3.554 + ///\warning There is no safety check at all!
3.555 + ///Using operator = between maps attached to different graph may
3.556 + ///cause serious problem.
3.557 + ///\todo Is this really so?
3.558 + ///\todo It can copy between different types.
3.559 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
3.560 + {
3.561 + container = m.container;
3.562 + return *this;
3.563 + }
3.564 + template<typename TT>
3.565 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
3.566 + {
3.567 + std::copy(m.container.begin(), m.container.end(), container.begin());
3.568 + return *this;
3.569 + }
3.570 +
3.571 + void update() {} //Useless for DynMaps
3.572 + void update(T a) {} //Useless for DynMaps
3.573 + };
3.574 +
3.575 + };
3.576 +
3.577 + ///Graph for bidirectional edges.
3.578 +
3.579 + ///The purpose of this graph structure is to handle graphs
3.580 + ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
3.581 + ///of oppositely directed edges.
3.582 + ///There is a new edge map type called
3.583 + ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
3.584 + ///that complements this
3.585 + ///feature by
3.586 + ///storing shared values for the edge pairs. The usual
3.587 + ///\ref GraphSkeleton::EdgeMap "EdgeMap"
3.588 + ///can be used
3.589 + ///as well.
3.590 + ///
3.591 + ///The oppositely directed edge can also be obtained easily
3.592 + ///using \ref opposite.
3.593 + ///
3.594 + ///Here erase(Edge) deletes a pair of edges.
3.595 + ///
3.596 + ///\todo this date structure need some reconsiderations. Maybe it
3.597 + ///should be implemented independently from ListGraph.
3.598 +
3.599 + class SymListGraph : public ListGraph
3.600 + {
3.601 + public:
3.602 + template<typename T> class SymEdgeMap;
3.603 + template<typename T> friend class SymEdgeMap;
3.604 +
3.605 + SymListGraph() : ListGraph() { }
3.606 + SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
3.607 + ///Adds a pair of oppositely directed edges to the graph.
3.608 + Edge addEdge(Node u, Node v)
3.609 + {
3.610 + Edge e = ListGraph::addEdge(u,v);
3.611 + ListGraph::addEdge(v,u);
3.612 + return e;
3.613 + }
3.614 +
3.615 + void erase(Node n) { ListGraph::erase(n); }
3.616 + ///The oppositely directed edge.
3.617 +
3.618 + ///Returns the oppositely directed
3.619 + ///pair of the edge \c e.
3.620 + Edge opposite(Edge e) const
3.621 + {
3.622 + Edge f;
3.623 + f.idref() = e.idref() - 2*(e.idref()%2) + 1;
3.624 + return f;
3.625 + }
3.626 +
3.627 + ///Removes a pair of oppositely directed edges to the graph.
3.628 + void erase(Edge e) {
3.629 + ListGraph::erase(opposite(e));
3.630 + ListGraph::erase(e);
3.631 + }
3.632 +
3.633 + ///Common data storage for the edge pairs.
3.634 +
3.635 + ///This map makes it possible to store data shared by the oppositely
3.636 + ///directed pairs of edges.
3.637 + template <typename T> class SymEdgeMap : public DynMapBase<Edge>
3.638 + {
3.639 + std::vector<T> container;
3.640 +
3.641 + public:
3.642 + typedef T ValueType;
3.643 + typedef Edge KeyType;
3.644 +
3.645 + SymEdgeMap(const SymListGraph &_G) :
3.646 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
3.647 + {
3.648 + static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
3.649 + }
3.650 + SymEdgeMap(const SymListGraph &_G,const T &t) :
3.651 + DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
3.652 + {
3.653 + G->dyn_edge_maps.push_back(this);
3.654 + }
3.655 +
3.656 + SymEdgeMap(const SymEdgeMap<T> &m) :
3.657 + DynMapBase<SymEdge>(*m.G), container(m.container)
3.658 + {
3.659 + G->dyn_node_maps.push_back(this);
3.660 + }
3.661 +
3.662 + // template<typename TT> friend class SymEdgeMap;
3.663 +
3.664 + ///\todo It can copy between different types.
3.665 + ///
3.666 +
3.667 + template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
3.668 + DynMapBase<SymEdge>(*m.G)
3.669 + {
3.670 + G->dyn_node_maps.push_back(this);
3.671 + typename std::vector<TT>::const_iterator i;
3.672 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.673 + i!=m.container.end();
3.674 + i++)
3.675 + container.push_back(*i);
3.676 + }
3.677 +
3.678 + ~SymEdgeMap()
3.679 + {
3.680 + if(G) {
3.681 + std::vector<DynMapBase<Edge>* >::iterator i;
3.682 + for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
3.683 + i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
3.684 + && *i!=this; ++i) ;
3.685 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
3.686 + //A better way to do that: (Is this really important?)
3.687 + if(*i==this) {
3.688 + *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
3.689 + static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
3.690 + }
3.691 + }
3.692 + }
3.693 +
3.694 + void add(const Edge k)
3.695 + {
3.696 + if(!k.idref()%2&&k.idref()/2>=int(container.size()))
3.697 + container.resize(k.idref()/2+1);
3.698 + }
3.699 + void erase(const Edge k) { }
3.700 +
3.701 + void set(Edge n, T a) { container[n.idref()/2]=a; }
3.702 + //T get(Edge n) const { return container[n.idref()/2]; }
3.703 + typename std::vector<T>::reference
3.704 + operator[](Edge n) { return container[n.idref()/2]; }
3.705 + typename std::vector<T>::const_reference
3.706 + operator[](Edge n) const { return container[n.idref()/2]; }
3.707 +
3.708 + ///\warning There is no safety check at all!
3.709 + ///Using operator = between maps attached to different graph may
3.710 + ///cause serious problem.
3.711 + ///\todo Is this really so?
3.712 + ///\todo It can copy between different types.
3.713 + const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
3.714 + {
3.715 + container = m.container;
3.716 + return *this;
3.717 + }
3.718 + template<typename TT>
3.719 + const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
3.720 + {
3.721 + std::copy(m.container.begin(), m.container.end(), container.begin());
3.722 + return *this;
3.723 + }
3.724 +
3.725 + void update() {} //Useless for DynMaps
3.726 + void update(T a) {} //Useless for DynMaps
3.727 +
3.728 + };
3.729 +
3.730 + };
3.731 +
3.732 +
3.733 + ///A graph class containing only nodes.
3.734 +
3.735 + ///This class implements a graph structure without edges.
3.736 + ///The most useful application of this class is to be the node set of an
3.737 + ///\ref EdgeSet class.
3.738 + ///
3.739 + ///It conforms to the graph interface documented under
3.740 + ///the description of \ref GraphSkeleton with the exception that you cannot
3.741 + ///add (or delete) edges. The usual edge iterators are exists, but they are
3.742 + ///always \ref INVALID.
3.743 + ///\sa \ref GraphSkeleton
3.744 + ///\sa \ref EdgeSet
3.745 + class NodeSet {
3.746 +
3.747 + //Nodes are double linked.
3.748 + //The free nodes are only single linked using the "next" field.
3.749 + struct NodeT
3.750 + {
3.751 + int first_in,first_out;
3.752 + int prev, next;
3.753 + // NodeT() {}
3.754 + };
3.755 +
3.756 + std::vector<NodeT> nodes;
3.757 + //The first node
3.758 + int first_node;
3.759 + //The first free node
3.760 + int first_free_node;
3.761 +
3.762 + protected:
3.763 +
3.764 + template <typename Key> class DynMapBase
3.765 + {
3.766 + protected:
3.767 + const NodeSet* G;
3.768 + public:
3.769 + virtual void add(const Key k) = 0;
3.770 + virtual void erase(const Key k) = 0;
3.771 + DynMapBase(const NodeSet &_G) : G(&_G) {}
3.772 + virtual ~DynMapBase() {}
3.773 + friend class NodeSet;
3.774 + };
3.775 +
3.776 + public:
3.777 + template <typename T> class EdgeMap;
3.778 + template <typename T> class NodeMap;
3.779 +
3.780 + class Node;
3.781 + class Edge;
3.782 +
3.783 + // protected:
3.784 + // HELPME:
3.785 + protected:
3.786 + ///\bug It must be public because of SymEdgeMap.
3.787 + ///
3.788 + mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
3.789 + //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
3.790 +
3.791 + public:
3.792 +
3.793 + class NodeIt;
3.794 + class EdgeIt;
3.795 + class OutEdgeIt;
3.796 + class InEdgeIt;
3.797 +
3.798 + template <typename T> class NodeMap;
3.799 + template <typename T> class EdgeMap;
3.800 +
3.801 + public:
3.802 +
3.803 + ///Default constructor
3.804 + NodeSet() : nodes(), first_node(-1),
3.805 + first_free_node(-1) {}
3.806 + ///Copy constructor
3.807 + NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
3.808 + first_free_node(_g.first_free_node) {}
3.809 +
3.810 + ~NodeSet()
3.811 + {
3.812 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.813 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
3.814 + //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
3.815 + // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
3.816 + }
3.817 +
3.818 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
3.819 + int edgeNum() const { return 0; } //FIXME: What is this?
3.820 +
3.821 + ///\bug This function does something different than
3.822 + ///its name would suggests...
3.823 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
3.824 + ///\bug This function does something different than
3.825 + ///its name would suggests...
3.826 + int maxEdgeId() const { return 0; } //FIXME: What is this?
3.827 +
3.828 + Node tail(Edge e) const { return INVALID; }
3.829 + Node head(Edge e) const { return INVALID; }
3.830 +
3.831 + Node aNode(OutEdgeIt e) const { return INVALID; }
3.832 + Node aNode(InEdgeIt e) const { return INVALID; }
3.833 +
3.834 + Node bNode(OutEdgeIt e) const { return INVALID; }
3.835 + Node bNode(InEdgeIt e) const { return INVALID; }
3.836 +
3.837 + NodeIt& first(NodeIt& v) const {
3.838 + v=NodeIt(*this); return v; }
3.839 + EdgeIt& first(EdgeIt& e) const {
3.840 + e=EdgeIt(*this); return e; }
3.841 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
3.842 + e=OutEdgeIt(*this,v); return e; }
3.843 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
3.844 + e=InEdgeIt(*this,v); return e; }
3.845 +
3.846 +// template< typename It >
3.847 +// It first() const { It e; first(e); return e; }
3.848 +
3.849 +// template< typename It >
3.850 +// It first(Node v) const { It e; first(e,v); return e; }
3.851 +
3.852 + bool valid(Edge e) const { return false; }
3.853 + bool valid(Node n) const { return n.n!=-1; }
3.854 +
3.855 + void setInvalid(Edge &e) { }
3.856 + void setInvalid(Node &n) { n.n=-1; }
3.857 +
3.858 + template <typename It> It getNext(It it) const
3.859 + { It tmp(it); return next(tmp); }
3.860 +
3.861 + NodeIt& next(NodeIt& it) const {
3.862 + it.n=nodes[it.n].next;
3.863 + return it;
3.864 + }
3.865 + OutEdgeIt& next(OutEdgeIt& it) const { return it; }
3.866 + InEdgeIt& next(InEdgeIt& it) const { return it; }
3.867 + EdgeIt& next(EdgeIt& it) const { return it; }
3.868 +
3.869 + int id(Node v) const { return v.n; }
3.870 + int id(Edge e) const { return -1; }
3.871 +
3.872 + /// Adds a new node to the graph.
3.873 +
3.874 + /// \todo It adds the nodes in a reversed order.
3.875 + /// (i.e. the lastly added node becomes the first.)
3.876 + Node addNode() {
3.877 + int n;
3.878 +
3.879 + if(first_free_node==-1)
3.880 + {
3.881 + n = nodes.size();
3.882 + nodes.push_back(NodeT());
3.883 + }
3.884 + else {
3.885 + n = first_free_node;
3.886 + first_free_node = nodes[n].next;
3.887 + }
3.888 +
3.889 + nodes[n].next = first_node;
3.890 + if(first_node != -1) nodes[first_node].prev = n;
3.891 + first_node = n;
3.892 + nodes[n].prev = -1;
3.893 +
3.894 + nodes[n].first_in = nodes[n].first_out = -1;
3.895 +
3.896 + Node nn; nn.n=n;
3.897 +
3.898 + //Update dynamic maps
3.899 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.900 + i!=dyn_node_maps.end(); ++i) (**i).add(nn);
3.901 +
3.902 + return nn;
3.903 + }
3.904 +
3.905 + void erase(Node nn) {
3.906 + int n=nn.n;
3.907 +
3.908 + if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
3.909 + if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
3.910 + else first_node = nodes[n].next;
3.911 +
3.912 + nodes[n].next = first_free_node;
3.913 + first_free_node = n;
3.914 +
3.915 + //Update dynamic maps
3.916 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.917 + i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
3.918 + }
3.919 +
3.920 + ///\bug Dynamic maps must be updated!
3.921 + ///
3.922 + void clear() {
3.923 + nodes.clear();
3.924 + first_node = first_free_node = -1;
3.925 + }
3.926 +
3.927 + class Node {
3.928 + friend class NodeSet;
3.929 + template <typename T> friend class NodeMap;
3.930 +
3.931 + friend class Edge;
3.932 + friend class OutEdgeIt;
3.933 + friend class InEdgeIt;
3.934 +
3.935 + protected:
3.936 + int n;
3.937 + friend int NodeSet::id(Node v) const;
3.938 + Node(int nn) {n=nn;}
3.939 + public:
3.940 + Node() {}
3.941 + Node (Invalid i) { n=-1; }
3.942 + bool operator==(const Node i) const {return n==i.n;}
3.943 + bool operator!=(const Node i) const {return n!=i.n;}
3.944 + bool operator<(const Node i) const {return n<i.n;}
3.945 + };
3.946 +
3.947 + class NodeIt : public Node {
3.948 + friend class NodeSet;
3.949 + public:
3.950 + NodeIt(const NodeSet& G) : Node(G.first_node) { }
3.951 + NodeIt() : Node() { }
3.952 + };
3.953 +
3.954 + class Edge {
3.955 + //friend class NodeSet;
3.956 + //template <typename T> friend class EdgeMap;
3.957 +
3.958 + //template <typename T> friend class SymNodeSet::SymEdgeMap;
3.959 + //friend Edge SymNodeSet::opposite(Edge) const;
3.960 +
3.961 + // friend class Node;
3.962 + // friend class NodeIt;
3.963 + protected:
3.964 + //friend int NodeSet::id(Edge e) const;
3.965 + // Edge(int nn) {}
3.966 + public:
3.967 + Edge() { }
3.968 + Edge (Invalid) { }
3.969 + bool operator==(const Edge i) const {return true;}
3.970 + bool operator!=(const Edge i) const {return false;}
3.971 + bool operator<(const Edge i) const {return false;}
3.972 + ///\bug This is a workaround until somebody tells me how to
3.973 + ///make class \c SymNodeSet::SymEdgeMap friend of Edge
3.974 + // int idref() {return -1;}
3.975 + // int idref() const {return -1;}
3.976 + };
3.977 +
3.978 + class EdgeIt : public Edge {
3.979 + //friend class NodeSet;
3.980 + public:
3.981 + EdgeIt(const NodeSet& G) : Edge() { }
3.982 + EdgeIt (Invalid i) : Edge(i) { }
3.983 + EdgeIt() : Edge() { }
3.984 + ///\bug This is a workaround until somebody tells me how to
3.985 + ///make class \c SymNodeSet::SymEdgeMap friend of Edge
3.986 + // int idref() {return -1;}
3.987 + };
3.988 +
3.989 + class OutEdgeIt : public Edge {
3.990 + friend class NodeSet;
3.991 + public:
3.992 + OutEdgeIt() : Edge() { }
3.993 + OutEdgeIt (Invalid i) : Edge(i) { }
3.994 + OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
3.995 + };
3.996 +
3.997 + class InEdgeIt : public Edge {
3.998 + friend class NodeSet;
3.999 + public:
3.1000 + InEdgeIt() : Edge() { }
3.1001 + InEdgeIt (Invalid i) : Edge(i) { }
3.1002 + InEdgeIt(const NodeSet& G,Node v) :Edge() {}
3.1003 + };
3.1004 +
3.1005 + template <typename T> class NodeMap : public DynMapBase<Node>
3.1006 + {
3.1007 + std::vector<T> container;
3.1008 +
3.1009 + public:
3.1010 + typedef T ValueType;
3.1011 + typedef Node KeyType;
3.1012 +
3.1013 + NodeMap(const NodeSet &_G) :
3.1014 + DynMapBase<Node>(_G), container(_G.maxNodeId())
3.1015 + {
3.1016 + G->dyn_node_maps.push_back(this);
3.1017 + }
3.1018 + NodeMap(const NodeSet &_G,const T &t) :
3.1019 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
3.1020 + {
3.1021 + G->dyn_node_maps.push_back(this);
3.1022 + }
3.1023 +
3.1024 + NodeMap(const NodeMap<T> &m) :
3.1025 + DynMapBase<Node>(*m.G), container(m.container)
3.1026 + {
3.1027 + G->dyn_node_maps.push_back(this);
3.1028 + }
3.1029 +
3.1030 + template<typename TT> friend class NodeMap;
3.1031 +
3.1032 + ///\todo It can copy between different types.
3.1033 + ///
3.1034 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
3.1035 + DynMapBase<Node>(*m.G)
3.1036 + {
3.1037 + G->dyn_node_maps.push_back(this);
3.1038 + typename std::vector<TT>::const_iterator i;
3.1039 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.1040 + i!=m.container.end();
3.1041 + i++)
3.1042 + container.push_back(*i);
3.1043 + }
3.1044 + ~NodeMap()
3.1045 + {
3.1046 + if(G) {
3.1047 + std::vector<DynMapBase<Node>* >::iterator i;
3.1048 + for(i=G->dyn_node_maps.begin();
3.1049 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
3.1050 + //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
3.1051 + //A better way to do that: (Is this really important?)
3.1052 + if(*i==this) {
3.1053 + *i=G->dyn_node_maps.back();
3.1054 + G->dyn_node_maps.pop_back();
3.1055 + }
3.1056 + }
3.1057 + }
3.1058 +
3.1059 + void add(const Node k)
3.1060 + {
3.1061 + if(k.n>=int(container.size())) container.resize(k.n+1);
3.1062 + }
3.1063 +
3.1064 + void erase(const Node) { }
3.1065 +
3.1066 + void set(Node n, T a) { container[n.n]=a; }
3.1067 + //'T& operator[](Node n)' would be wrong here
3.1068 + typename std::vector<T>::reference
3.1069 + operator[](Node n) { return container[n.n]; }
3.1070 + //'const T& operator[](Node n)' would be wrong here
3.1071 + typename std::vector<T>::const_reference
3.1072 + operator[](Node n) const { return container[n.n]; }
3.1073 +
3.1074 + ///\warning There is no safety check at all!
3.1075 + ///Using operator = between maps attached to different graph may
3.1076 + ///cause serious problem.
3.1077 + ///\todo Is this really so?
3.1078 + ///\todo It can copy between different types.
3.1079 + const NodeMap<T>& operator=(const NodeMap<T> &m)
3.1080 + {
3.1081 + container = m.container;
3.1082 + return *this;
3.1083 + }
3.1084 + template<typename TT>
3.1085 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
3.1086 + {
3.1087 + std::copy(m.container.begin(), m.container.end(), container.begin());
3.1088 + return *this;
3.1089 + }
3.1090 +
3.1091 + void update() {} //Useless for Dynamic Maps
3.1092 + void update(T a) {} //Useless for Dynamic Maps
3.1093 + };
3.1094 +
3.1095 + template <typename T> class EdgeMap
3.1096 + {
3.1097 + public:
3.1098 + typedef T ValueType;
3.1099 + typedef Edge KeyType;
3.1100 +
3.1101 + EdgeMap(const NodeSet &) { }
3.1102 + EdgeMap(const NodeSet &,const T &) { }
3.1103 + EdgeMap(const EdgeMap<T> &) { }
3.1104 + // template<typename TT> friend class EdgeMap;
3.1105 +
3.1106 + ///\todo It can copy between different types.
3.1107 + ///
3.1108 + template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
3.1109 + ~EdgeMap() { }
3.1110 +
3.1111 + void add(const Edge ) { }
3.1112 + void erase(const Edge) { }
3.1113 +
3.1114 + void set(Edge, T) { }
3.1115 + //T get(Edge n) const { return container[n.n]; }
3.1116 + ValueType &operator[](Edge) { return *((T*)(NULL)); }
3.1117 + const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
3.1118 +
3.1119 + const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
3.1120 +
3.1121 + template<typename TT>
3.1122 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
3.1123 +
3.1124 + void update() {}
3.1125 + void update(T a) {}
3.1126 + };
3.1127 + };
3.1128 +
3.1129 +
3.1130 +
3.1131 + ///Graph structure using a node set of another graph.
3.1132 +
3.1133 + ///This structure can be used to establish another graph over a node set
3.1134 + /// of an existing one. The node iterator will go through the nodes of the
3.1135 + /// original graph, and the NodeMap's of both graphs will convert to
3.1136 + /// each other.
3.1137 + ///
3.1138 + ///\warning Adding or deleting nodes from the graph is not safe if an
3.1139 + ///\ref EdgeSet is currently attached to it!
3.1140 + ///
3.1141 + ///\todo Make it possible to add/delete edges from the base graph
3.1142 + ///(and from \ref EdgeSet, as well)
3.1143 + ///
3.1144 + ///\param GG The type of the graph which shares its node set with this class.
3.1145 + ///Its interface must conform with \ref GraphSkeleton.
3.1146 + ///
3.1147 + ///It conforms to the graph interface documented under
3.1148 + ///the description of \ref GraphSkeleton.
3.1149 + ///\sa \ref GraphSkeleton.
3.1150 + ///\sa \ref NodeSet.
3.1151 + template<typename GG>
3.1152 + class EdgeSet {
3.1153 +
3.1154 + typedef GG NodeGraphType;
3.1155 +
3.1156 + NodeGraphType &G;
3.1157 +
3.1158 + public:
3.1159 + class Node;
3.1160 + int id(Node v) const;
3.1161 +
3.1162 + class Node : public NodeGraphType::Node {
3.1163 + friend class EdgeSet;
3.1164 + // template <typename T> friend class NodeMap;
3.1165 +
3.1166 + friend class Edge;
3.1167 + friend class OutEdgeIt;
3.1168 + friend class InEdgeIt;
3.1169 + friend class SymEdge;
3.1170 +
3.1171 + public:
3.1172 + friend int EdgeSet::id(Node v) const;
3.1173 + // Node(int nn) {n=nn;}
3.1174 + public:
3.1175 + Node() : NodeGraphType::Node() {}
3.1176 + Node (Invalid i) : NodeGraphType::Node(i) {}
3.1177 + Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
3.1178 + };
3.1179 +
3.1180 + class NodeIt : public NodeGraphType::NodeIt {
3.1181 + friend class EdgeSet;
3.1182 + public:
3.1183 + NodeIt() : NodeGraphType::NodeIt() { }
3.1184 + NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
3.1185 + NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
3.1186 + NodeIt(const typename NodeGraphType::NodeIt &n)
3.1187 + : NodeGraphType::NodeIt(n) {}
3.1188 + operator Node() { return Node(*this);}
3.1189 + };
3.1190 +
3.1191 + private:
3.1192 + //Edges are double linked.
3.1193 + //The free edges are only single linked using the "next_in" field.
3.1194 + struct NodeT
3.1195 + {
3.1196 + int first_in,first_out;
3.1197 + NodeT() : first_in(-1), first_out(-1) { }
3.1198 + };
3.1199 +
3.1200 + struct EdgeT
3.1201 + {
3.1202 + Node head, tail;
3.1203 + int prev_in, prev_out;
3.1204 + int next_in, next_out;
3.1205 + };
3.1206 +
3.1207 +
3.1208 + typename NodeGraphType::template NodeMap<NodeT> nodes;
3.1209 +
3.1210 + std::vector<EdgeT> edges;
3.1211 + //The first free edge
3.1212 + int first_free_edge;
3.1213 +
3.1214 + protected:
3.1215 +
3.1216 + template <typename Key> class DynMapBase
3.1217 + {
3.1218 + protected:
3.1219 + const EdgeSet* G;
3.1220 + public:
3.1221 + virtual void add(const Key k) = 0;
3.1222 + virtual void erase(const Key k) = 0;
3.1223 + DynMapBase(const EdgeSet &_G) : G(&_G) {}
3.1224 + virtual ~DynMapBase() {}
3.1225 + friend class EdgeSet;
3.1226 + };
3.1227 +
3.1228 + public:
3.1229 + //template <typename T> class NodeMap;
3.1230 + template <typename T> class EdgeMap;
3.1231 +
3.1232 + class Node;
3.1233 + class Edge;
3.1234 +
3.1235 + // protected:
3.1236 + // HELPME:
3.1237 + protected:
3.1238 + // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
3.1239 + ///\bug It must be public because of SymEdgeMap.
3.1240 + ///
3.1241 + mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
3.1242 +
3.1243 + public:
3.1244 +
3.1245 + class NodeIt;
3.1246 + class EdgeIt;
3.1247 + class OutEdgeIt;
3.1248 + class InEdgeIt;
3.1249 +
3.1250 + template <typename T> class NodeMap;
3.1251 + template <typename T> class EdgeMap;
3.1252 +
3.1253 + public:
3.1254 +
3.1255 + ///Constructor
3.1256 +
3.1257 + ///Construates a new graph based on the nodeset of an existing one.
3.1258 + ///\param _G the base graph.
3.1259 + ///\todo It looks like a copy constructor, but it isn't.
3.1260 + EdgeSet(NodeGraphType &_G) : G(_G),
3.1261 + nodes(_G), edges(),
3.1262 + first_free_edge(-1) { }
3.1263 + ///Copy constructor
3.1264 +
3.1265 + ///Makes a copy of an EdgeSet.
3.1266 + ///It will be based on the same graph.
3.1267 + EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
3.1268 + first_free_edge(_g.first_free_edge) { }
3.1269 +
3.1270 + ~EdgeSet()
3.1271 + {
3.1272 + // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
3.1273 + // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
3.1274 + for(typename std::vector<DynMapBase<Edge> * >::iterator
3.1275 + i=dyn_edge_maps.begin();
3.1276 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
3.1277 + }
3.1278 +
3.1279 + int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
3.1280 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
3.1281 +
3.1282 + ///\bug This function does something different than
3.1283 + ///its name would suggests...
3.1284 + int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
3.1285 + ///\bug This function does something different than
3.1286 + ///its name would suggests...
3.1287 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
3.1288 +
3.1289 + Node tail(Edge e) const { return edges[e.n].tail; }
3.1290 + Node head(Edge e) const { return edges[e.n].head; }
3.1291 +
3.1292 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
3.1293 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
3.1294 +
3.1295 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
3.1296 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
3.1297 +
3.1298 + NodeIt& first(NodeIt& v) const {
3.1299 + v=NodeIt(*this); return v; }
3.1300 + EdgeIt& first(EdgeIt& e) const {
3.1301 + e=EdgeIt(*this); return e; }
3.1302 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
3.1303 + e=OutEdgeIt(*this,v); return e; }
3.1304 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
3.1305 + e=InEdgeIt(*this,v); return e; }
3.1306 +
3.1307 +// template< typename It >
3.1308 +// It first() const { It e; first(e); return e; }
3.1309 +
3.1310 +// template< typename It >
3.1311 +// It first(Node v) const { It e; first(e,v); return e; }
3.1312 +
3.1313 + bool valid(Edge e) const { return e.n!=-1; }
3.1314 + bool valid(Node n) const { return G.valid(n); }
3.1315 +
3.1316 + void setInvalid(Edge &e) { e.n=-1; }
3.1317 + void setInvalid(Node &n) { G.setInvalid(n); }
3.1318 +
3.1319 + template <typename It> It getNext(It it) const
3.1320 + { It tmp(it); return next(tmp); }
3.1321 +
3.1322 + NodeIt& next(NodeIt& it) const { G.next(it); return it; }
3.1323 + OutEdgeIt& next(OutEdgeIt& it) const
3.1324 + { it.n=edges[it.n].next_out; return it; }
3.1325 + InEdgeIt& next(InEdgeIt& it) const
3.1326 + { it.n=edges[it.n].next_in; return it; }
3.1327 + EdgeIt& next(EdgeIt& it) const {
3.1328 + if(edges[it.n].next_in!=-1) {
3.1329 + it.n=edges[it.n].next_in;
3.1330 + }
3.1331 + else {
3.1332 + NodeIt n;
3.1333 + for(n=next(edges[it.n].head);
3.1334 + valid(n) && nodes[n].first_in == -1;
3.1335 + next(n)) ;
3.1336 + it.n = (valid(n))?-1:nodes[n].first_in;
3.1337 + }
3.1338 + return it;
3.1339 + }
3.1340 +
3.1341 + int id(Edge e) const { return e.n; }
3.1342 +
3.1343 + /// Adds a new node to the graph.
3.1344 + Node addNode() { return G.AddNode(); }
3.1345 +
3.1346 + Edge addEdge(Node u, Node v) {
3.1347 + int n;
3.1348 +
3.1349 + if(first_free_edge==-1)
3.1350 + {
3.1351 + n = edges.size();
3.1352 + edges.push_back(EdgeT());
3.1353 + }
3.1354 + else {
3.1355 + n = first_free_edge;
3.1356 + first_free_edge = edges[n].next_in;
3.1357 + }
3.1358 +
3.1359 + edges[n].tail = u; edges[n].head = v;
3.1360 +
3.1361 + edges[n].next_out = nodes[u].first_out;
3.1362 + if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
3.1363 + edges[n].next_in = nodes[v].first_in;
3.1364 + if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
3.1365 + edges[n].prev_in = edges[n].prev_out = -1;
3.1366 +
3.1367 + nodes[u].first_out = nodes[v].first_in = n;
3.1368 +
3.1369 + Edge e; e.n=n;
3.1370 +
3.1371 + //Update dynamic maps
3.1372 + for(typename std::vector<DynMapBase<Edge> * >::iterator
3.1373 + i=dyn_edge_maps.begin();
3.1374 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
3.1375 +
3.1376 + return e;
3.1377 + }
3.1378 +
3.1379 + private:
3.1380 + void eraseEdge(int n) {
3.1381 +
3.1382 + if(edges[n].next_in!=-1)
3.1383 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
3.1384 + if(edges[n].prev_in!=-1)
3.1385 + edges[edges[n].prev_in].next_in = edges[n].next_in;
3.1386 + else nodes[edges[n].head].first_in = edges[n].next_in;
3.1387 +
3.1388 + if(edges[n].next_out!=-1)
3.1389 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
3.1390 + if(edges[n].prev_out!=-1)
3.1391 + edges[edges[n].prev_out].next_out = edges[n].next_out;
3.1392 + else nodes[edges[n].tail].first_out = edges[n].next_out;
3.1393 +
3.1394 + edges[n].next_in = first_free_edge;
3.1395 + first_free_edge = -1;
3.1396 +
3.1397 + //Update dynamic maps
3.1398 + Edge e; e.n=n;
3.1399 + for(typename std::vector<DynMapBase<Edge> * >::iterator
3.1400 + i=dyn_edge_maps.begin();
3.1401 + i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
3.1402 + }
3.1403 +
3.1404 + public:
3.1405 +
3.1406 +// void erase(Node nn) {
3.1407 +// int n=nn.n;
3.1408 +// int m;
3.1409 +// while((m=nodes[n].first_in)!=-1) eraseEdge(m);
3.1410 +// while((m=nodes[n].first_out)!=-1) eraseEdge(m);
3.1411 +// }
3.1412 +
3.1413 + void erase(Edge e) { eraseEdge(e.n); }
3.1414 +
3.1415 +// //\bug Dynamic maps must be updated!
3.1416 +// //
3.1417 +// void clear() {
3.1418 +// nodes.clear();edges.clear();
3.1419 +// first_node=first_free_node=first_free_edge=-1;
3.1420 +// }
3.1421 +
3.1422 + class Edge {
3.1423 + friend class EdgeSet;
3.1424 + template <typename T> friend class EdgeMap;
3.1425 +
3.1426 + //template <typename T> friend class SymEdgeSet::SymEdgeMap;
3.1427 + //friend Edge SymEdgeSet::opposite(Edge) const;
3.1428 +
3.1429 + friend class Node;
3.1430 + friend class NodeIt;
3.1431 + protected:
3.1432 + int n;
3.1433 + friend int EdgeSet::id(Edge e) const;
3.1434 +
3.1435 + Edge(int nn) {n=nn;}
3.1436 + public:
3.1437 + Edge() { }
3.1438 + Edge (Invalid) { n=-1; }
3.1439 + bool operator==(const Edge i) const {return n==i.n;}
3.1440 + bool operator!=(const Edge i) const {return n!=i.n;}
3.1441 + bool operator<(const Edge i) const {return n<i.n;}
3.1442 + ///\bug This is a workaround until somebody tells me how to
3.1443 + ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
3.1444 + int &idref() {return n;}
3.1445 + const int &idref() const {return n;}
3.1446 + };
3.1447 +
3.1448 + class EdgeIt : public Edge {
3.1449 + friend class EdgeSet;
3.1450 + public:
3.1451 + EdgeIt(const EdgeSet& G) : Edge() {
3.1452 + // typename NodeGraphType::Node m;
3.1453 + NodeIt m;
3.1454 + for(G.first(m);
3.1455 + G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
3.1456 + //AJJAJ! This is a non sense!!!!!!!
3.1457 + this->n = G.valid(m)?-1:G.nodes[m].first_in;
3.1458 + }
3.1459 + EdgeIt (Invalid i) : Edge(i) { }
3.1460 + EdgeIt() : Edge() { }
3.1461 + ///\bug This is a workaround until somebody tells me how to
3.1462 + ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
3.1463 + int &idref() {return this->n;}
3.1464 + };
3.1465 +
3.1466 + class OutEdgeIt : public Edge {
3.1467 + friend class EdgeSet;
3.1468 + public:
3.1469 + OutEdgeIt() : Edge() { }
3.1470 + OutEdgeIt (Invalid i) : Edge(i) { }
3.1471 +
3.1472 + OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
3.1473 + };
3.1474 +
3.1475 + class InEdgeIt : public Edge {
3.1476 + friend class EdgeSet;
3.1477 + public:
3.1478 + InEdgeIt() : Edge() { }
3.1479 + InEdgeIt (Invalid i) : Edge(i) { }
3.1480 + InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
3.1481 + };
3.1482 +
3.1483 + template <typename T> class NodeMap :
3.1484 + public NodeGraphType::template NodeMap<T>
3.1485 + {
3.1486 + public:
3.1487 + NodeMap(const EdgeSet &_G) :
3.1488 + NodeGraphType::NodeMap(_G.G) { } //AJAJJ <T> would be wrong!!!
3.1489 + NodeMap(const EdgeSet &_G,const T &t) :
3.1490 + NodeGraphType::NodeMap(_G.G,t) { }
3.1491 + //It is unnecessary
3.1492 + NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
3.1493 + NodeGraphType::NodeMap(m) { }
3.1494 +
3.1495 + ///\todo It can copy between different types.
3.1496 + ///
3.1497 + template<typename TT>
3.1498 + NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
3.1499 + : NodeGraphType::NodeMap(m) { }
3.1500 + };
3.1501 +
3.1502 + template <typename T> class EdgeMap : public DynMapBase<Edge>
3.1503 + {
3.1504 + std::vector<T> container;
3.1505 +
3.1506 + public:
3.1507 + typedef T ValueType;
3.1508 + typedef Edge KeyType;
3.1509 +
3.1510 + EdgeMap(const EdgeSet &_G) :
3.1511 + DynMapBase<Edge>(_G), container(_G.maxEdgeId())
3.1512 + {
3.1513 + //FIXME: What if there are empty Id's?
3.1514 + //FIXME: Can I use 'this' in a constructor?
3.1515 + G->dyn_edge_maps.push_back(this);
3.1516 + }
3.1517 + EdgeMap(const EdgeSet &_G,const T &t) :
3.1518 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
3.1519 + {
3.1520 + G->dyn_edge_maps.push_back(this);
3.1521 + }
3.1522 + EdgeMap(const EdgeMap<T> &m) :
3.1523 + DynMapBase<Edge>(*m.G), container(m.container)
3.1524 + {
3.1525 + G->dyn_edge_maps.push_back(this);
3.1526 + }
3.1527 +
3.1528 + template<typename TT> friend class EdgeMap;
3.1529 +
3.1530 + ///\todo It can copy between different types.
3.1531 + ///
3.1532 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
3.1533 + DynMapBase<Edge>(*m.G)
3.1534 + {
3.1535 + G->dyn_edge_maps.push_back(this);
3.1536 + typename std::vector<TT>::const_iterator i;
3.1537 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
3.1538 + i!=m.container.end();
3.1539 + i++)
3.1540 + container.push_back(*i);
3.1541 + }
3.1542 + ~EdgeMap()
3.1543 + {
3.1544 + if(G) {
3.1545 + typename std::vector<DynMapBase<Edge>* >::iterator i;
3.1546 + for(i=G->dyn_edge_maps.begin();
3.1547 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
3.1548 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
3.1549 + //A better way to do that: (Is this really important?)
3.1550 + if(*i==this) {
3.1551 + *i=G->dyn_edge_maps.back();
3.1552 + G->dyn_edge_maps.pop_back();
3.1553 + }
3.1554 + }
3.1555 + }
3.1556 +
3.1557 + void add(const Edge k)
3.1558 + {
3.1559 + if(k.n>=int(container.size())) container.resize(k.n+1);
3.1560 + }
3.1561 + void erase(const Edge) { }
3.1562 +
3.1563 + void set(Edge n, T a) { container[n.n]=a; }
3.1564 + //T get(Edge n) const { return container[n.n]; }
3.1565 + typename std::vector<T>::reference
3.1566 + operator[](Edge n) { return container[n.n]; }
3.1567 + typename std::vector<T>::const_reference
3.1568 + operator[](Edge n) const { return container[n.n]; }
3.1569 +
3.1570 + ///\warning There is no safety check at all!
3.1571 + ///Using operator = between maps attached to different graph may
3.1572 + ///cause serious problem.
3.1573 + ///\todo Is this really so?
3.1574 + ///\todo It can copy between different types.
3.1575 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
3.1576 + {
3.1577 + container = m.container;
3.1578 + return *this;
3.1579 + }
3.1580 + template<typename TT>
3.1581 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
3.1582 + {
3.1583 + std::copy(m.container.begin(), m.container.end(), container.begin());
3.1584 + return *this;
3.1585 + }
3.1586 +
3.1587 + void update() {} //Useless for DynMaps
3.1588 + void update(T a) {} //Useless for DynMaps
3.1589 + };
3.1590 +
3.1591 + };
3.1592 +
3.1593 + template< typename GG>
3.1594 + int EdgeSet<GG>::id(Node v) const { return G.id(v); }
3.1595 +
3.1596 +/// @}
3.1597 +
3.1598 +} //namespace hugo
3.1599 +
3.1600 +#endif //HUGO_LIST_GRAPH_H
4.1 --- a/src/test/dijkstra_test.cc Fri May 07 11:57:34 2004 +0000
4.2 +++ b/src/test/dijkstra_test.cc Fri May 07 13:27:16 2004 +0000
4.3 @@ -1,4 +1,4 @@
4.4 -#include <test_tools.h>
4.5 +#include "test_tools.h"
4.6 #include <hugo/smart_graph.h>
4.7 #include <hugo/dijkstra.h>
4.8
4.9 @@ -59,7 +59,7 @@
4.10 Node s, t;
4.11 LengthMap cap(G);
4.12 PetStruct<Graph> ps = addPetersen(G,PET_SIZE);
4.13 -
4.14 +
4.15 for(int i=0;i<PET_SIZE;i++) {
4.16 cap[ps.outcir[i]]=4;
4.17 cap[ps.incir[i]]=1;
5.1 --- a/src/test/graph_test.cc Fri May 07 11:57:34 2004 +0000
5.2 +++ b/src/test/graph_test.cc Fri May 07 13:27:16 2004 +0000
5.3 @@ -1,10 +1,10 @@
5.4 #include<iostream>
5.5 #include<hugo/smart_graph.h>
5.6 #include<hugo/skeletons/graph.h>
5.7 +#include<hugo/list_graph.h>
5.8 +
5.9 #include"test_tools.h"
5.10
5.11 -//#include<../work/alpar/list_graph.h>
5.12 -
5.13 /*
5.14 This test makes consistency checks of list graph structures.
5.15
5.16 @@ -242,8 +242,8 @@
5.17 template void checkCompile<GraphSkeleton>(GraphSkeleton &);
5.18 template void checkCompile<SmartGraph>(SmartGraph &);
5.19 template void checkCompile<SymSmartGraph>(SymSmartGraph &);
5.20 -//template void checkCompile<ListGraph>(ListGraph &);
5.21 -//template void checkCompile<SymListGraph>(SymListGraph &);
5.22 +template void checkCompile<ListGraph>(ListGraph &);
5.23 +template void checkCompile<SymListGraph>(SymListGraph &);
5.24
5.25 //Due to some mysterious and some conceptual problems it does not work.
5.26 //template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
5.27 @@ -256,22 +256,22 @@
5.28 bidirPetersen(G);
5.29 checkPetersen(G);
5.30 }
5.31 -// {
5.32 -// ListGraph G;
5.33 -// addPetersen(G);
5.34 -// bidirPetersen(G);
5.35 -// checkPetersen(G);
5.36 -// }
5.37 + {
5.38 + ListGraph G;
5.39 + addPetersen(G);
5.40 + bidirPetersen(G);
5.41 + checkPetersen(G);
5.42 + }
5.43 {
5.44 SymSmartGraph G;
5.45 addPetersen(G);
5.46 checkPetersen(G);
5.47 }
5.48 -// {
5.49 -// SymListGraph G;
5.50 -// addPetersen(G);
5.51 -// checkPetersen(G);
5.52 -// }
5.53 + {
5.54 + SymListGraph G;
5.55 + addPetersen(G);
5.56 + checkPetersen(G);
5.57 + }
5.58
5.59 //\todo map tests.
5.60 //\todo copy constr tests.
6.1 --- a/src/work/alpar/list_graph.h Fri May 07 11:57:34 2004 +0000
6.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
6.3 @@ -1,1597 +0,0 @@
6.4 -// -*- mode:C++ -*-
6.5 -
6.6 -#ifndef HUGO_LIST_GRAPH_H
6.7 -#define HUGO_LIST_GRAPH_H
6.8 -
6.9 -///\ingroup graphs
6.10 -///\file
6.11 -///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
6.12 -
6.13 -#include <vector>
6.14 -#include <limits.h>
6.15 -
6.16 -#include <hugo/invalid.h>
6.17 -
6.18 -namespace hugo {
6.19 -
6.20 -/// \addtogroup graphs
6.21 -/// @{
6.22 -
6.23 - class SymListGraph;
6.24 -
6.25 - ///A list graph class.
6.26 -
6.27 - ///This is a simple and fast erasable graph implementation.
6.28 - ///
6.29 - ///It conforms to the graph interface documented under
6.30 - ///the description of \ref GraphSkeleton.
6.31 - ///\sa \ref GraphSkeleton.
6.32 - class ListGraph {
6.33 -
6.34 - //Nodes are double linked.
6.35 - //The free nodes are only single linked using the "next" field.
6.36 - struct NodeT
6.37 - {
6.38 - int first_in,first_out;
6.39 - int prev, next;
6.40 - // NodeT() {}
6.41 - };
6.42 - //Edges are double linked.
6.43 - //The free edges are only single linked using the "next_in" field.
6.44 - struct EdgeT
6.45 - {
6.46 - int head, tail;
6.47 - int prev_in, prev_out;
6.48 - int next_in, next_out;
6.49 - //FIXME: is this necessary?
6.50 - // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
6.51 - };
6.52 -
6.53 - std::vector<NodeT> nodes;
6.54 - //The first node
6.55 - int first_node;
6.56 - //The first free node
6.57 - int first_free_node;
6.58 - std::vector<EdgeT> edges;
6.59 - //The first free edge
6.60 - int first_free_edge;
6.61 -
6.62 - protected:
6.63 -
6.64 - template <typename Key> class DynMapBase
6.65 - {
6.66 - protected:
6.67 - const ListGraph* G;
6.68 - public:
6.69 - virtual void add(const Key k) = 0;
6.70 - virtual void erase(const Key k) = 0;
6.71 - DynMapBase(const ListGraph &_G) : G(&_G) {}
6.72 - virtual ~DynMapBase() {}
6.73 - friend class ListGraph;
6.74 - };
6.75 -
6.76 - public:
6.77 - template <typename T> class EdgeMap;
6.78 - template <typename T> class NodeMap;
6.79 -
6.80 - class Node;
6.81 - class Edge;
6.82 -
6.83 - // protected:
6.84 - // HELPME:
6.85 - protected:
6.86 - ///\bug It must be public because of SymEdgeMap.
6.87 - ///
6.88 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
6.89 - ///\bug It must be public because of SymEdgeMap.
6.90 - ///
6.91 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
6.92 -
6.93 - public:
6.94 -
6.95 - class NodeIt;
6.96 - class EdgeIt;
6.97 - class OutEdgeIt;
6.98 - class InEdgeIt;
6.99 -
6.100 - template <typename T> class NodeMap;
6.101 - template <typename T> class EdgeMap;
6.102 -
6.103 - public:
6.104 -
6.105 - ListGraph() : nodes(), first_node(-1),
6.106 - first_free_node(-1), edges(), first_free_edge(-1) {}
6.107 - ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
6.108 - first_free_node(_g.first_free_node),
6.109 - edges(_g.edges),
6.110 - first_free_edge(_g.first_free_edge) {}
6.111 -
6.112 - ~ListGraph()
6.113 - {
6.114 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.115 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
6.116 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
6.117 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
6.118 - }
6.119 -
6.120 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
6.121 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
6.122 -
6.123 - ///\bug This function does something different than
6.124 - ///its name would suggests...
6.125 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
6.126 - ///\bug This function does something different than
6.127 - ///its name would suggests...
6.128 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
6.129 -
6.130 - Node tail(Edge e) const { return edges[e.n].tail; }
6.131 - Node head(Edge e) const { return edges[e.n].head; }
6.132 -
6.133 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
6.134 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
6.135 -
6.136 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
6.137 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
6.138 -
6.139 - NodeIt& first(NodeIt& v) const {
6.140 - v=NodeIt(*this); return v; }
6.141 - EdgeIt& first(EdgeIt& e) const {
6.142 - e=EdgeIt(*this); return e; }
6.143 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
6.144 - e=OutEdgeIt(*this,v); return e; }
6.145 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
6.146 - e=InEdgeIt(*this,v); return e; }
6.147 -
6.148 -// template< typename It >
6.149 -// It first() const { It e; first(e); return e; }
6.150 -
6.151 -// template< typename It >
6.152 -// It first(Node v) const { It e; first(e,v); return e; }
6.153 -
6.154 - bool valid(Edge e) const { return e.n!=-1; }
6.155 - bool valid(Node n) const { return n.n!=-1; }
6.156 -
6.157 - void setInvalid(Edge &e) { e.n=-1; }
6.158 - void setInvalid(Node &n) { n.n=-1; }
6.159 -
6.160 - template <typename It> It getNext(It it) const
6.161 - { It tmp(it); return next(tmp); }
6.162 -
6.163 - NodeIt& next(NodeIt& it) const {
6.164 - it.n=nodes[it.n].next;
6.165 - return it;
6.166 - }
6.167 - OutEdgeIt& next(OutEdgeIt& it) const
6.168 - { it.n=edges[it.n].next_out; return it; }
6.169 - InEdgeIt& next(InEdgeIt& it) const
6.170 - { it.n=edges[it.n].next_in; return it; }
6.171 - EdgeIt& next(EdgeIt& it) const {
6.172 - if(edges[it.n].next_in!=-1) {
6.173 - it.n=edges[it.n].next_in;
6.174 - }
6.175 - else {
6.176 - int n;
6.177 - for(n=nodes[edges[it.n].head].next;
6.178 - n!=-1 && nodes[n].first_in == -1;
6.179 - n = nodes[n].next) ;
6.180 - it.n = (n==-1)?-1:nodes[n].first_in;
6.181 - }
6.182 - return it;
6.183 - }
6.184 -
6.185 - int id(Node v) const { return v.n; }
6.186 - int id(Edge e) const { return e.n; }
6.187 -
6.188 - /// Adds a new node to the graph.
6.189 -
6.190 - /// \todo It adds the nodes in a reversed order.
6.191 - /// (i.e. the lastly added node becomes the first.)
6.192 - Node addNode() {
6.193 - int n;
6.194 -
6.195 - if(first_free_node==-1)
6.196 - {
6.197 - n = nodes.size();
6.198 - nodes.push_back(NodeT());
6.199 - }
6.200 - else {
6.201 - n = first_free_node;
6.202 - first_free_node = nodes[n].next;
6.203 - }
6.204 -
6.205 - nodes[n].next = first_node;
6.206 - if(first_node != -1) nodes[first_node].prev = n;
6.207 - first_node = n;
6.208 - nodes[n].prev = -1;
6.209 -
6.210 - nodes[n].first_in = nodes[n].first_out = -1;
6.211 -
6.212 - Node nn; nn.n=n;
6.213 -
6.214 - //Update dynamic maps
6.215 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.216 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
6.217 -
6.218 - return nn;
6.219 - }
6.220 -
6.221 - Edge addEdge(Node u, Node v) {
6.222 - int n;
6.223 -
6.224 - if(first_free_edge==-1)
6.225 - {
6.226 - n = edges.size();
6.227 - edges.push_back(EdgeT());
6.228 - }
6.229 - else {
6.230 - n = first_free_edge;
6.231 - first_free_edge = edges[n].next_in;
6.232 - }
6.233 -
6.234 - edges[n].tail = u.n; edges[n].head = v.n;
6.235 -
6.236 - edges[n].next_out = nodes[u.n].first_out;
6.237 - if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
6.238 - edges[n].next_in = nodes[v.n].first_in;
6.239 - if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
6.240 - edges[n].prev_in = edges[n].prev_out = -1;
6.241 -
6.242 - nodes[u.n].first_out = nodes[v.n].first_in = n;
6.243 -
6.244 - Edge e; e.n=n;
6.245 -
6.246 - //Update dynamic maps
6.247 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
6.248 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
6.249 -
6.250 - return e;
6.251 - }
6.252 -
6.253 - private:
6.254 - void eraseEdge(int n) {
6.255 -
6.256 - if(edges[n].next_in!=-1)
6.257 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
6.258 - if(edges[n].prev_in!=-1)
6.259 - edges[edges[n].prev_in].next_in = edges[n].next_in;
6.260 - else nodes[edges[n].head].first_in = edges[n].next_in;
6.261 -
6.262 - if(edges[n].next_out!=-1)
6.263 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
6.264 - if(edges[n].prev_out!=-1)
6.265 - edges[edges[n].prev_out].next_out = edges[n].next_out;
6.266 - else nodes[edges[n].tail].first_out = edges[n].next_out;
6.267 -
6.268 - edges[n].next_in = first_free_edge;
6.269 - first_free_edge = -1;
6.270 -
6.271 - //Update dynamic maps
6.272 - Edge e; e.n=n;
6.273 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
6.274 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
6.275 - }
6.276 -
6.277 - public:
6.278 -
6.279 - void erase(Node nn) {
6.280 - int n=nn.n;
6.281 -
6.282 - int m;
6.283 - while((m=nodes[n].first_in)!=-1) eraseEdge(m);
6.284 - while((m=nodes[n].first_out)!=-1) eraseEdge(m);
6.285 -
6.286 - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
6.287 - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
6.288 - else first_node = nodes[n].next;
6.289 -
6.290 - nodes[n].next = first_free_node;
6.291 - first_free_node = n;
6.292 -
6.293 - //Update dynamic maps
6.294 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.295 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
6.296 - }
6.297 -
6.298 - void erase(Edge e) { eraseEdge(e.n); }
6.299 -
6.300 - ///\bug Dynamic maps must be updated!
6.301 - ///
6.302 - void clear() {
6.303 - nodes.clear();edges.clear();
6.304 - first_node=first_free_node=first_free_edge=-1;
6.305 - }
6.306 -
6.307 - class Node {
6.308 - friend class ListGraph;
6.309 - template <typename T> friend class NodeMap;
6.310 -
6.311 - friend class Edge;
6.312 - friend class OutEdgeIt;
6.313 - friend class InEdgeIt;
6.314 - friend class SymEdge;
6.315 -
6.316 - protected:
6.317 - int n;
6.318 - friend int ListGraph::id(Node v) const;
6.319 - Node(int nn) {n=nn;}
6.320 - public:
6.321 - Node() {}
6.322 - Node (Invalid) { n=-1; }
6.323 - bool operator==(const Node i) const {return n==i.n;}
6.324 - bool operator!=(const Node i) const {return n!=i.n;}
6.325 - bool operator<(const Node i) const {return n<i.n;}
6.326 - };
6.327 -
6.328 - class NodeIt : public Node {
6.329 - friend class ListGraph;
6.330 - public:
6.331 - NodeIt() : Node() { }
6.332 - NodeIt(Invalid i) : Node(i) { }
6.333 - NodeIt(const ListGraph& G) : Node(G.first_node) { }
6.334 - };
6.335 -
6.336 - class Edge {
6.337 - friend class ListGraph;
6.338 - template <typename T> friend class EdgeMap;
6.339 -
6.340 - //template <typename T> friend class SymListGraph::SymEdgeMap;
6.341 - //friend Edge SymListGraph::opposite(Edge) const;
6.342 -
6.343 - friend class Node;
6.344 - friend class NodeIt;
6.345 - protected:
6.346 - int n;
6.347 - friend int ListGraph::id(Edge e) const;
6.348 -
6.349 - Edge(int nn) {n=nn;}
6.350 - public:
6.351 - Edge() { }
6.352 - Edge (Invalid) { n=-1; }
6.353 - bool operator==(const Edge i) const {return n==i.n;}
6.354 - bool operator!=(const Edge i) const {return n!=i.n;}
6.355 - bool operator<(const Edge i) const {return n<i.n;}
6.356 - ///\bug This is a workaround until somebody tells me how to
6.357 - ///make class \c SymListGraph::SymEdgeMap friend of Edge
6.358 - int &idref() {return n;}
6.359 - const int &idref() const {return n;}
6.360 - };
6.361 -
6.362 - class EdgeIt : public Edge {
6.363 - friend class ListGraph;
6.364 - public:
6.365 - EdgeIt(const ListGraph& G) : Edge() {
6.366 - int m;
6.367 - for(m=G.first_node;
6.368 - m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
6.369 - n = (m==-1)?-1:G.nodes[m].first_in;
6.370 - }
6.371 - EdgeIt (Invalid i) : Edge(i) { }
6.372 - EdgeIt() : Edge() { }
6.373 - ///\bug This is a workaround until somebody tells me how to
6.374 - ///make class \c SymListGraph::SymEdgeMap friend of Edge
6.375 - int &idref() {return n;}
6.376 - };
6.377 -
6.378 - class OutEdgeIt : public Edge {
6.379 - friend class ListGraph;
6.380 - public:
6.381 - OutEdgeIt() : Edge() { }
6.382 - OutEdgeIt (Invalid i) : Edge(i) { }
6.383 -
6.384 - OutEdgeIt(const ListGraph& G,const Node v)
6.385 - : Edge(G.nodes[v.n].first_out) {}
6.386 - };
6.387 -
6.388 - class InEdgeIt : public Edge {
6.389 - friend class ListGraph;
6.390 - public:
6.391 - InEdgeIt() : Edge() { }
6.392 - InEdgeIt (Invalid i) : Edge(i) { }
6.393 - InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
6.394 - };
6.395 -
6.396 - template <typename T> class NodeMap : public DynMapBase<Node>
6.397 - {
6.398 - std::vector<T> container;
6.399 -
6.400 - public:
6.401 - typedef T ValueType;
6.402 - typedef Node KeyType;
6.403 -
6.404 - NodeMap(const ListGraph &_G) :
6.405 - DynMapBase<Node>(_G), container(_G.maxNodeId())
6.406 - {
6.407 - G->dyn_node_maps.push_back(this);
6.408 - }
6.409 - NodeMap(const ListGraph &_G,const T &t) :
6.410 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
6.411 - {
6.412 - G->dyn_node_maps.push_back(this);
6.413 - }
6.414 -
6.415 - NodeMap(const NodeMap<T> &m) :
6.416 - DynMapBase<Node>(*m.G), container(m.container)
6.417 - {
6.418 - G->dyn_node_maps.push_back(this);
6.419 - }
6.420 -
6.421 - template<typename TT> friend class NodeMap;
6.422 -
6.423 - ///\todo It can copy between different types.
6.424 - ///
6.425 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
6.426 - DynMapBase<Node>(*m.G)
6.427 - {
6.428 - G->dyn_node_maps.push_back(this);
6.429 - typename std::vector<TT>::const_iterator i;
6.430 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
6.431 - i!=m.container.end();
6.432 - i++)
6.433 - container.push_back(*i);
6.434 - }
6.435 - ~NodeMap()
6.436 - {
6.437 - if(G) {
6.438 - std::vector<DynMapBase<Node>* >::iterator i;
6.439 - for(i=G->dyn_node_maps.begin();
6.440 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
6.441 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
6.442 - //A better way to do that: (Is this really important?)
6.443 - if(*i==this) {
6.444 - *i=G->dyn_node_maps.back();
6.445 - G->dyn_node_maps.pop_back();
6.446 - }
6.447 - }
6.448 - }
6.449 -
6.450 - void add(const Node k)
6.451 - {
6.452 - if(k.n>=int(container.size())) container.resize(k.n+1);
6.453 - }
6.454 -
6.455 - void erase(const Node) { }
6.456 -
6.457 - void set(Node n, T a) { container[n.n]=a; }
6.458 - //'T& operator[](Node n)' would be wrong here
6.459 - typename std::vector<T>::reference
6.460 - operator[](Node n) { return container[n.n]; }
6.461 - //'const T& operator[](Node n)' would be wrong here
6.462 - typename std::vector<T>::const_reference
6.463 - operator[](Node n) const { return container[n.n]; }
6.464 -
6.465 - ///\warning There is no safety check at all!
6.466 - ///Using operator = between maps attached to different graph may
6.467 - ///cause serious problem.
6.468 - ///\todo Is this really so?
6.469 - ///\todo It can copy between different types.
6.470 - const NodeMap<T>& operator=(const NodeMap<T> &m)
6.471 - {
6.472 - container = m.container;
6.473 - return *this;
6.474 - }
6.475 - template<typename TT>
6.476 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
6.477 - {
6.478 - std::copy(m.container.begin(), m.container.end(), container.begin());
6.479 - return *this;
6.480 - }
6.481 -
6.482 - void update() {} //Useless for Dynamic Maps
6.483 - void update(T a) {} //Useless for Dynamic Maps
6.484 - };
6.485 -
6.486 - template <typename T> class EdgeMap : public DynMapBase<Edge>
6.487 - {
6.488 - std::vector<T> container;
6.489 -
6.490 - public:
6.491 - typedef T ValueType;
6.492 - typedef Edge KeyType;
6.493 -
6.494 - EdgeMap(const ListGraph &_G) :
6.495 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
6.496 - {
6.497 - //FIXME: What if there are empty Id's?
6.498 - //FIXME: Can I use 'this' in a constructor?
6.499 - G->dyn_edge_maps.push_back(this);
6.500 - }
6.501 - EdgeMap(const ListGraph &_G,const T &t) :
6.502 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
6.503 - {
6.504 - G->dyn_edge_maps.push_back(this);
6.505 - }
6.506 - EdgeMap(const EdgeMap<T> &m) :
6.507 - DynMapBase<Edge>(*m.G), container(m.container)
6.508 - {
6.509 - G->dyn_edge_maps.push_back(this);
6.510 - }
6.511 -
6.512 - template<typename TT> friend class EdgeMap;
6.513 -
6.514 - ///\todo It can copy between different types.
6.515 - ///
6.516 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
6.517 - DynMapBase<Edge>(*m.G)
6.518 - {
6.519 - G->dyn_edge_maps.push_back(this);
6.520 - typename std::vector<TT>::const_iterator i;
6.521 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
6.522 - i!=m.container.end();
6.523 - i++)
6.524 - container.push_back(*i);
6.525 - }
6.526 - ~EdgeMap()
6.527 - {
6.528 - if(G) {
6.529 - std::vector<DynMapBase<Edge>* >::iterator i;
6.530 - for(i=G->dyn_edge_maps.begin();
6.531 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
6.532 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
6.533 - //A better way to do that: (Is this really important?)
6.534 - if(*i==this) {
6.535 - *i=G->dyn_edge_maps.back();
6.536 - G->dyn_edge_maps.pop_back();
6.537 - }
6.538 - }
6.539 - }
6.540 -
6.541 - void add(const Edge k)
6.542 - {
6.543 - if(k.n>=int(container.size())) container.resize(k.n+1);
6.544 - }
6.545 - void erase(const Edge) { }
6.546 -
6.547 - void set(Edge n, T a) { container[n.n]=a; }
6.548 - //T get(Edge n) const { return container[n.n]; }
6.549 - typename std::vector<T>::reference
6.550 - operator[](Edge n) { return container[n.n]; }
6.551 - typename std::vector<T>::const_reference
6.552 - operator[](Edge n) const { return container[n.n]; }
6.553 -
6.554 - ///\warning There is no safety check at all!
6.555 - ///Using operator = between maps attached to different graph may
6.556 - ///cause serious problem.
6.557 - ///\todo Is this really so?
6.558 - ///\todo It can copy between different types.
6.559 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
6.560 - {
6.561 - container = m.container;
6.562 - return *this;
6.563 - }
6.564 - template<typename TT>
6.565 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
6.566 - {
6.567 - std::copy(m.container.begin(), m.container.end(), container.begin());
6.568 - return *this;
6.569 - }
6.570 -
6.571 - void update() {} //Useless for DynMaps
6.572 - void update(T a) {} //Useless for DynMaps
6.573 - };
6.574 -
6.575 - };
6.576 -
6.577 - ///Graph for bidirectional edges.
6.578 -
6.579 - ///The purpose of this graph structure is to handle graphs
6.580 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
6.581 - ///of oppositely directed edges.
6.582 - ///There is a new edge map type called
6.583 - ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
6.584 - ///that complements this
6.585 - ///feature by
6.586 - ///storing shared values for the edge pairs. The usual
6.587 - ///\ref GraphSkeleton::EdgeMap "EdgeMap"
6.588 - ///can be used
6.589 - ///as well.
6.590 - ///
6.591 - ///The oppositely directed edge can also be obtained easily
6.592 - ///using \ref opposite.
6.593 - ///
6.594 - ///Here erase(Edge) deletes a pair of edges.
6.595 - ///
6.596 - ///\todo this date structure need some reconsiderations. Maybe it
6.597 - ///should be implemented independently from ListGraph.
6.598 -
6.599 - class SymListGraph : public ListGraph
6.600 - {
6.601 - public:
6.602 - template<typename T> class SymEdgeMap;
6.603 - template<typename T> friend class SymEdgeMap;
6.604 -
6.605 - SymListGraph() : ListGraph() { }
6.606 - SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
6.607 - ///Adds a pair of oppositely directed edges to the graph.
6.608 - Edge addEdge(Node u, Node v)
6.609 - {
6.610 - Edge e = ListGraph::addEdge(u,v);
6.611 - ListGraph::addEdge(v,u);
6.612 - return e;
6.613 - }
6.614 -
6.615 - void erase(Node n) { ListGraph::erase(n); }
6.616 - ///The oppositely directed edge.
6.617 -
6.618 - ///Returns the oppositely directed
6.619 - ///pair of the edge \c e.
6.620 - Edge opposite(Edge e) const
6.621 - {
6.622 - Edge f;
6.623 - f.idref() = e.idref() - 2*(e.idref()%2) + 1;
6.624 - return f;
6.625 - }
6.626 -
6.627 - ///Removes a pair of oppositely directed edges to the graph.
6.628 - void erase(Edge e) {
6.629 - ListGraph::erase(opposite(e));
6.630 - ListGraph::erase(e);
6.631 - }
6.632 -
6.633 - ///Common data storage for the edge pairs.
6.634 -
6.635 - ///This map makes it possible to store data shared by the oppositely
6.636 - ///directed pairs of edges.
6.637 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
6.638 - {
6.639 - std::vector<T> container;
6.640 -
6.641 - public:
6.642 - typedef T ValueType;
6.643 - typedef Edge KeyType;
6.644 -
6.645 - SymEdgeMap(const SymListGraph &_G) :
6.646 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
6.647 - {
6.648 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
6.649 - }
6.650 - SymEdgeMap(const SymListGraph &_G,const T &t) :
6.651 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
6.652 - {
6.653 - G->dyn_edge_maps.push_back(this);
6.654 - }
6.655 -
6.656 - SymEdgeMap(const SymEdgeMap<T> &m) :
6.657 - DynMapBase<SymEdge>(*m.G), container(m.container)
6.658 - {
6.659 - G->dyn_node_maps.push_back(this);
6.660 - }
6.661 -
6.662 - // template<typename TT> friend class SymEdgeMap;
6.663 -
6.664 - ///\todo It can copy between different types.
6.665 - ///
6.666 -
6.667 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
6.668 - DynMapBase<SymEdge>(*m.G)
6.669 - {
6.670 - G->dyn_node_maps.push_back(this);
6.671 - typename std::vector<TT>::const_iterator i;
6.672 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
6.673 - i!=m.container.end();
6.674 - i++)
6.675 - container.push_back(*i);
6.676 - }
6.677 -
6.678 - ~SymEdgeMap()
6.679 - {
6.680 - if(G) {
6.681 - std::vector<DynMapBase<Edge>* >::iterator i;
6.682 - for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
6.683 - i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
6.684 - && *i!=this; ++i) ;
6.685 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
6.686 - //A better way to do that: (Is this really important?)
6.687 - if(*i==this) {
6.688 - *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
6.689 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
6.690 - }
6.691 - }
6.692 - }
6.693 -
6.694 - void add(const Edge k)
6.695 - {
6.696 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
6.697 - container.resize(k.idref()/2+1);
6.698 - }
6.699 - void erase(const Edge k) { }
6.700 -
6.701 - void set(Edge n, T a) { container[n.idref()/2]=a; }
6.702 - //T get(Edge n) const { return container[n.idref()/2]; }
6.703 - typename std::vector<T>::reference
6.704 - operator[](Edge n) { return container[n.idref()/2]; }
6.705 - typename std::vector<T>::const_reference
6.706 - operator[](Edge n) const { return container[n.idref()/2]; }
6.707 -
6.708 - ///\warning There is no safety check at all!
6.709 - ///Using operator = between maps attached to different graph may
6.710 - ///cause serious problem.
6.711 - ///\todo Is this really so?
6.712 - ///\todo It can copy between different types.
6.713 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
6.714 - {
6.715 - container = m.container;
6.716 - return *this;
6.717 - }
6.718 - template<typename TT>
6.719 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
6.720 - {
6.721 - std::copy(m.container.begin(), m.container.end(), container.begin());
6.722 - return *this;
6.723 - }
6.724 -
6.725 - void update() {} //Useless for DynMaps
6.726 - void update(T a) {} //Useless for DynMaps
6.727 -
6.728 - };
6.729 -
6.730 - };
6.731 -
6.732 -
6.733 - ///A graph class containing only nodes.
6.734 -
6.735 - ///This class implements a graph structure without edges.
6.736 - ///The most useful application of this class is to be the node set of an
6.737 - ///\ref EdgeSet class.
6.738 - ///
6.739 - ///It conforms to the graph interface documented under
6.740 - ///the description of \ref GraphSkeleton with the exception that you cannot
6.741 - ///add (or delete) edges. The usual edge iterators are exists, but they are
6.742 - ///always \ref INVALID.
6.743 - ///\sa \ref GraphSkeleton
6.744 - ///\sa \ref EdgeSet
6.745 - class NodeSet {
6.746 -
6.747 - //Nodes are double linked.
6.748 - //The free nodes are only single linked using the "next" field.
6.749 - struct NodeT
6.750 - {
6.751 - int first_in,first_out;
6.752 - int prev, next;
6.753 - // NodeT() {}
6.754 - };
6.755 -
6.756 - std::vector<NodeT> nodes;
6.757 - //The first node
6.758 - int first_node;
6.759 - //The first free node
6.760 - int first_free_node;
6.761 -
6.762 - protected:
6.763 -
6.764 - template <typename Key> class DynMapBase
6.765 - {
6.766 - protected:
6.767 - const NodeSet* G;
6.768 - public:
6.769 - virtual void add(const Key k) = 0;
6.770 - virtual void erase(const Key k) = 0;
6.771 - DynMapBase(const NodeSet &_G) : G(&_G) {}
6.772 - virtual ~DynMapBase() {}
6.773 - friend class NodeSet;
6.774 - };
6.775 -
6.776 - public:
6.777 - template <typename T> class EdgeMap;
6.778 - template <typename T> class NodeMap;
6.779 -
6.780 - class Node;
6.781 - class Edge;
6.782 -
6.783 - // protected:
6.784 - // HELPME:
6.785 - protected:
6.786 - ///\bug It must be public because of SymEdgeMap.
6.787 - ///
6.788 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
6.789 - //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
6.790 -
6.791 - public:
6.792 -
6.793 - class NodeIt;
6.794 - class EdgeIt;
6.795 - class OutEdgeIt;
6.796 - class InEdgeIt;
6.797 -
6.798 - template <typename T> class NodeMap;
6.799 - template <typename T> class EdgeMap;
6.800 -
6.801 - public:
6.802 -
6.803 - ///Default constructor
6.804 - NodeSet() : nodes(), first_node(-1),
6.805 - first_free_node(-1) {}
6.806 - ///Copy constructor
6.807 - NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
6.808 - first_free_node(_g.first_free_node) {}
6.809 -
6.810 - ~NodeSet()
6.811 - {
6.812 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.813 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
6.814 - //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
6.815 - // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
6.816 - }
6.817 -
6.818 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
6.819 - int edgeNum() const { return 0; } //FIXME: What is this?
6.820 -
6.821 - ///\bug This function does something different than
6.822 - ///its name would suggests...
6.823 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
6.824 - ///\bug This function does something different than
6.825 - ///its name would suggests...
6.826 - int maxEdgeId() const { return 0; } //FIXME: What is this?
6.827 -
6.828 - Node tail(Edge e) const { return INVALID; }
6.829 - Node head(Edge e) const { return INVALID; }
6.830 -
6.831 - Node aNode(OutEdgeIt e) const { return INVALID; }
6.832 - Node aNode(InEdgeIt e) const { return INVALID; }
6.833 -
6.834 - Node bNode(OutEdgeIt e) const { return INVALID; }
6.835 - Node bNode(InEdgeIt e) const { return INVALID; }
6.836 -
6.837 - NodeIt& first(NodeIt& v) const {
6.838 - v=NodeIt(*this); return v; }
6.839 - EdgeIt& first(EdgeIt& e) const {
6.840 - e=EdgeIt(*this); return e; }
6.841 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
6.842 - e=OutEdgeIt(*this,v); return e; }
6.843 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
6.844 - e=InEdgeIt(*this,v); return e; }
6.845 -
6.846 -// template< typename It >
6.847 -// It first() const { It e; first(e); return e; }
6.848 -
6.849 -// template< typename It >
6.850 -// It first(Node v) const { It e; first(e,v); return e; }
6.851 -
6.852 - bool valid(Edge e) const { return false; }
6.853 - bool valid(Node n) const { return n.n!=-1; }
6.854 -
6.855 - void setInvalid(Edge &e) { }
6.856 - void setInvalid(Node &n) { n.n=-1; }
6.857 -
6.858 - template <typename It> It getNext(It it) const
6.859 - { It tmp(it); return next(tmp); }
6.860 -
6.861 - NodeIt& next(NodeIt& it) const {
6.862 - it.n=nodes[it.n].next;
6.863 - return it;
6.864 - }
6.865 - OutEdgeIt& next(OutEdgeIt& it) const { return it; }
6.866 - InEdgeIt& next(InEdgeIt& it) const { return it; }
6.867 - EdgeIt& next(EdgeIt& it) const { return it; }
6.868 -
6.869 - int id(Node v) const { return v.n; }
6.870 - int id(Edge e) const { return -1; }
6.871 -
6.872 - /// Adds a new node to the graph.
6.873 -
6.874 - /// \todo It adds the nodes in a reversed order.
6.875 - /// (i.e. the lastly added node becomes the first.)
6.876 - Node addNode() {
6.877 - int n;
6.878 -
6.879 - if(first_free_node==-1)
6.880 - {
6.881 - n = nodes.size();
6.882 - nodes.push_back(NodeT());
6.883 - }
6.884 - else {
6.885 - n = first_free_node;
6.886 - first_free_node = nodes[n].next;
6.887 - }
6.888 -
6.889 - nodes[n].next = first_node;
6.890 - if(first_node != -1) nodes[first_node].prev = n;
6.891 - first_node = n;
6.892 - nodes[n].prev = -1;
6.893 -
6.894 - nodes[n].first_in = nodes[n].first_out = -1;
6.895 -
6.896 - Node nn; nn.n=n;
6.897 -
6.898 - //Update dynamic maps
6.899 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.900 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
6.901 -
6.902 - return nn;
6.903 - }
6.904 -
6.905 - void erase(Node nn) {
6.906 - int n=nn.n;
6.907 -
6.908 - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
6.909 - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
6.910 - else first_node = nodes[n].next;
6.911 -
6.912 - nodes[n].next = first_free_node;
6.913 - first_free_node = n;
6.914 -
6.915 - //Update dynamic maps
6.916 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.917 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
6.918 - }
6.919 -
6.920 - ///\bug Dynamic maps must be updated!
6.921 - ///
6.922 - void clear() {
6.923 - nodes.clear();
6.924 - first_node = first_free_node = -1;
6.925 - }
6.926 -
6.927 - class Node {
6.928 - friend class NodeSet;
6.929 - template <typename T> friend class NodeMap;
6.930 -
6.931 - friend class Edge;
6.932 - friend class OutEdgeIt;
6.933 - friend class InEdgeIt;
6.934 -
6.935 - protected:
6.936 - int n;
6.937 - friend int NodeSet::id(Node v) const;
6.938 - Node(int nn) {n=nn;}
6.939 - public:
6.940 - Node() {}
6.941 - Node (Invalid i) { n=-1; }
6.942 - bool operator==(const Node i) const {return n==i.n;}
6.943 - bool operator!=(const Node i) const {return n!=i.n;}
6.944 - bool operator<(const Node i) const {return n<i.n;}
6.945 - };
6.946 -
6.947 - class NodeIt : public Node {
6.948 - friend class NodeSet;
6.949 - public:
6.950 - NodeIt(const NodeSet& G) : Node(G.first_node) { }
6.951 - NodeIt() : Node() { }
6.952 - };
6.953 -
6.954 - class Edge {
6.955 - //friend class NodeSet;
6.956 - //template <typename T> friend class EdgeMap;
6.957 -
6.958 - //template <typename T> friend class SymNodeSet::SymEdgeMap;
6.959 - //friend Edge SymNodeSet::opposite(Edge) const;
6.960 -
6.961 - // friend class Node;
6.962 - // friend class NodeIt;
6.963 - protected:
6.964 - //friend int NodeSet::id(Edge e) const;
6.965 - // Edge(int nn) {}
6.966 - public:
6.967 - Edge() { }
6.968 - Edge (Invalid) { }
6.969 - bool operator==(const Edge i) const {return true;}
6.970 - bool operator!=(const Edge i) const {return false;}
6.971 - bool operator<(const Edge i) const {return false;}
6.972 - ///\bug This is a workaround until somebody tells me how to
6.973 - ///make class \c SymNodeSet::SymEdgeMap friend of Edge
6.974 - // int idref() {return -1;}
6.975 - // int idref() const {return -1;}
6.976 - };
6.977 -
6.978 - class EdgeIt : public Edge {
6.979 - //friend class NodeSet;
6.980 - public:
6.981 - EdgeIt(const NodeSet& G) : Edge() { }
6.982 - EdgeIt (Invalid i) : Edge(i) { }
6.983 - EdgeIt() : Edge() { }
6.984 - ///\bug This is a workaround until somebody tells me how to
6.985 - ///make class \c SymNodeSet::SymEdgeMap friend of Edge
6.986 - // int idref() {return -1;}
6.987 - };
6.988 -
6.989 - class OutEdgeIt : public Edge {
6.990 - friend class NodeSet;
6.991 - public:
6.992 - OutEdgeIt() : Edge() { }
6.993 - OutEdgeIt (Invalid i) : Edge(i) { }
6.994 - OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
6.995 - };
6.996 -
6.997 - class InEdgeIt : public Edge {
6.998 - friend class NodeSet;
6.999 - public:
6.1000 - InEdgeIt() : Edge() { }
6.1001 - InEdgeIt (Invalid i) : Edge(i) { }
6.1002 - InEdgeIt(const NodeSet& G,Node v) :Edge() {}
6.1003 - };
6.1004 -
6.1005 - template <typename T> class NodeMap : public DynMapBase<Node>
6.1006 - {
6.1007 - std::vector<T> container;
6.1008 -
6.1009 - public:
6.1010 - typedef T ValueType;
6.1011 - typedef Node KeyType;
6.1012 -
6.1013 - NodeMap(const NodeSet &_G) :
6.1014 - DynMapBase<Node>(_G), container(_G.maxNodeId())
6.1015 - {
6.1016 - G->dyn_node_maps.push_back(this);
6.1017 - }
6.1018 - NodeMap(const NodeSet &_G,const T &t) :
6.1019 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
6.1020 - {
6.1021 - G->dyn_node_maps.push_back(this);
6.1022 - }
6.1023 -
6.1024 - NodeMap(const NodeMap<T> &m) :
6.1025 - DynMapBase<Node>(*m.G), container(m.container)
6.1026 - {
6.1027 - G->dyn_node_maps.push_back(this);
6.1028 - }
6.1029 -
6.1030 - template<typename TT> friend class NodeMap;
6.1031 -
6.1032 - ///\todo It can copy between different types.
6.1033 - ///
6.1034 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
6.1035 - DynMapBase<Node>(*m.G)
6.1036 - {
6.1037 - G->dyn_node_maps.push_back(this);
6.1038 - typename std::vector<TT>::const_iterator i;
6.1039 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
6.1040 - i!=m.container.end();
6.1041 - i++)
6.1042 - container.push_back(*i);
6.1043 - }
6.1044 - ~NodeMap()
6.1045 - {
6.1046 - if(G) {
6.1047 - std::vector<DynMapBase<Node>* >::iterator i;
6.1048 - for(i=G->dyn_node_maps.begin();
6.1049 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
6.1050 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
6.1051 - //A better way to do that: (Is this really important?)
6.1052 - if(*i==this) {
6.1053 - *i=G->dyn_node_maps.back();
6.1054 - G->dyn_node_maps.pop_back();
6.1055 - }
6.1056 - }
6.1057 - }
6.1058 -
6.1059 - void add(const Node k)
6.1060 - {
6.1061 - if(k.n>=int(container.size())) container.resize(k.n+1);
6.1062 - }
6.1063 -
6.1064 - void erase(const Node) { }
6.1065 -
6.1066 - void set(Node n, T a) { container[n.n]=a; }
6.1067 - //'T& operator[](Node n)' would be wrong here
6.1068 - typename std::vector<T>::reference
6.1069 - operator[](Node n) { return container[n.n]; }
6.1070 - //'const T& operator[](Node n)' would be wrong here
6.1071 - typename std::vector<T>::const_reference
6.1072 - operator[](Node n) const { return container[n.n]; }
6.1073 -
6.1074 - ///\warning There is no safety check at all!
6.1075 - ///Using operator = between maps attached to different graph may
6.1076 - ///cause serious problem.
6.1077 - ///\todo Is this really so?
6.1078 - ///\todo It can copy between different types.
6.1079 - const NodeMap<T>& operator=(const NodeMap<T> &m)
6.1080 - {
6.1081 - container = m.container;
6.1082 - return *this;
6.1083 - }
6.1084 - template<typename TT>
6.1085 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
6.1086 - {
6.1087 - std::copy(m.container.begin(), m.container.end(), container.begin());
6.1088 - return *this;
6.1089 - }
6.1090 -
6.1091 - void update() {} //Useless for Dynamic Maps
6.1092 - void update(T a) {} //Useless for Dynamic Maps
6.1093 - };
6.1094 -
6.1095 - template <typename T> class EdgeMap
6.1096 - {
6.1097 - public:
6.1098 - typedef T ValueType;
6.1099 - typedef Edge KeyType;
6.1100 -
6.1101 - EdgeMap(const NodeSet &) { }
6.1102 - EdgeMap(const NodeSet &,const T &) { }
6.1103 - EdgeMap(const EdgeMap<T> &) { }
6.1104 - // template<typename TT> friend class EdgeMap;
6.1105 -
6.1106 - ///\todo It can copy between different types.
6.1107 - ///
6.1108 - template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
6.1109 - ~EdgeMap() { }
6.1110 -
6.1111 - void add(const Edge ) { }
6.1112 - void erase(const Edge) { }
6.1113 -
6.1114 - void set(Edge, T) { }
6.1115 - //T get(Edge n) const { return container[n.n]; }
6.1116 - ValueType &operator[](Edge) { return *((T*)(NULL)); }
6.1117 - const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
6.1118 -
6.1119 - const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
6.1120 -
6.1121 - template<typename TT>
6.1122 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
6.1123 -
6.1124 - void update() {}
6.1125 - void update(T a) {}
6.1126 - };
6.1127 - };
6.1128 -
6.1129 -
6.1130 -
6.1131 - ///Graph structure using a node set of another graph.
6.1132 -
6.1133 - ///This structure can be used to establish another graph over a node set
6.1134 - /// of an existing one. The node iterator will go through the nodes of the
6.1135 - /// original graph, and the NodeMap's of both graphs will convert to
6.1136 - /// each other.
6.1137 - ///
6.1138 - ///\warning Adding or deleting nodes from the graph is not safe if an
6.1139 - ///\ref EdgeSet is currently attached to it!
6.1140 - ///
6.1141 - ///\todo Make it possible to add/delete edges from the base graph
6.1142 - ///(and from \ref EdgeSet, as well)
6.1143 - ///
6.1144 - ///\param GG The type of the graph which shares its node set with this class.
6.1145 - ///Its interface must conform with \ref GraphSkeleton.
6.1146 - ///
6.1147 - ///It conforms to the graph interface documented under
6.1148 - ///the description of \ref GraphSkeleton.
6.1149 - ///\sa \ref GraphSkeleton.
6.1150 - ///\sa \ref NodeSet.
6.1151 - template<typename GG>
6.1152 - class EdgeSet {
6.1153 -
6.1154 - typedef GG NodeGraphType;
6.1155 -
6.1156 - NodeGraphType &G;
6.1157 -
6.1158 - public:
6.1159 - class Node;
6.1160 - int id(Node v) const;
6.1161 -
6.1162 - class Node : public NodeGraphType::Node {
6.1163 - friend class EdgeSet;
6.1164 - // template <typename T> friend class NodeMap;
6.1165 -
6.1166 - friend class Edge;
6.1167 - friend class OutEdgeIt;
6.1168 - friend class InEdgeIt;
6.1169 - friend class SymEdge;
6.1170 -
6.1171 - public:
6.1172 - friend int EdgeSet::id(Node v) const;
6.1173 - // Node(int nn) {n=nn;}
6.1174 - public:
6.1175 - Node() : NodeGraphType::Node() {}
6.1176 - Node (Invalid i) : NodeGraphType::Node(i) {}
6.1177 - Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
6.1178 - };
6.1179 -
6.1180 - class NodeIt : public NodeGraphType::NodeIt {
6.1181 - friend class EdgeSet;
6.1182 - public:
6.1183 - NodeIt() : NodeGraphType::NodeIt() { }
6.1184 - NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
6.1185 - NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
6.1186 - NodeIt(const typename NodeGraphType::NodeIt &n)
6.1187 - : NodeGraphType::NodeIt(n) {}
6.1188 - operator Node() { return Node(*this);}
6.1189 - };
6.1190 -
6.1191 - private:
6.1192 - //Edges are double linked.
6.1193 - //The free edges are only single linked using the "next_in" field.
6.1194 - struct NodeT
6.1195 - {
6.1196 - int first_in,first_out;
6.1197 - NodeT() : first_in(-1), first_out(-1) { }
6.1198 - };
6.1199 -
6.1200 - struct EdgeT
6.1201 - {
6.1202 - Node head, tail;
6.1203 - int prev_in, prev_out;
6.1204 - int next_in, next_out;
6.1205 - };
6.1206 -
6.1207 -
6.1208 - typename NodeGraphType::template NodeMap<NodeT> nodes;
6.1209 -
6.1210 - std::vector<EdgeT> edges;
6.1211 - //The first free edge
6.1212 - int first_free_edge;
6.1213 -
6.1214 - protected:
6.1215 -
6.1216 - template <typename Key> class DynMapBase
6.1217 - {
6.1218 - protected:
6.1219 - const EdgeSet* G;
6.1220 - public:
6.1221 - virtual void add(const Key k) = 0;
6.1222 - virtual void erase(const Key k) = 0;
6.1223 - DynMapBase(const EdgeSet &_G) : G(&_G) {}
6.1224 - virtual ~DynMapBase() {}
6.1225 - friend class EdgeSet;
6.1226 - };
6.1227 -
6.1228 - public:
6.1229 - //template <typename T> class NodeMap;
6.1230 - template <typename T> class EdgeMap;
6.1231 -
6.1232 - class Node;
6.1233 - class Edge;
6.1234 -
6.1235 - // protected:
6.1236 - // HELPME:
6.1237 - protected:
6.1238 - // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
6.1239 - ///\bug It must be public because of SymEdgeMap.
6.1240 - ///
6.1241 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
6.1242 -
6.1243 - public:
6.1244 -
6.1245 - class NodeIt;
6.1246 - class EdgeIt;
6.1247 - class OutEdgeIt;
6.1248 - class InEdgeIt;
6.1249 -
6.1250 - template <typename T> class NodeMap;
6.1251 - template <typename T> class EdgeMap;
6.1252 -
6.1253 - public:
6.1254 -
6.1255 - ///Constructor
6.1256 -
6.1257 - ///Construates a new graph based on the nodeset of an existing one.
6.1258 - ///\param _G the base graph.
6.1259 - ///\todo It looks like a copy constructor, but it isn't.
6.1260 - EdgeSet(NodeGraphType &_G) : G(_G),
6.1261 - nodes(_G), edges(),
6.1262 - first_free_edge(-1) { }
6.1263 - ///Copy constructor
6.1264 -
6.1265 - ///Makes a copy of an EdgeSet.
6.1266 - ///It will be based on the same graph.
6.1267 - EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
6.1268 - first_free_edge(_g.first_free_edge) { }
6.1269 -
6.1270 - ~EdgeSet()
6.1271 - {
6.1272 - // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
6.1273 - // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
6.1274 - for(typename std::vector<DynMapBase<Edge> * >::iterator
6.1275 - i=dyn_edge_maps.begin();
6.1276 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
6.1277 - }
6.1278 -
6.1279 - int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
6.1280 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
6.1281 -
6.1282 - ///\bug This function does something different than
6.1283 - ///its name would suggests...
6.1284 - int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
6.1285 - ///\bug This function does something different than
6.1286 - ///its name would suggests...
6.1287 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
6.1288 -
6.1289 - Node tail(Edge e) const { return edges[e.n].tail; }
6.1290 - Node head(Edge e) const { return edges[e.n].head; }
6.1291 -
6.1292 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
6.1293 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
6.1294 -
6.1295 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
6.1296 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
6.1297 -
6.1298 - NodeIt& first(NodeIt& v) const {
6.1299 - v=NodeIt(*this); return v; }
6.1300 - EdgeIt& first(EdgeIt& e) const {
6.1301 - e=EdgeIt(*this); return e; }
6.1302 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
6.1303 - e=OutEdgeIt(*this,v); return e; }
6.1304 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
6.1305 - e=InEdgeIt(*this,v); return e; }
6.1306 -
6.1307 -// template< typename It >
6.1308 -// It first() const { It e; first(e); return e; }
6.1309 -
6.1310 -// template< typename It >
6.1311 -// It first(Node v) const { It e; first(e,v); return e; }
6.1312 -
6.1313 - bool valid(Edge e) const { return e.n!=-1; }
6.1314 - bool valid(Node n) const { return G.valid(n); }
6.1315 -
6.1316 - void setInvalid(Edge &e) { e.n=-1; }
6.1317 - void setInvalid(Node &n) { G.setInvalid(n); }
6.1318 -
6.1319 - template <typename It> It getNext(It it) const
6.1320 - { It tmp(it); return next(tmp); }
6.1321 -
6.1322 - NodeIt& next(NodeIt& it) const { G.next(it); return it; }
6.1323 - OutEdgeIt& next(OutEdgeIt& it) const
6.1324 - { it.n=edges[it.n].next_out; return it; }
6.1325 - InEdgeIt& next(InEdgeIt& it) const
6.1326 - { it.n=edges[it.n].next_in; return it; }
6.1327 - EdgeIt& next(EdgeIt& it) const {
6.1328 - if(edges[it.n].next_in!=-1) {
6.1329 - it.n=edges[it.n].next_in;
6.1330 - }
6.1331 - else {
6.1332 - NodeIt n;
6.1333 - for(n=next(edges[it.n].head);
6.1334 - valid(n) && nodes[n].first_in == -1;
6.1335 - next(n)) ;
6.1336 - it.n = (valid(n))?-1:nodes[n].first_in;
6.1337 - }
6.1338 - return it;
6.1339 - }
6.1340 -
6.1341 - int id(Edge e) const { return e.n; }
6.1342 -
6.1343 - /// Adds a new node to the graph.
6.1344 - Node addNode() { return G.AddNode(); }
6.1345 -
6.1346 - Edge addEdge(Node u, Node v) {
6.1347 - int n;
6.1348 -
6.1349 - if(first_free_edge==-1)
6.1350 - {
6.1351 - n = edges.size();
6.1352 - edges.push_back(EdgeT());
6.1353 - }
6.1354 - else {
6.1355 - n = first_free_edge;
6.1356 - first_free_edge = edges[n].next_in;
6.1357 - }
6.1358 -
6.1359 - edges[n].tail = u; edges[n].head = v;
6.1360 -
6.1361 - edges[n].next_out = nodes[u].first_out;
6.1362 - if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
6.1363 - edges[n].next_in = nodes[v].first_in;
6.1364 - if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
6.1365 - edges[n].prev_in = edges[n].prev_out = -1;
6.1366 -
6.1367 - nodes[u].first_out = nodes[v].first_in = n;
6.1368 -
6.1369 - Edge e; e.n=n;
6.1370 -
6.1371 - //Update dynamic maps
6.1372 - for(typename std::vector<DynMapBase<Edge> * >::iterator
6.1373 - i=dyn_edge_maps.begin();
6.1374 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
6.1375 -
6.1376 - return e;
6.1377 - }
6.1378 -
6.1379 - private:
6.1380 - void eraseEdge(int n) {
6.1381 -
6.1382 - if(edges[n].next_in!=-1)
6.1383 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
6.1384 - if(edges[n].prev_in!=-1)
6.1385 - edges[edges[n].prev_in].next_in = edges[n].next_in;
6.1386 - else nodes[edges[n].head].first_in = edges[n].next_in;
6.1387 -
6.1388 - if(edges[n].next_out!=-1)
6.1389 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
6.1390 - if(edges[n].prev_out!=-1)
6.1391 - edges[edges[n].prev_out].next_out = edges[n].next_out;
6.1392 - else nodes[edges[n].tail].first_out = edges[n].next_out;
6.1393 -
6.1394 - edges[n].next_in = first_free_edge;
6.1395 - first_free_edge = -1;
6.1396 -
6.1397 - //Update dynamic maps
6.1398 - Edge e; e.n=n;
6.1399 - for(typename std::vector<DynMapBase<Edge> * >::iterator
6.1400 - i=dyn_edge_maps.begin();
6.1401 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
6.1402 - }
6.1403 -
6.1404 - public:
6.1405 -
6.1406 -// void erase(Node nn) {
6.1407 -// int n=nn.n;
6.1408 -// int m;
6.1409 -// while((m=nodes[n].first_in)!=-1) eraseEdge(m);
6.1410 -// while((m=nodes[n].first_out)!=-1) eraseEdge(m);
6.1411 -// }
6.1412 -
6.1413 - void erase(Edge e) { eraseEdge(e.n); }
6.1414 -
6.1415 -// //\bug Dynamic maps must be updated!
6.1416 -// //
6.1417 -// void clear() {
6.1418 -// nodes.clear();edges.clear();
6.1419 -// first_node=first_free_node=first_free_edge=-1;
6.1420 -// }
6.1421 -
6.1422 - class Edge {
6.1423 - friend class EdgeSet;
6.1424 - template <typename T> friend class EdgeMap;
6.1425 -
6.1426 - //template <typename T> friend class SymEdgeSet::SymEdgeMap;
6.1427 - //friend Edge SymEdgeSet::opposite(Edge) const;
6.1428 -
6.1429 - friend class Node;
6.1430 - friend class NodeIt;
6.1431 - protected:
6.1432 - int n;
6.1433 - friend int EdgeSet::id(Edge e) const;
6.1434 -
6.1435 - Edge(int nn) {n=nn;}
6.1436 - public:
6.1437 - Edge() { }
6.1438 - Edge (Invalid) { n=-1; }
6.1439 - bool operator==(const Edge i) const {return n==i.n;}
6.1440 - bool operator!=(const Edge i) const {return n!=i.n;}
6.1441 - bool operator<(const Edge i) const {return n<i.n;}
6.1442 - ///\bug This is a workaround until somebody tells me how to
6.1443 - ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
6.1444 - int &idref() {return n;}
6.1445 - const int &idref() const {return n;}
6.1446 - };
6.1447 -
6.1448 - class EdgeIt : public Edge {
6.1449 - friend class EdgeSet;
6.1450 - public:
6.1451 - EdgeIt(const EdgeSet& G) : Edge() {
6.1452 - // typename NodeGraphType::Node m;
6.1453 - NodeIt m;
6.1454 - for(G.first(m);
6.1455 - G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
6.1456 - //AJJAJ! This is a non sense!!!!!!!
6.1457 - this->n = G.valid(m)?-1:G.nodes[m].first_in;
6.1458 - }
6.1459 - EdgeIt (Invalid i) : Edge(i) { }
6.1460 - EdgeIt() : Edge() { }
6.1461 - ///\bug This is a workaround until somebody tells me how to
6.1462 - ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
6.1463 - int &idref() {return this->n;}
6.1464 - };
6.1465 -
6.1466 - class OutEdgeIt : public Edge {
6.1467 - friend class EdgeSet;
6.1468 - public:
6.1469 - OutEdgeIt() : Edge() { }
6.1470 - OutEdgeIt (Invalid i) : Edge(i) { }
6.1471 -
6.1472 - OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
6.1473 - };
6.1474 -
6.1475 - class InEdgeIt : public Edge {
6.1476 - friend class EdgeSet;
6.1477 - public:
6.1478 - InEdgeIt() : Edge() { }
6.1479 - InEdgeIt (Invalid i) : Edge(i) { }
6.1480 - InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
6.1481 - };
6.1482 -
6.1483 - template <typename T> class NodeMap :
6.1484 - public NodeGraphType::template NodeMap<T>
6.1485 - {
6.1486 - public:
6.1487 - NodeMap(const EdgeSet &_G) :
6.1488 - NodeGraphType::NodeMap(_G.G) { } //AJAJJ <T> would be wrong!!!
6.1489 - NodeMap(const EdgeSet &_G,const T &t) :
6.1490 - NodeGraphType::NodeMap(_G.G,t) { }
6.1491 - //It is unnecessary
6.1492 - NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
6.1493 - NodeGraphType::NodeMap(m) { }
6.1494 -
6.1495 - ///\todo It can copy between different types.
6.1496 - ///
6.1497 - template<typename TT>
6.1498 - NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
6.1499 - : NodeGraphType::NodeMap(m) { }
6.1500 - };
6.1501 -
6.1502 - template <typename T> class EdgeMap : public DynMapBase<Edge>
6.1503 - {
6.1504 - std::vector<T> container;
6.1505 -
6.1506 - public:
6.1507 - typedef T ValueType;
6.1508 - typedef Edge KeyType;
6.1509 -
6.1510 - EdgeMap(const EdgeSet &_G) :
6.1511 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
6.1512 - {
6.1513 - //FIXME: What if there are empty Id's?
6.1514 - //FIXME: Can I use 'this' in a constructor?
6.1515 - G->dyn_edge_maps.push_back(this);
6.1516 - }
6.1517 - EdgeMap(const EdgeSet &_G,const T &t) :
6.1518 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
6.1519 - {
6.1520 - G->dyn_edge_maps.push_back(this);
6.1521 - }
6.1522 - EdgeMap(const EdgeMap<T> &m) :
6.1523 - DynMapBase<Edge>(*m.G), container(m.container)
6.1524 - {
6.1525 - G->dyn_edge_maps.push_back(this);
6.1526 - }
6.1527 -
6.1528 - template<typename TT> friend class EdgeMap;
6.1529 -
6.1530 - ///\todo It can copy between different types.
6.1531 - ///
6.1532 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
6.1533 - DynMapBase<Edge>(*m.G)
6.1534 - {
6.1535 - G->dyn_edge_maps.push_back(this);
6.1536 - typename std::vector<TT>::const_iterator i;
6.1537 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
6.1538 - i!=m.container.end();
6.1539 - i++)
6.1540 - container.push_back(*i);
6.1541 - }
6.1542 - ~EdgeMap()
6.1543 - {
6.1544 - if(G) {
6.1545 - typename std::vector<DynMapBase<Edge>* >::iterator i;
6.1546 - for(i=G->dyn_edge_maps.begin();
6.1547 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
6.1548 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
6.1549 - //A better way to do that: (Is this really important?)
6.1550 - if(*i==this) {
6.1551 - *i=G->dyn_edge_maps.back();
6.1552 - G->dyn_edge_maps.pop_back();
6.1553 - }
6.1554 - }
6.1555 - }
6.1556 -
6.1557 - void add(const Edge k)
6.1558 - {
6.1559 - if(k.n>=int(container.size())) container.resize(k.n+1);
6.1560 - }
6.1561 - void erase(const Edge) { }
6.1562 -
6.1563 - void set(Edge n, T a) { container[n.n]=a; }
6.1564 - //T get(Edge n) const { return container[n.n]; }
6.1565 - typename std::vector<T>::reference
6.1566 - operator[](Edge n) { return container[n.n]; }
6.1567 - typename std::vector<T>::const_reference
6.1568 - operator[](Edge n) const { return container[n.n]; }
6.1569 -
6.1570 - ///\warning There is no safety check at all!
6.1571 - ///Using operator = between maps attached to different graph may
6.1572 - ///cause serious problem.
6.1573 - ///\todo Is this really so?
6.1574 - ///\todo It can copy between different types.
6.1575 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
6.1576 - {
6.1577 - container = m.container;
6.1578 - return *this;
6.1579 - }
6.1580 - template<typename TT>
6.1581 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
6.1582 - {
6.1583 - std::copy(m.container.begin(), m.container.end(), container.begin());
6.1584 - return *this;
6.1585 - }
6.1586 -
6.1587 - void update() {} //Useless for DynMaps
6.1588 - void update(T a) {} //Useless for DynMaps
6.1589 - };
6.1590 -
6.1591 - };
6.1592 -
6.1593 - template< typename GG>
6.1594 - int EdgeSet<GG>::id(Node v) const { return G.id(v); }
6.1595 -
6.1596 -/// @}
6.1597 -
6.1598 -} //namespace hugo
6.1599 -
6.1600 -#endif //HUGO_LIST_GRAPH_H