1.1 --- a/lemon/smart_graph.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/smart_graph.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -45,20 +45,20 @@
1.13 class SmartDigraphBase {
1.14 protected:
1.15
1.16 - struct NodeT
1.17 + struct NodeT
1.18 {
1.19 - int first_in, first_out;
1.20 + int first_in, first_out;
1.21 NodeT() {}
1.22 };
1.23 - struct ArcT
1.24 + struct ArcT
1.25 {
1.26 - int target, source, next_in, next_out;
1.27 - ArcT() {}
1.28 + int target, source, next_in, next_out;
1.29 + ArcT() {}
1.30 };
1.31
1.32 std::vector<NodeT> nodes;
1.33 std::vector<ArcT> arcs;
1.34 -
1.35 +
1.36 public:
1.37
1.38 typedef SmartDigraphBase Graph;
1.39 @@ -69,9 +69,9 @@
1.40 public:
1.41
1.42 SmartDigraphBase() : nodes(), arcs() { }
1.43 - SmartDigraphBase(const SmartDigraphBase &_g)
1.44 + SmartDigraphBase(const SmartDigraphBase &_g)
1.45 : nodes(_g.nodes), arcs(_g.arcs) { }
1.46 -
1.47 +
1.48 typedef True NodeNumTag;
1.49 typedef True EdgeNumTag;
1.50
1.51 @@ -82,17 +82,17 @@
1.52 int maxArcId() const { return arcs.size()-1; }
1.53
1.54 Node addNode() {
1.55 - int n = nodes.size();
1.56 + int n = nodes.size();
1.57 nodes.push_back(NodeT());
1.58 nodes[n].first_in = -1;
1.59 nodes[n].first_out = -1;
1.60 return Node(n);
1.61 }
1.62 -
1.63 +
1.64 Arc addArc(Node u, Node v) {
1.65 - int n = arcs.size();
1.66 + int n = arcs.size();
1.67 arcs.push_back(ArcT());
1.68 - arcs[n].source = u._id;
1.69 + arcs[n].source = u._id;
1.70 arcs[n].target = v._id;
1.71 arcs[n].next_out = nodes[u._id].first_out;
1.72 arcs[n].next_in = nodes[v._id].first_in;
1.73 @@ -115,11 +115,11 @@
1.74 static Node nodeFromId(int id) { return Node(id);}
1.75 static Arc arcFromId(int id) { return Arc(id);}
1.76
1.77 - bool valid(Node n) const {
1.78 - return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.79 + bool valid(Node n) const {
1.80 + return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.81 }
1.82 - bool valid(Arc a) const {
1.83 - return a._id >= 0 && a._id < static_cast<int>(arcs.size());
1.84 + bool valid(Arc a) const {
1.85 + return a._id >= 0 && a._id < static_cast<int>(arcs.size());
1.86 }
1.87
1.88 class Node {
1.89 @@ -136,7 +136,7 @@
1.90 bool operator!=(const Node i) const {return _id != i._id;}
1.91 bool operator<(const Node i) const {return _id < i._id;}
1.92 };
1.93 -
1.94 +
1.95
1.96 class Arc {
1.97 friend class SmartDigraphBase;
1.98 @@ -180,7 +180,7 @@
1.99 void firstIn(Arc& arc, const Node& node) const {
1.100 arc._id = nodes[node._id].first_in;
1.101 }
1.102 -
1.103 +
1.104 void nextIn(Arc& arc) const {
1.105 arc._id = arcs[arc._id].next_in;
1.106 }
1.107 @@ -222,26 +222,26 @@
1.108 void operator=(const SmartDigraph &) {}
1.109
1.110 public:
1.111 -
1.112 +
1.113 /// Constructor
1.114 -
1.115 +
1.116 /// Constructor.
1.117 ///
1.118 SmartDigraph() {};
1.119 -
1.120 +
1.121 ///Add a new node to the digraph.
1.122 -
1.123 +
1.124 /// \return the new node.
1.125 ///
1.126 Node addNode() { return Parent::addNode(); }
1.127 -
1.128 +
1.129 ///Add a new arc to the digraph.
1.130 -
1.131 +
1.132 ///Add a new arc to the digraph with source node \c s
1.133 ///and target node \c t.
1.134 ///\return the new arc.
1.135 - Arc addArc(const Node& s, const Node& t) {
1.136 - return Parent::addArc(s, t);
1.137 + Arc addArc(const Node& s, const Node& t) {
1.138 + return Parent::addArc(s, t);
1.139 }
1.140
1.141 /// \brief Using this it is possible to avoid the superfluous memory
1.142 @@ -269,7 +269,7 @@
1.143 /// \brief Node validity check
1.144 ///
1.145 /// This function gives back true if the given node is valid,
1.146 - /// ie. it is a real node of the graph.
1.147 + /// ie. it is a real node of the graph.
1.148 ///
1.149 /// \warning A removed node (using Snapshot) could become valid again
1.150 /// when new nodes are added to the graph.
1.151 @@ -278,14 +278,14 @@
1.152 /// \brief Arc validity check
1.153 ///
1.154 /// This function gives back true if the given arc is valid,
1.155 - /// ie. it is a real arc of the graph.
1.156 + /// ie. it is a real arc of the graph.
1.157 ///
1.158 /// \warning A removed arc (using Snapshot) could become valid again
1.159 /// when new arcs are added to the graph.
1.160 bool valid(Arc a) const { return Parent::valid(a); }
1.161
1.162 ///Clear the digraph.
1.163 -
1.164 +
1.165 ///Erase all the nodes and arcs from the digraph.
1.166 ///
1.167 void clear() {
1.168 @@ -293,7 +293,7 @@
1.169 }
1.170
1.171 ///Split a node.
1.172 -
1.173 +
1.174 ///This function splits a node. First a new node is added to the digraph,
1.175 ///then the source of each outgoing arc of \c n is moved to this new node.
1.176 ///If \c connect is \c true (this is the default value), then a new arc
1.177 @@ -318,7 +318,7 @@
1.178 }
1.179
1.180 public:
1.181 -
1.182 +
1.183 class Snapshot;
1.184
1.185 protected:
1.186 @@ -327,17 +327,17 @@
1.187 {
1.188 while(s.arc_num<arcs.size()) {
1.189 Arc arc = arcFromId(arcs.size()-1);
1.190 - Parent::notifier(Arc()).erase(arc);
1.191 - nodes[arcs.back().source].first_out=arcs.back().next_out;
1.192 - nodes[arcs.back().target].first_in=arcs.back().next_in;
1.193 - arcs.pop_back();
1.194 + Parent::notifier(Arc()).erase(arc);
1.195 + nodes[arcs.back().source].first_out=arcs.back().next_out;
1.196 + nodes[arcs.back().target].first_in=arcs.back().next_in;
1.197 + arcs.pop_back();
1.198 }
1.199 while(s.node_num<nodes.size()) {
1.200 Node node = nodeFromId(nodes.size()-1);
1.201 - Parent::notifier(Node()).erase(node);
1.202 - nodes.pop_back();
1.203 + Parent::notifier(Node()).erase(node);
1.204 + nodes.pop_back();
1.205 }
1.206 - }
1.207 + }
1.208
1.209 public:
1.210
1.211 @@ -355,7 +355,7 @@
1.212 ///either broken program, invalid state of the digraph, valid but
1.213 ///not the restored digraph or no change. Because the runtime performance
1.214 ///the validity of the snapshot is not stored.
1.215 - class Snapshot
1.216 + class Snapshot
1.217 {
1.218 SmartDigraph *_graph;
1.219 protected:
1.220 @@ -364,18 +364,18 @@
1.221 unsigned int arc_num;
1.222 public:
1.223 ///Default constructor.
1.224 -
1.225 +
1.226 ///Default constructor.
1.227 ///To actually make a snapshot you must call save().
1.228 ///
1.229 Snapshot() : _graph(0) {}
1.230 ///Constructor that immediately makes a snapshot
1.231 -
1.232 +
1.233 ///This constructor immediately makes a snapshot of the digraph.
1.234 ///\param _g The digraph we make a snapshot of.
1.235 Snapshot(SmartDigraph &graph) : _graph(&graph) {
1.236 - node_num=_graph->nodes.size();
1.237 - arc_num=_graph->arcs.size();
1.238 + node_num=_graph->nodes.size();
1.239 + arc_num=_graph->arcs.size();
1.240 }
1.241
1.242 ///Make a snapshot.
1.243 @@ -385,15 +385,15 @@
1.244 ///This function can be called more than once. In case of a repeated
1.245 ///call, the previous snapshot gets lost.
1.246 ///\param _g The digraph we make the snapshot of.
1.247 - void save(SmartDigraph &graph)
1.248 + void save(SmartDigraph &graph)
1.249 {
1.250 - _graph=&graph;
1.251 - node_num=_graph->nodes.size();
1.252 - arc_num=_graph->arcs.size();
1.253 + _graph=&graph;
1.254 + node_num=_graph->nodes.size();
1.255 + arc_num=_graph->arcs.size();
1.256 }
1.257
1.258 ///Undo the changes until a snapshot.
1.259 -
1.260 +
1.261 ///Undo the changes until a snapshot created by save().
1.262 ///
1.263 ///\note After you restored a state, you cannot restore
1.264 @@ -401,7 +401,7 @@
1.265 ///by restore().
1.266 void restore()
1.267 {
1.268 - _graph->restoreSnapshot(*this);
1.269 + _graph->restoreSnapshot(*this);
1.270 }
1.271 };
1.272 };
1.273 @@ -414,7 +414,7 @@
1.274 struct NodeT {
1.275 int first_out;
1.276 };
1.277 -
1.278 +
1.279 struct ArcT {
1.280 int target;
1.281 int next_out;
1.282 @@ -424,15 +424,15 @@
1.283 std::vector<ArcT> arcs;
1.284
1.285 int first_free_arc;
1.286 -
1.287 +
1.288 public:
1.289 -
1.290 +
1.291 typedef SmartGraphBase Digraph;
1.292
1.293 class Node;
1.294 class Arc;
1.295 class Edge;
1.296 -
1.297 +
1.298 class Node {
1.299 friend class SmartGraphBase;
1.300 protected:
1.301 @@ -485,8 +485,8 @@
1.302 SmartGraphBase()
1.303 : nodes(), arcs() {}
1.304
1.305 -
1.306 - int maxNodeId() const { return nodes.size()-1; }
1.307 +
1.308 + int maxNodeId() const { return nodes.size()-1; }
1.309 int maxEdgeId() const { return arcs.size() / 2 - 1; }
1.310 int maxArcId() const { return arcs.size()-1; }
1.311
1.312 @@ -504,7 +504,7 @@
1.313 return Arc(e._id * 2 + (d ? 1 : 0));
1.314 }
1.315
1.316 - void first(Node& node) const {
1.317 + void first(Node& node) const {
1.318 node._id = nodes.size() - 1;
1.319 }
1.320
1.321 @@ -512,7 +512,7 @@
1.322 --node._id;
1.323 }
1.324
1.325 - void first(Arc& arc) const {
1.326 + void first(Arc& arc) const {
1.327 arc._id = arcs.size() - 1;
1.328 }
1.329
1.330 @@ -520,7 +520,7 @@
1.331 --arc._id;
1.332 }
1.333
1.334 - void first(Edge& arc) const {
1.335 + void first(Edge& arc) const {
1.336 arc._id = arcs.size() / 2 - 1;
1.337 }
1.338
1.339 @@ -561,10 +561,10 @@
1.340 d = ((de & 1) == 1);
1.341 } else {
1.342 arc._id = -1;
1.343 - d = true;
1.344 + d = true;
1.345 }
1.346 }
1.347 -
1.348 +
1.349 static int id(Node v) { return v._id; }
1.350 static int id(Arc e) { return e._id; }
1.351 static int id(Edge e) { return e._id; }
1.352 @@ -573,41 +573,41 @@
1.353 static Arc arcFromId(int id) { return Arc(id);}
1.354 static Edge edgeFromId(int id) { return Edge(id);}
1.355
1.356 - bool valid(Node n) const {
1.357 - return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.358 + bool valid(Node n) const {
1.359 + return n._id >= 0 && n._id < static_cast<int>(nodes.size());
1.360 }
1.361 - bool valid(Arc a) const {
1.362 + bool valid(Arc a) const {
1.363 return a._id >= 0 && a._id < static_cast<int>(arcs.size());
1.364 }
1.365 - bool valid(Edge e) const {
1.366 - return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
1.367 + bool valid(Edge e) const {
1.368 + return e._id >= 0 && 2 * e._id < static_cast<int>(arcs.size());
1.369 }
1.370
1.371 - Node addNode() {
1.372 + Node addNode() {
1.373 int n = nodes.size();
1.374 nodes.push_back(NodeT());
1.375 nodes[n].first_out = -1;
1.376 -
1.377 +
1.378 return Node(n);
1.379 }
1.380 -
1.381 +
1.382 Edge addEdge(Node u, Node v) {
1.383 int n = arcs.size();
1.384 arcs.push_back(ArcT());
1.385 arcs.push_back(ArcT());
1.386 -
1.387 +
1.388 arcs[n].target = u._id;
1.389 arcs[n | 1].target = v._id;
1.390
1.391 arcs[n].next_out = nodes[v._id].first_out;
1.392 nodes[v._id].first_out = n;
1.393
1.394 - arcs[n | 1].next_out = nodes[u._id].first_out;
1.395 + arcs[n | 1].next_out = nodes[u._id].first_out;
1.396 nodes[u._id].first_out = (n | 1);
1.397
1.398 return Edge(n / 2);
1.399 }
1.400 -
1.401 +
1.402 void clear() {
1.403 arcs.clear();
1.404 nodes.clear();
1.405 @@ -625,7 +625,7 @@
1.406 /// It is also quite memory efficient, but at the price
1.407 /// that <b> it does support only limited (only stack-like)
1.408 /// node and arc deletions</b>.
1.409 - /// Except from this it conforms to
1.410 + /// Except from this it conforms to
1.411 /// the \ref concepts::Graph "Graph concept".
1.412 ///
1.413 /// It also has an
1.414 @@ -655,30 +655,30 @@
1.415 typedef ExtendedSmartGraphBase Parent;
1.416
1.417 /// Constructor
1.418 -
1.419 +
1.420 /// Constructor.
1.421 ///
1.422 SmartGraph() {}
1.423
1.424 ///Add a new node to the graph.
1.425 -
1.426 +
1.427 /// \return the new node.
1.428 ///
1.429 Node addNode() { return Parent::addNode(); }
1.430 -
1.431 +
1.432 ///Add a new edge to the graph.
1.433 -
1.434 +
1.435 ///Add a new edge to the graph with node \c s
1.436 ///and \c t.
1.437 ///\return the new edge.
1.438 - Edge addEdge(const Node& s, const Node& t) {
1.439 - return Parent::addEdge(s, t);
1.440 + Edge addEdge(const Node& s, const Node& t) {
1.441 + return Parent::addEdge(s, t);
1.442 }
1.443
1.444 /// \brief Node validity check
1.445 ///
1.446 /// This function gives back true if the given node is valid,
1.447 - /// ie. it is a real node of the graph.
1.448 + /// ie. it is a real node of the graph.
1.449 ///
1.450 /// \warning A removed node (using Snapshot) could become valid again
1.451 /// when new nodes are added to the graph.
1.452 @@ -687,7 +687,7 @@
1.453 /// \brief Arc validity check
1.454 ///
1.455 /// This function gives back true if the given arc is valid,
1.456 - /// ie. it is a real arc of the graph.
1.457 + /// ie. it is a real arc of the graph.
1.458 ///
1.459 /// \warning A removed arc (using Snapshot) could become valid again
1.460 /// when new edges are added to the graph.
1.461 @@ -696,14 +696,14 @@
1.462 /// \brief Edge validity check
1.463 ///
1.464 /// This function gives back true if the given edge is valid,
1.465 - /// ie. it is a real edge of the graph.
1.466 + /// ie. it is a real edge of the graph.
1.467 ///
1.468 /// \warning A removed edge (using Snapshot) could become valid again
1.469 /// when new edges are added to the graph.
1.470 bool valid(Edge e) const { return Parent::valid(e); }
1.471
1.472 ///Clear the graph.
1.473 -
1.474 +
1.475 ///Erase all the nodes and edges from the graph.
1.476 ///
1.477 void clear() {
1.478 @@ -711,7 +711,7 @@
1.479 }
1.480
1.481 public:
1.482 -
1.483 +
1.484 class Snapshot;
1.485
1.486 protected:
1.487 @@ -728,23 +728,23 @@
1.488 while(s.arc_num<arcs.size()) {
1.489 int n=arcs.size()-1;
1.490 Edge arc=edgeFromId(n/2);
1.491 - Parent::notifier(Edge()).erase(arc);
1.492 + Parent::notifier(Edge()).erase(arc);
1.493 std::vector<Arc> dir;
1.494 dir.push_back(arcFromId(n));
1.495 dir.push_back(arcFromId(n-1));
1.496 - Parent::notifier(Arc()).erase(dir);
1.497 - nodes[arcs[n].target].first_out=arcs[n].next_out;
1.498 - nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
1.499 - arcs.pop_back();
1.500 - arcs.pop_back();
1.501 + Parent::notifier(Arc()).erase(dir);
1.502 + nodes[arcs[n].target].first_out=arcs[n].next_out;
1.503 + nodes[arcs[n-1].target].first_out=arcs[n-1].next_out;
1.504 + arcs.pop_back();
1.505 + arcs.pop_back();
1.506 }
1.507 while(s.node_num<nodes.size()) {
1.508 int n=nodes.size()-1;
1.509 Node node = nodeFromId(n);
1.510 - Parent::notifier(Node()).erase(node);
1.511 - nodes.pop_back();
1.512 + Parent::notifier(Node()).erase(node);
1.513 + nodes.pop_back();
1.514 }
1.515 - }
1.516 + }
1.517
1.518 public:
1.519
1.520 @@ -763,7 +763,7 @@
1.521 ///either broken program, invalid state of the digraph, valid but
1.522 ///not the restored digraph or no change. Because the runtime performance
1.523 ///the validity of the snapshot is not stored.
1.524 - class Snapshot
1.525 + class Snapshot
1.526 {
1.527 SmartGraph *_graph;
1.528 protected:
1.529 @@ -772,13 +772,13 @@
1.530 unsigned int arc_num;
1.531 public:
1.532 ///Default constructor.
1.533 -
1.534 +
1.535 ///Default constructor.
1.536 ///To actually make a snapshot you must call save().
1.537 ///
1.538 Snapshot() : _graph(0) {}
1.539 ///Constructor that immediately makes a snapshot
1.540 -
1.541 +
1.542 ///This constructor immediately makes a snapshot of the digraph.
1.543 ///\param g The digraph we make a snapshot of.
1.544 Snapshot(SmartGraph &graph) {
1.545 @@ -792,13 +792,13 @@
1.546 ///This function can be called more than once. In case of a repeated
1.547 ///call, the previous snapshot gets lost.
1.548 ///\param g The digraph we make the snapshot of.
1.549 - void save(SmartGraph &graph)
1.550 + void save(SmartGraph &graph)
1.551 {
1.552 graph.saveSnapshot(*this);
1.553 }
1.554
1.555 ///Undo the changes until a snapshot.
1.556 -
1.557 +
1.558 ///Undo the changes until a snapshot created by save().
1.559 ///
1.560 ///\note After you restored a state, you cannot restore
1.561 @@ -810,7 +810,7 @@
1.562 }
1.563 };
1.564 };
1.565 -
1.566 +
1.567 } //namespace lemon
1.568
1.569