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