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