CompactDigraph implementation (#377)
authorGabriel Gouvine <gabriel.gouvine.GIT@gmx.com>
Sun, 19 Mar 2017 14:38:08 +0100 (2017-03-19)
changeset 120073bd8d5200df
parent 1199 15282595e6f4
child 1201 1f4f01870c1e
CompactDigraph implementation (#377)

Smaller version of StaticDigraph (n+m) if InArcIt is not needed
lemon/compact_graph.h
test/digraph_test.cc
     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);