1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/static_graph.h Tue Dec 20 18:15:14 2011 +0100
1.3 @@ -0,0 +1,476 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_STATIC_GRAPH_H
1.23 +#define LEMON_STATIC_GRAPH_H
1.24 +
1.25 +///\ingroup graphs
1.26 +///\file
1.27 +///\brief StaticDigraph class.
1.28 +
1.29 +#include <lemon/core.h>
1.30 +#include <lemon/bits/graph_extender.h>
1.31 +
1.32 +namespace lemon {
1.33 +
1.34 + class StaticDigraphBase {
1.35 + public:
1.36 +
1.37 + StaticDigraphBase()
1.38 + : built(false), node_num(0), arc_num(0),
1.39 + node_first_out(NULL), node_first_in(NULL),
1.40 + arc_source(NULL), arc_target(NULL),
1.41 + arc_next_in(NULL), arc_next_out(NULL) {}
1.42 +
1.43 + ~StaticDigraphBase() {
1.44 + if (built) {
1.45 + delete[] node_first_out;
1.46 + delete[] node_first_in;
1.47 + delete[] arc_source;
1.48 + delete[] arc_target;
1.49 + delete[] arc_next_out;
1.50 + delete[] arc_next_in;
1.51 + }
1.52 + }
1.53 +
1.54 + class Node {
1.55 + friend class StaticDigraphBase;
1.56 + protected:
1.57 + int id;
1.58 + Node(int _id) : id(_id) {}
1.59 + public:
1.60 + Node() {}
1.61 + Node (Invalid) : id(-1) {}
1.62 + bool operator==(const Node& node) const { return id == node.id; }
1.63 + bool operator!=(const Node& node) const { return id != node.id; }
1.64 + bool operator<(const Node& node) const { return id < node.id; }
1.65 + };
1.66 +
1.67 + class Arc {
1.68 + friend class StaticDigraphBase;
1.69 + protected:
1.70 + int id;
1.71 + Arc(int _id) : id(_id) {}
1.72 + public:
1.73 + Arc() { }
1.74 + Arc (Invalid) : id(-1) {}
1.75 + bool operator==(const Arc& arc) const { return id == arc.id; }
1.76 + bool operator!=(const Arc& arc) const { return id != arc.id; }
1.77 + bool operator<(const Arc& arc) const { return id < arc.id; }
1.78 + };
1.79 +
1.80 + Node source(const Arc& e) const { return Node(arc_source[e.id]); }
1.81 + Node target(const Arc& e) const { return Node(arc_target[e.id]); }
1.82 +
1.83 + void first(Node& n) const { n.id = node_num - 1; }
1.84 + static void next(Node& n) { --n.id; }
1.85 +
1.86 + void first(Arc& e) const { e.id = arc_num - 1; }
1.87 + static void next(Arc& e) { --e.id; }
1.88 +
1.89 + void firstOut(Arc& e, const Node& n) const {
1.90 + e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
1.91 + node_first_out[n.id] : -1;
1.92 + }
1.93 + void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
1.94 +
1.95 + void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
1.96 + void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
1.97 +
1.98 + static int id(const Node& n) { return n.id; }
1.99 + static Node nodeFromId(int id) { return Node(id); }
1.100 + int maxNodeId() const { return node_num - 1; }
1.101 +
1.102 + static int id(const Arc& e) { return e.id; }
1.103 + static Arc arcFromId(int id) { return Arc(id); }
1.104 + int maxArcId() const { return arc_num - 1; }
1.105 +
1.106 + typedef True NodeNumTag;
1.107 + typedef True ArcNumTag;
1.108 +
1.109 + int nodeNum() const { return node_num; }
1.110 + int arcNum() const { return arc_num; }
1.111 +
1.112 + private:
1.113 +
1.114 + template <typename Digraph, typename NodeRefMap>
1.115 + class ArcLess {
1.116 + public:
1.117 + typedef typename Digraph::Arc Arc;
1.118 +
1.119 + ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
1.120 + : digraph(_graph), nodeRef(_nodeRef) {}
1.121 +
1.122 + bool operator()(const Arc& left, const Arc& right) const {
1.123 + return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
1.124 + }
1.125 + private:
1.126 + const Digraph& digraph;
1.127 + const NodeRefMap& nodeRef;
1.128 + };
1.129 +
1.130 + public:
1.131 +
1.132 + typedef True BuildTag;
1.133 +
1.134 + void clear() {
1.135 + if (built) {
1.136 + delete[] node_first_out;
1.137 + delete[] node_first_in;
1.138 + delete[] arc_source;
1.139 + delete[] arc_target;
1.140 + delete[] arc_next_out;
1.141 + delete[] arc_next_in;
1.142 + }
1.143 + built = false;
1.144 + node_num = 0;
1.145 + arc_num = 0;
1.146 + }
1.147 +
1.148 + template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
1.149 + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
1.150 + typedef typename Digraph::Node GNode;
1.151 + typedef typename Digraph::Arc GArc;
1.152 +
1.153 + built = true;
1.154 +
1.155 + node_num = countNodes(digraph);
1.156 + arc_num = countArcs(digraph);
1.157 +
1.158 + node_first_out = new int[node_num + 1];
1.159 + node_first_in = new int[node_num];
1.160 +
1.161 + arc_source = new int[arc_num];
1.162 + arc_target = new int[arc_num];
1.163 + arc_next_out = new int[arc_num];
1.164 + arc_next_in = new int[arc_num];
1.165 +
1.166 + int node_index = 0;
1.167 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.168 + nodeRef[n] = Node(node_index);
1.169 + node_first_in[node_index] = -1;
1.170 + ++node_index;
1.171 + }
1.172 +
1.173 + ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
1.174 +
1.175 + int arc_index = 0;
1.176 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.177 + int source = nodeRef[n].id;
1.178 + std::vector<GArc> arcs;
1.179 + for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
1.180 + arcs.push_back(e);
1.181 + }
1.182 + if (!arcs.empty()) {
1.183 + node_first_out[source] = arc_index;
1.184 + std::sort(arcs.begin(), arcs.end(), arcLess);
1.185 + for (typename std::vector<GArc>::iterator it = arcs.begin();
1.186 + it != arcs.end(); ++it) {
1.187 + int target = nodeRef[digraph.target(*it)].id;
1.188 + arcRef[*it] = Arc(arc_index);
1.189 + arc_source[arc_index] = source;
1.190 + arc_target[arc_index] = target;
1.191 + arc_next_in[arc_index] = node_first_in[target];
1.192 + node_first_in[target] = arc_index;
1.193 + arc_next_out[arc_index] = arc_index + 1;
1.194 + ++arc_index;
1.195 + }
1.196 + arc_next_out[arc_index - 1] = -1;
1.197 + } else {
1.198 + node_first_out[source] = arc_index;
1.199 + }
1.200 + }
1.201 + node_first_out[node_num] = arc_num;
1.202 + }
1.203 +
1.204 + template <typename ArcListIterator>
1.205 + void build(int n, ArcListIterator first, ArcListIterator last) {
1.206 + built = true;
1.207 +
1.208 + node_num = n;
1.209 + arc_num = std::distance(first, last);
1.210 +
1.211 + node_first_out = new int[node_num + 1];
1.212 + node_first_in = new int[node_num];
1.213 +
1.214 + arc_source = new int[arc_num];
1.215 + arc_target = new int[arc_num];
1.216 + arc_next_out = new int[arc_num];
1.217 + arc_next_in = new int[arc_num];
1.218 +
1.219 + for (int i = 0; i != node_num; ++i) {
1.220 + node_first_in[i] = -1;
1.221 + }
1.222 +
1.223 + int arc_index = 0;
1.224 + for (int i = 0; i != node_num; ++i) {
1.225 + node_first_out[i] = arc_index;
1.226 + for ( ; first != last && (*first).first == i; ++first) {
1.227 + int j = (*first).second;
1.228 + LEMON_ASSERT(j >= 0 && j < node_num,
1.229 + "Wrong arc list for StaticDigraph::build()");
1.230 + arc_source[arc_index] = i;
1.231 + arc_target[arc_index] = j;
1.232 + arc_next_in[arc_index] = node_first_in[j];
1.233 + node_first_in[j] = arc_index;
1.234 + arc_next_out[arc_index] = arc_index + 1;
1.235 + ++arc_index;
1.236 + }
1.237 + if (arc_index > node_first_out[i])
1.238 + arc_next_out[arc_index - 1] = -1;
1.239 + }
1.240 + LEMON_ASSERT(first == last,
1.241 + "Wrong arc list for StaticDigraph::build()");
1.242 + node_first_out[node_num] = arc_num;
1.243 + }
1.244 +
1.245 + protected:
1.246 +
1.247 + void fastFirstOut(Arc& e, const Node& n) const {
1.248 + e.id = node_first_out[n.id];
1.249 + }
1.250 +
1.251 + static void fastNextOut(Arc& e) {
1.252 + ++e.id;
1.253 + }
1.254 + void fastLastOut(Arc& e, const Node& n) const {
1.255 + e.id = node_first_out[n.id + 1];
1.256 + }
1.257 +
1.258 + protected:
1.259 + bool built;
1.260 + int node_num;
1.261 + int arc_num;
1.262 + int *node_first_out;
1.263 + int *node_first_in;
1.264 + int *arc_source;
1.265 + int *arc_target;
1.266 + int *arc_next_in;
1.267 + int *arc_next_out;
1.268 + };
1.269 +
1.270 + typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
1.271 +
1.272 +
1.273 + /// \ingroup graphs
1.274 + ///
1.275 + /// \brief A static directed graph class.
1.276 + ///
1.277 + /// \ref StaticDigraph is a highly efficient digraph implementation,
1.278 + /// but it is fully static.
1.279 + /// It stores only two \c int values for each node and only four \c int
1.280 + /// values for each arc. Moreover it provides faster item iteration than
1.281 + /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
1.282 + /// iterators, since its arcs are stored in an appropriate order.
1.283 + /// However it only provides build() and clear() functions and does not
1.284 + /// support any other modification of the digraph.
1.285 + ///
1.286 + /// Since this digraph structure is completely static, its nodes and arcs
1.287 + /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
1.288 + /// and <tt>[0..arcNum()-1]</tt>, respectively.
1.289 + /// The index of an item is the same as its ID, it can be obtained
1.290 + /// using the corresponding \ref index() or \ref concepts::Digraph::id()
1.291 + /// "id()" function. A node or arc with a certain index can be obtained
1.292 + /// using node() or arc().
1.293 + ///
1.294 + /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
1.295 + /// Most of its member functions and nested classes are documented
1.296 + /// only in the concept class.
1.297 + ///
1.298 + /// This class provides constant time counting for nodes and arcs.
1.299 + ///
1.300 + /// \sa concepts::Digraph
1.301 + class StaticDigraph : public ExtendedStaticDigraphBase {
1.302 + public:
1.303 +
1.304 + typedef ExtendedStaticDigraphBase Parent;
1.305 +
1.306 + public:
1.307 +
1.308 + /// \brief Constructor
1.309 + ///
1.310 + /// Default constructor.
1.311 + StaticDigraph() : Parent() {}
1.312 +
1.313 + /// \brief The node with the given index.
1.314 + ///
1.315 + /// This function returns the node with the given index.
1.316 + /// \sa index()
1.317 + static Node node(int ix) { return Parent::nodeFromId(ix); }
1.318 +
1.319 + /// \brief The arc with the given index.
1.320 + ///
1.321 + /// This function returns the arc with the given index.
1.322 + /// \sa index()
1.323 + static Arc arc(int ix) { return Parent::arcFromId(ix); }
1.324 +
1.325 + /// \brief The index of the given node.
1.326 + ///
1.327 + /// This function returns the index of the the given node.
1.328 + /// \sa node()
1.329 + static int index(Node node) { return Parent::id(node); }
1.330 +
1.331 + /// \brief The index of the given arc.
1.332 + ///
1.333 + /// This function returns the index of the the given arc.
1.334 + /// \sa arc()
1.335 + static int index(Arc arc) { return Parent::id(arc); }
1.336 +
1.337 + /// \brief Number of nodes.
1.338 + ///
1.339 + /// This function returns the number of nodes.
1.340 + int nodeNum() const { return node_num; }
1.341 +
1.342 + /// \brief Number of arcs.
1.343 + ///
1.344 + /// This function returns the number of arcs.
1.345 + int arcNum() const { return arc_num; }
1.346 +
1.347 + /// \brief Build the digraph copying another digraph.
1.348 + ///
1.349 + /// This function builds the digraph copying another digraph of any
1.350 + /// kind. It can be called more than once, but in such case, the whole
1.351 + /// structure and all maps will be cleared and rebuilt.
1.352 + ///
1.353 + /// This method also makes possible to copy a digraph to a StaticDigraph
1.354 + /// structure using \ref DigraphCopy.
1.355 + ///
1.356 + /// \param digraph An existing digraph to be copied.
1.357 + /// \param nodeRef The node references will be copied into this map.
1.358 + /// Its key type must be \c Digraph::Node and its value type must be
1.359 + /// \c StaticDigraph::Node.
1.360 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.361 + /// concept.
1.362 + /// \param arcRef The arc references will be copied into this map.
1.363 + /// Its key type must be \c Digraph::Arc and its value type must be
1.364 + /// \c StaticDigraph::Arc.
1.365 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.366 + ///
1.367 + /// \note If you do not need the arc references, then you could use
1.368 + /// \ref NullMap for the last parameter. However the node references
1.369 + /// are required by the function itself, thus they must be readable
1.370 + /// from the map.
1.371 + template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
1.372 + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
1.373 + if (built) Parent::clear();
1.374 + Parent::build(digraph, nodeRef, arcRef);
1.375 + }
1.376 +
1.377 + /// \brief Build the digraph from an arc list.
1.378 + ///
1.379 + /// This function builds the digraph from the given arc list.
1.380 + /// It can be called more than once, but in such case, the whole
1.381 + /// structure and all maps will be cleared and rebuilt.
1.382 + ///
1.383 + /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
1.384 + /// specified by STL compatible itartors whose \c value_type must be
1.385 + /// <tt>std::pair<int,int></tt>.
1.386 + /// Each arc must be specified by a pair of integer indices
1.387 + /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
1.388 + /// non-decreasing order with respect to their first values.</i>
1.389 + /// If the k-th pair in the list is <tt>(i,j)</tt>, then
1.390 + /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
1.391 + ///
1.392 + /// \param n The number of nodes.
1.393 + /// \param begin An iterator pointing to the beginning of the arc list.
1.394 + /// \param end An iterator pointing to the end of the arc list.
1.395 + ///
1.396 + /// For example, a simple digraph can be constructed like this.
1.397 + /// \code
1.398 + /// std::vector<std::pair<int,int> > arcs;
1.399 + /// arcs.push_back(std::make_pair(0,1));
1.400 + /// arcs.push_back(std::make_pair(0,2));
1.401 + /// arcs.push_back(std::make_pair(1,3));
1.402 + /// arcs.push_back(std::make_pair(1,2));
1.403 + /// arcs.push_back(std::make_pair(3,0));
1.404 + /// StaticDigraph gr;
1.405 + /// gr.build(4, arcs.begin(), arcs.end());
1.406 + /// \endcode
1.407 + template <typename ArcListIterator>
1.408 + void build(int n, ArcListIterator begin, ArcListIterator end) {
1.409 + if (built) Parent::clear();
1.410 + StaticDigraphBase::build(n, begin, end);
1.411 + notifier(Node()).build();
1.412 + notifier(Arc()).build();
1.413 + }
1.414 +
1.415 + /// \brief Clear the digraph.
1.416 + ///
1.417 + /// This function erases all nodes and arcs from the digraph.
1.418 + void clear() {
1.419 + Parent::clear();
1.420 + }
1.421 +
1.422 + protected:
1.423 +
1.424 + using Parent::fastFirstOut;
1.425 + using Parent::fastNextOut;
1.426 + using Parent::fastLastOut;
1.427 +
1.428 + public:
1.429 +
1.430 + class OutArcIt : public Arc {
1.431 + public:
1.432 +
1.433 + OutArcIt() { }
1.434 +
1.435 + OutArcIt(Invalid i) : Arc(i) { }
1.436 +
1.437 + OutArcIt(const StaticDigraph& digraph, const Node& node) {
1.438 + digraph.fastFirstOut(*this, node);
1.439 + digraph.fastLastOut(last, node);
1.440 + if (last == *this) *this = INVALID;
1.441 + }
1.442 +
1.443 + OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
1.444 + if (arc != INVALID) {
1.445 + digraph.fastLastOut(last, digraph.source(arc));
1.446 + }
1.447 + }
1.448 +
1.449 + OutArcIt& operator++() {
1.450 + StaticDigraph::fastNextOut(*this);
1.451 + if (last == *this) *this = INVALID;
1.452 + return *this;
1.453 + }
1.454 +
1.455 + private:
1.456 + Arc last;
1.457 + };
1.458 +
1.459 + Node baseNode(const OutArcIt &arc) const {
1.460 + return Parent::source(static_cast<const Arc&>(arc));
1.461 + }
1.462 +
1.463 + Node runningNode(const OutArcIt &arc) const {
1.464 + return Parent::target(static_cast<const Arc&>(arc));
1.465 + }
1.466 +
1.467 + Node baseNode(const InArcIt &arc) const {
1.468 + return Parent::target(static_cast<const Arc&>(arc));
1.469 + }
1.470 +
1.471 + Node runningNode(const InArcIt &arc) const {
1.472 + return Parent::source(static_cast<const Arc&>(arc));
1.473 + }
1.474 +
1.475 + };
1.476 +
1.477 +}
1.478 +
1.479 +#endif