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