COIN-OR::LEMON - Graph Library

source: lemon-main/lemon/static_graph.h @ 1157:0898f3371d1d

Last change on this file since 1157:0898f3371d1d was 1157:0898f3371d1d, checked in by Gabriel Gouvine <gabriel.gouvine.GIT@…>, 20 months ago

Forbid copy construction of StaticDigraph?

File size: 15.1 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) 2003-2010
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_STATIC_GRAPH_H
20#define LEMON_STATIC_GRAPH_H
21
22///\ingroup graphs
23///\file
24///\brief StaticDigraph class.
25
26#include <lemon/core.h>
27#include <lemon/bits/graph_extender.h>
28
29namespace lemon {
30
31  class StaticDigraphBase {
32
33  public:
34
35    StaticDigraphBase()
36      : built(false), node_num(0), arc_num(0),
37        node_first_out(NULL), node_first_in(NULL),
38        arc_source(NULL), arc_target(NULL),
39        arc_next_in(NULL), arc_next_out(NULL) {}
40
41    ~StaticDigraphBase() {
42      if (built) {
43        delete[] node_first_out;
44        delete[] node_first_in;
45        delete[] arc_source;
46        delete[] arc_target;
47        delete[] arc_next_out;
48        delete[] arc_next_in;
49      }
50    }
51
52    class Node {
53      friend class StaticDigraphBase;
54    protected:
55      int id;
56      Node(int _id) : id(_id) {}
57    public:
58      Node() {}
59      Node (Invalid) : id(-1) {}
60      bool operator==(const Node& node) const { return id == node.id; }
61      bool operator!=(const Node& node) const { return id != node.id; }
62      bool operator<(const Node& node) const { return id < node.id; }
63    };
64
65    class Arc {
66      friend class StaticDigraphBase;
67    protected:
68      int id;
69      Arc(int _id) : id(_id) {}
70    public:
71      Arc() { }
72      Arc (Invalid) : id(-1) {}
73      bool operator==(const Arc& arc) const { return id == arc.id; }
74      bool operator!=(const Arc& arc) const { return id != arc.id; }
75      bool operator<(const Arc& arc) const { return id < arc.id; }
76    };
77
78    Node source(const Arc& e) const { return Node(arc_source[e.id]); }
79    Node target(const Arc& e) const { return Node(arc_target[e.id]); }
80
81    void first(Node& n) const { n.id = node_num - 1; }
82    static void next(Node& n) { --n.id; }
83
84    void first(Arc& e) const { e.id = arc_num - 1; }
85    static void next(Arc& e) { --e.id; }
86
87    void firstOut(Arc& e, const Node& n) const {
88      e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
89        node_first_out[n.id] : -1;
90    }
91    void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
92
93    void firstIn(Arc& e, const Node& n) const { e.id = node_first_in[n.id]; }
94    void nextIn(Arc& e) const { e.id = arc_next_in[e.id]; }
95
96    static int id(const Node& n) { return n.id; }
97    static Node nodeFromId(int id) { return Node(id); }
98    int maxNodeId() const { return node_num - 1; }
99
100    static int id(const Arc& e) { return e.id; }
101    static Arc arcFromId(int id) { return Arc(id); }
102    int maxArcId() const { return arc_num - 1; }
103
104    typedef True NodeNumTag;
105    typedef True ArcNumTag;
106
107    int nodeNum() const { return node_num; }
108    int arcNum() const { return arc_num; }
109
110  private:
111
112    template <typename Digraph, typename NodeRefMap>
113    class ArcLess {
114    public:
115      typedef typename Digraph::Arc Arc;
116
117      ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
118        : digraph(_graph), nodeRef(_nodeRef) {}
119
120      bool operator()(const Arc& left, const Arc& right) const {
121        return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
122      }
123    private:
124      const Digraph& digraph;
125      const NodeRefMap& nodeRef;
126    };
127
128  public:
129
130    typedef True BuildTag;
131
132    void clear() {
133      if (built) {
134        delete[] node_first_out;
135        delete[] node_first_in;
136        delete[] arc_source;
137        delete[] arc_target;
138        delete[] arc_next_out;
139        delete[] arc_next_in;
140      }
141      built = false;
142      node_num = 0;
143      arc_num = 0;
144    }
145
146    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
147    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
148      typedef typename Digraph::Node GNode;
149      typedef typename Digraph::Arc GArc;
150
151      built = true;
152
153      node_num = countNodes(digraph);
154      arc_num = countArcs(digraph);
155
156      node_first_out = new int[node_num + 1];
157      node_first_in = new int[node_num];
158
159      arc_source = new int[arc_num];
160      arc_target = new int[arc_num];
161      arc_next_out = new int[arc_num];
162      arc_next_in = new int[arc_num];
163
164      int node_index = 0;
165      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
166        nodeRef[n] = Node(node_index);
167        node_first_in[node_index] = -1;
168        ++node_index;
169      }
170
171      ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
172
173      int arc_index = 0;
174      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
175        int source = nodeRef[n].id;
176        std::vector<GArc> arcs;
177        for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
178          arcs.push_back(e);
179        }
180        if (!arcs.empty()) {
181          node_first_out[source] = arc_index;
182          std::sort(arcs.begin(), arcs.end(), arcLess);
183          for (typename std::vector<GArc>::iterator it = arcs.begin();
184               it != arcs.end(); ++it) {
185            int target = nodeRef[digraph.target(*it)].id;
186            arcRef[*it] = Arc(arc_index);
187            arc_source[arc_index] = source;
188            arc_target[arc_index] = target;
189            arc_next_in[arc_index] = node_first_in[target];
190            node_first_in[target] = arc_index;
191            arc_next_out[arc_index] = arc_index + 1;
192            ++arc_index;
193          }
194          arc_next_out[arc_index - 1] = -1;
195        } else {
196          node_first_out[source] = arc_index;
197        }
198      }
199      node_first_out[node_num] = arc_num;
200    }
201
202    template <typename ArcListIterator>
203    void build(int n, ArcListIterator first, ArcListIterator last) {
204      built = true;
205
206      node_num = n;
207      arc_num = static_cast<int>(std::distance(first, last));
208
209      node_first_out = new int[node_num + 1];
210      node_first_in = new int[node_num];
211
212      arc_source = new int[arc_num];
213      arc_target = new int[arc_num];
214      arc_next_out = new int[arc_num];
215      arc_next_in = new int[arc_num];
216
217      for (int i = 0; i != node_num; ++i) {
218        node_first_in[i] = -1;
219      }
220
221      int arc_index = 0;
222      for (int i = 0; i != node_num; ++i) {
223        node_first_out[i] = arc_index;
224        for ( ; first != last && (*first).first == i; ++first) {
225          int j = (*first).second;
226          LEMON_ASSERT(j >= 0 && j < node_num,
227            "Wrong arc list for StaticDigraph::build()");
228          arc_source[arc_index] = i;
229          arc_target[arc_index] = j;
230          arc_next_in[arc_index] = node_first_in[j];
231          node_first_in[j] = arc_index;
232          arc_next_out[arc_index] = arc_index + 1;
233          ++arc_index;
234        }
235        if (arc_index > node_first_out[i])
236          arc_next_out[arc_index - 1] = -1;
237      }
238      LEMON_ASSERT(first == last,
239        "Wrong arc list for StaticDigraph::build()");
240      node_first_out[node_num] = arc_num;
241    }
242
243  protected:
244
245    void fastFirstOut(Arc& e, const Node& n) const {
246      e.id = node_first_out[n.id];
247    }
248
249    static void fastNextOut(Arc& e) {
250      ++e.id;
251    }
252    void fastLastOut(Arc& e, const Node& n) const {
253      e.id = node_first_out[n.id + 1];
254    }
255
256  protected:
257    bool built;
258    int node_num;
259    int arc_num;
260    int *node_first_out;
261    int *node_first_in;
262    int *arc_source;
263    int *arc_target;
264    int *arc_next_in;
265    int *arc_next_out;
266  };
267
268  typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
269
270
271  /// \ingroup graphs
272  ///
273  /// \brief A static directed graph class.
274  ///
275  /// \ref StaticDigraph is a highly efficient digraph implementation,
276  /// but it is fully static.
277  /// It stores only two \c int values for each node and only four \c int
278  /// values for each arc. Moreover it provides faster item iteration than
279  /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
280  /// iterators, since its arcs are stored in an appropriate order.
281  /// However it only provides build() and clear() functions and does not
282  /// support any other modification of the digraph.
283  ///
284  /// Since this digraph structure is completely static, its nodes and arcs
285  /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
286  /// and <tt>[0..arcNum()-1]</tt>, respectively.
287  /// The index of an item is the same as its ID, it can be obtained
288  /// using the corresponding \ref index() or \ref concepts::Digraph::id()
289  /// "id()" function. A node or arc with a certain index can be obtained
290  /// using node() or arc().
291  ///
292  /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
293  /// Most of its member functions and nested classes are documented
294  /// only in the concept class.
295  ///
296  /// This class provides constant time counting for nodes and arcs.
297  ///
298  /// \sa concepts::Digraph
299  class StaticDigraph : public ExtendedStaticDigraphBase {
300
301  private:
302    /// Graphs are \e not copy constructible. Use DigraphCopy instead.
303    StaticDigraph(const StaticDigraph &) : ExtendedStaticDigraphBase() {};
304    /// \brief Assignment of a graph to another one is \e not allowed.
305    /// Use DigraphCopy instead.
306    void operator=(const StaticDigraph&) {}
307
308  public:
309
310    typedef ExtendedStaticDigraphBase Parent;
311
312  public:
313
314    /// \brief Constructor
315    ///
316    /// Default constructor.
317    StaticDigraph() : Parent() {}
318
319    /// \brief The node with the given index.
320    ///
321    /// This function returns the node with the given index.
322    /// \sa index()
323    static Node node(int ix) { return Parent::nodeFromId(ix); }
324
325    /// \brief The arc with the given index.
326    ///
327    /// This function returns the arc with the given index.
328    /// \sa index()
329    static Arc arc(int ix) { return Parent::arcFromId(ix); }
330
331    /// \brief The index of the given node.
332    ///
333    /// This function returns the index of the the given node.
334    /// \sa node()
335    static int index(Node node) { return Parent::id(node); }
336
337    /// \brief The index of the given arc.
338    ///
339    /// This function returns the index of the the given arc.
340    /// \sa arc()
341    static int index(Arc arc) { return Parent::id(arc); }
342
343    /// \brief Number of nodes.
344    ///
345    /// This function returns the number of nodes.
346    int nodeNum() const { return node_num; }
347
348    /// \brief Number of arcs.
349    ///
350    /// This function returns the number of arcs.
351    int arcNum() const { return arc_num; }
352
353    /// \brief Build the digraph copying another digraph.
354    ///
355    /// This function builds the digraph copying another digraph of any
356    /// kind. It can be called more than once, but in such case, the whole
357    /// structure and all maps will be cleared and rebuilt.
358    ///
359    /// This method also makes possible to copy a digraph to a StaticDigraph
360    /// structure using \ref DigraphCopy.
361    ///
362    /// \param digraph An existing digraph to be copied.
363    /// \param nodeRef The node references will be copied into this map.
364    /// Its key type must be \c Digraph::Node and its value type must be
365    /// \c StaticDigraph::Node.
366    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
367    /// concept.
368    /// \param arcRef The arc references will be copied into this map.
369    /// Its key type must be \c Digraph::Arc and its value type must be
370    /// \c StaticDigraph::Arc.
371    /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
372    ///
373    /// \note If you do not need the arc references, then you could use
374    /// \ref NullMap for the last parameter. However the node references
375    /// are required by the function itself, thus they must be readable
376    /// from the map.
377    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
378    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
379      if (built) Parent::clear();
380      Parent::build(digraph, nodeRef, arcRef);
381    }
382
383    /// \brief Build the digraph from an arc list.
384    ///
385    /// This function builds the digraph from the given arc list.
386    /// It can be called more than once, but in such case, the whole
387    /// structure and all maps will be cleared and rebuilt.
388    ///
389    /// The list of the arcs must be given in the range <tt>[begin, end)</tt>
390    /// specified by STL compatible itartors whose \c value_type must be
391    /// <tt>std::pair<int,int></tt>.
392    /// Each arc must be specified by a pair of integer indices
393    /// from the range <tt>[0..n-1]</tt>. <i>The pairs must be in a
394    /// non-decreasing order with respect to their first values.</i>
395    /// If the k-th pair in the list is <tt>(i,j)</tt>, then
396    /// <tt>arc(k-1)</tt> will connect <tt>node(i)</tt> to <tt>node(j)</tt>.
397    ///
398    /// \param n The number of nodes.
399    /// \param begin An iterator pointing to the beginning of the arc list.
400    /// \param end An iterator pointing to the end of the arc list.
401    ///
402    /// For example, a simple digraph can be constructed like this.
403    /// \code
404    ///   std::vector<std::pair<int,int> > arcs;
405    ///   arcs.push_back(std::make_pair(0,1));
406    ///   arcs.push_back(std::make_pair(0,2));
407    ///   arcs.push_back(std::make_pair(1,3));
408    ///   arcs.push_back(std::make_pair(1,2));
409    ///   arcs.push_back(std::make_pair(3,0));
410    ///   StaticDigraph gr;
411    ///   gr.build(4, arcs.begin(), arcs.end());
412    /// \endcode
413    template <typename ArcListIterator>
414    void build(int n, ArcListIterator begin, ArcListIterator end) {
415      if (built) Parent::clear();
416      StaticDigraphBase::build(n, begin, end);
417      notifier(Node()).build();
418      notifier(Arc()).build();
419    }
420
421    /// \brief Clear the digraph.
422    ///
423    /// This function erases all nodes and arcs from the digraph.
424    void clear() {
425      Parent::clear();
426    }
427
428  protected:
429
430    using Parent::fastFirstOut;
431    using Parent::fastNextOut;
432    using Parent::fastLastOut;
433
434  public:
435
436    class OutArcIt : public Arc {
437    public:
438
439      OutArcIt() { }
440
441      OutArcIt(Invalid i) : Arc(i) { }
442
443      OutArcIt(const StaticDigraph& digraph, const Node& node) {
444        digraph.fastFirstOut(*this, node);
445        digraph.fastLastOut(last, node);
446        if (last == *this) *this = INVALID;
447      }
448
449      OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
450        if (arc != INVALID) {
451          digraph.fastLastOut(last, digraph.source(arc));
452        }
453      }
454
455      OutArcIt& operator++() {
456        StaticDigraph::fastNextOut(*this);
457        if (last == *this) *this = INVALID;
458        return *this;
459      }
460
461    private:
462      Arc last;
463    };
464
465    Node baseNode(const OutArcIt &arc) const {
466      return Parent::source(static_cast<const Arc&>(arc));
467    }
468
469    Node runningNode(const OutArcIt &arc) const {
470      return Parent::target(static_cast<const Arc&>(arc));
471    }
472
473    Node baseNode(const InArcIt &arc) const {
474      return Parent::target(static_cast<const Arc&>(arc));
475    }
476
477    Node runningNode(const InArcIt &arc) const {
478      return Parent::source(static_cast<const Arc&>(arc));
479    }
480
481  };
482
483}
484
485#endif
Note: See TracBrowser for help on using the repository browser.