1.1 --- a/src/work/alpar/list_graph.h Fri May 07 11:57:34 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1597 +0,0 @@
1.4 -// -*- mode:C++ -*-
1.5 -
1.6 -#ifndef HUGO_LIST_GRAPH_H
1.7 -#define HUGO_LIST_GRAPH_H
1.8 -
1.9 -///\ingroup graphs
1.10 -///\file
1.11 -///\brief ListGraph, SymListGraph, NodeSet and EdgeSet classes.
1.12 -
1.13 -#include <vector>
1.14 -#include <limits.h>
1.15 -
1.16 -#include <hugo/invalid.h>
1.17 -
1.18 -namespace hugo {
1.19 -
1.20 -/// \addtogroup graphs
1.21 -/// @{
1.22 -
1.23 - class SymListGraph;
1.24 -
1.25 - ///A list graph class.
1.26 -
1.27 - ///This is a simple and fast erasable graph implementation.
1.28 - ///
1.29 - ///It conforms to the graph interface documented under
1.30 - ///the description of \ref GraphSkeleton.
1.31 - ///\sa \ref GraphSkeleton.
1.32 - class ListGraph {
1.33 -
1.34 - //Nodes are double linked.
1.35 - //The free nodes are only single linked using the "next" field.
1.36 - struct NodeT
1.37 - {
1.38 - int first_in,first_out;
1.39 - int prev, next;
1.40 - // NodeT() {}
1.41 - };
1.42 - //Edges are double linked.
1.43 - //The free edges are only single linked using the "next_in" field.
1.44 - struct EdgeT
1.45 - {
1.46 - int head, tail;
1.47 - int prev_in, prev_out;
1.48 - int next_in, next_out;
1.49 - //FIXME: is this necessary?
1.50 - // EdgeT() : next_in(-1), next_out(-1) prev_in(-1), prev_out(-1) {}
1.51 - };
1.52 -
1.53 - std::vector<NodeT> nodes;
1.54 - //The first node
1.55 - int first_node;
1.56 - //The first free node
1.57 - int first_free_node;
1.58 - std::vector<EdgeT> edges;
1.59 - //The first free edge
1.60 - int first_free_edge;
1.61 -
1.62 - protected:
1.63 -
1.64 - template <typename Key> class DynMapBase
1.65 - {
1.66 - protected:
1.67 - const ListGraph* G;
1.68 - public:
1.69 - virtual void add(const Key k) = 0;
1.70 - virtual void erase(const Key k) = 0;
1.71 - DynMapBase(const ListGraph &_G) : G(&_G) {}
1.72 - virtual ~DynMapBase() {}
1.73 - friend class ListGraph;
1.74 - };
1.75 -
1.76 - public:
1.77 - template <typename T> class EdgeMap;
1.78 - template <typename T> class NodeMap;
1.79 -
1.80 - class Node;
1.81 - class Edge;
1.82 -
1.83 - // protected:
1.84 - // HELPME:
1.85 - protected:
1.86 - ///\bug It must be public because of SymEdgeMap.
1.87 - ///
1.88 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.89 - ///\bug It must be public because of SymEdgeMap.
1.90 - ///
1.91 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.92 -
1.93 - public:
1.94 -
1.95 - class NodeIt;
1.96 - class EdgeIt;
1.97 - class OutEdgeIt;
1.98 - class InEdgeIt;
1.99 -
1.100 - template <typename T> class NodeMap;
1.101 - template <typename T> class EdgeMap;
1.102 -
1.103 - public:
1.104 -
1.105 - ListGraph() : nodes(), first_node(-1),
1.106 - first_free_node(-1), edges(), first_free_edge(-1) {}
1.107 - ListGraph(const ListGraph &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.108 - first_free_node(_g.first_free_node),
1.109 - edges(_g.edges),
1.110 - first_free_edge(_g.first_free_edge) {}
1.111 -
1.112 - ~ListGraph()
1.113 - {
1.114 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.115 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.116 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.117 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.118 - }
1.119 -
1.120 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.121 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.122 -
1.123 - ///\bug This function does something different than
1.124 - ///its name would suggests...
1.125 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
1.126 - ///\bug This function does something different than
1.127 - ///its name would suggests...
1.128 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1.129 -
1.130 - Node tail(Edge e) const { return edges[e.n].tail; }
1.131 - Node head(Edge e) const { return edges[e.n].head; }
1.132 -
1.133 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1.134 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1.135 -
1.136 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1.137 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1.138 -
1.139 - NodeIt& first(NodeIt& v) const {
1.140 - v=NodeIt(*this); return v; }
1.141 - EdgeIt& first(EdgeIt& e) const {
1.142 - e=EdgeIt(*this); return e; }
1.143 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.144 - e=OutEdgeIt(*this,v); return e; }
1.145 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.146 - e=InEdgeIt(*this,v); return e; }
1.147 -
1.148 -// template< typename It >
1.149 -// It first() const { It e; first(e); return e; }
1.150 -
1.151 -// template< typename It >
1.152 -// It first(Node v) const { It e; first(e,v); return e; }
1.153 -
1.154 - bool valid(Edge e) const { return e.n!=-1; }
1.155 - bool valid(Node n) const { return n.n!=-1; }
1.156 -
1.157 - void setInvalid(Edge &e) { e.n=-1; }
1.158 - void setInvalid(Node &n) { n.n=-1; }
1.159 -
1.160 - template <typename It> It getNext(It it) const
1.161 - { It tmp(it); return next(tmp); }
1.162 -
1.163 - NodeIt& next(NodeIt& it) const {
1.164 - it.n=nodes[it.n].next;
1.165 - return it;
1.166 - }
1.167 - OutEdgeIt& next(OutEdgeIt& it) const
1.168 - { it.n=edges[it.n].next_out; return it; }
1.169 - InEdgeIt& next(InEdgeIt& it) const
1.170 - { it.n=edges[it.n].next_in; return it; }
1.171 - EdgeIt& next(EdgeIt& it) const {
1.172 - if(edges[it.n].next_in!=-1) {
1.173 - it.n=edges[it.n].next_in;
1.174 - }
1.175 - else {
1.176 - int n;
1.177 - for(n=nodes[edges[it.n].head].next;
1.178 - n!=-1 && nodes[n].first_in == -1;
1.179 - n = nodes[n].next) ;
1.180 - it.n = (n==-1)?-1:nodes[n].first_in;
1.181 - }
1.182 - return it;
1.183 - }
1.184 -
1.185 - int id(Node v) const { return v.n; }
1.186 - int id(Edge e) const { return e.n; }
1.187 -
1.188 - /// Adds a new node to the graph.
1.189 -
1.190 - /// \todo It adds the nodes in a reversed order.
1.191 - /// (i.e. the lastly added node becomes the first.)
1.192 - Node addNode() {
1.193 - int n;
1.194 -
1.195 - if(first_free_node==-1)
1.196 - {
1.197 - n = nodes.size();
1.198 - nodes.push_back(NodeT());
1.199 - }
1.200 - else {
1.201 - n = first_free_node;
1.202 - first_free_node = nodes[n].next;
1.203 - }
1.204 -
1.205 - nodes[n].next = first_node;
1.206 - if(first_node != -1) nodes[first_node].prev = n;
1.207 - first_node = n;
1.208 - nodes[n].prev = -1;
1.209 -
1.210 - nodes[n].first_in = nodes[n].first_out = -1;
1.211 -
1.212 - Node nn; nn.n=n;
1.213 -
1.214 - //Update dynamic maps
1.215 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.216 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
1.217 -
1.218 - return nn;
1.219 - }
1.220 -
1.221 - Edge addEdge(Node u, Node v) {
1.222 - int n;
1.223 -
1.224 - if(first_free_edge==-1)
1.225 - {
1.226 - n = edges.size();
1.227 - edges.push_back(EdgeT());
1.228 - }
1.229 - else {
1.230 - n = first_free_edge;
1.231 - first_free_edge = edges[n].next_in;
1.232 - }
1.233 -
1.234 - edges[n].tail = u.n; edges[n].head = v.n;
1.235 -
1.236 - edges[n].next_out = nodes[u.n].first_out;
1.237 - if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
1.238 - edges[n].next_in = nodes[v.n].first_in;
1.239 - if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
1.240 - edges[n].prev_in = edges[n].prev_out = -1;
1.241 -
1.242 - nodes[u.n].first_out = nodes[v.n].first_in = n;
1.243 -
1.244 - Edge e; e.n=n;
1.245 -
1.246 - //Update dynamic maps
1.247 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.248 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.249 -
1.250 - return e;
1.251 - }
1.252 -
1.253 - private:
1.254 - void eraseEdge(int n) {
1.255 -
1.256 - if(edges[n].next_in!=-1)
1.257 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.258 - if(edges[n].prev_in!=-1)
1.259 - edges[edges[n].prev_in].next_in = edges[n].next_in;
1.260 - else nodes[edges[n].head].first_in = edges[n].next_in;
1.261 -
1.262 - if(edges[n].next_out!=-1)
1.263 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.264 - if(edges[n].prev_out!=-1)
1.265 - edges[edges[n].prev_out].next_out = edges[n].next_out;
1.266 - else nodes[edges[n].tail].first_out = edges[n].next_out;
1.267 -
1.268 - edges[n].next_in = first_free_edge;
1.269 - first_free_edge = -1;
1.270 -
1.271 - //Update dynamic maps
1.272 - Edge e; e.n=n;
1.273 - for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.274 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1.275 - }
1.276 -
1.277 - public:
1.278 -
1.279 - void erase(Node nn) {
1.280 - int n=nn.n;
1.281 -
1.282 - int m;
1.283 - while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1.284 - while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1.285 -
1.286 - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
1.287 - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
1.288 - else first_node = nodes[n].next;
1.289 -
1.290 - nodes[n].next = first_free_node;
1.291 - first_free_node = n;
1.292 -
1.293 - //Update dynamic maps
1.294 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.295 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
1.296 - }
1.297 -
1.298 - void erase(Edge e) { eraseEdge(e.n); }
1.299 -
1.300 - ///\bug Dynamic maps must be updated!
1.301 - ///
1.302 - void clear() {
1.303 - nodes.clear();edges.clear();
1.304 - first_node=first_free_node=first_free_edge=-1;
1.305 - }
1.306 -
1.307 - class Node {
1.308 - friend class ListGraph;
1.309 - template <typename T> friend class NodeMap;
1.310 -
1.311 - friend class Edge;
1.312 - friend class OutEdgeIt;
1.313 - friend class InEdgeIt;
1.314 - friend class SymEdge;
1.315 -
1.316 - protected:
1.317 - int n;
1.318 - friend int ListGraph::id(Node v) const;
1.319 - Node(int nn) {n=nn;}
1.320 - public:
1.321 - Node() {}
1.322 - Node (Invalid) { n=-1; }
1.323 - bool operator==(const Node i) const {return n==i.n;}
1.324 - bool operator!=(const Node i) const {return n!=i.n;}
1.325 - bool operator<(const Node i) const {return n<i.n;}
1.326 - };
1.327 -
1.328 - class NodeIt : public Node {
1.329 - friend class ListGraph;
1.330 - public:
1.331 - NodeIt() : Node() { }
1.332 - NodeIt(Invalid i) : Node(i) { }
1.333 - NodeIt(const ListGraph& G) : Node(G.first_node) { }
1.334 - };
1.335 -
1.336 - class Edge {
1.337 - friend class ListGraph;
1.338 - template <typename T> friend class EdgeMap;
1.339 -
1.340 - //template <typename T> friend class SymListGraph::SymEdgeMap;
1.341 - //friend Edge SymListGraph::opposite(Edge) const;
1.342 -
1.343 - friend class Node;
1.344 - friend class NodeIt;
1.345 - protected:
1.346 - int n;
1.347 - friend int ListGraph::id(Edge e) const;
1.348 -
1.349 - Edge(int nn) {n=nn;}
1.350 - public:
1.351 - Edge() { }
1.352 - Edge (Invalid) { n=-1; }
1.353 - bool operator==(const Edge i) const {return n==i.n;}
1.354 - bool operator!=(const Edge i) const {return n!=i.n;}
1.355 - bool operator<(const Edge i) const {return n<i.n;}
1.356 - ///\bug This is a workaround until somebody tells me how to
1.357 - ///make class \c SymListGraph::SymEdgeMap friend of Edge
1.358 - int &idref() {return n;}
1.359 - const int &idref() const {return n;}
1.360 - };
1.361 -
1.362 - class EdgeIt : public Edge {
1.363 - friend class ListGraph;
1.364 - public:
1.365 - EdgeIt(const ListGraph& G) : Edge() {
1.366 - int m;
1.367 - for(m=G.first_node;
1.368 - m!=-1 && G.nodes[m].first_in == -1; m = G.nodes[m].next);
1.369 - n = (m==-1)?-1:G.nodes[m].first_in;
1.370 - }
1.371 - EdgeIt (Invalid i) : Edge(i) { }
1.372 - EdgeIt() : Edge() { }
1.373 - ///\bug This is a workaround until somebody tells me how to
1.374 - ///make class \c SymListGraph::SymEdgeMap friend of Edge
1.375 - int &idref() {return n;}
1.376 - };
1.377 -
1.378 - class OutEdgeIt : public Edge {
1.379 - friend class ListGraph;
1.380 - public:
1.381 - OutEdgeIt() : Edge() { }
1.382 - OutEdgeIt (Invalid i) : Edge(i) { }
1.383 -
1.384 - OutEdgeIt(const ListGraph& G,const Node v)
1.385 - : Edge(G.nodes[v.n].first_out) {}
1.386 - };
1.387 -
1.388 - class InEdgeIt : public Edge {
1.389 - friend class ListGraph;
1.390 - public:
1.391 - InEdgeIt() : Edge() { }
1.392 - InEdgeIt (Invalid i) : Edge(i) { }
1.393 - InEdgeIt(const ListGraph& G,Node v) :Edge(G.nodes[v.n].first_in){}
1.394 - };
1.395 -
1.396 - template <typename T> class NodeMap : public DynMapBase<Node>
1.397 - {
1.398 - std::vector<T> container;
1.399 -
1.400 - public:
1.401 - typedef T ValueType;
1.402 - typedef Node KeyType;
1.403 -
1.404 - NodeMap(const ListGraph &_G) :
1.405 - DynMapBase<Node>(_G), container(_G.maxNodeId())
1.406 - {
1.407 - G->dyn_node_maps.push_back(this);
1.408 - }
1.409 - NodeMap(const ListGraph &_G,const T &t) :
1.410 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.411 - {
1.412 - G->dyn_node_maps.push_back(this);
1.413 - }
1.414 -
1.415 - NodeMap(const NodeMap<T> &m) :
1.416 - DynMapBase<Node>(*m.G), container(m.container)
1.417 - {
1.418 - G->dyn_node_maps.push_back(this);
1.419 - }
1.420 -
1.421 - template<typename TT> friend class NodeMap;
1.422 -
1.423 - ///\todo It can copy between different types.
1.424 - ///
1.425 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.426 - DynMapBase<Node>(*m.G)
1.427 - {
1.428 - G->dyn_node_maps.push_back(this);
1.429 - typename std::vector<TT>::const_iterator i;
1.430 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.431 - i!=m.container.end();
1.432 - i++)
1.433 - container.push_back(*i);
1.434 - }
1.435 - ~NodeMap()
1.436 - {
1.437 - if(G) {
1.438 - std::vector<DynMapBase<Node>* >::iterator i;
1.439 - for(i=G->dyn_node_maps.begin();
1.440 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1.441 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1.442 - //A better way to do that: (Is this really important?)
1.443 - if(*i==this) {
1.444 - *i=G->dyn_node_maps.back();
1.445 - G->dyn_node_maps.pop_back();
1.446 - }
1.447 - }
1.448 - }
1.449 -
1.450 - void add(const Node k)
1.451 - {
1.452 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.453 - }
1.454 -
1.455 - void erase(const Node) { }
1.456 -
1.457 - void set(Node n, T a) { container[n.n]=a; }
1.458 - //'T& operator[](Node n)' would be wrong here
1.459 - typename std::vector<T>::reference
1.460 - operator[](Node n) { return container[n.n]; }
1.461 - //'const T& operator[](Node n)' would be wrong here
1.462 - typename std::vector<T>::const_reference
1.463 - operator[](Node n) const { return container[n.n]; }
1.464 -
1.465 - ///\warning There is no safety check at all!
1.466 - ///Using operator = between maps attached to different graph may
1.467 - ///cause serious problem.
1.468 - ///\todo Is this really so?
1.469 - ///\todo It can copy between different types.
1.470 - const NodeMap<T>& operator=(const NodeMap<T> &m)
1.471 - {
1.472 - container = m.container;
1.473 - return *this;
1.474 - }
1.475 - template<typename TT>
1.476 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.477 - {
1.478 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.479 - return *this;
1.480 - }
1.481 -
1.482 - void update() {} //Useless for Dynamic Maps
1.483 - void update(T a) {} //Useless for Dynamic Maps
1.484 - };
1.485 -
1.486 - template <typename T> class EdgeMap : public DynMapBase<Edge>
1.487 - {
1.488 - std::vector<T> container;
1.489 -
1.490 - public:
1.491 - typedef T ValueType;
1.492 - typedef Edge KeyType;
1.493 -
1.494 - EdgeMap(const ListGraph &_G) :
1.495 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.496 - {
1.497 - //FIXME: What if there are empty Id's?
1.498 - //FIXME: Can I use 'this' in a constructor?
1.499 - G->dyn_edge_maps.push_back(this);
1.500 - }
1.501 - EdgeMap(const ListGraph &_G,const T &t) :
1.502 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.503 - {
1.504 - G->dyn_edge_maps.push_back(this);
1.505 - }
1.506 - EdgeMap(const EdgeMap<T> &m) :
1.507 - DynMapBase<Edge>(*m.G), container(m.container)
1.508 - {
1.509 - G->dyn_edge_maps.push_back(this);
1.510 - }
1.511 -
1.512 - template<typename TT> friend class EdgeMap;
1.513 -
1.514 - ///\todo It can copy between different types.
1.515 - ///
1.516 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.517 - DynMapBase<Edge>(*m.G)
1.518 - {
1.519 - G->dyn_edge_maps.push_back(this);
1.520 - typename std::vector<TT>::const_iterator i;
1.521 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.522 - i!=m.container.end();
1.523 - i++)
1.524 - container.push_back(*i);
1.525 - }
1.526 - ~EdgeMap()
1.527 - {
1.528 - if(G) {
1.529 - std::vector<DynMapBase<Edge>* >::iterator i;
1.530 - for(i=G->dyn_edge_maps.begin();
1.531 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.532 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.533 - //A better way to do that: (Is this really important?)
1.534 - if(*i==this) {
1.535 - *i=G->dyn_edge_maps.back();
1.536 - G->dyn_edge_maps.pop_back();
1.537 - }
1.538 - }
1.539 - }
1.540 -
1.541 - void add(const Edge k)
1.542 - {
1.543 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.544 - }
1.545 - void erase(const Edge) { }
1.546 -
1.547 - void set(Edge n, T a) { container[n.n]=a; }
1.548 - //T get(Edge n) const { return container[n.n]; }
1.549 - typename std::vector<T>::reference
1.550 - operator[](Edge n) { return container[n.n]; }
1.551 - typename std::vector<T>::const_reference
1.552 - operator[](Edge n) const { return container[n.n]; }
1.553 -
1.554 - ///\warning There is no safety check at all!
1.555 - ///Using operator = between maps attached to different graph may
1.556 - ///cause serious problem.
1.557 - ///\todo Is this really so?
1.558 - ///\todo It can copy between different types.
1.559 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.560 - {
1.561 - container = m.container;
1.562 - return *this;
1.563 - }
1.564 - template<typename TT>
1.565 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.566 - {
1.567 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.568 - return *this;
1.569 - }
1.570 -
1.571 - void update() {} //Useless for DynMaps
1.572 - void update(T a) {} //Useless for DynMaps
1.573 - };
1.574 -
1.575 - };
1.576 -
1.577 - ///Graph for bidirectional edges.
1.578 -
1.579 - ///The purpose of this graph structure is to handle graphs
1.580 - ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair
1.581 - ///of oppositely directed edges.
1.582 - ///There is a new edge map type called
1.583 - ///\ref SymListGraph::SymEdgeMap "SymEdgeMap"
1.584 - ///that complements this
1.585 - ///feature by
1.586 - ///storing shared values for the edge pairs. The usual
1.587 - ///\ref GraphSkeleton::EdgeMap "EdgeMap"
1.588 - ///can be used
1.589 - ///as well.
1.590 - ///
1.591 - ///The oppositely directed edge can also be obtained easily
1.592 - ///using \ref opposite.
1.593 - ///
1.594 - ///Here erase(Edge) deletes a pair of edges.
1.595 - ///
1.596 - ///\todo this date structure need some reconsiderations. Maybe it
1.597 - ///should be implemented independently from ListGraph.
1.598 -
1.599 - class SymListGraph : public ListGraph
1.600 - {
1.601 - public:
1.602 - template<typename T> class SymEdgeMap;
1.603 - template<typename T> friend class SymEdgeMap;
1.604 -
1.605 - SymListGraph() : ListGraph() { }
1.606 - SymListGraph(const ListGraph &_g) : ListGraph(_g) { }
1.607 - ///Adds a pair of oppositely directed edges to the graph.
1.608 - Edge addEdge(Node u, Node v)
1.609 - {
1.610 - Edge e = ListGraph::addEdge(u,v);
1.611 - ListGraph::addEdge(v,u);
1.612 - return e;
1.613 - }
1.614 -
1.615 - void erase(Node n) { ListGraph::erase(n); }
1.616 - ///The oppositely directed edge.
1.617 -
1.618 - ///Returns the oppositely directed
1.619 - ///pair of the edge \c e.
1.620 - Edge opposite(Edge e) const
1.621 - {
1.622 - Edge f;
1.623 - f.idref() = e.idref() - 2*(e.idref()%2) + 1;
1.624 - return f;
1.625 - }
1.626 -
1.627 - ///Removes a pair of oppositely directed edges to the graph.
1.628 - void erase(Edge e) {
1.629 - ListGraph::erase(opposite(e));
1.630 - ListGraph::erase(e);
1.631 - }
1.632 -
1.633 - ///Common data storage for the edge pairs.
1.634 -
1.635 - ///This map makes it possible to store data shared by the oppositely
1.636 - ///directed pairs of edges.
1.637 - template <typename T> class SymEdgeMap : public DynMapBase<Edge>
1.638 - {
1.639 - std::vector<T> container;
1.640 -
1.641 - public:
1.642 - typedef T ValueType;
1.643 - typedef Edge KeyType;
1.644 -
1.645 - SymEdgeMap(const SymListGraph &_G) :
1.646 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2)
1.647 - {
1.648 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.push_back(this);
1.649 - }
1.650 - SymEdgeMap(const SymListGraph &_G,const T &t) :
1.651 - DynMapBase<Edge>(_G), container(_G.maxEdgeId()/2,t)
1.652 - {
1.653 - G->dyn_edge_maps.push_back(this);
1.654 - }
1.655 -
1.656 - SymEdgeMap(const SymEdgeMap<T> &m) :
1.657 - DynMapBase<SymEdge>(*m.G), container(m.container)
1.658 - {
1.659 - G->dyn_node_maps.push_back(this);
1.660 - }
1.661 -
1.662 - // template<typename TT> friend class SymEdgeMap;
1.663 -
1.664 - ///\todo It can copy between different types.
1.665 - ///
1.666 -
1.667 - template<typename TT> SymEdgeMap(const SymEdgeMap<TT> &m) :
1.668 - DynMapBase<SymEdge>(*m.G)
1.669 - {
1.670 - G->dyn_node_maps.push_back(this);
1.671 - typename std::vector<TT>::const_iterator i;
1.672 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.673 - i!=m.container.end();
1.674 - i++)
1.675 - container.push_back(*i);
1.676 - }
1.677 -
1.678 - ~SymEdgeMap()
1.679 - {
1.680 - if(G) {
1.681 - std::vector<DynMapBase<Edge>* >::iterator i;
1.682 - for(i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.begin();
1.683 - i!=static_cast<const SymListGraph*>(G)->dyn_edge_maps.end()
1.684 - && *i!=this; ++i) ;
1.685 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.686 - //A better way to do that: (Is this really important?)
1.687 - if(*i==this) {
1.688 - *i=static_cast<const SymListGraph*>(G)->dyn_edge_maps.back();
1.689 - static_cast<const SymListGraph*>(G)->dyn_edge_maps.pop_back();
1.690 - }
1.691 - }
1.692 - }
1.693 -
1.694 - void add(const Edge k)
1.695 - {
1.696 - if(!k.idref()%2&&k.idref()/2>=int(container.size()))
1.697 - container.resize(k.idref()/2+1);
1.698 - }
1.699 - void erase(const Edge k) { }
1.700 -
1.701 - void set(Edge n, T a) { container[n.idref()/2]=a; }
1.702 - //T get(Edge n) const { return container[n.idref()/2]; }
1.703 - typename std::vector<T>::reference
1.704 - operator[](Edge n) { return container[n.idref()/2]; }
1.705 - typename std::vector<T>::const_reference
1.706 - operator[](Edge n) const { return container[n.idref()/2]; }
1.707 -
1.708 - ///\warning There is no safety check at all!
1.709 - ///Using operator = between maps attached to different graph may
1.710 - ///cause serious problem.
1.711 - ///\todo Is this really so?
1.712 - ///\todo It can copy between different types.
1.713 - const SymEdgeMap<T>& operator=(const SymEdgeMap<T> &m)
1.714 - {
1.715 - container = m.container;
1.716 - return *this;
1.717 - }
1.718 - template<typename TT>
1.719 - const SymEdgeMap<T>& operator=(const SymEdgeMap<TT> &m)
1.720 - {
1.721 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.722 - return *this;
1.723 - }
1.724 -
1.725 - void update() {} //Useless for DynMaps
1.726 - void update(T a) {} //Useless for DynMaps
1.727 -
1.728 - };
1.729 -
1.730 - };
1.731 -
1.732 -
1.733 - ///A graph class containing only nodes.
1.734 -
1.735 - ///This class implements a graph structure without edges.
1.736 - ///The most useful application of this class is to be the node set of an
1.737 - ///\ref EdgeSet class.
1.738 - ///
1.739 - ///It conforms to the graph interface documented under
1.740 - ///the description of \ref GraphSkeleton with the exception that you cannot
1.741 - ///add (or delete) edges. The usual edge iterators are exists, but they are
1.742 - ///always \ref INVALID.
1.743 - ///\sa \ref GraphSkeleton
1.744 - ///\sa \ref EdgeSet
1.745 - class NodeSet {
1.746 -
1.747 - //Nodes are double linked.
1.748 - //The free nodes are only single linked using the "next" field.
1.749 - struct NodeT
1.750 - {
1.751 - int first_in,first_out;
1.752 - int prev, next;
1.753 - // NodeT() {}
1.754 - };
1.755 -
1.756 - std::vector<NodeT> nodes;
1.757 - //The first node
1.758 - int first_node;
1.759 - //The first free node
1.760 - int first_free_node;
1.761 -
1.762 - protected:
1.763 -
1.764 - template <typename Key> class DynMapBase
1.765 - {
1.766 - protected:
1.767 - const NodeSet* G;
1.768 - public:
1.769 - virtual void add(const Key k) = 0;
1.770 - virtual void erase(const Key k) = 0;
1.771 - DynMapBase(const NodeSet &_G) : G(&_G) {}
1.772 - virtual ~DynMapBase() {}
1.773 - friend class NodeSet;
1.774 - };
1.775 -
1.776 - public:
1.777 - template <typename T> class EdgeMap;
1.778 - template <typename T> class NodeMap;
1.779 -
1.780 - class Node;
1.781 - class Edge;
1.782 -
1.783 - // protected:
1.784 - // HELPME:
1.785 - protected:
1.786 - ///\bug It must be public because of SymEdgeMap.
1.787 - ///
1.788 - mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.789 - //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.790 -
1.791 - public:
1.792 -
1.793 - class NodeIt;
1.794 - class EdgeIt;
1.795 - class OutEdgeIt;
1.796 - class InEdgeIt;
1.797 -
1.798 - template <typename T> class NodeMap;
1.799 - template <typename T> class EdgeMap;
1.800 -
1.801 - public:
1.802 -
1.803 - ///Default constructor
1.804 - NodeSet() : nodes(), first_node(-1),
1.805 - first_free_node(-1) {}
1.806 - ///Copy constructor
1.807 - NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.808 - first_free_node(_g.first_free_node) {}
1.809 -
1.810 - ~NodeSet()
1.811 - {
1.812 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.813 - i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.814 - //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.815 - // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.816 - }
1.817 -
1.818 - int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.819 - int edgeNum() const { return 0; } //FIXME: What is this?
1.820 -
1.821 - ///\bug This function does something different than
1.822 - ///its name would suggests...
1.823 - int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
1.824 - ///\bug This function does something different than
1.825 - ///its name would suggests...
1.826 - int maxEdgeId() const { return 0; } //FIXME: What is this?
1.827 -
1.828 - Node tail(Edge e) const { return INVALID; }
1.829 - Node head(Edge e) const { return INVALID; }
1.830 -
1.831 - Node aNode(OutEdgeIt e) const { return INVALID; }
1.832 - Node aNode(InEdgeIt e) const { return INVALID; }
1.833 -
1.834 - Node bNode(OutEdgeIt e) const { return INVALID; }
1.835 - Node bNode(InEdgeIt e) const { return INVALID; }
1.836 -
1.837 - NodeIt& first(NodeIt& v) const {
1.838 - v=NodeIt(*this); return v; }
1.839 - EdgeIt& first(EdgeIt& e) const {
1.840 - e=EdgeIt(*this); return e; }
1.841 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.842 - e=OutEdgeIt(*this,v); return e; }
1.843 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.844 - e=InEdgeIt(*this,v); return e; }
1.845 -
1.846 -// template< typename It >
1.847 -// It first() const { It e; first(e); return e; }
1.848 -
1.849 -// template< typename It >
1.850 -// It first(Node v) const { It e; first(e,v); return e; }
1.851 -
1.852 - bool valid(Edge e) const { return false; }
1.853 - bool valid(Node n) const { return n.n!=-1; }
1.854 -
1.855 - void setInvalid(Edge &e) { }
1.856 - void setInvalid(Node &n) { n.n=-1; }
1.857 -
1.858 - template <typename It> It getNext(It it) const
1.859 - { It tmp(it); return next(tmp); }
1.860 -
1.861 - NodeIt& next(NodeIt& it) const {
1.862 - it.n=nodes[it.n].next;
1.863 - return it;
1.864 - }
1.865 - OutEdgeIt& next(OutEdgeIt& it) const { return it; }
1.866 - InEdgeIt& next(InEdgeIt& it) const { return it; }
1.867 - EdgeIt& next(EdgeIt& it) const { return it; }
1.868 -
1.869 - int id(Node v) const { return v.n; }
1.870 - int id(Edge e) const { return -1; }
1.871 -
1.872 - /// Adds a new node to the graph.
1.873 -
1.874 - /// \todo It adds the nodes in a reversed order.
1.875 - /// (i.e. the lastly added node becomes the first.)
1.876 - Node addNode() {
1.877 - int n;
1.878 -
1.879 - if(first_free_node==-1)
1.880 - {
1.881 - n = nodes.size();
1.882 - nodes.push_back(NodeT());
1.883 - }
1.884 - else {
1.885 - n = first_free_node;
1.886 - first_free_node = nodes[n].next;
1.887 - }
1.888 -
1.889 - nodes[n].next = first_node;
1.890 - if(first_node != -1) nodes[first_node].prev = n;
1.891 - first_node = n;
1.892 - nodes[n].prev = -1;
1.893 -
1.894 - nodes[n].first_in = nodes[n].first_out = -1;
1.895 -
1.896 - Node nn; nn.n=n;
1.897 -
1.898 - //Update dynamic maps
1.899 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.900 - i!=dyn_node_maps.end(); ++i) (**i).add(nn);
1.901 -
1.902 - return nn;
1.903 - }
1.904 -
1.905 - void erase(Node nn) {
1.906 - int n=nn.n;
1.907 -
1.908 - if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
1.909 - if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
1.910 - else first_node = nodes[n].next;
1.911 -
1.912 - nodes[n].next = first_free_node;
1.913 - first_free_node = n;
1.914 -
1.915 - //Update dynamic maps
1.916 - for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.917 - i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
1.918 - }
1.919 -
1.920 - ///\bug Dynamic maps must be updated!
1.921 - ///
1.922 - void clear() {
1.923 - nodes.clear();
1.924 - first_node = first_free_node = -1;
1.925 - }
1.926 -
1.927 - class Node {
1.928 - friend class NodeSet;
1.929 - template <typename T> friend class NodeMap;
1.930 -
1.931 - friend class Edge;
1.932 - friend class OutEdgeIt;
1.933 - friend class InEdgeIt;
1.934 -
1.935 - protected:
1.936 - int n;
1.937 - friend int NodeSet::id(Node v) const;
1.938 - Node(int nn) {n=nn;}
1.939 - public:
1.940 - Node() {}
1.941 - Node (Invalid i) { n=-1; }
1.942 - bool operator==(const Node i) const {return n==i.n;}
1.943 - bool operator!=(const Node i) const {return n!=i.n;}
1.944 - bool operator<(const Node i) const {return n<i.n;}
1.945 - };
1.946 -
1.947 - class NodeIt : public Node {
1.948 - friend class NodeSet;
1.949 - public:
1.950 - NodeIt(const NodeSet& G) : Node(G.first_node) { }
1.951 - NodeIt() : Node() { }
1.952 - };
1.953 -
1.954 - class Edge {
1.955 - //friend class NodeSet;
1.956 - //template <typename T> friend class EdgeMap;
1.957 -
1.958 - //template <typename T> friend class SymNodeSet::SymEdgeMap;
1.959 - //friend Edge SymNodeSet::opposite(Edge) const;
1.960 -
1.961 - // friend class Node;
1.962 - // friend class NodeIt;
1.963 - protected:
1.964 - //friend int NodeSet::id(Edge e) const;
1.965 - // Edge(int nn) {}
1.966 - public:
1.967 - Edge() { }
1.968 - Edge (Invalid) { }
1.969 - bool operator==(const Edge i) const {return true;}
1.970 - bool operator!=(const Edge i) const {return false;}
1.971 - bool operator<(const Edge i) const {return false;}
1.972 - ///\bug This is a workaround until somebody tells me how to
1.973 - ///make class \c SymNodeSet::SymEdgeMap friend of Edge
1.974 - // int idref() {return -1;}
1.975 - // int idref() const {return -1;}
1.976 - };
1.977 -
1.978 - class EdgeIt : public Edge {
1.979 - //friend class NodeSet;
1.980 - public:
1.981 - EdgeIt(const NodeSet& G) : Edge() { }
1.982 - EdgeIt (Invalid i) : Edge(i) { }
1.983 - EdgeIt() : Edge() { }
1.984 - ///\bug This is a workaround until somebody tells me how to
1.985 - ///make class \c SymNodeSet::SymEdgeMap friend of Edge
1.986 - // int idref() {return -1;}
1.987 - };
1.988 -
1.989 - class OutEdgeIt : public Edge {
1.990 - friend class NodeSet;
1.991 - public:
1.992 - OutEdgeIt() : Edge() { }
1.993 - OutEdgeIt (Invalid i) : Edge(i) { }
1.994 - OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
1.995 - };
1.996 -
1.997 - class InEdgeIt : public Edge {
1.998 - friend class NodeSet;
1.999 - public:
1.1000 - InEdgeIt() : Edge() { }
1.1001 - InEdgeIt (Invalid i) : Edge(i) { }
1.1002 - InEdgeIt(const NodeSet& G,Node v) :Edge() {}
1.1003 - };
1.1004 -
1.1005 - template <typename T> class NodeMap : public DynMapBase<Node>
1.1006 - {
1.1007 - std::vector<T> container;
1.1008 -
1.1009 - public:
1.1010 - typedef T ValueType;
1.1011 - typedef Node KeyType;
1.1012 -
1.1013 - NodeMap(const NodeSet &_G) :
1.1014 - DynMapBase<Node>(_G), container(_G.maxNodeId())
1.1015 - {
1.1016 - G->dyn_node_maps.push_back(this);
1.1017 - }
1.1018 - NodeMap(const NodeSet &_G,const T &t) :
1.1019 - DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.1020 - {
1.1021 - G->dyn_node_maps.push_back(this);
1.1022 - }
1.1023 -
1.1024 - NodeMap(const NodeMap<T> &m) :
1.1025 - DynMapBase<Node>(*m.G), container(m.container)
1.1026 - {
1.1027 - G->dyn_node_maps.push_back(this);
1.1028 - }
1.1029 -
1.1030 - template<typename TT> friend class NodeMap;
1.1031 -
1.1032 - ///\todo It can copy between different types.
1.1033 - ///
1.1034 - template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.1035 - DynMapBase<Node>(*m.G)
1.1036 - {
1.1037 - G->dyn_node_maps.push_back(this);
1.1038 - typename std::vector<TT>::const_iterator i;
1.1039 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.1040 - i!=m.container.end();
1.1041 - i++)
1.1042 - container.push_back(*i);
1.1043 - }
1.1044 - ~NodeMap()
1.1045 - {
1.1046 - if(G) {
1.1047 - std::vector<DynMapBase<Node>* >::iterator i;
1.1048 - for(i=G->dyn_node_maps.begin();
1.1049 - i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1.1050 - //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1.1051 - //A better way to do that: (Is this really important?)
1.1052 - if(*i==this) {
1.1053 - *i=G->dyn_node_maps.back();
1.1054 - G->dyn_node_maps.pop_back();
1.1055 - }
1.1056 - }
1.1057 - }
1.1058 -
1.1059 - void add(const Node k)
1.1060 - {
1.1061 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.1062 - }
1.1063 -
1.1064 - void erase(const Node) { }
1.1065 -
1.1066 - void set(Node n, T a) { container[n.n]=a; }
1.1067 - //'T& operator[](Node n)' would be wrong here
1.1068 - typename std::vector<T>::reference
1.1069 - operator[](Node n) { return container[n.n]; }
1.1070 - //'const T& operator[](Node n)' would be wrong here
1.1071 - typename std::vector<T>::const_reference
1.1072 - operator[](Node n) const { return container[n.n]; }
1.1073 -
1.1074 - ///\warning There is no safety check at all!
1.1075 - ///Using operator = between maps attached to different graph may
1.1076 - ///cause serious problem.
1.1077 - ///\todo Is this really so?
1.1078 - ///\todo It can copy between different types.
1.1079 - const NodeMap<T>& operator=(const NodeMap<T> &m)
1.1080 - {
1.1081 - container = m.container;
1.1082 - return *this;
1.1083 - }
1.1084 - template<typename TT>
1.1085 - const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.1086 - {
1.1087 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.1088 - return *this;
1.1089 - }
1.1090 -
1.1091 - void update() {} //Useless for Dynamic Maps
1.1092 - void update(T a) {} //Useless for Dynamic Maps
1.1093 - };
1.1094 -
1.1095 - template <typename T> class EdgeMap
1.1096 - {
1.1097 - public:
1.1098 - typedef T ValueType;
1.1099 - typedef Edge KeyType;
1.1100 -
1.1101 - EdgeMap(const NodeSet &) { }
1.1102 - EdgeMap(const NodeSet &,const T &) { }
1.1103 - EdgeMap(const EdgeMap<T> &) { }
1.1104 - // template<typename TT> friend class EdgeMap;
1.1105 -
1.1106 - ///\todo It can copy between different types.
1.1107 - ///
1.1108 - template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1.1109 - ~EdgeMap() { }
1.1110 -
1.1111 - void add(const Edge ) { }
1.1112 - void erase(const Edge) { }
1.1113 -
1.1114 - void set(Edge, T) { }
1.1115 - //T get(Edge n) const { return container[n.n]; }
1.1116 - ValueType &operator[](Edge) { return *((T*)(NULL)); }
1.1117 - const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1.1118 -
1.1119 - const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1.1120 -
1.1121 - template<typename TT>
1.1122 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1.1123 -
1.1124 - void update() {}
1.1125 - void update(T a) {}
1.1126 - };
1.1127 - };
1.1128 -
1.1129 -
1.1130 -
1.1131 - ///Graph structure using a node set of another graph.
1.1132 -
1.1133 - ///This structure can be used to establish another graph over a node set
1.1134 - /// of an existing one. The node iterator will go through the nodes of the
1.1135 - /// original graph, and the NodeMap's of both graphs will convert to
1.1136 - /// each other.
1.1137 - ///
1.1138 - ///\warning Adding or deleting nodes from the graph is not safe if an
1.1139 - ///\ref EdgeSet is currently attached to it!
1.1140 - ///
1.1141 - ///\todo Make it possible to add/delete edges from the base graph
1.1142 - ///(and from \ref EdgeSet, as well)
1.1143 - ///
1.1144 - ///\param GG The type of the graph which shares its node set with this class.
1.1145 - ///Its interface must conform with \ref GraphSkeleton.
1.1146 - ///
1.1147 - ///It conforms to the graph interface documented under
1.1148 - ///the description of \ref GraphSkeleton.
1.1149 - ///\sa \ref GraphSkeleton.
1.1150 - ///\sa \ref NodeSet.
1.1151 - template<typename GG>
1.1152 - class EdgeSet {
1.1153 -
1.1154 - typedef GG NodeGraphType;
1.1155 -
1.1156 - NodeGraphType &G;
1.1157 -
1.1158 - public:
1.1159 - class Node;
1.1160 - int id(Node v) const;
1.1161 -
1.1162 - class Node : public NodeGraphType::Node {
1.1163 - friend class EdgeSet;
1.1164 - // template <typename T> friend class NodeMap;
1.1165 -
1.1166 - friend class Edge;
1.1167 - friend class OutEdgeIt;
1.1168 - friend class InEdgeIt;
1.1169 - friend class SymEdge;
1.1170 -
1.1171 - public:
1.1172 - friend int EdgeSet::id(Node v) const;
1.1173 - // Node(int nn) {n=nn;}
1.1174 - public:
1.1175 - Node() : NodeGraphType::Node() {}
1.1176 - Node (Invalid i) : NodeGraphType::Node(i) {}
1.1177 - Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1.1178 - };
1.1179 -
1.1180 - class NodeIt : public NodeGraphType::NodeIt {
1.1181 - friend class EdgeSet;
1.1182 - public:
1.1183 - NodeIt() : NodeGraphType::NodeIt() { }
1.1184 - NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1.1185 - NodeIt(const EdgeSet& _G) : NodeGraphType::NodeIt(_G.G) { }
1.1186 - NodeIt(const typename NodeGraphType::NodeIt &n)
1.1187 - : NodeGraphType::NodeIt(n) {}
1.1188 - operator Node() { return Node(*this);}
1.1189 - };
1.1190 -
1.1191 - private:
1.1192 - //Edges are double linked.
1.1193 - //The free edges are only single linked using the "next_in" field.
1.1194 - struct NodeT
1.1195 - {
1.1196 - int first_in,first_out;
1.1197 - NodeT() : first_in(-1), first_out(-1) { }
1.1198 - };
1.1199 -
1.1200 - struct EdgeT
1.1201 - {
1.1202 - Node head, tail;
1.1203 - int prev_in, prev_out;
1.1204 - int next_in, next_out;
1.1205 - };
1.1206 -
1.1207 -
1.1208 - typename NodeGraphType::template NodeMap<NodeT> nodes;
1.1209 -
1.1210 - std::vector<EdgeT> edges;
1.1211 - //The first free edge
1.1212 - int first_free_edge;
1.1213 -
1.1214 - protected:
1.1215 -
1.1216 - template <typename Key> class DynMapBase
1.1217 - {
1.1218 - protected:
1.1219 - const EdgeSet* G;
1.1220 - public:
1.1221 - virtual void add(const Key k) = 0;
1.1222 - virtual void erase(const Key k) = 0;
1.1223 - DynMapBase(const EdgeSet &_G) : G(&_G) {}
1.1224 - virtual ~DynMapBase() {}
1.1225 - friend class EdgeSet;
1.1226 - };
1.1227 -
1.1228 - public:
1.1229 - //template <typename T> class NodeMap;
1.1230 - template <typename T> class EdgeMap;
1.1231 -
1.1232 - class Node;
1.1233 - class Edge;
1.1234 -
1.1235 - // protected:
1.1236 - // HELPME:
1.1237 - protected:
1.1238 - // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.1239 - ///\bug It must be public because of SymEdgeMap.
1.1240 - ///
1.1241 - mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.1242 -
1.1243 - public:
1.1244 -
1.1245 - class NodeIt;
1.1246 - class EdgeIt;
1.1247 - class OutEdgeIt;
1.1248 - class InEdgeIt;
1.1249 -
1.1250 - template <typename T> class NodeMap;
1.1251 - template <typename T> class EdgeMap;
1.1252 -
1.1253 - public:
1.1254 -
1.1255 - ///Constructor
1.1256 -
1.1257 - ///Construates a new graph based on the nodeset of an existing one.
1.1258 - ///\param _G the base graph.
1.1259 - ///\todo It looks like a copy constructor, but it isn't.
1.1260 - EdgeSet(NodeGraphType &_G) : G(_G),
1.1261 - nodes(_G), edges(),
1.1262 - first_free_edge(-1) { }
1.1263 - ///Copy constructor
1.1264 -
1.1265 - ///Makes a copy of an EdgeSet.
1.1266 - ///It will be based on the same graph.
1.1267 - EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1.1268 - first_free_edge(_g.first_free_edge) { }
1.1269 -
1.1270 - ~EdgeSet()
1.1271 - {
1.1272 - // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.1273 - // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.1274 - for(typename std::vector<DynMapBase<Edge> * >::iterator
1.1275 - i=dyn_edge_maps.begin();
1.1276 - i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.1277 - }
1.1278 -
1.1279 - int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1.1280 - int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.1281 -
1.1282 - ///\bug This function does something different than
1.1283 - ///its name would suggests...
1.1284 - int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
1.1285 - ///\bug This function does something different than
1.1286 - ///its name would suggests...
1.1287 - int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1.1288 -
1.1289 - Node tail(Edge e) const { return edges[e.n].tail; }
1.1290 - Node head(Edge e) const { return edges[e.n].head; }
1.1291 -
1.1292 - Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1.1293 - Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1.1294 -
1.1295 - Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1.1296 - Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1.1297 -
1.1298 - NodeIt& first(NodeIt& v) const {
1.1299 - v=NodeIt(*this); return v; }
1.1300 - EdgeIt& first(EdgeIt& e) const {
1.1301 - e=EdgeIt(*this); return e; }
1.1302 - OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.1303 - e=OutEdgeIt(*this,v); return e; }
1.1304 - InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.1305 - e=InEdgeIt(*this,v); return e; }
1.1306 -
1.1307 -// template< typename It >
1.1308 -// It first() const { It e; first(e); return e; }
1.1309 -
1.1310 -// template< typename It >
1.1311 -// It first(Node v) const { It e; first(e,v); return e; }
1.1312 -
1.1313 - bool valid(Edge e) const { return e.n!=-1; }
1.1314 - bool valid(Node n) const { return G.valid(n); }
1.1315 -
1.1316 - void setInvalid(Edge &e) { e.n=-1; }
1.1317 - void setInvalid(Node &n) { G.setInvalid(n); }
1.1318 -
1.1319 - template <typename It> It getNext(It it) const
1.1320 - { It tmp(it); return next(tmp); }
1.1321 -
1.1322 - NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1.1323 - OutEdgeIt& next(OutEdgeIt& it) const
1.1324 - { it.n=edges[it.n].next_out; return it; }
1.1325 - InEdgeIt& next(InEdgeIt& it) const
1.1326 - { it.n=edges[it.n].next_in; return it; }
1.1327 - EdgeIt& next(EdgeIt& it) const {
1.1328 - if(edges[it.n].next_in!=-1) {
1.1329 - it.n=edges[it.n].next_in;
1.1330 - }
1.1331 - else {
1.1332 - NodeIt n;
1.1333 - for(n=next(edges[it.n].head);
1.1334 - valid(n) && nodes[n].first_in == -1;
1.1335 - next(n)) ;
1.1336 - it.n = (valid(n))?-1:nodes[n].first_in;
1.1337 - }
1.1338 - return it;
1.1339 - }
1.1340 -
1.1341 - int id(Edge e) const { return e.n; }
1.1342 -
1.1343 - /// Adds a new node to the graph.
1.1344 - Node addNode() { return G.AddNode(); }
1.1345 -
1.1346 - Edge addEdge(Node u, Node v) {
1.1347 - int n;
1.1348 -
1.1349 - if(first_free_edge==-1)
1.1350 - {
1.1351 - n = edges.size();
1.1352 - edges.push_back(EdgeT());
1.1353 - }
1.1354 - else {
1.1355 - n = first_free_edge;
1.1356 - first_free_edge = edges[n].next_in;
1.1357 - }
1.1358 -
1.1359 - edges[n].tail = u; edges[n].head = v;
1.1360 -
1.1361 - edges[n].next_out = nodes[u].first_out;
1.1362 - if(nodes[u].first_out != -1) edges[nodes[u].first_out].prev_out = n;
1.1363 - edges[n].next_in = nodes[v].first_in;
1.1364 - if(nodes[v].first_in != -1) edges[nodes[v].first_in].prev_in = n;
1.1365 - edges[n].prev_in = edges[n].prev_out = -1;
1.1366 -
1.1367 - nodes[u].first_out = nodes[v].first_in = n;
1.1368 -
1.1369 - Edge e; e.n=n;
1.1370 -
1.1371 - //Update dynamic maps
1.1372 - for(typename std::vector<DynMapBase<Edge> * >::iterator
1.1373 - i=dyn_edge_maps.begin();
1.1374 - i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.1375 -
1.1376 - return e;
1.1377 - }
1.1378 -
1.1379 - private:
1.1380 - void eraseEdge(int n) {
1.1381 -
1.1382 - if(edges[n].next_in!=-1)
1.1383 - edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.1384 - if(edges[n].prev_in!=-1)
1.1385 - edges[edges[n].prev_in].next_in = edges[n].next_in;
1.1386 - else nodes[edges[n].head].first_in = edges[n].next_in;
1.1387 -
1.1388 - if(edges[n].next_out!=-1)
1.1389 - edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.1390 - if(edges[n].prev_out!=-1)
1.1391 - edges[edges[n].prev_out].next_out = edges[n].next_out;
1.1392 - else nodes[edges[n].tail].first_out = edges[n].next_out;
1.1393 -
1.1394 - edges[n].next_in = first_free_edge;
1.1395 - first_free_edge = -1;
1.1396 -
1.1397 - //Update dynamic maps
1.1398 - Edge e; e.n=n;
1.1399 - for(typename std::vector<DynMapBase<Edge> * >::iterator
1.1400 - i=dyn_edge_maps.begin();
1.1401 - i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1.1402 - }
1.1403 -
1.1404 - public:
1.1405 -
1.1406 -// void erase(Node nn) {
1.1407 -// int n=nn.n;
1.1408 -// int m;
1.1409 -// while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1.1410 -// while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1.1411 -// }
1.1412 -
1.1413 - void erase(Edge e) { eraseEdge(e.n); }
1.1414 -
1.1415 -// //\bug Dynamic maps must be updated!
1.1416 -// //
1.1417 -// void clear() {
1.1418 -// nodes.clear();edges.clear();
1.1419 -// first_node=first_free_node=first_free_edge=-1;
1.1420 -// }
1.1421 -
1.1422 - class Edge {
1.1423 - friend class EdgeSet;
1.1424 - template <typename T> friend class EdgeMap;
1.1425 -
1.1426 - //template <typename T> friend class SymEdgeSet::SymEdgeMap;
1.1427 - //friend Edge SymEdgeSet::opposite(Edge) const;
1.1428 -
1.1429 - friend class Node;
1.1430 - friend class NodeIt;
1.1431 - protected:
1.1432 - int n;
1.1433 - friend int EdgeSet::id(Edge e) const;
1.1434 -
1.1435 - Edge(int nn) {n=nn;}
1.1436 - public:
1.1437 - Edge() { }
1.1438 - Edge (Invalid) { n=-1; }
1.1439 - bool operator==(const Edge i) const {return n==i.n;}
1.1440 - bool operator!=(const Edge i) const {return n!=i.n;}
1.1441 - bool operator<(const Edge i) const {return n<i.n;}
1.1442 - ///\bug This is a workaround until somebody tells me how to
1.1443 - ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1.1444 - int &idref() {return n;}
1.1445 - const int &idref() const {return n;}
1.1446 - };
1.1447 -
1.1448 - class EdgeIt : public Edge {
1.1449 - friend class EdgeSet;
1.1450 - public:
1.1451 - EdgeIt(const EdgeSet& G) : Edge() {
1.1452 - // typename NodeGraphType::Node m;
1.1453 - NodeIt m;
1.1454 - for(G.first(m);
1.1455 - G.valid(m) && G.nodes[m].first_in == -1; G.next(m));
1.1456 - //AJJAJ! This is a non sense!!!!!!!
1.1457 - this->n = G.valid(m)?-1:G.nodes[m].first_in;
1.1458 - }
1.1459 - EdgeIt (Invalid i) : Edge(i) { }
1.1460 - EdgeIt() : Edge() { }
1.1461 - ///\bug This is a workaround until somebody tells me how to
1.1462 - ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1.1463 - int &idref() {return this->n;}
1.1464 - };
1.1465 -
1.1466 - class OutEdgeIt : public Edge {
1.1467 - friend class EdgeSet;
1.1468 - public:
1.1469 - OutEdgeIt() : Edge() { }
1.1470 - OutEdgeIt (Invalid i) : Edge(i) { }
1.1471 -
1.1472 - OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
1.1473 - };
1.1474 -
1.1475 - class InEdgeIt : public Edge {
1.1476 - friend class EdgeSet;
1.1477 - public:
1.1478 - InEdgeIt() : Edge() { }
1.1479 - InEdgeIt (Invalid i) : Edge(i) { }
1.1480 - InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
1.1481 - };
1.1482 -
1.1483 - template <typename T> class NodeMap :
1.1484 - public NodeGraphType::template NodeMap<T>
1.1485 - {
1.1486 - public:
1.1487 - NodeMap(const EdgeSet &_G) :
1.1488 - NodeGraphType::NodeMap(_G.G) { } //AJAJJ <T> would be wrong!!!
1.1489 - NodeMap(const EdgeSet &_G,const T &t) :
1.1490 - NodeGraphType::NodeMap(_G.G,t) { }
1.1491 - //It is unnecessary
1.1492 - NodeMap(const typename NodeGraphType::template NodeMap<T> &m) :
1.1493 - NodeGraphType::NodeMap(m) { }
1.1494 -
1.1495 - ///\todo It can copy between different types.
1.1496 - ///
1.1497 - template<typename TT>
1.1498 - NodeMap(const typename NodeGraphType::template NodeMap<TT> &m)
1.1499 - : NodeGraphType::NodeMap(m) { }
1.1500 - };
1.1501 -
1.1502 - template <typename T> class EdgeMap : public DynMapBase<Edge>
1.1503 - {
1.1504 - std::vector<T> container;
1.1505 -
1.1506 - public:
1.1507 - typedef T ValueType;
1.1508 - typedef Edge KeyType;
1.1509 -
1.1510 - EdgeMap(const EdgeSet &_G) :
1.1511 - DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.1512 - {
1.1513 - //FIXME: What if there are empty Id's?
1.1514 - //FIXME: Can I use 'this' in a constructor?
1.1515 - G->dyn_edge_maps.push_back(this);
1.1516 - }
1.1517 - EdgeMap(const EdgeSet &_G,const T &t) :
1.1518 - DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.1519 - {
1.1520 - G->dyn_edge_maps.push_back(this);
1.1521 - }
1.1522 - EdgeMap(const EdgeMap<T> &m) :
1.1523 - DynMapBase<Edge>(*m.G), container(m.container)
1.1524 - {
1.1525 - G->dyn_edge_maps.push_back(this);
1.1526 - }
1.1527 -
1.1528 - template<typename TT> friend class EdgeMap;
1.1529 -
1.1530 - ///\todo It can copy between different types.
1.1531 - ///
1.1532 - template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.1533 - DynMapBase<Edge>(*m.G)
1.1534 - {
1.1535 - G->dyn_edge_maps.push_back(this);
1.1536 - typename std::vector<TT>::const_iterator i;
1.1537 - for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.1538 - i!=m.container.end();
1.1539 - i++)
1.1540 - container.push_back(*i);
1.1541 - }
1.1542 - ~EdgeMap()
1.1543 - {
1.1544 - if(G) {
1.1545 - typename std::vector<DynMapBase<Edge>* >::iterator i;
1.1546 - for(i=G->dyn_edge_maps.begin();
1.1547 - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.1548 - //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.1549 - //A better way to do that: (Is this really important?)
1.1550 - if(*i==this) {
1.1551 - *i=G->dyn_edge_maps.back();
1.1552 - G->dyn_edge_maps.pop_back();
1.1553 - }
1.1554 - }
1.1555 - }
1.1556 -
1.1557 - void add(const Edge k)
1.1558 - {
1.1559 - if(k.n>=int(container.size())) container.resize(k.n+1);
1.1560 - }
1.1561 - void erase(const Edge) { }
1.1562 -
1.1563 - void set(Edge n, T a) { container[n.n]=a; }
1.1564 - //T get(Edge n) const { return container[n.n]; }
1.1565 - typename std::vector<T>::reference
1.1566 - operator[](Edge n) { return container[n.n]; }
1.1567 - typename std::vector<T>::const_reference
1.1568 - operator[](Edge n) const { return container[n.n]; }
1.1569 -
1.1570 - ///\warning There is no safety check at all!
1.1571 - ///Using operator = between maps attached to different graph may
1.1572 - ///cause serious problem.
1.1573 - ///\todo Is this really so?
1.1574 - ///\todo It can copy between different types.
1.1575 - const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.1576 - {
1.1577 - container = m.container;
1.1578 - return *this;
1.1579 - }
1.1580 - template<typename TT>
1.1581 - const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.1582 - {
1.1583 - std::copy(m.container.begin(), m.container.end(), container.begin());
1.1584 - return *this;
1.1585 - }
1.1586 -
1.1587 - void update() {} //Useless for DynMaps
1.1588 - void update(T a) {} //Useless for DynMaps
1.1589 - };
1.1590 -
1.1591 - };
1.1592 -
1.1593 - template< typename GG>
1.1594 - int EdgeSet<GG>::id(Node v) const { return G.id(v); }
1.1595 -
1.1596 -/// @}
1.1597 -
1.1598 -} //namespace hugo
1.1599 -
1.1600 -#endif //HUGO_LIST_GRAPH_H