COIN-OR::LEMON - Graph Library

source: lemon/lemon/compact_graph.h @ 1419:73bd8d5200df

Last change on this file since 1419:73bd8d5200df was 1419:73bd8d5200df, checked in by Gabriel Gouvine <gabriel.gouvine.GIT@…>, 2 years ago

CompactDigraph? implementation (#377)

Smaller version of StaticDigraph? (n+m) if InArcIt? is not needed

File size: 12.9 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2017
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_COMPACT_GRAPH_H
20#define LEMON_COMPACT_GRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief CompactDigraph class.
25
26#include <lemon/core.h>
27#include <lemon/bits/graph_extender.h>
28
29#include <algorithm>
30
31namespace lemon {
32
33  class CompactDigraphBase {
34
35  public:
36
37    CompactDigraphBase()
38      : built(false), node_num(0), arc_num(0),
39        node_first_out(NULL),
40        arc_target(NULL) {}
41
42    ~CompactDigraphBase() {
43      if (built) {
44        delete[] node_first_out;
45        delete[] arc_target;
46      }
47    }
48
49    class Node {
50      friend class CompactDigraphBase;
51    protected:
52      int id;
53      Node(int _id) : id(_id) {}
54    public:
55      Node() {}
56      Node (Invalid) : id(-1) {}
57      bool operator==(const Node& node) const { return id == node.id; }
58      bool operator!=(const Node& node) const { return id != node.id; }
59      bool operator<(const Node& node) const { return id < node.id; }
60    };
61
62    class Arc {
63      friend class CompactDigraphBase;
64    protected:
65      int id;
66      int source;
67      Arc(int _id, int _source) : id(_id), source(_source) {}
68    public:
69      Arc() { }
70      Arc (Invalid) : id(-1), source(-1) {}
71      bool operator==(const Arc& arc) const { return id == arc.id; }
72      bool operator!=(const Arc& arc) const { return id != arc.id; }
73      bool operator<(const Arc& arc) const { return id < arc.id; }
74    };
75
76    Node source(const Arc& e) const { return Node(e.source); }
77    Node target(const Arc& e) const { return Node(arc_target[e.id]); }
78
79    void first(Node& n) const { n.id = node_num - 1; }
80    static void next(Node& n) { --n.id; }
81
82  private:
83
84    void nextSource(Arc& e) const {
85      if (e.id == -1) return;
86      int last = node_first_out[e.source] - 1;
87      while (e.id == last) {
88        --e.source;
89        last = node_first_out[e.source] - 1;
90      }
91    }
92
93  public:
94
95    void first(Arc& e) const {
96      e.id = arc_num - 1;
97      e.source = node_num - 1;
98      nextSource(e);
99    }
100    void next(Arc& e) const {
101      --e.id;
102      nextSource(e);
103    }
104
105    void firstOut(Arc& e, const Node& n) const {
106      e.source = n.id;
107      e.id = node_first_out[n.id];
108      if (e.id == node_first_out[n.id + 1]) e = INVALID;
109    }
110    void nextOut(Arc& e) const {
111      ++e.id;
112      if (e.id == node_first_out[e.source + 1]) e = INVALID;
113    }
114
115    void firstIn(Arc& e, const Node& n) const {
116      first(e);
117      while(e != INVALID && target(e) != n) {
118        next(e);
119      }
120    }
121    void nextIn(Arc& e) const {
122      Node arcTarget = target(e);
123      do {
124        next(e);
125      } while(e != INVALID && target(e) != arcTarget);
126    }
127
128    static int id(const Node& n) { return n.id; }
129    static Node nodeFromId(int id) { return Node(id); }
130    int maxNodeId() const { return node_num - 1; }
131
132    static int id(const Arc& e) { return e.id; }
133    Arc arcFromId(int id) const {
134      int *l = std::upper_bound(node_first_out, node_first_out + node_num, id) - 1;
135      int src = l - node_first_out;
136      return Arc(id, src);
137    }
138    int maxArcId() const { return arc_num - 1; }
139
140    typedef True NodeNumTag;
141    typedef True ArcNumTag;
142
143    int nodeNum() const { return node_num; }
144    int arcNum() const { return arc_num; }
145
146  private:
147
148    template <typename Digraph, typename NodeRefMap>
149    class ArcLess {
150    public:
151      typedef typename Digraph::Arc Arc;
152
153      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
154        : digraph(_graph), nodeRef(_nodeRef) {}
155
156      bool operator()(const Arc& left, const Arc& right) const {
157        return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
158      }
159    private:
160      const Digraph& digraph;
161      const NodeRefMap& nodeRef;
162    };
163
164  public:
165
166    typedef True BuildTag;
167
168    void clear() {
169      if (built) {
170        delete[] node_first_out;
171        delete[] arc_target;
172      }
173      built = false;
174      node_num = 0;
175      arc_num = 0;
176    }
177
178    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
179    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
180      typedef typename Digraph::Node GNode;
181      typedef typename Digraph::Arc GArc;
182
183      built = true;
184
185      node_num = countNodes(digraph);
186      arc_num = countArcs(digraph);
187
188      node_first_out = new int[node_num + 1];
189
190      arc_target = new int[arc_num];
191
192      int node_index = 0;
193      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
194        nodeRef[n] = Node(node_index);
195        ++node_index;
196      }
197
198      ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
199
200      int arc_index = 0;
201      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
202        int source = nodeRef[n].id;
203        std::vector<GArc> arcs;
204        for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
205          arcs.push_back(e);
206        }
207        if (!arcs.empty()) {
208          node_first_out[source] = arc_index;
209          std::sort(arcs.begin(), arcs.end(), arcLess);
210          for (typename std::vector<GArc>::iterator it = arcs.begin();
211               it != arcs.end(); ++it) {
212            int target = nodeRef[digraph.target(*it)].id;
213            arcRef[*it] = Arc(arc_index, source);
214            arc_target[arc_index] = target;
215            ++arc_index;
216          }
217        } else {
218          node_first_out[source] = arc_index;
219        }
220      }
221      node_first_out[node_num] = arc_num;
222    }
223
224    template <typename ArcListIterator>
225    void build(int n, ArcListIterator first, ArcListIterator last) {
226      built = true;
227
228      node_num = n;
229      arc_num = static_cast<int>(std::distance(first, last));
230
231      node_first_out = new int[node_num + 1];
232
233      arc_target = new int[arc_num];
234
235      int arc_index = 0;
236      for (int i = 0; i != node_num; ++i) {
237        node_first_out[i] = arc_index;
238        for ( ; first != last && (*first).first == i; ++first) {
239          int j = (*first).second;
240          LEMON_ASSERT(j >= 0 && j < node_num,
241            "Wrong arc list for CompactDigraph::build()");
242          arc_target[arc_index] = j;
243          ++arc_index;
244        }
245      }
246      LEMON_ASSERT(first == last,
247        "Wrong arc list for CompactDigraph::build()");
248      node_first_out[node_num] = arc_num;
249    }
250
251  protected:
252    bool built;
253    int node_num;
254    int arc_num;
255    int *node_first_out;
256    int *arc_target;
257  };
258
259  typedef DigraphExtender<CompactDigraphBase> ExtendedCompactDigraphBase;
260
261
262  /// \ingroup graphs
263  ///
264  /// \brief A static directed graph class.
265  ///
266  /// \ref CompactDigraph is a highly efficient digraph implementation
267  /// similar to \ref StaticDigraph. It is more memory efficient but does
268  /// not provide efficient iteration over incoming arcs.
269  ///
270  /// It stores only one \c int values for each node and one \c int value
271  /// for each arc. Its \ref InArcIt implementation is inefficient and
272  /// provided only for compatibility with the \ref concepts::Digraph "Digraph concept".
273  ///
274  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
275  /// Most of its member functions and nested classes are documented
276  /// only in the concept class.
277  ///
278  /// \sa concepts::Digraph
279  class CompactDigraph : public ExtendedCompactDigraphBase {
280
281  private:
282    /// Graphs are \e not copy constructible. Use DigraphCopy instead.
283    CompactDigraph(const CompactDigraph &) : ExtendedCompactDigraphBase() {};
284    /// \brief Assignment of a graph to another one is \e not allowed.
285    /// Use DigraphCopy instead.
286    void operator=(const CompactDigraph&) {}
287
288  public:
289
290    typedef ExtendedCompactDigraphBase Parent;
291
292  public:
293
294    /// \brief Constructor
295    ///
296    /// Default constructor.
297    CompactDigraph() : Parent() {}
298
299    /// \brief The node with the given index.
300    ///
301    /// This function returns the node with the given index.
302    /// \sa index()
303    static Node node(int ix) { return Parent::nodeFromId(ix); }
304
305    /// \brief The arc with the given index.
306    ///
307    /// This function returns the arc with the given index.
308    /// \sa index()
309    Arc arc(int ix) { return arcFromId(ix); }
310
311    /// \brief The index of the given node.
312    ///
313    /// This function returns the index of the the given node.
314    /// \sa node()
315    static int index(Node node) { return Parent::id(node); }
316
317    /// \brief The index of the given arc.
318    ///
319    /// This function returns the index of the the given arc.
320    /// \sa arc()
321    static int index(Arc arc) { return Parent::id(arc); }
322
323    /// \brief Number of nodes.
324    ///
325    /// This function returns the number of nodes.
326    int nodeNum() const { return node_num; }
327
328    /// \brief Number of arcs.
329    ///
330    /// This function returns the number of arcs.
331    int arcNum() const { return arc_num; }
332
333    /// \brief Build the digraph copying another digraph.
334    ///
335    /// This function builds the digraph copying another digraph of any
336    /// kind. It can be called more than once, but in such case, the whole
337    /// structure and all maps will be cleared and rebuilt.
338    ///
339    /// This method also makes possible to copy a digraph to a CompactDigraph
340    /// structure using \ref DigraphCopy.
341    ///
342    /// \param digraph An existing digraph to be copied.
343    /// \param nodeRef The node references will be copied into this map.
344    /// Its key type must be \c Digraph::Node and its value type must be
345    /// \c CompactDigraph::Node.
346    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
347    /// concept.
348    /// \param arcRef The arc references will be copied into this map.
349    /// Its key type must be \c Digraph::Arc and its value type must be
350    /// \c CompactDigraph::Arc.
351    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
352    ///
353    /// \note If you do not need the arc references, then you could use
354    /// \ref NullMap for the last parameter. However the node references
355    /// are required by the function itself, thus they must be readable
356    /// from the map.
357    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
358    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
359      if (built) Parent::clear();
360      Parent::build(digraph, nodeRef, arcRef);
361    }
362
363    /// \brief Build the digraph from an arc list.
364    ///
365    /// This function builds the digraph from the given arc list.
366    /// It can be called more than once, but in such case, the whole
367    /// structure and all maps will be cleared and rebuilt.
368    ///
369    /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
370    /// specified by STL compatible itartors whose \c value_type must be
371    /// <tt>std::pair<int,int></tt>.
372    /// Each arc must be specified by a pair of integer indices
373    /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
374    /// non-decreasing order with respect to their first values.</i>
375    /// If the k-th pair in the list is <tt>(i,j)</tt>, then
376    /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
377    ///
378    /// \param n The number of nodes.
379    /// \param begin An iterator pointing to the beginning of the arc list.
380    /// \param end An iterator pointing to the end of the arc list.
381    ///
382    /// For example, a simple digraph can be constructed like this.
383    /// \code
384    ///   std::vector<std::pair<int,int> > arcs;
385    ///   arcs.push_back(std::make_pair(0,1));
386    ///   arcs.push_back(std::make_pair(0,2));
387    ///   arcs.push_back(std::make_pair(1,3));
388    ///   arcs.push_back(std::make_pair(1,2));
389    ///   arcs.push_back(std::make_pair(3,0));
390    ///   CompactDigraph gr;
391    ///   gr.build(4, arcs.begin(), arcs.end());
392    /// \endcode
393    template <typename ArcListIterator>
394    void build(int n, ArcListIterator begin, ArcListIterator end) {
395      if (built) Parent::clear();
396      CompactDigraphBase::build(n, begin, end);
397      notifier(Node()).build();
398      notifier(Arc()).build();
399    }
400
401    /// \brief Clear the digraph.
402    ///
403    /// This function erases all nodes and arcs from the digraph.
404    void clear() {
405      Parent::clear();
406    }
407
408  public:
409
410    Node baseNode(const OutArcIt &arc) const {
411      return Parent::source(static_cast<const Arc&>(arc));
412    }
413
414    Node runningNode(const OutArcIt &arc) const {
415      return Parent::target(static_cast<const Arc&>(arc));
416    }
417
418    Node baseNode(const InArcIt &arc) const {
419      return Parent::target(static_cast<const Arc&>(arc));
420    }
421
422    Node runningNode(const InArcIt &arc) const {
423      return Parent::source(static_cast<const Arc&>(arc));
424    }
425
426  };
427
428}
429
430#endif
Note: See TracBrowser for help on using the repository browser.