1.1 --- a/lemon/edge_set.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/edge_set.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -22,20 +22,19 @@
1.4 #include <lemon/core.h>
1.5 #include <lemon/bits/edge_set_extender.h>
1.6
1.7 -/// \ingroup semi_adaptors
1.8 +/// \ingroup graphs
1.9 /// \file
1.10 /// \brief ArcSet and EdgeSet classes.
1.11 ///
1.12 /// Graphs which use another graph's node-set as own.
1.13 namespace lemon {
1.14
1.15 - template <typename _Graph>
1.16 + template <typename GR>
1.17 class ListArcSetBase {
1.18 public:
1.19
1.20 - typedef _Graph Graph;
1.21 - typedef typename Graph::Node Node;
1.22 - typedef typename Graph::NodeIt NodeIt;
1.23 + typedef typename GR::Node Node;
1.24 + typedef typename GR::NodeIt NodeIt;
1.25
1.26 protected:
1.27
1.28 @@ -44,10 +43,10 @@
1.29 NodeT() : first_out(-1), first_in(-1) {}
1.30 };
1.31
1.32 - typedef typename ItemSetTraits<Graph, Node>::
1.33 + typedef typename ItemSetTraits<GR, Node>::
1.34 template Map<NodeT>::Type NodesImplBase;
1.35
1.36 - NodesImplBase* nodes;
1.37 + NodesImplBase* _nodes;
1.38
1.39 struct ArcT {
1.40 Node source, target;
1.41 @@ -61,17 +60,17 @@
1.42 int first_arc;
1.43 int first_free_arc;
1.44
1.45 - const Graph* graph;
1.46 + const GR* _graph;
1.47
1.48 - void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.49 - graph = &_graph;
1.50 - nodes = &_nodes;
1.51 + void initalize(const GR& graph, NodesImplBase& nodes) {
1.52 + _graph = &graph;
1.53 + _nodes = &nodes;
1.54 }
1.55
1.56 public:
1.57
1.58 class Arc {
1.59 - friend class ListArcSetBase<Graph>;
1.60 + friend class ListArcSetBase<GR>;
1.61 protected:
1.62 Arc(int _id) : id(_id) {}
1.63 int id;
1.64 @@ -85,6 +84,12 @@
1.65
1.66 ListArcSetBase() : first_arc(-1), first_free_arc(-1) {}
1.67
1.68 + Node addNode() {
1.69 + LEMON_ASSERT(false,
1.70 + "This graph structure does not support node insertion");
1.71 + return INVALID; // avoid warning
1.72 + }
1.73 +
1.74 Arc addArc(const Node& u, const Node& v) {
1.75 int n;
1.76 if (first_free_arc == -1) {
1.77 @@ -94,16 +99,16 @@
1.78 n = first_free_arc;
1.79 first_free_arc = arcs[first_free_arc].next_in;
1.80 }
1.81 - arcs[n].next_in = (*nodes)[v].first_in;
1.82 - if ((*nodes)[v].first_in != -1) {
1.83 - arcs[(*nodes)[v].first_in].prev_in = n;
1.84 + arcs[n].next_in = (*_nodes)[v].first_in;
1.85 + if ((*_nodes)[v].first_in != -1) {
1.86 + arcs[(*_nodes)[v].first_in].prev_in = n;
1.87 }
1.88 - (*nodes)[v].first_in = n;
1.89 - arcs[n].next_out = (*nodes)[u].first_out;
1.90 - if ((*nodes)[u].first_out != -1) {
1.91 - arcs[(*nodes)[u].first_out].prev_out = n;
1.92 + (*_nodes)[v].first_in = n;
1.93 + arcs[n].next_out = (*_nodes)[u].first_out;
1.94 + if ((*_nodes)[u].first_out != -1) {
1.95 + arcs[(*_nodes)[u].first_out].prev_out = n;
1.96 }
1.97 - (*nodes)[u].first_out = n;
1.98 + (*_nodes)[u].first_out = n;
1.99 arcs[n].source = u;
1.100 arcs[n].target = v;
1.101 return Arc(n);
1.102 @@ -114,7 +119,7 @@
1.103 if (arcs[n].prev_in != -1) {
1.104 arcs[arcs[n].prev_in].next_in = arcs[n].next_in;
1.105 } else {
1.106 - (*nodes)[arcs[n].target].first_in = arcs[n].next_in;
1.107 + (*_nodes)[arcs[n].target].first_in = arcs[n].next_in;
1.108 }
1.109 if (arcs[n].next_in != -1) {
1.110 arcs[arcs[n].next_in].prev_in = arcs[n].prev_in;
1.111 @@ -123,7 +128,7 @@
1.112 if (arcs[n].prev_out != -1) {
1.113 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.114 } else {
1.115 - (*nodes)[arcs[n].source].first_out = arcs[n].next_out;
1.116 + (*_nodes)[arcs[n].source].first_out = arcs[n].next_out;
1.117 }
1.118 if (arcs[n].next_out != -1) {
1.119 arcs[arcs[n].next_out].prev_out = arcs[n].prev_out;
1.120 @@ -134,8 +139,8 @@
1.121 void clear() {
1.122 Node node;
1.123 for (first(node); node != INVALID; next(node)) {
1.124 - (*nodes)[node].first_in = -1;
1.125 - (*nodes)[node].first_out = -1;
1.126 + (*_nodes)[node].first_in = -1;
1.127 + (*_nodes)[node].first_out = -1;
1.128 }
1.129 arcs.clear();
1.130 first_arc = -1;
1.131 @@ -143,20 +148,20 @@
1.132 }
1.133
1.134 void first(Node& node) const {
1.135 - graph->first(node);
1.136 + _graph->first(node);
1.137 }
1.138
1.139 void next(Node& node) const {
1.140 - graph->next(node);
1.141 + _graph->next(node);
1.142 }
1.143
1.144 void first(Arc& arc) const {
1.145 Node node;
1.146 first(node);
1.147 - while (node != INVALID && (*nodes)[node].first_in == -1) {
1.148 + while (node != INVALID && (*_nodes)[node].first_in == -1) {
1.149 next(node);
1.150 }
1.151 - arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.152 + arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
1.153 }
1.154
1.155 void next(Arc& arc) const {
1.156 @@ -165,15 +170,15 @@
1.157 } else {
1.158 Node node = arcs[arc.id].target;
1.159 next(node);
1.160 - while (node != INVALID && (*nodes)[node].first_in == -1) {
1.161 + while (node != INVALID && (*_nodes)[node].first_in == -1) {
1.162 next(node);
1.163 }
1.164 - arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_in;
1.165 + arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_in;
1.166 }
1.167 }
1.168
1.169 void firstOut(Arc& arc, const Node& node) const {
1.170 - arc.id = (*nodes)[node].first_out;
1.171 + arc.id = (*_nodes)[node].first_out;
1.172 }
1.173
1.174 void nextOut(Arc& arc) const {
1.175 @@ -181,42 +186,42 @@
1.176 }
1.177
1.178 void firstIn(Arc& arc, const Node& node) const {
1.179 - arc.id = (*nodes)[node].first_in;
1.180 + arc.id = (*_nodes)[node].first_in;
1.181 }
1.182
1.183 void nextIn(Arc& arc) const {
1.184 arc.id = arcs[arc.id].next_in;
1.185 }
1.186
1.187 - int id(const Node& node) const { return graph->id(node); }
1.188 + int id(const Node& node) const { return _graph->id(node); }
1.189 int id(const Arc& arc) const { return arc.id; }
1.190
1.191 - Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
1.192 + Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
1.193 Arc arcFromId(int ix) const { return Arc(ix); }
1.194
1.195 - int maxNodeId() const { return graph->maxNodeId(); };
1.196 + int maxNodeId() const { return _graph->maxNodeId(); };
1.197 int maxArcId() const { return arcs.size() - 1; }
1.198
1.199 Node source(const Arc& arc) const { return arcs[arc.id].source;}
1.200 Node target(const Arc& arc) const { return arcs[arc.id].target;}
1.201
1.202 - typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.203 + typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
1.204
1.205 NodeNotifier& notifier(Node) const {
1.206 - return graph->notifier(Node());
1.207 + return _graph->notifier(Node());
1.208 }
1.209
1.210 - template <typename _Value>
1.211 - class NodeMap : public Graph::template NodeMap<_Value> {
1.212 + template <typename V>
1.213 + class NodeMap : public GR::template NodeMap<V> {
1.214 + typedef typename GR::template NodeMap<V> Parent;
1.215 +
1.216 public:
1.217
1.218 - typedef typename _Graph::template NodeMap<_Value> Parent;
1.219 + explicit NodeMap(const ListArcSetBase<GR>& arcset)
1.220 + : Parent(*arcset._graph) {}
1.221
1.222 - explicit NodeMap(const ListArcSetBase<Graph>& arcset)
1.223 - : Parent(*arcset.graph) {}
1.224 -
1.225 - NodeMap(const ListArcSetBase<Graph>& arcset, const _Value& value)
1.226 - : Parent(*arcset.graph, value) {}
1.227 + NodeMap(const ListArcSetBase<GR>& arcset, const V& value)
1.228 + : Parent(*arcset._graph, value) {}
1.229
1.230 NodeMap& operator=(const NodeMap& cmap) {
1.231 return operator=<NodeMap>(cmap);
1.232 @@ -231,7 +236,7 @@
1.233
1.234 };
1.235
1.236 - /// \ingroup semi_adaptors
1.237 + /// \ingroup graphs
1.238 ///
1.239 /// \brief Digraph using a node set of another digraph or graph and
1.240 /// an own arc set.
1.241 @@ -250,26 +255,22 @@
1.242 /// that node can be removed from the underlying graph, in this case
1.243 /// all arcs incident to the given node is erased from the arc set.
1.244 ///
1.245 - /// \param _Graph The type of the graph which shares its node set with
1.246 + /// \param GR The type of the graph which shares its node set with
1.247 /// this class. Its interface must conform to the
1.248 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.249 /// concept.
1.250 ///
1.251 - /// This class is fully conform to the \ref concepts::Digraph
1.252 + /// This class fully conforms to the \ref concepts::Digraph
1.253 /// "Digraph" concept.
1.254 - template <typename _Graph>
1.255 - class ListArcSet : public ArcSetExtender<ListArcSetBase<_Graph> > {
1.256 + template <typename GR>
1.257 + class ListArcSet : public ArcSetExtender<ListArcSetBase<GR> > {
1.258 + typedef ArcSetExtender<ListArcSetBase<GR> > Parent;
1.259
1.260 public:
1.261
1.262 - typedef ArcSetExtender<ListArcSetBase<_Graph> > Parent;
1.263 -
1.264 typedef typename Parent::Node Node;
1.265 typedef typename Parent::Arc Arc;
1.266
1.267 - typedef _Graph Graph;
1.268 -
1.269 -
1.270 typedef typename Parent::NodesImplBase NodesImplBase;
1.271
1.272 void eraseNode(const Node& node) {
1.273 @@ -292,10 +293,10 @@
1.274 }
1.275
1.276 class NodesImpl : public NodesImplBase {
1.277 - public:
1.278 typedef NodesImplBase Parent;
1.279
1.280 - NodesImpl(const Graph& graph, ListArcSet& arcset)
1.281 + public:
1.282 + NodesImpl(const GR& graph, ListArcSet& arcset)
1.283 : Parent(graph), _arcset(arcset) {}
1.284
1.285 virtual ~NodesImpl() {}
1.286 @@ -321,22 +322,22 @@
1.287 ListArcSet& _arcset;
1.288 };
1.289
1.290 - NodesImpl nodes;
1.291 + NodesImpl _nodes;
1.292
1.293 public:
1.294
1.295 /// \brief Constructor of the ArcSet.
1.296 ///
1.297 /// Constructor of the ArcSet.
1.298 - ListArcSet(const Graph& graph) : nodes(graph, *this) {
1.299 - Parent::initalize(graph, nodes);
1.300 + ListArcSet(const GR& graph) : _nodes(graph, *this) {
1.301 + Parent::initalize(graph, _nodes);
1.302 }
1.303
1.304 /// \brief Add a new arc to the digraph.
1.305 ///
1.306 /// Add a new arc to the digraph with source node \c s
1.307 /// and target node \c t.
1.308 - /// \return the new arc.
1.309 + /// \return The new arc.
1.310 Arc addArc(const Node& s, const Node& t) {
1.311 return Parent::addArc(s, t);
1.312 }
1.313 @@ -350,13 +351,12 @@
1.314
1.315 };
1.316
1.317 - template <typename _Graph>
1.318 + template <typename GR>
1.319 class ListEdgeSetBase {
1.320 public:
1.321
1.322 - typedef _Graph Graph;
1.323 - typedef typename Graph::Node Node;
1.324 - typedef typename Graph::NodeIt NodeIt;
1.325 + typedef typename GR::Node Node;
1.326 + typedef typename GR::NodeIt NodeIt;
1.327
1.328 protected:
1.329
1.330 @@ -365,10 +365,10 @@
1.331 NodeT() : first_out(-1) {}
1.332 };
1.333
1.334 - typedef typename ItemSetTraits<Graph, Node>::
1.335 + typedef typename ItemSetTraits<GR, Node>::
1.336 template Map<NodeT>::Type NodesImplBase;
1.337
1.338 - NodesImplBase* nodes;
1.339 + NodesImplBase* _nodes;
1.340
1.341 struct ArcT {
1.342 Node target;
1.343 @@ -381,11 +381,11 @@
1.344 int first_arc;
1.345 int first_free_arc;
1.346
1.347 - const Graph* graph;
1.348 + const GR* _graph;
1.349
1.350 - void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.351 - graph = &_graph;
1.352 - nodes = &_nodes;
1.353 + void initalize(const GR& graph, NodesImplBase& nodes) {
1.354 + _graph = &graph;
1.355 + _nodes = &nodes;
1.356 }
1.357
1.358 public:
1.359 @@ -422,6 +422,12 @@
1.360
1.361 ListEdgeSetBase() : first_arc(-1), first_free_arc(-1) {}
1.362
1.363 + Node addNode() {
1.364 + LEMON_ASSERT(false,
1.365 + "This graph structure does not support node insertion");
1.366 + return INVALID; // avoid warning
1.367 + }
1.368 +
1.369 Edge addEdge(const Node& u, const Node& v) {
1.370 int n;
1.371
1.372 @@ -437,18 +443,18 @@
1.373 arcs[n].target = u;
1.374 arcs[n | 1].target = v;
1.375
1.376 - arcs[n].next_out = (*nodes)[v].first_out;
1.377 - if ((*nodes)[v].first_out != -1) {
1.378 - arcs[(*nodes)[v].first_out].prev_out = n;
1.379 + arcs[n].next_out = (*_nodes)[v].first_out;
1.380 + if ((*_nodes)[v].first_out != -1) {
1.381 + arcs[(*_nodes)[v].first_out].prev_out = n;
1.382 }
1.383 - (*nodes)[v].first_out = n;
1.384 + (*_nodes)[v].first_out = n;
1.385 arcs[n].prev_out = -1;
1.386
1.387 - if ((*nodes)[u].first_out != -1) {
1.388 - arcs[(*nodes)[u].first_out].prev_out = (n | 1);
1.389 + if ((*_nodes)[u].first_out != -1) {
1.390 + arcs[(*_nodes)[u].first_out].prev_out = (n | 1);
1.391 }
1.392 - arcs[n | 1].next_out = (*nodes)[u].first_out;
1.393 - (*nodes)[u].first_out = (n | 1);
1.394 + arcs[n | 1].next_out = (*_nodes)[u].first_out;
1.395 + (*_nodes)[u].first_out = (n | 1);
1.396 arcs[n | 1].prev_out = -1;
1.397
1.398 return Edge(n / 2);
1.399 @@ -464,7 +470,7 @@
1.400 if (arcs[n].prev_out != -1) {
1.401 arcs[arcs[n].prev_out].next_out = arcs[n].next_out;
1.402 } else {
1.403 - (*nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
1.404 + (*_nodes)[arcs[n | 1].target].first_out = arcs[n].next_out;
1.405 }
1.406
1.407 if (arcs[n | 1].next_out != -1) {
1.408 @@ -474,7 +480,7 @@
1.409 if (arcs[n | 1].prev_out != -1) {
1.410 arcs[arcs[n | 1].prev_out].next_out = arcs[n | 1].next_out;
1.411 } else {
1.412 - (*nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
1.413 + (*_nodes)[arcs[n].target].first_out = arcs[n | 1].next_out;
1.414 }
1.415
1.416 arcs[n].next_out = first_free_arc;
1.417 @@ -485,7 +491,7 @@
1.418 void clear() {
1.419 Node node;
1.420 for (first(node); node != INVALID; next(node)) {
1.421 - (*nodes)[node].first_out = -1;
1.422 + (*_nodes)[node].first_out = -1;
1.423 }
1.424 arcs.clear();
1.425 first_arc = -1;
1.426 @@ -493,20 +499,20 @@
1.427 }
1.428
1.429 void first(Node& node) const {
1.430 - graph->first(node);
1.431 + _graph->first(node);
1.432 }
1.433
1.434 void next(Node& node) const {
1.435 - graph->next(node);
1.436 + _graph->next(node);
1.437 }
1.438
1.439 void first(Arc& arc) const {
1.440 Node node;
1.441 first(node);
1.442 - while (node != INVALID && (*nodes)[node].first_out == -1) {
1.443 + while (node != INVALID && (*_nodes)[node].first_out == -1) {
1.444 next(node);
1.445 }
1.446 - arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
1.447 + arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
1.448 }
1.449
1.450 void next(Arc& arc) const {
1.451 @@ -515,10 +521,10 @@
1.452 } else {
1.453 Node node = arcs[arc.id ^ 1].target;
1.454 next(node);
1.455 - while(node != INVALID && (*nodes)[node].first_out == -1) {
1.456 + while(node != INVALID && (*_nodes)[node].first_out == -1) {
1.457 next(node);
1.458 }
1.459 - arc.id = (node == INVALID) ? -1 : (*nodes)[node].first_out;
1.460 + arc.id = (node == INVALID) ? -1 : (*_nodes)[node].first_out;
1.461 }
1.462 }
1.463
1.464 @@ -526,7 +532,7 @@
1.465 Node node;
1.466 first(node);
1.467 while (node != INVALID) {
1.468 - edge.id = (*nodes)[node].first_out;
1.469 + edge.id = (*_nodes)[node].first_out;
1.470 while ((edge.id & 1) != 1) {
1.471 edge.id = arcs[edge.id].next_out;
1.472 }
1.473 @@ -551,7 +557,7 @@
1.474 }
1.475 next(node);
1.476 while (node != INVALID) {
1.477 - edge.id = (*nodes)[node].first_out;
1.478 + edge.id = (*_nodes)[node].first_out;
1.479 while ((edge.id & 1) != 1) {
1.480 edge.id = arcs[edge.id].next_out;
1.481 }
1.482 @@ -565,7 +571,7 @@
1.483 }
1.484
1.485 void firstOut(Arc& arc, const Node& node) const {
1.486 - arc.id = (*nodes)[node].first_out;
1.487 + arc.id = (*_nodes)[node].first_out;
1.488 }
1.489
1.490 void nextOut(Arc& arc) const {
1.491 @@ -573,7 +579,7 @@
1.492 }
1.493
1.494 void firstIn(Arc& arc, const Node& node) const {
1.495 - arc.id = (((*nodes)[node].first_out) ^ 1);
1.496 + arc.id = (((*_nodes)[node].first_out) ^ 1);
1.497 if (arc.id == -2) arc.id = -1;
1.498 }
1.499
1.500 @@ -583,7 +589,7 @@
1.501 }
1.502
1.503 void firstInc(Edge &arc, bool& dir, const Node& node) const {
1.504 - int de = (*nodes)[node].first_out;
1.505 + int de = (*_nodes)[node].first_out;
1.506 if (de != -1 ) {
1.507 arc.id = de / 2;
1.508 dir = ((de & 1) == 1);
1.509 @@ -611,15 +617,15 @@
1.510 return Arc(edge.id * 2 + (dir ? 1 : 0));
1.511 }
1.512
1.513 - int id(const Node& node) const { return graph->id(node); }
1.514 + int id(const Node& node) const { return _graph->id(node); }
1.515 static int id(Arc e) { return e.id; }
1.516 static int id(Edge e) { return e.id; }
1.517
1.518 - Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1.519 + Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
1.520 static Arc arcFromId(int id) { return Arc(id);}
1.521 static Edge edgeFromId(int id) { return Edge(id);}
1.522
1.523 - int maxNodeId() const { return graph->maxNodeId(); };
1.524 + int maxNodeId() const { return _graph->maxNodeId(); };
1.525 int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.526 int maxArcId() const { return arcs.size()-1; }
1.527
1.528 @@ -629,23 +635,23 @@
1.529 Node u(Edge e) const { return arcs[2 * e.id].target; }
1.530 Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
1.531
1.532 - typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.533 + typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
1.534
1.535 NodeNotifier& notifier(Node) const {
1.536 - return graph->notifier(Node());
1.537 + return _graph->notifier(Node());
1.538 }
1.539
1.540 - template <typename _Value>
1.541 - class NodeMap : public Graph::template NodeMap<_Value> {
1.542 + template <typename V>
1.543 + class NodeMap : public GR::template NodeMap<V> {
1.544 + typedef typename GR::template NodeMap<V> Parent;
1.545 +
1.546 public:
1.547
1.548 - typedef typename _Graph::template NodeMap<_Value> Parent;
1.549 + explicit NodeMap(const ListEdgeSetBase<GR>& arcset)
1.550 + : Parent(*arcset._graph) {}
1.551
1.552 - explicit NodeMap(const ListEdgeSetBase<Graph>& arcset)
1.553 - : Parent(*arcset.graph) {}
1.554 -
1.555 - NodeMap(const ListEdgeSetBase<Graph>& arcset, const _Value& value)
1.556 - : Parent(*arcset.graph, value) {}
1.557 + NodeMap(const ListEdgeSetBase<GR>& arcset, const V& value)
1.558 + : Parent(*arcset._graph, value) {}
1.559
1.560 NodeMap& operator=(const NodeMap& cmap) {
1.561 return operator=<NodeMap>(cmap);
1.562 @@ -660,7 +666,7 @@
1.563
1.564 };
1.565
1.566 - /// \ingroup semi_adaptors
1.567 + /// \ingroup graphs
1.568 ///
1.569 /// \brief Graph using a node set of another digraph or graph and an
1.570 /// own edge set.
1.571 @@ -679,27 +685,23 @@
1.572 /// be removed from the underlying graph, in this case all edges
1.573 /// incident to the given node is erased from the arc set.
1.574 ///
1.575 - /// \param _Graph The type of the graph which shares its node set
1.576 + /// \param GR The type of the graph which shares its node set
1.577 /// with this class. Its interface must conform to the
1.578 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.579 /// concept.
1.580 ///
1.581 - /// This class is fully conform to the \ref concepts::Graph "Graph"
1.582 + /// This class fully conforms to the \ref concepts::Graph "Graph"
1.583 /// concept.
1.584 - template <typename _Graph>
1.585 - class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<_Graph> > {
1.586 + template <typename GR>
1.587 + class ListEdgeSet : public EdgeSetExtender<ListEdgeSetBase<GR> > {
1.588 + typedef EdgeSetExtender<ListEdgeSetBase<GR> > Parent;
1.589
1.590 public:
1.591
1.592 - typedef EdgeSetExtender<ListEdgeSetBase<_Graph> > Parent;
1.593 -
1.594 typedef typename Parent::Node Node;
1.595 typedef typename Parent::Arc Arc;
1.596 typedef typename Parent::Edge Edge;
1.597
1.598 - typedef _Graph Graph;
1.599 -
1.600 -
1.601 typedef typename Parent::NodesImplBase NodesImplBase;
1.602
1.603 void eraseNode(const Node& node) {
1.604 @@ -717,10 +719,10 @@
1.605 }
1.606
1.607 class NodesImpl : public NodesImplBase {
1.608 - public:
1.609 typedef NodesImplBase Parent;
1.610
1.611 - NodesImpl(const Graph& graph, ListEdgeSet& arcset)
1.612 + public:
1.613 + NodesImpl(const GR& graph, ListEdgeSet& arcset)
1.614 : Parent(graph), _arcset(arcset) {}
1.615
1.616 virtual ~NodesImpl() {}
1.617 @@ -746,22 +748,22 @@
1.618 ListEdgeSet& _arcset;
1.619 };
1.620
1.621 - NodesImpl nodes;
1.622 + NodesImpl _nodes;
1.623
1.624 public:
1.625
1.626 /// \brief Constructor of the EdgeSet.
1.627 ///
1.628 /// Constructor of the EdgeSet.
1.629 - ListEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.630 - Parent::initalize(graph, nodes);
1.631 + ListEdgeSet(const GR& graph) : _nodes(graph, *this) {
1.632 + Parent::initalize(graph, _nodes);
1.633 }
1.634
1.635 /// \brief Add a new edge to the graph.
1.636 ///
1.637 /// Add a new edge to the graph with node \c u
1.638 /// and node \c v endpoints.
1.639 - /// \return the new edge.
1.640 + /// \return The new edge.
1.641 Edge addEdge(const Node& u, const Node& v) {
1.642 return Parent::addEdge(u, v);
1.643 }
1.644 @@ -775,13 +777,12 @@
1.645
1.646 };
1.647
1.648 - template <typename _Graph>
1.649 + template <typename GR>
1.650 class SmartArcSetBase {
1.651 public:
1.652
1.653 - typedef _Graph Graph;
1.654 - typedef typename Graph::Node Node;
1.655 - typedef typename Graph::NodeIt NodeIt;
1.656 + typedef typename GR::Node Node;
1.657 + typedef typename GR::NodeIt NodeIt;
1.658
1.659 protected:
1.660
1.661 @@ -790,10 +791,10 @@
1.662 NodeT() : first_out(-1), first_in(-1) {}
1.663 };
1.664
1.665 - typedef typename ItemSetTraits<Graph, Node>::
1.666 + typedef typename ItemSetTraits<GR, Node>::
1.667 template Map<NodeT>::Type NodesImplBase;
1.668
1.669 - NodesImplBase* nodes;
1.670 + NodesImplBase* _nodes;
1.671
1.672 struct ArcT {
1.673 Node source, target;
1.674 @@ -803,17 +804,17 @@
1.675
1.676 std::vector<ArcT> arcs;
1.677
1.678 - const Graph* graph;
1.679 + const GR* _graph;
1.680
1.681 - void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.682 - graph = &_graph;
1.683 - nodes = &_nodes;
1.684 + void initalize(const GR& graph, NodesImplBase& nodes) {
1.685 + _graph = &graph;
1.686 + _nodes = &nodes;
1.687 }
1.688
1.689 public:
1.690
1.691 class Arc {
1.692 - friend class SmartArcSetBase<Graph>;
1.693 + friend class SmartArcSetBase<GR>;
1.694 protected:
1.695 Arc(int _id) : id(_id) {}
1.696 int id;
1.697 @@ -827,13 +828,19 @@
1.698
1.699 SmartArcSetBase() {}
1.700
1.701 + Node addNode() {
1.702 + LEMON_ASSERT(false,
1.703 + "This graph structure does not support node insertion");
1.704 + return INVALID; // avoid warning
1.705 + }
1.706 +
1.707 Arc addArc(const Node& u, const Node& v) {
1.708 int n = arcs.size();
1.709 arcs.push_back(ArcT());
1.710 - arcs[n].next_in = (*nodes)[v].first_in;
1.711 - (*nodes)[v].first_in = n;
1.712 - arcs[n].next_out = (*nodes)[u].first_out;
1.713 - (*nodes)[u].first_out = n;
1.714 + arcs[n].next_in = (*_nodes)[v].first_in;
1.715 + (*_nodes)[v].first_in = n;
1.716 + arcs[n].next_out = (*_nodes)[u].first_out;
1.717 + (*_nodes)[u].first_out = n;
1.718 arcs[n].source = u;
1.719 arcs[n].target = v;
1.720 return Arc(n);
1.721 @@ -842,30 +849,30 @@
1.722 void clear() {
1.723 Node node;
1.724 for (first(node); node != INVALID; next(node)) {
1.725 - (*nodes)[node].first_in = -1;
1.726 - (*nodes)[node].first_out = -1;
1.727 + (*_nodes)[node].first_in = -1;
1.728 + (*_nodes)[node].first_out = -1;
1.729 }
1.730 arcs.clear();
1.731 }
1.732
1.733 void first(Node& node) const {
1.734 - graph->first(node);
1.735 + _graph->first(node);
1.736 }
1.737
1.738 void next(Node& node) const {
1.739 - graph->next(node);
1.740 + _graph->next(node);
1.741 }
1.742
1.743 void first(Arc& arc) const {
1.744 arc.id = arcs.size() - 1;
1.745 }
1.746
1.747 - void next(Arc& arc) const {
1.748 + static void next(Arc& arc) {
1.749 --arc.id;
1.750 }
1.751
1.752 void firstOut(Arc& arc, const Node& node) const {
1.753 - arc.id = (*nodes)[node].first_out;
1.754 + arc.id = (*_nodes)[node].first_out;
1.755 }
1.756
1.757 void nextOut(Arc& arc) const {
1.758 @@ -873,42 +880,42 @@
1.759 }
1.760
1.761 void firstIn(Arc& arc, const Node& node) const {
1.762 - arc.id = (*nodes)[node].first_in;
1.763 + arc.id = (*_nodes)[node].first_in;
1.764 }
1.765
1.766 void nextIn(Arc& arc) const {
1.767 arc.id = arcs[arc.id].next_in;
1.768 }
1.769
1.770 - int id(const Node& node) const { return graph->id(node); }
1.771 + int id(const Node& node) const { return _graph->id(node); }
1.772 int id(const Arc& arc) const { return arc.id; }
1.773
1.774 - Node nodeFromId(int ix) const { return graph->nodeFromId(ix); }
1.775 + Node nodeFromId(int ix) const { return _graph->nodeFromId(ix); }
1.776 Arc arcFromId(int ix) const { return Arc(ix); }
1.777
1.778 - int maxNodeId() const { return graph->maxNodeId(); };
1.779 + int maxNodeId() const { return _graph->maxNodeId(); };
1.780 int maxArcId() const { return arcs.size() - 1; }
1.781
1.782 Node source(const Arc& arc) const { return arcs[arc.id].source;}
1.783 Node target(const Arc& arc) const { return arcs[arc.id].target;}
1.784
1.785 - typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.786 + typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
1.787
1.788 NodeNotifier& notifier(Node) const {
1.789 - return graph->notifier(Node());
1.790 + return _graph->notifier(Node());
1.791 }
1.792
1.793 - template <typename _Value>
1.794 - class NodeMap : public Graph::template NodeMap<_Value> {
1.795 + template <typename V>
1.796 + class NodeMap : public GR::template NodeMap<V> {
1.797 + typedef typename GR::template NodeMap<V> Parent;
1.798 +
1.799 public:
1.800
1.801 - typedef typename _Graph::template NodeMap<_Value> Parent;
1.802 + explicit NodeMap(const SmartArcSetBase<GR>& arcset)
1.803 + : Parent(*arcset._graph) { }
1.804
1.805 - explicit NodeMap(const SmartArcSetBase<Graph>& arcset)
1.806 - : Parent(*arcset.graph) { }
1.807 -
1.808 - NodeMap(const SmartArcSetBase<Graph>& arcset, const _Value& value)
1.809 - : Parent(*arcset.graph, value) { }
1.810 + NodeMap(const SmartArcSetBase<GR>& arcset, const V& value)
1.811 + : Parent(*arcset._graph, value) { }
1.812
1.813 NodeMap& operator=(const NodeMap& cmap) {
1.814 return operator=<NodeMap>(cmap);
1.815 @@ -924,7 +931,7 @@
1.816 };
1.817
1.818
1.819 - /// \ingroup semi_adaptors
1.820 + /// \ingroup graphs
1.821 ///
1.822 /// \brief Digraph using a node set of another digraph or graph and
1.823 /// an own arc set.
1.824 @@ -937,7 +944,7 @@
1.825 /// class. The node handling functions (id handling, observing, and
1.826 /// iterators) works equivalently as in the original graph.
1.827 ///
1.828 - /// \param _Graph The type of the graph which shares its node set with
1.829 + /// \param GR The type of the graph which shares its node set with
1.830 /// this class. Its interface must conform to the
1.831 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.832 /// concept.
1.833 @@ -952,20 +959,17 @@
1.834 /// the arc set is invalidated, and it cannot be used anymore. The
1.835 /// validity can be checked with the \c valid() member function.
1.836 ///
1.837 - /// This class is fully conform to the \ref concepts::Digraph
1.838 + /// This class fully conforms to the \ref concepts::Digraph
1.839 /// "Digraph" concept.
1.840 - template <typename _Graph>
1.841 - class SmartArcSet : public ArcSetExtender<SmartArcSetBase<_Graph> > {
1.842 + template <typename GR>
1.843 + class SmartArcSet : public ArcSetExtender<SmartArcSetBase<GR> > {
1.844 + typedef ArcSetExtender<SmartArcSetBase<GR> > Parent;
1.845
1.846 public:
1.847
1.848 - typedef ArcSetExtender<SmartArcSetBase<_Graph> > Parent;
1.849 -
1.850 typedef typename Parent::Node Node;
1.851 typedef typename Parent::Arc Arc;
1.852
1.853 - typedef _Graph Graph;
1.854 -
1.855 protected:
1.856
1.857 typedef typename Parent::NodesImplBase NodesImplBase;
1.858 @@ -983,10 +987,10 @@
1.859 }
1.860
1.861 class NodesImpl : public NodesImplBase {
1.862 - public:
1.863 typedef NodesImplBase Parent;
1.864
1.865 - NodesImpl(const Graph& graph, SmartArcSet& arcset)
1.866 + public:
1.867 + NodesImpl(const GR& graph, SmartArcSet& arcset)
1.868 : Parent(graph), _arcset(arcset) {}
1.869
1.870 virtual ~NodesImpl() {}
1.871 @@ -1026,22 +1030,22 @@
1.872 SmartArcSet& _arcset;
1.873 };
1.874
1.875 - NodesImpl nodes;
1.876 + NodesImpl _nodes;
1.877
1.878 public:
1.879
1.880 /// \brief Constructor of the ArcSet.
1.881 ///
1.882 /// Constructor of the ArcSet.
1.883 - SmartArcSet(const Graph& graph) : nodes(graph, *this) {
1.884 - Parent::initalize(graph, nodes);
1.885 + SmartArcSet(const GR& graph) : _nodes(graph, *this) {
1.886 + Parent::initalize(graph, _nodes);
1.887 }
1.888
1.889 /// \brief Add a new arc to the digraph.
1.890 ///
1.891 /// Add a new arc to the digraph with source node \c s
1.892 /// and target node \c t.
1.893 - /// \return the new arc.
1.894 + /// \return The new arc.
1.895 Arc addArc(const Node& s, const Node& t) {
1.896 return Parent::addArc(s, t);
1.897 }
1.898 @@ -1052,19 +1056,18 @@
1.899 /// invalidated. It occurs when a node in the underlying graph is
1.900 /// erased and it is not isolated in the ArcSet.
1.901 bool valid() const {
1.902 - return nodes.attached();
1.903 + return _nodes.attached();
1.904 }
1.905
1.906 };
1.907
1.908
1.909 - template <typename _Graph>
1.910 + template <typename GR>
1.911 class SmartEdgeSetBase {
1.912 public:
1.913
1.914 - typedef _Graph Graph;
1.915 - typedef typename Graph::Node Node;
1.916 - typedef typename Graph::NodeIt NodeIt;
1.917 + typedef typename GR::Node Node;
1.918 + typedef typename GR::NodeIt NodeIt;
1.919
1.920 protected:
1.921
1.922 @@ -1073,10 +1076,10 @@
1.923 NodeT() : first_out(-1) {}
1.924 };
1.925
1.926 - typedef typename ItemSetTraits<Graph, Node>::
1.927 + typedef typename ItemSetTraits<GR, Node>::
1.928 template Map<NodeT>::Type NodesImplBase;
1.929
1.930 - NodesImplBase* nodes;
1.931 + NodesImplBase* _nodes;
1.932
1.933 struct ArcT {
1.934 Node target;
1.935 @@ -1086,11 +1089,11 @@
1.936
1.937 std::vector<ArcT> arcs;
1.938
1.939 - const Graph* graph;
1.940 + const GR* _graph;
1.941
1.942 - void initalize(const Graph& _graph, NodesImplBase& _nodes) {
1.943 - graph = &_graph;
1.944 - nodes = &_nodes;
1.945 + void initalize(const GR& graph, NodesImplBase& nodes) {
1.946 + _graph = &graph;
1.947 + _nodes = &nodes;
1.948 }
1.949
1.950 public:
1.951 @@ -1127,6 +1130,12 @@
1.952
1.953 SmartEdgeSetBase() {}
1.954
1.955 + Node addNode() {
1.956 + LEMON_ASSERT(false,
1.957 + "This graph structure does not support node insertion");
1.958 + return INVALID; // avoid warning
1.959 + }
1.960 +
1.961 Edge addEdge(const Node& u, const Node& v) {
1.962 int n = arcs.size();
1.963 arcs.push_back(ArcT());
1.964 @@ -1135,11 +1144,11 @@
1.965 arcs[n].target = u;
1.966 arcs[n | 1].target = v;
1.967
1.968 - arcs[n].next_out = (*nodes)[v].first_out;
1.969 - (*nodes)[v].first_out = n;
1.970 + arcs[n].next_out = (*_nodes)[v].first_out;
1.971 + (*_nodes)[v].first_out = n;
1.972
1.973 - arcs[n | 1].next_out = (*nodes)[u].first_out;
1.974 - (*nodes)[u].first_out = (n | 1);
1.975 + arcs[n | 1].next_out = (*_nodes)[u].first_out;
1.976 + (*_nodes)[u].first_out = (n | 1);
1.977
1.978 return Edge(n / 2);
1.979 }
1.980 @@ -1147,24 +1156,24 @@
1.981 void clear() {
1.982 Node node;
1.983 for (first(node); node != INVALID; next(node)) {
1.984 - (*nodes)[node].first_out = -1;
1.985 + (*_nodes)[node].first_out = -1;
1.986 }
1.987 arcs.clear();
1.988 }
1.989
1.990 void first(Node& node) const {
1.991 - graph->first(node);
1.992 + _graph->first(node);
1.993 }
1.994
1.995 void next(Node& node) const {
1.996 - graph->next(node);
1.997 + _graph->next(node);
1.998 }
1.999
1.1000 void first(Arc& arc) const {
1.1001 arc.id = arcs.size() - 1;
1.1002 }
1.1003
1.1004 - void next(Arc& arc) const {
1.1005 + static void next(Arc& arc) {
1.1006 --arc.id;
1.1007 }
1.1008
1.1009 @@ -1172,12 +1181,12 @@
1.1010 arc.id = arcs.size() / 2 - 1;
1.1011 }
1.1012
1.1013 - void next(Edge& arc) const {
1.1014 + static void next(Edge& arc) {
1.1015 --arc.id;
1.1016 }
1.1017
1.1018 void firstOut(Arc& arc, const Node& node) const {
1.1019 - arc.id = (*nodes)[node].first_out;
1.1020 + arc.id = (*_nodes)[node].first_out;
1.1021 }
1.1022
1.1023 void nextOut(Arc& arc) const {
1.1024 @@ -1185,7 +1194,7 @@
1.1025 }
1.1026
1.1027 void firstIn(Arc& arc, const Node& node) const {
1.1028 - arc.id = (((*nodes)[node].first_out) ^ 1);
1.1029 + arc.id = (((*_nodes)[node].first_out) ^ 1);
1.1030 if (arc.id == -2) arc.id = -1;
1.1031 }
1.1032
1.1033 @@ -1195,7 +1204,7 @@
1.1034 }
1.1035
1.1036 void firstInc(Edge &arc, bool& dir, const Node& node) const {
1.1037 - int de = (*nodes)[node].first_out;
1.1038 + int de = (*_nodes)[node].first_out;
1.1039 if (de != -1 ) {
1.1040 arc.id = de / 2;
1.1041 dir = ((de & 1) == 1);
1.1042 @@ -1223,15 +1232,15 @@
1.1043 return Arc(edge.id * 2 + (dir ? 1 : 0));
1.1044 }
1.1045
1.1046 - int id(Node node) const { return graph->id(node); }
1.1047 + int id(Node node) const { return _graph->id(node); }
1.1048 static int id(Arc arc) { return arc.id; }
1.1049 static int id(Edge arc) { return arc.id; }
1.1050
1.1051 - Node nodeFromId(int id) const { return graph->nodeFromId(id); }
1.1052 + Node nodeFromId(int id) const { return _graph->nodeFromId(id); }
1.1053 static Arc arcFromId(int id) { return Arc(id); }
1.1054 static Edge edgeFromId(int id) { return Edge(id);}
1.1055
1.1056 - int maxNodeId() const { return graph->maxNodeId(); };
1.1057 + int maxNodeId() const { return _graph->maxNodeId(); };
1.1058 int maxArcId() const { return arcs.size() - 1; }
1.1059 int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.1060
1.1061 @@ -1241,23 +1250,23 @@
1.1062 Node u(Edge e) const { return arcs[2 * e.id].target; }
1.1063 Node v(Edge e) const { return arcs[2 * e.id + 1].target; }
1.1064
1.1065 - typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;
1.1066 + typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
1.1067
1.1068 NodeNotifier& notifier(Node) const {
1.1069 - return graph->notifier(Node());
1.1070 + return _graph->notifier(Node());
1.1071 }
1.1072
1.1073 - template <typename _Value>
1.1074 - class NodeMap : public Graph::template NodeMap<_Value> {
1.1075 + template <typename V>
1.1076 + class NodeMap : public GR::template NodeMap<V> {
1.1077 + typedef typename GR::template NodeMap<V> Parent;
1.1078 +
1.1079 public:
1.1080
1.1081 - typedef typename _Graph::template NodeMap<_Value> Parent;
1.1082 + explicit NodeMap(const SmartEdgeSetBase<GR>& arcset)
1.1083 + : Parent(*arcset._graph) { }
1.1084
1.1085 - explicit NodeMap(const SmartEdgeSetBase<Graph>& arcset)
1.1086 - : Parent(*arcset.graph) { }
1.1087 -
1.1088 - NodeMap(const SmartEdgeSetBase<Graph>& arcset, const _Value& value)
1.1089 - : Parent(*arcset.graph, value) { }
1.1090 + NodeMap(const SmartEdgeSetBase<GR>& arcset, const V& value)
1.1091 + : Parent(*arcset._graph, value) { }
1.1092
1.1093 NodeMap& operator=(const NodeMap& cmap) {
1.1094 return operator=<NodeMap>(cmap);
1.1095 @@ -1272,7 +1281,7 @@
1.1096
1.1097 };
1.1098
1.1099 - /// \ingroup semi_adaptors
1.1100 + /// \ingroup graphs
1.1101 ///
1.1102 /// \brief Graph using a node set of another digraph or graph and an
1.1103 /// own edge set.
1.1104 @@ -1285,7 +1294,7 @@
1.1105 /// node handling functions (id handling, observing, and iterators)
1.1106 /// works equivalently as in the original graph.
1.1107 ///
1.1108 - /// \param _Graph The type of the graph which shares its node set
1.1109 + /// \param GR The type of the graph which shares its node set
1.1110 /// with this class. Its interface must conform to the
1.1111 /// \ref concepts::Digraph "Digraph" or \ref concepts::Graph "Graph"
1.1112 /// concept.
1.1113 @@ -1300,21 +1309,18 @@
1.1114 /// is invalidated, and it cannot be used anymore. The validity can
1.1115 /// be checked with the \c valid() member function.
1.1116 ///
1.1117 - /// This class is fully conform to the \ref concepts::Graph
1.1118 + /// This class fully conforms to the \ref concepts::Graph
1.1119 /// "Graph" concept.
1.1120 - template <typename _Graph>
1.1121 - class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<_Graph> > {
1.1122 + template <typename GR>
1.1123 + class SmartEdgeSet : public EdgeSetExtender<SmartEdgeSetBase<GR> > {
1.1124 + typedef EdgeSetExtender<SmartEdgeSetBase<GR> > Parent;
1.1125
1.1126 public:
1.1127
1.1128 - typedef EdgeSetExtender<SmartEdgeSetBase<_Graph> > Parent;
1.1129 -
1.1130 typedef typename Parent::Node Node;
1.1131 typedef typename Parent::Arc Arc;
1.1132 typedef typename Parent::Edge Edge;
1.1133
1.1134 - typedef _Graph Graph;
1.1135 -
1.1136 protected:
1.1137
1.1138 typedef typename Parent::NodesImplBase NodesImplBase;
1.1139 @@ -1331,10 +1337,10 @@
1.1140 }
1.1141
1.1142 class NodesImpl : public NodesImplBase {
1.1143 - public:
1.1144 typedef NodesImplBase Parent;
1.1145
1.1146 - NodesImpl(const Graph& graph, SmartEdgeSet& arcset)
1.1147 + public:
1.1148 + NodesImpl(const GR& graph, SmartEdgeSet& arcset)
1.1149 : Parent(graph), _arcset(arcset) {}
1.1150
1.1151 virtual ~NodesImpl() {}
1.1152 @@ -1374,22 +1380,22 @@
1.1153 SmartEdgeSet& _arcset;
1.1154 };
1.1155
1.1156 - NodesImpl nodes;
1.1157 + NodesImpl _nodes;
1.1158
1.1159 public:
1.1160
1.1161 /// \brief Constructor of the EdgeSet.
1.1162 ///
1.1163 /// Constructor of the EdgeSet.
1.1164 - SmartEdgeSet(const Graph& graph) : nodes(graph, *this) {
1.1165 - Parent::initalize(graph, nodes);
1.1166 + SmartEdgeSet(const GR& graph) : _nodes(graph, *this) {
1.1167 + Parent::initalize(graph, _nodes);
1.1168 }
1.1169
1.1170 /// \brief Add a new edge to the graph.
1.1171 ///
1.1172 /// Add a new edge to the graph with node \c u
1.1173 /// and node \c v endpoints.
1.1174 - /// \return the new edge.
1.1175 + /// \return The new edge.
1.1176 Edge addEdge(const Node& u, const Node& v) {
1.1177 return Parent::addEdge(u, v);
1.1178 }
1.1179 @@ -1400,7 +1406,7 @@
1.1180 /// invalidated. It occurs when a node in the underlying graph is
1.1181 /// erased and it is not isolated in the EdgeSet.
1.1182 bool valid() const {
1.1183 - return nodes.attached();
1.1184 + return _nodes.attached();
1.1185 }
1.1186
1.1187 };