1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/compact_graph.h Sun Mar 19 14:38:08 2017 +0100
1.3 @@ -0,0 +1,430 @@
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) 2017
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_COMPACT_GRAPH_H
1.23 +#define LEMON_COMPACT_GRAPH_H
1.24 +
1.25 +///\ingroup graphs
1.26 +///\file
1.27 +///\brief CompactDigraph class.
1.28 +
1.29 +#include <lemon/core.h>
1.30 +#include <lemon/bits/graph_extender.h>
1.31 +
1.32 +#include <algorithm>
1.33 +
1.34 +namespace lemon {
1.35 +
1.36 + class CompactDigraphBase {
1.37 +
1.38 + public:
1.39 +
1.40 + CompactDigraphBase()
1.41 + : built(false), node_num(0), arc_num(0),
1.42 + node_first_out(NULL),
1.43 + arc_target(NULL) {}
1.44 +
1.45 + ~CompactDigraphBase() {
1.46 + if (built) {
1.47 + delete[] node_first_out;
1.48 + delete[] arc_target;
1.49 + }
1.50 + }
1.51 +
1.52 + class Node {
1.53 + friend class CompactDigraphBase;
1.54 + protected:
1.55 + int id;
1.56 + Node(int _id) : id(_id) {}
1.57 + public:
1.58 + Node() {}
1.59 + Node (Invalid) : id(-1) {}
1.60 + bool operator==(const Node& node) const { return id == node.id; }
1.61 + bool operator!=(const Node& node) const { return id != node.id; }
1.62 + bool operator<(const Node& node) const { return id < node.id; }
1.63 + };
1.64 +
1.65 + class Arc {
1.66 + friend class CompactDigraphBase;
1.67 + protected:
1.68 + int id;
1.69 + int source;
1.70 + Arc(int _id, int _source) : id(_id), source(_source) {}
1.71 + public:
1.72 + Arc() { }
1.73 + Arc (Invalid) : id(-1), source(-1) {}
1.74 + bool operator==(const Arc& arc) const { return id == arc.id; }
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 + };
1.78 +
1.79 + Node source(const Arc& e) const { return Node(e.source); }
1.80 + Node target(const Arc& e) const { return Node(arc_target[e.id]); }
1.81 +
1.82 + void first(Node& n) const { n.id = node_num - 1; }
1.83 + static void next(Node& n) { --n.id; }
1.84 +
1.85 + private:
1.86 +
1.87 + void nextSource(Arc& e) const {
1.88 + if (e.id == -1) return;
1.89 + int last = node_first_out[e.source] - 1;
1.90 + while (e.id == last) {
1.91 + --e.source;
1.92 + last = node_first_out[e.source] - 1;
1.93 + }
1.94 + }
1.95 +
1.96 + public:
1.97 +
1.98 + void first(Arc& e) const {
1.99 + e.id = arc_num - 1;
1.100 + e.source = node_num - 1;
1.101 + nextSource(e);
1.102 + }
1.103 + void next(Arc& e) const {
1.104 + --e.id;
1.105 + nextSource(e);
1.106 + }
1.107 +
1.108 + void firstOut(Arc& e, const Node& n) const {
1.109 + e.source = n.id;
1.110 + e.id = node_first_out[n.id];
1.111 + if (e.id == node_first_out[n.id + 1]) e = INVALID;
1.112 + }
1.113 + void nextOut(Arc& e) const {
1.114 + ++e.id;
1.115 + if (e.id == node_first_out[e.source + 1]) e = INVALID;
1.116 + }
1.117 +
1.118 + void firstIn(Arc& e, const Node& n) const {
1.119 + first(e);
1.120 + while(e != INVALID && target(e) != n) {
1.121 + next(e);
1.122 + }
1.123 + }
1.124 + void nextIn(Arc& e) const {
1.125 + Node arcTarget = target(e);
1.126 + do {
1.127 + next(e);
1.128 + } while(e != INVALID && target(e) != arcTarget);
1.129 + }
1.130 +
1.131 + static int id(const Node& n) { return n.id; }
1.132 + static Node nodeFromId(int id) { return Node(id); }
1.133 + int maxNodeId() const { return node_num - 1; }
1.134 +
1.135 + static int id(const Arc& e) { return e.id; }
1.136 + Arc arcFromId(int id) const {
1.137 + int *l = std::upper_bound(node_first_out, node_first_out + node_num, id) - 1;
1.138 + int src = l - node_first_out;
1.139 + return Arc(id, src);
1.140 + }
1.141 + int maxArcId() const { return arc_num - 1; }
1.142 +
1.143 + typedef True NodeNumTag;
1.144 + typedef True ArcNumTag;
1.145 +
1.146 + int nodeNum() const { return node_num; }
1.147 + int arcNum() const { return arc_num; }
1.148 +
1.149 + private:
1.150 +
1.151 + template <typename Digraph, typename NodeRefMap>
1.152 + class ArcLess {
1.153 + public:
1.154 + typedef typename Digraph::Arc Arc;
1.155 +
1.156 + ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
1.157 + : digraph(_graph), nodeRef(_nodeRef) {}
1.158 +
1.159 + bool operator()(const Arc& left, const Arc& right) const {
1.160 + return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
1.161 + }
1.162 + private:
1.163 + const Digraph& digraph;
1.164 + const NodeRefMap& nodeRef;
1.165 + };
1.166 +
1.167 + public:
1.168 +
1.169 + typedef True BuildTag;
1.170 +
1.171 + void clear() {
1.172 + if (built) {
1.173 + delete[] node_first_out;
1.174 + delete[] arc_target;
1.175 + }
1.176 + built = false;
1.177 + node_num = 0;
1.178 + arc_num = 0;
1.179 + }
1.180 +
1.181 + template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
1.182 + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
1.183 + typedef typename Digraph::Node GNode;
1.184 + typedef typename Digraph::Arc GArc;
1.185 +
1.186 + built = true;
1.187 +
1.188 + node_num = countNodes(digraph);
1.189 + arc_num = countArcs(digraph);
1.190 +
1.191 + node_first_out = new int[node_num + 1];
1.192 +
1.193 + arc_target = new int[arc_num];
1.194 +
1.195 + int node_index = 0;
1.196 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.197 + nodeRef[n] = Node(node_index);
1.198 + ++node_index;
1.199 + }
1.200 +
1.201 + ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
1.202 +
1.203 + int arc_index = 0;
1.204 + for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
1.205 + int source = nodeRef[n].id;
1.206 + std::vector<GArc> arcs;
1.207 + for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
1.208 + arcs.push_back(e);
1.209 + }
1.210 + if (!arcs.empty()) {
1.211 + node_first_out[source] = arc_index;
1.212 + std::sort(arcs.begin(), arcs.end(), arcLess);
1.213 + for (typename std::vector<GArc>::iterator it = arcs.begin();
1.214 + it != arcs.end(); ++it) {
1.215 + int target = nodeRef[digraph.target(*it)].id;
1.216 + arcRef[*it] = Arc(arc_index, source);
1.217 + arc_target[arc_index] = target;
1.218 + ++arc_index;
1.219 + }
1.220 + } else {
1.221 + node_first_out[source] = arc_index;
1.222 + }
1.223 + }
1.224 + node_first_out[node_num] = arc_num;
1.225 + }
1.226 +
1.227 + template <typename ArcListIterator>
1.228 + void build(int n, ArcListIterator first, ArcListIterator last) {
1.229 + built = true;
1.230 +
1.231 + node_num = n;
1.232 + arc_num = static_cast<int>(std::distance(first, last));
1.233 +
1.234 + node_first_out = new int[node_num + 1];
1.235 +
1.236 + arc_target = new int[arc_num];
1.237 +
1.238 + int arc_index = 0;
1.239 + for (int i = 0; i != node_num; ++i) {
1.240 + node_first_out[i] = arc_index;
1.241 + for ( ; first != last && (*first).first == i; ++first) {
1.242 + int j = (*first).second;
1.243 + LEMON_ASSERT(j >= 0 && j < node_num,
1.244 + "Wrong arc list for CompactDigraph::build()");
1.245 + arc_target[arc_index] = j;
1.246 + ++arc_index;
1.247 + }
1.248 + }
1.249 + LEMON_ASSERT(first == last,
1.250 + "Wrong arc list for CompactDigraph::build()");
1.251 + node_first_out[node_num] = arc_num;
1.252 + }
1.253 +
1.254 + protected:
1.255 + bool built;
1.256 + int node_num;
1.257 + int arc_num;
1.258 + int *node_first_out;
1.259 + int *arc_target;
1.260 + };
1.261 +
1.262 + typedef DigraphExtender<CompactDigraphBase> ExtendedCompactDigraphBase;
1.263 +
1.264 +
1.265 + /// \ingroup graphs
1.266 + ///
1.267 + /// \brief A static directed graph class.
1.268 + ///
1.269 + /// \ref CompactDigraph is a highly efficient digraph implementation
1.270 + /// similar to \ref StaticDigraph. It is more memory efficient but does
1.271 + /// not provide efficient iteration over incoming arcs.
1.272 + ///
1.273 + /// It stores only one \c int values for each node and one \c int value
1.274 + /// for each arc. Its \ref InArcIt implementation is inefficient and
1.275 + /// provided only for compatibility with the \ref concepts::Digraph "Digraph concept".
1.276 + ///
1.277 + /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
1.278 + /// Most of its member functions and nested classes are documented
1.279 + /// only in the concept class.
1.280 + ///
1.281 + /// \sa concepts::Digraph
1.282 + class CompactDigraph : public ExtendedCompactDigraphBase {
1.283 +
1.284 + private:
1.285 + /// Graphs are \e not copy constructible. Use DigraphCopy instead.
1.286 + CompactDigraph(const CompactDigraph &) : ExtendedCompactDigraphBase() {};
1.287 + /// \brief Assignment of a graph to another one is \e not allowed.
1.288 + /// Use DigraphCopy instead.
1.289 + void operator=(const CompactDigraph&) {}
1.290 +
1.291 + public:
1.292 +
1.293 + typedef ExtendedCompactDigraphBase Parent;
1.294 +
1.295 + public:
1.296 +
1.297 + /// \brief Constructor
1.298 + ///
1.299 + /// Default constructor.
1.300 + CompactDigraph() : Parent() {}
1.301 +
1.302 + /// \brief The node with the given index.
1.303 + ///
1.304 + /// This function returns the node with the given index.
1.305 + /// \sa index()
1.306 + static Node node(int ix) { return Parent::nodeFromId(ix); }
1.307 +
1.308 + /// \brief The arc with the given index.
1.309 + ///
1.310 + /// This function returns the arc with the given index.
1.311 + /// \sa index()
1.312 + Arc arc(int ix) { return arcFromId(ix); }
1.313 +
1.314 + /// \brief The index of the given node.
1.315 + ///
1.316 + /// This function returns the index of the the given node.
1.317 + /// \sa node()
1.318 + static int index(Node node) { return Parent::id(node); }
1.319 +
1.320 + /// \brief The index of the given arc.
1.321 + ///
1.322 + /// This function returns the index of the the given arc.
1.323 + /// \sa arc()
1.324 + static int index(Arc arc) { return Parent::id(arc); }
1.325 +
1.326 + /// \brief Number of nodes.
1.327 + ///
1.328 + /// This function returns the number of nodes.
1.329 + int nodeNum() const { return node_num; }
1.330 +
1.331 + /// \brief Number of arcs.
1.332 + ///
1.333 + /// This function returns the number of arcs.
1.334 + int arcNum() const { return arc_num; }
1.335 +
1.336 + /// \brief Build the digraph copying another digraph.
1.337 + ///
1.338 + /// This function builds the digraph copying another digraph of any
1.339 + /// kind. It can be called more than once, but in such case, the whole
1.340 + /// structure and all maps will be cleared and rebuilt.
1.341 + ///
1.342 + /// This method also makes possible to copy a digraph to a CompactDigraph
1.343 + /// structure using \ref DigraphCopy.
1.344 + ///
1.345 + /// \param digraph An existing digraph to be copied.
1.346 + /// \param nodeRef The node references will be copied into this map.
1.347 + /// Its key type must be \c Digraph::Node and its value type must be
1.348 + /// \c CompactDigraph::Node.
1.349 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
1.350 + /// concept.
1.351 + /// \param arcRef The arc references will be copied into this map.
1.352 + /// Its key type must be \c Digraph::Arc and its value type must be
1.353 + /// \c CompactDigraph::Arc.
1.354 + /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.355 + ///
1.356 + /// \note If you do not need the arc references, then you could use
1.357 + /// \ref NullMap for the last parameter. However the node references
1.358 + /// are required by the function itself, thus they must be readable
1.359 + /// from the map.
1.360 + template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
1.361 + void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
1.362 + if (built) Parent::clear();
1.363 + Parent::build(digraph, nodeRef, arcRef);
1.364 + }
1.365 +
1.366 + /// \brief Build the digraph from an arc list.
1.367 + ///
1.368 + /// This function builds the digraph from the given arc list.
1.369 + /// It can be called more than once, but in such case, the whole
1.370 + /// structure and all maps will be cleared and rebuilt.
1.371 + ///
1.372 + /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
1.373 + /// specified by STL compatible itartors whose \c value_type must be
1.374 + /// <tt>std::pair<int,int></tt>.
1.375 + /// Each arc must be specified by a pair of integer indices
1.376 + /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
1.377 + /// non-decreasing order with respect to their first values.</i>
1.378 + /// If the k-th pair in the list is <tt>(i,j)</tt>, then
1.379 + /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
1.380 + ///
1.381 + /// \param n The number of nodes.
1.382 + /// \param begin An iterator pointing to the beginning of the arc list.
1.383 + /// \param end An iterator pointing to the end of the arc list.
1.384 + ///
1.385 + /// For example, a simple digraph can be constructed like this.
1.386 + /// \code
1.387 + /// std::vector<std::pair<int,int> > arcs;
1.388 + /// arcs.push_back(std::make_pair(0,1));
1.389 + /// arcs.push_back(std::make_pair(0,2));
1.390 + /// arcs.push_back(std::make_pair(1,3));
1.391 + /// arcs.push_back(std::make_pair(1,2));
1.392 + /// arcs.push_back(std::make_pair(3,0));
1.393 + /// CompactDigraph gr;
1.394 + /// gr.build(4, arcs.begin(), arcs.end());
1.395 + /// \endcode
1.396 + template <typename ArcListIterator>
1.397 + void build(int n, ArcListIterator begin, ArcListIterator end) {
1.398 + if (built) Parent::clear();
1.399 + CompactDigraphBase::build(n, begin, end);
1.400 + notifier(Node()).build();
1.401 + notifier(Arc()).build();
1.402 + }
1.403 +
1.404 + /// \brief Clear the digraph.
1.405 + ///
1.406 + /// This function erases all nodes and arcs from the digraph.
1.407 + void clear() {
1.408 + Parent::clear();
1.409 + }
1.410 +
1.411 + public:
1.412 +
1.413 + Node baseNode(const OutArcIt &arc) const {
1.414 + return Parent::source(static_cast<const Arc&>(arc));
1.415 + }
1.416 +
1.417 + Node runningNode(const OutArcIt &arc) const {
1.418 + return Parent::target(static_cast<const Arc&>(arc));
1.419 + }
1.420 +
1.421 + Node baseNode(const InArcIt &arc) const {
1.422 + return Parent::target(static_cast<const Arc&>(arc));
1.423 + }
1.424 +
1.425 + Node runningNode(const InArcIt &arc) const {
1.426 + return Parent::source(static_cast<const Arc&>(arc));
1.427 + }
1.428 +
1.429 + };
1.430 +
1.431 +}
1.432 +
1.433 +#endif
2.1 --- a/test/digraph_test.cc Sun Aug 17 15:02:03 2008 +0200
2.2 +++ b/test/digraph_test.cc Sun Mar 19 14:38:08 2017 +0100
2.3 @@ -20,6 +20,7 @@
2.4 #include <lemon/list_graph.h>
2.5 #include <lemon/smart_graph.h>
2.6 #include <lemon/static_graph.h>
2.7 +#include <lemon/compact_graph.h>
2.8 #include <lemon/full_graph.h>
2.9
2.10 #include "test_tools.h"
2.11 @@ -338,6 +339,10 @@
2.12 checkConcept<Digraph, StaticDigraph>();
2.13 checkConcept<ClearableDigraphComponent<>, StaticDigraph>();
2.14 }
2.15 + { // Checking CompactDigraph
2.16 + checkConcept<Digraph, CompactDigraph>();
2.17 + checkConcept<ClearableDigraphComponent<>, CompactDigraph>();
2.18 + }
2.19 { // Checking FullDigraph
2.20 checkConcept<Digraph, FullDigraph>();
2.21 }
2.22 @@ -394,12 +399,13 @@
2.23 check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
2.24 }
2.25
2.26 +template <typename GR>
2.27 void checkStaticDigraph() {
2.28 SmartDigraph g;
2.29 - SmartDigraph::NodeMap<StaticDigraph::Node> nref(g);
2.30 - SmartDigraph::ArcMap<StaticDigraph::Arc> aref(g);
2.31 + SmartDigraph::NodeMap<typename GR::Node> nref(g);
2.32 + SmartDigraph::ArcMap<typename GR::Arc> aref(g);
2.33
2.34 - StaticDigraph G;
2.35 + GR G;
2.36
2.37 checkGraphNodeList(G, 0);
2.38 checkGraphArcList(G, 0);
2.39 @@ -555,7 +561,8 @@
2.40 checkDigraphValidity<SmartDigraph>();
2.41 }
2.42 { // Checking StaticDigraph
2.43 - checkStaticDigraph();
2.44 + checkStaticDigraph<StaticDigraph>();
2.45 + checkStaticDigraph<CompactDigraph>();
2.46 }
2.47 { // Checking FullDigraph
2.48 checkFullDigraph(8);