1.1 --- a/src/work/alpar/list_graph.h Sun Apr 25 17:06:40 2004 +0000
1.2 +++ b/src/work/alpar/list_graph.h Sun Apr 25 20:16:16 2004 +0000
1.3 @@ -68,7 +68,7 @@
1.4
1.5 public:
1.6 template <typename T> class EdgeMap;
1.7 - template <typename T> class EdgeMap;
1.8 + template <typename T> class NodeMap;
1.9
1.10 class Node;
1.11 class Edge;
1.12 @@ -300,7 +300,7 @@
1.13 class Node {
1.14 friend class ListGraph;
1.15 template <typename T> friend class NodeMap;
1.16 -
1.17 +
1.18 friend class Edge;
1.19 friend class OutEdgeIt;
1.20 friend class InEdgeIt;
1.21 @@ -321,8 +321,9 @@
1.22 class NodeIt : public Node {
1.23 friend class ListGraph;
1.24 public:
1.25 + NodeIt() : Node() { }
1.26 + NodeIt(Invalid i) : Node(i) { }
1.27 NodeIt(const ListGraph& G) : Node(G.first_node) { }
1.28 - NodeIt() : Node() { }
1.29 };
1.30
1.31 class Edge {
1.32 @@ -721,6 +722,837 @@
1.33
1.34 };
1.35
1.36 +
1.37 + ///A smart graph class.
1.38 +
1.39 + ///This is a simple and fast erasable graph implementation.
1.40 + ///
1.41 + ///It conforms to the graph interface documented under
1.42 + ///the description of \ref GraphSkeleton.
1.43 + ///\sa \ref GraphSkeleton.
1.44 + class NodeSet {
1.45 +
1.46 + //Nodes are double linked.
1.47 + //The free nodes are only single linked using the "next" field.
1.48 + struct NodeT
1.49 + {
1.50 + int first_in,first_out;
1.51 + int prev, next;
1.52 + // NodeT() {}
1.53 + };
1.54 +
1.55 + std::vector<NodeT> nodes;
1.56 + //The first node
1.57 + int first_node;
1.58 + //The first free node
1.59 + int first_free_node;
1.60 +
1.61 + protected:
1.62 +
1.63 + template <typename Key> class DynMapBase
1.64 + {
1.65 + protected:
1.66 + const NodeSet* G;
1.67 + public:
1.68 + virtual void add(const Key k) = NULL;
1.69 + virtual void erase(const Key k) = NULL;
1.70 + DynMapBase(const NodeSet &_G) : G(&_G) {}
1.71 + virtual ~DynMapBase() {}
1.72 + friend class NodeSet;
1.73 + };
1.74 +
1.75 + public:
1.76 + template <typename T> class EdgeMap;
1.77 + template <typename T> class NodeMap;
1.78 +
1.79 + class Node;
1.80 + class Edge;
1.81 +
1.82 + // protected:
1.83 + // HELPME:
1.84 + protected:
1.85 + ///\bug It must be public because of SymEdgeMap.
1.86 + ///
1.87 + mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.88 + //mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.89 +
1.90 + public:
1.91 +
1.92 + class NodeIt;
1.93 + class EdgeIt;
1.94 + class OutEdgeIt;
1.95 + class InEdgeIt;
1.96 +
1.97 + template <typename T> class NodeMap;
1.98 + template <typename T> class EdgeMap;
1.99 +
1.100 + public:
1.101 +
1.102 + NodeSet() : nodes(), first_node(-1),
1.103 + first_free_node(-1) {}
1.104 + NodeSet(const NodeSet &_g) : nodes(_g.nodes), first_node(_g.first_node),
1.105 + first_free_node(_g.first_free_node) {}
1.106 +
1.107 + ~NodeSet()
1.108 + {
1.109 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.110 + i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.111 + //for(std::vector<DynMapBase<Edge> * >::iterator i=dyn_edge_maps.begin();
1.112 + // i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.113 + }
1.114 +
1.115 + int nodeNum() const { return nodes.size(); } //FIXME: What is this?
1.116 + int edgeNum() const { return 0; } //FIXME: What is this?
1.117 +
1.118 + ///\bug This function does something different than
1.119 + ///its name would suggests...
1.120 + int maxNodeId() const { return nodes.size(); } //FIXME: What is this?
1.121 + ///\bug This function does something different than
1.122 + ///its name would suggests...
1.123 + int maxEdgeId() const { return 0; } //FIXME: What is this?
1.124 +
1.125 + Node tail(Edge e) const { return INVALID; }
1.126 + Node head(Edge e) const { return INVALID; }
1.127 +
1.128 + Node aNode(OutEdgeIt e) const { return INVALID; }
1.129 + Node aNode(InEdgeIt e) const { return INVALID; }
1.130 +
1.131 + Node bNode(OutEdgeIt e) const { return INVALID; }
1.132 + Node bNode(InEdgeIt e) const { return INVALID; }
1.133 +
1.134 + NodeIt& first(NodeIt& v) const {
1.135 + v=NodeIt(*this); return v; }
1.136 + EdgeIt& first(EdgeIt& e) const {
1.137 + e=EdgeIt(*this); return e; }
1.138 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.139 + e=OutEdgeIt(*this,v); return e; }
1.140 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.141 + e=InEdgeIt(*this,v); return e; }
1.142 +
1.143 +// template< typename It >
1.144 +// It first() const { It e; first(e); return e; }
1.145 +
1.146 +// template< typename It >
1.147 +// It first(Node v) const { It e; first(e,v); return e; }
1.148 +
1.149 + bool valid(Edge e) const { return false; }
1.150 + bool valid(Node n) const { return n.n!=-1; }
1.151 +
1.152 + void setInvalid(Edge &e) { }
1.153 + void setInvalid(Node &n) { n.n=-1; }
1.154 +
1.155 + template <typename It> It getNext(It it) const
1.156 + { It tmp(it); return next(tmp); }
1.157 +
1.158 + NodeIt& next(NodeIt& it) const {
1.159 + it.n=nodes[it.n].next;
1.160 + return it;
1.161 + }
1.162 + OutEdgeIt& next(OutEdgeIt& it) const { return it; }
1.163 + InEdgeIt& next(InEdgeIt& it) const { return it; }
1.164 + EdgeIt& next(EdgeIt& it) const { return it; }
1.165 +
1.166 + int id(Node v) const { return v.n; }
1.167 + int id(Edge e) const { return -1; }
1.168 +
1.169 + /// Adds a new node to the graph.
1.170 +
1.171 + /// \todo It adds the nodes in a reversed order.
1.172 + /// (i.e. the lastly added node becomes the first.)
1.173 + Node addNode() {
1.174 + int n;
1.175 +
1.176 + if(first_free_node==-1)
1.177 + {
1.178 + n = nodes.size();
1.179 + nodes.push_back(NodeT());
1.180 + }
1.181 + else {
1.182 + n = first_free_node;
1.183 + first_free_node = nodes[n].next;
1.184 + }
1.185 +
1.186 + nodes[n].next = first_node;
1.187 + if(first_node != -1) nodes[first_node].prev = n;
1.188 + first_node = n;
1.189 + nodes[n].prev = -1;
1.190 +
1.191 + nodes[n].first_in = nodes[n].first_out = -1;
1.192 +
1.193 + Node nn; nn.n=n;
1.194 +
1.195 + //Update dynamic maps
1.196 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.197 + i!=dyn_node_maps.end(); ++i) (**i).add(nn);
1.198 +
1.199 + return nn;
1.200 + }
1.201 +
1.202 + void erase(Node nn) {
1.203 + int n=nn.n;
1.204 +
1.205 + if(nodes[n].next != -1) nodes[nodes[n].next].prev = nodes[n].prev;
1.206 + if(nodes[n].prev != -1) nodes[nodes[n].prev].next = nodes[n].next;
1.207 + else first_node = nodes[n].next;
1.208 +
1.209 + nodes[n].next = first_free_node;
1.210 + first_free_node = n;
1.211 +
1.212 + //Update dynamic maps
1.213 + for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.214 + i!=dyn_node_maps.end(); ++i) (**i).erase(nn);
1.215 + }
1.216 +
1.217 + ///\bug Dynamic maps must be updated!
1.218 + ///
1.219 + void clear() {
1.220 + nodes.clear();
1.221 + first_node = first_free_node = -1;
1.222 + }
1.223 +
1.224 + class Node {
1.225 + friend class NodeSet;
1.226 + template <typename T> friend class NodeMap;
1.227 +
1.228 + friend class Edge;
1.229 + friend class OutEdgeIt;
1.230 + friend class InEdgeIt;
1.231 +
1.232 + protected:
1.233 + int n;
1.234 + friend int NodeSet::id(Node v) const;
1.235 + Node(int nn) {n=nn;}
1.236 + public:
1.237 + Node() {}
1.238 + Node (Invalid i) { n=-1; }
1.239 + bool operator==(const Node i) const {return n==i.n;}
1.240 + bool operator!=(const Node i) const {return n!=i.n;}
1.241 + bool operator<(const Node i) const {return n<i.n;}
1.242 + };
1.243 +
1.244 + class NodeIt : public Node {
1.245 + friend class NodeSet;
1.246 + public:
1.247 + NodeIt(const NodeSet& G) : Node(G.first_node) { }
1.248 + NodeIt() : Node() { }
1.249 + };
1.250 +
1.251 + class Edge {
1.252 + //friend class NodeSet;
1.253 + //template <typename T> friend class EdgeMap;
1.254 +
1.255 + //template <typename T> friend class SymNodeSet::SymEdgeMap;
1.256 + //friend Edge SymNodeSet::opposite(Edge) const;
1.257 +
1.258 + // friend class Node;
1.259 + // friend class NodeIt;
1.260 + protected:
1.261 + //friend int NodeSet::id(Edge e) const;
1.262 + // Edge(int nn) {}
1.263 + public:
1.264 + Edge() { }
1.265 + Edge (Invalid) { }
1.266 + bool operator==(const Edge i) const {return true;}
1.267 + bool operator!=(const Edge i) const {return false;}
1.268 + bool operator<(const Edge i) const {return false;}
1.269 + ///\bug This is a workaround until somebody tells me how to
1.270 + ///make class \c SymNodeSet::SymEdgeMap friend of Edge
1.271 + // int idref() {return -1;}
1.272 + // int idref() const {return -1;}
1.273 + };
1.274 +
1.275 + class EdgeIt : public Edge {
1.276 + //friend class NodeSet;
1.277 + public:
1.278 + EdgeIt(const NodeSet& G) : Edge() { }
1.279 + EdgeIt (Invalid i) : Edge(i) { }
1.280 + EdgeIt() : Edge() { }
1.281 + ///\bug This is a workaround until somebody tells me how to
1.282 + ///make class \c SymNodeSet::SymEdgeMap friend of Edge
1.283 + // int idref() {return -1;}
1.284 + };
1.285 +
1.286 + class OutEdgeIt : public Edge {
1.287 + friend class NodeSet;
1.288 + public:
1.289 + OutEdgeIt() : Edge() { }
1.290 + OutEdgeIt (Invalid i) : Edge(i) { }
1.291 + OutEdgeIt(const NodeSet& G,const Node v) : Edge() {}
1.292 + };
1.293 +
1.294 + class InEdgeIt : public Edge {
1.295 + friend class NodeSet;
1.296 + public:
1.297 + InEdgeIt() : Edge() { }
1.298 + InEdgeIt (Invalid i) : Edge(i) { }
1.299 + InEdgeIt(const NodeSet& G,Node v) :Edge() {}
1.300 + };
1.301 +
1.302 + template <typename T> class NodeMap : public DynMapBase<Node>
1.303 + {
1.304 + std::vector<T> container;
1.305 +
1.306 + public:
1.307 + typedef T ValueType;
1.308 + typedef Node KeyType;
1.309 +
1.310 + NodeMap(const NodeSet &_G) :
1.311 + DynMapBase<Node>(_G), container(_G.maxNodeId())
1.312 + {
1.313 + G->dyn_node_maps.push_back(this);
1.314 + }
1.315 + NodeMap(const NodeSet &_G,const T &t) :
1.316 + DynMapBase<Node>(_G), container(_G.maxNodeId(),t)
1.317 + {
1.318 + G->dyn_node_maps.push_back(this);
1.319 + }
1.320 +
1.321 + NodeMap(const NodeMap<T> &m) :
1.322 + DynMapBase<Node>(*m.G), container(m.container)
1.323 + {
1.324 + G->dyn_node_maps.push_back(this);
1.325 + }
1.326 +
1.327 + template<typename TT> friend class NodeMap;
1.328 +
1.329 + ///\todo It can copy between different types.
1.330 + ///
1.331 + template<typename TT> NodeMap(const NodeMap<TT> &m) :
1.332 + DynMapBase<Node>(*m.G)
1.333 + {
1.334 + G->dyn_node_maps.push_back(this);
1.335 + typename std::vector<TT>::const_iterator i;
1.336 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.337 + i!=m.container.end();
1.338 + i++)
1.339 + container.push_back(*i);
1.340 + }
1.341 + ~NodeMap()
1.342 + {
1.343 + if(G) {
1.344 + std::vector<DynMapBase<Node>* >::iterator i;
1.345 + for(i=G->dyn_node_maps.begin();
1.346 + i!=G->dyn_node_maps.end() && *i!=this; ++i) ;
1.347 + //if(*i==this) G->dyn_node_maps.erase(i); //FIXME: Way too slow...
1.348 + //A better way to do that: (Is this really important?)
1.349 + if(*i==this) {
1.350 + *i=G->dyn_node_maps.back();
1.351 + G->dyn_node_maps.pop_back();
1.352 + }
1.353 + }
1.354 + }
1.355 +
1.356 + void add(const Node k)
1.357 + {
1.358 + if(k.n>=int(container.size())) container.resize(k.n+1);
1.359 + }
1.360 +
1.361 + void erase(const Node) { }
1.362 +
1.363 + void set(Node n, T a) { container[n.n]=a; }
1.364 + //'T& operator[](Node n)' would be wrong here
1.365 + typename std::vector<T>::reference
1.366 + operator[](Node n) { return container[n.n]; }
1.367 + //'const T& operator[](Node n)' would be wrong here
1.368 + typename std::vector<T>::const_reference
1.369 + operator[](Node n) const { return container[n.n]; }
1.370 +
1.371 + ///\warning There is no safety check at all!
1.372 + ///Using operator = between maps attached to different graph may
1.373 + ///cause serious problem.
1.374 + ///\todo Is this really so?
1.375 + ///\todo It can copy between different types.
1.376 + const NodeMap<T>& operator=(const NodeMap<T> &m)
1.377 + {
1.378 + container = m.container;
1.379 + return *this;
1.380 + }
1.381 + template<typename TT>
1.382 + const NodeMap<T>& operator=(const NodeMap<TT> &m)
1.383 + {
1.384 + copy(m.container.begin(), m.container.end(), container.begin());
1.385 + return *this;
1.386 + }
1.387 +
1.388 + void update() {} //Useless for Dynamic Maps
1.389 + void update(T a) {} //Useless for Dynamic Maps
1.390 + };
1.391 +
1.392 + template <typename T> class EdgeMap
1.393 + {
1.394 + public:
1.395 + typedef T ValueType;
1.396 + typedef Edge KeyType;
1.397 +
1.398 + EdgeMap(const NodeSet &) { }
1.399 + EdgeMap(const NodeSet &,const T &) { }
1.400 + EdgeMap(const EdgeMap<T> &) { }
1.401 + // template<typename TT> friend class EdgeMap;
1.402 +
1.403 + ///\todo It can copy between different types.
1.404 + ///
1.405 + template<typename TT> EdgeMap(const EdgeMap<TT> &) { }
1.406 + ~EdgeMap() { }
1.407 +
1.408 + void add(const Edge ) { }
1.409 + void erase(const Edge) { }
1.410 +
1.411 + void set(Edge, T) { }
1.412 + //T get(Edge n) const { return container[n.n]; }
1.413 + ValueType &operator[](Edge) { return *((T*)(NULL)); }
1.414 + const ValueType &operator[](Edge) const { return *((T*)(NULL)); }
1.415 +
1.416 + const EdgeMap<T>& operator=(const EdgeMap<T> &) { return *this; }
1.417 +
1.418 + template<typename TT>
1.419 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m) { return *this; }
1.420 +
1.421 + void update() {}
1.422 + void update(T a) {}
1.423 + };
1.424 + };
1.425 +
1.426 +
1.427 +
1.428 + ///This is a simple and fast erasable graph implementation.
1.429 + ///
1.430 + ///It conforms to the graph interface documented under
1.431 + ///the description of \ref GraphSkeleton.
1.432 + ///\sa \ref GraphSkeleton.
1.433 + template<typename GG>
1.434 + class EdgeSet {
1.435 +
1.436 + typedef GG NodeGraphType;
1.437 +
1.438 + NodeGraphType &G;
1.439 +
1.440 + class Node;
1.441 +
1.442 + //Edges are double linked.
1.443 + //The free edges are only single linked using the "next_in" field.
1.444 + struct NodeT
1.445 + {
1.446 + int first_in,first_out;
1.447 + NodeT() : first_in(-1), first_out(-1) { }
1.448 + };
1.449 +
1.450 + struct EdgeT
1.451 + {
1.452 + Node head, tail;
1.453 + int prev_in, prev_out;
1.454 + int next_in, next_out;
1.455 + };
1.456 +
1.457 +
1.458 + typename NodeGraphType::NodeMap<NodeT> nodes;
1.459 +
1.460 + std::vector<EdgeT> edges;
1.461 + //The first free edge
1.462 + int first_free_edge;
1.463 +
1.464 + protected:
1.465 +
1.466 + template <typename Key> class DynMapBase
1.467 + {
1.468 + protected:
1.469 + const EdgeSet* G;
1.470 + public:
1.471 + virtual void add(const Key k) = NULL;
1.472 + virtual void erase(const Key k) = NULL;
1.473 + DynMapBase(const EdgeSet &_G) : G(&_G) {}
1.474 + virtual ~DynMapBase() {}
1.475 + friend class EdgeSet;
1.476 + };
1.477 +
1.478 + public:
1.479 + //template <typename T> class NodeMap;
1.480 + template <typename T> class EdgeMap;
1.481 +
1.482 + class Node;
1.483 + class Edge;
1.484 +
1.485 + // protected:
1.486 + // HELPME:
1.487 + protected:
1.488 + // mutable std::vector<DynMapBase<Node> * > dyn_node_maps;
1.489 + ///\bug It must be public because of SymEdgeMap.
1.490 + ///
1.491 + mutable std::vector<DynMapBase<Edge> * > dyn_edge_maps;
1.492 +
1.493 + public:
1.494 +
1.495 + class NodeIt;
1.496 + class EdgeIt;
1.497 + class OutEdgeIt;
1.498 + class InEdgeIt;
1.499 +
1.500 + template <typename T> class NodeMap;
1.501 + template <typename T> class EdgeMap;
1.502 +
1.503 + public:
1.504 +
1.505 + EdgeSet(const NodeGraphType &_G) : G(_G),
1.506 + nodes(_G), edges(),
1.507 + first_free_edge(-1) {}
1.508 + EdgeSet(const EdgeSet &_g) : G(_g.G), nodes(_g.G), edges(_g.edges),
1.509 + first_free_edge(_g.first_free_edge) {}
1.510 +
1.511 + ~EdgeSet()
1.512 + {
1.513 + // for(std::vector<DynMapBase<Node> * >::iterator i=dyn_node_maps.begin();
1.514 + // i!=dyn_node_maps.end(); ++i) (**i).G=NULL;
1.515 + for(typename std::vector<DynMapBase<Edge> * >::iterator
1.516 + i=dyn_edge_maps.begin();
1.517 + i!=dyn_edge_maps.end(); ++i) (**i).G=NULL;
1.518 + }
1.519 +
1.520 + int nodeNum() const { return G.nodeNum(); } //FIXME: What is this?
1.521 + int edgeNum() const { return edges.size(); } //FIXME: What is this?
1.522 +
1.523 + ///\bug This function does something different than
1.524 + ///its name would suggests...
1.525 + int maxNodeId() const { return G.maxNodeId(); } //FIXME: What is this?
1.526 + ///\bug This function does something different than
1.527 + ///its name would suggests...
1.528 + int maxEdgeId() const { return edges.size(); } //FIXME: What is this?
1.529 +
1.530 + Node tail(Edge e) const { return edges[e.n].tail; }
1.531 + Node head(Edge e) const { return edges[e.n].head; }
1.532 +
1.533 + Node aNode(OutEdgeIt e) const { return edges[e.n].tail; }
1.534 + Node aNode(InEdgeIt e) const { return edges[e.n].head; }
1.535 +
1.536 + Node bNode(OutEdgeIt e) const { return edges[e.n].head; }
1.537 + Node bNode(InEdgeIt e) const { return edges[e.n].tail; }
1.538 +
1.539 + NodeIt& first(NodeIt& v) const {
1.540 + v=NodeIt(*this); return v; }
1.541 + EdgeIt& first(EdgeIt& e) const {
1.542 + e=EdgeIt(*this); return e; }
1.543 + OutEdgeIt& first(OutEdgeIt& e, const Node v) const {
1.544 + e=OutEdgeIt(*this,v); return e; }
1.545 + InEdgeIt& first(InEdgeIt& e, const Node v) const {
1.546 + e=InEdgeIt(*this,v); return e; }
1.547 +
1.548 +// template< typename It >
1.549 +// It first() const { It e; first(e); return e; }
1.550 +
1.551 +// template< typename It >
1.552 +// It first(Node v) const { It e; first(e,v); return e; }
1.553 +
1.554 + bool valid(Edge e) const { return e.n!=-1; }
1.555 + bool valid(Node n) const { return G.valid(n); }
1.556 +
1.557 + void setInvalid(Edge &e) { e.n=-1; }
1.558 + void setInvalid(Node &n) { G.setInvalid(n); }
1.559 +
1.560 + template <typename It> It getNext(It it) const
1.561 + { It tmp(it); return next(tmp); }
1.562 +
1.563 + NodeIt& next(NodeIt& it) const { G.next(it); return it; }
1.564 + OutEdgeIt& next(OutEdgeIt& it) const
1.565 + { it.n=edges[it.n].next_out; return it; }
1.566 + InEdgeIt& next(InEdgeIt& it) const
1.567 + { it.n=edges[it.n].next_in; return it; }
1.568 + EdgeIt& next(EdgeIt& it) const {
1.569 + if(edges[it.n].next_in!=-1) {
1.570 + it.n=edges[it.n].next_in;
1.571 + }
1.572 + else {
1.573 + typename NodeGraphType::Node n;
1.574 + for(n=G.next(edges[it.n].head);
1.575 + G.valid(n) && nodes[n].first_in == -1;
1.576 + G.next(n)) ;
1.577 + it.n = (G.valid(n))?-1:nodes[n].first_in;
1.578 + }
1.579 + return it;
1.580 + }
1.581 +
1.582 + int id(Node v) const { return G.id(v); }
1.583 + int id(Edge e) const { return e.n; }
1.584 +
1.585 + /// Adds a new node to the graph.
1.586 + Node addNode() { return G.AddNode(); }
1.587 +
1.588 + Edge addEdge(Node u, Node v) {
1.589 + int n;
1.590 +
1.591 + if(first_free_edge==-1)
1.592 + {
1.593 + n = edges.size();
1.594 + edges.push_back(EdgeT());
1.595 + }
1.596 + else {
1.597 + n = first_free_edge;
1.598 + first_free_edge = edges[n].next_in;
1.599 + }
1.600 +
1.601 + edges[n].tail = u.n; edges[n].head = v.n;
1.602 +
1.603 + edges[n].next_out = nodes[u.n].first_out;
1.604 + if(nodes[u.n].first_out != -1) edges[nodes[u.n].first_out].prev_out = n;
1.605 + edges[n].next_in = nodes[v.n].first_in;
1.606 + if(nodes[v.n].first_in != -1) edges[nodes[v.n].first_in].prev_in = n;
1.607 + edges[n].prev_in = edges[n].prev_out = -1;
1.608 +
1.609 + nodes[u.n].first_out = nodes[v.n].first_in = n;
1.610 +
1.611 + Edge e; e.n=n;
1.612 +
1.613 + //Update dynamic maps
1.614 + for(typename std::vector<DynMapBase<Edge> * >::iterator
1.615 + i=dyn_edge_maps.begin();
1.616 + i!=dyn_edge_maps.end(); ++i) (**i).add(e);
1.617 +
1.618 + return e;
1.619 + }
1.620 +
1.621 + private:
1.622 + void eraseEdge(int n) {
1.623 +
1.624 + if(edges[n].next_in!=-1)
1.625 + edges[edges[n].next_in].prev_in = edges[n].prev_in;
1.626 + if(edges[n].prev_in!=-1)
1.627 + edges[edges[n].prev_in].next_in = edges[n].next_in;
1.628 + else nodes[edges[n].head].first_in = edges[n].next_in;
1.629 +
1.630 + if(edges[n].next_out!=-1)
1.631 + edges[edges[n].next_out].prev_out = edges[n].prev_out;
1.632 + if(edges[n].prev_out!=-1)
1.633 + edges[edges[n].prev_out].next_out = edges[n].next_out;
1.634 + else nodes[edges[n].tail].first_out = edges[n].next_out;
1.635 +
1.636 + edges[n].next_in = first_free_edge;
1.637 + first_free_edge = -1;
1.638 +
1.639 + //Update dynamic maps
1.640 + Edge e; e.n=n;
1.641 + for(typename std::vector<DynMapBase<Edge> * >::iterator
1.642 + i=dyn_edge_maps.begin();
1.643 + i!=dyn_edge_maps.end(); ++i) (**i).erase(e);
1.644 + }
1.645 +
1.646 + public:
1.647 +
1.648 +// void erase(Node nn) {
1.649 +// int n=nn.n;
1.650 +// int m;
1.651 +// while((m=nodes[n].first_in)!=-1) eraseEdge(m);
1.652 +// while((m=nodes[n].first_out)!=-1) eraseEdge(m);
1.653 +// }
1.654 +
1.655 + void erase(Edge e) { eraseEdge(e.n); }
1.656 +
1.657 +// //\bug Dynamic maps must be updated!
1.658 +// //
1.659 +// void clear() {
1.660 +// nodes.clear();edges.clear();
1.661 +// first_node=first_free_node=first_free_edge=-1;
1.662 +// }
1.663 +
1.664 + class Node : public NodeGraphType::Node {
1.665 + friend class EdgeSet;
1.666 + // template <typename T> friend class NodeMap;
1.667 +
1.668 + friend class Edge;
1.669 + friend class OutEdgeIt;
1.670 + friend class InEdgeIt;
1.671 + friend class SymEdge;
1.672 +
1.673 + protected:
1.674 + friend int EdgeSet::id(Node v) const;
1.675 + // Node(int nn) {n=nn;}
1.676 + public:
1.677 + Node() : NodeGraphType::Node() {}
1.678 + Node (Invalid i) : NodeGraphType::Node(i) {}
1.679 + Node(const typename NodeGraphType::Node &n) : NodeGraphType::Node(n) {}
1.680 + };
1.681 +
1.682 + class NodeIt : public NodeGraphType::NodeIt {
1.683 + friend class EdgeSet;
1.684 + public:
1.685 + NodeIt() : NodeGraphType::NodeIt() { }
1.686 + NodeIt (Invalid i) : NodeGraphType::NodeIt(i) {}
1.687 + NodeIt(const EdgeSet& _G) : NodeGraphType::Node(_G.G) { }
1.688 + NodeIt(const typename NodeGraphType::NodeIt &n)
1.689 + : NodeGraphType::NodeIt(n) {}
1.690 + operator Node() { return Node(*this);}
1.691 + };
1.692 +
1.693 + class Edge {
1.694 + friend class EdgeSet;
1.695 + template <typename T> friend class EdgeMap;
1.696 +
1.697 + //template <typename T> friend class SymEdgeSet::SymEdgeMap;
1.698 + //friend Edge SymEdgeSet::opposite(Edge) const;
1.699 +
1.700 + friend class Node;
1.701 + friend class NodeIt;
1.702 + protected:
1.703 + int n;
1.704 + friend int EdgeSet::id(Edge e) const;
1.705 +
1.706 + Edge(int nn) {n=nn;}
1.707 + public:
1.708 + Edge() { }
1.709 + Edge (Invalid) { n=-1; }
1.710 + bool operator==(const Edge i) const {return n==i.n;}
1.711 + bool operator!=(const Edge i) const {return n!=i.n;}
1.712 + bool operator<(const Edge i) const {return n<i.n;}
1.713 + ///\bug This is a workaround until somebody tells me how to
1.714 + ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1.715 + int &idref() {return n;}
1.716 + const int &idref() const {return n;}
1.717 + };
1.718 +
1.719 + class EdgeIt : public Edge {
1.720 + friend class EdgeSet;
1.721 + public:
1.722 + EdgeIt(const EdgeSet& G) : Edge() {
1.723 + typename NodeGraphType::Node m;
1.724 + for(G.first(m);
1.725 + G.valid(m) && nodes[m].first_in == -1; G.next[m]);
1.726 + n = G.valid(m)?-1:nodes[m].first_in;
1.727 + }
1.728 + EdgeIt (Invalid i) : Edge(i) { }
1.729 + EdgeIt() : Edge() { }
1.730 + ///\bug This is a workaround until somebody tells me how to
1.731 + ///make class \c SymEdgeSet::SymEdgeMap friend of Edge
1.732 + int &idref() {return n;}
1.733 + };
1.734 +
1.735 + class OutEdgeIt : public Edge {
1.736 + friend class EdgeSet;
1.737 + public:
1.738 + OutEdgeIt() : Edge() { }
1.739 + OutEdgeIt (Invalid i) : Edge(i) { }
1.740 +
1.741 + OutEdgeIt(const EdgeSet& G,const Node v) : Edge(nodes[v].first_out) { }
1.742 + };
1.743 +
1.744 + class InEdgeIt : public Edge {
1.745 + friend class EdgeSet;
1.746 + public:
1.747 + InEdgeIt() : Edge() { }
1.748 + InEdgeIt (Invalid i) : Edge(i) { }
1.749 + InEdgeIt(const EdgeSet& G,Node v) :Edge(nodes[v].first_in) { }
1.750 + };
1.751 +
1.752 + template <typename T> class NodeMap : public NodeGraphType::NodeMap<T>
1.753 + {
1.754 + public:
1.755 + NodeMap(const EdgeSet &_G) :
1.756 + NodeGraphType::NodeMap<T>(_G.G) { }
1.757 + NodeMap(const EdgeSet &_G,const T &t) :
1.758 + NodeGraphType::NodeMap<T>(_G.G,t) { }
1.759 + //It is unnecessary
1.760 + NodeMap(const typename NodeGraphType::NodeMap<T> &m)
1.761 + : NodeGraphType::NodeMap<T>(m) { }
1.762 +
1.763 + ///\todo It can copy between different types.
1.764 + ///
1.765 + template<typename TT> friend class NodeMap;
1.766 + NodeMap(const typename NodeGraphType::NodeMap<TT> &m)
1.767 + : NodeGraphType::NodeMap<T>(m) { }
1.768 + };
1.769 +
1.770 + template <typename T> class EdgeMap : public DynMapBase<Edge>
1.771 + {
1.772 + std::vector<T> container;
1.773 +
1.774 + public:
1.775 + typedef T ValueType;
1.776 + typedef Edge KeyType;
1.777 +
1.778 + EdgeMap(const EdgeSet &_G) :
1.779 + DynMapBase<Edge>(_G), container(_G.maxEdgeId())
1.780 + {
1.781 + //FIXME: What if there are empty Id's?
1.782 + //FIXME: Can I use 'this' in a constructor?
1.783 + G->dyn_edge_maps.push_back(this);
1.784 + }
1.785 + EdgeMap(const EdgeSet &_G,const T &t) :
1.786 + DynMapBase<Edge>(_G), container(_G.maxEdgeId(),t)
1.787 + {
1.788 + G->dyn_edge_maps.push_back(this);
1.789 + }
1.790 + EdgeMap(const EdgeMap<T> &m) :
1.791 + DynMapBase<Edge>(*m.G), container(m.container)
1.792 + {
1.793 + G->dyn_node_maps.push_back(this);
1.794 + }
1.795 +
1.796 + template<typename TT> friend class EdgeMap;
1.797 +
1.798 + ///\todo It can copy between different types.
1.799 + ///
1.800 + template<typename TT> EdgeMap(const EdgeMap<TT> &m) :
1.801 + DynMapBase<Edge>(*m.G)
1.802 + {
1.803 + G->dyn_node_maps.push_back(this);
1.804 + typename std::vector<TT>::const_iterator i;
1.805 + for(typename std::vector<TT>::const_iterator i=m.container.begin();
1.806 + i!=m.container.end();
1.807 + i++)
1.808 + container.push_back(*i);
1.809 + }
1.810 + ~EdgeMap()
1.811 + {
1.812 + if(G) {
1.813 + typename std::vector<DynMapBase<Edge>* >::iterator i;
1.814 + for(i=G->dyn_edge_maps.begin();
1.815 + i!=G->dyn_edge_maps.end() && *i!=this; ++i) ;
1.816 + //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow...
1.817 + //A better way to do that: (Is this really important?)
1.818 + if(*i==this) {
1.819 + *i=G->dyn_edge_maps.back();
1.820 + G->dyn_edge_maps.pop_back();
1.821 + }
1.822 + }
1.823 + }
1.824 +
1.825 + void add(const Edge k)
1.826 + {
1.827 + if(k.n>=int(container.size())) container.resize(k.n+1);
1.828 + }
1.829 + void erase(const Edge) { }
1.830 +
1.831 + void set(Edge n, T a) { container[n.n]=a; }
1.832 + //T get(Edge n) const { return container[n.n]; }
1.833 + typename std::vector<T>::reference
1.834 + operator[](Edge n) { return container[n.n]; }
1.835 + typename std::vector<T>::const_reference
1.836 + operator[](Edge n) const { return container[n.n]; }
1.837 +
1.838 + ///\warning There is no safety check at all!
1.839 + ///Using operator = between maps attached to different graph may
1.840 + ///cause serious problem.
1.841 + ///\todo Is this really so?
1.842 + ///\todo It can copy between different types.
1.843 + const EdgeMap<T>& operator=(const EdgeMap<T> &m)
1.844 + {
1.845 + container = m.container;
1.846 + return *this;
1.847 + }
1.848 + template<typename TT>
1.849 + const EdgeMap<T>& operator=(const EdgeMap<TT> &m)
1.850 + {
1.851 + copy(m.container.begin(), m.container.end(), container.begin());
1.852 + return *this;
1.853 + }
1.854 +
1.855 + void update() {} //Useless for DynMaps
1.856 + void update(T a) {} //Useless for DynMaps
1.857 + };
1.858 +
1.859 + };
1.860 +
1.861 +
1.862 +
1.863 +
1.864 +
1.865 +
1.866 +
1.867
1.868 } //namespace hugo
1.869