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