COIN-OR::LEMON - Graph Library

source: lemon/lemon/static_graph.h @ 824:5764dd9b6e18

Last change on this file since 824:5764dd9b6e18 was 824:5764dd9b6e18, checked in by Peter Kovacs <kpeter@…>, 10 years ago

Add a new build() function to StaticDigraph? (#68)

This function builds the digraph from an arc list that
contains pairs of integer indices from the range [0..n-1].
It is useful in the cases when you would like to build a
StaticDigraph? from scratch, i.e. you do not want to build
another digraph that can be copied using the other build()
function.

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