COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/static_graph.h @ 773:cf360f758f25

Last change on this file since 773:cf360f758f25 was 773:cf360f758f25, checked in by Peter Kovacs <kpeter@…>, 11 years ago

Port StaticDigraph? from SVN -r3524 (#68)

File size: 7.2 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      : node_num(-1), 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 (node_num != -1) {
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    template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
132    void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
133
134      if (node_num != -1) {
135        delete[] node_first_out;
136        delete[] node_first_in;
137        delete[] arc_source;
138        delete[] arc_target;
139        delete[] arc_next_out;
140        delete[] arc_next_in;
141      }
142
143      typedef typename Digraph::Node GNode;
144      typedef typename Digraph::Arc GArc;
145
146      node_num = countNodes(digraph);
147      arc_num = countArcs(digraph);
148
149      node_first_out = new int[node_num + 1];
150      node_first_in = new int[node_num];
151
152      arc_source = new int[arc_num];
153      arc_target = new int[arc_num];
154      arc_next_out = new int[arc_num];
155      arc_next_in = new int[arc_num];
156
157      int node_index = 0;
158      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
159        nodeRef[n] = Node(node_index);
160        node_first_in[node_index] = -1;
161        ++node_index;
162      }
163
164      ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
165
166      int arc_index = 0;
167      for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
168        int source = nodeRef[n].id;
169        std::vector<GArc> arcs;
170        for (typename Digraph::OutArcIt e(digraph, n); e != INVALID; ++e) {
171          arcs.push_back(e);
172        }
173        if (!arcs.empty()) {
174          node_first_out[source] = arc_index;
175          std::sort(arcs.begin(), arcs.end(), arcLess);
176          for (typename std::vector<GArc>::iterator it = arcs.begin();
177               it != arcs.end(); ++it) {
178            int target = nodeRef[digraph.target(*it)].id;
179            arcRef[*it] = Arc(arc_index);
180            arc_source[arc_index] = source;
181            arc_target[arc_index] = target;
182            arc_next_in[arc_index] = node_first_in[target];
183            node_first_in[target] = arc_index;
184            arc_next_out[arc_index] = arc_index + 1;
185            ++arc_index;
186          }
187          arc_next_out[arc_index - 1] = -1;
188        } else {
189          node_first_out[source] = arc_index;
190        }
191      }
192      node_first_out[node_num] = arc_num;
193    }
194
195  protected:
196
197    void fastFirstOut(Arc& e, const Node& n) const {
198      e.id = node_first_out[n.id];
199    }
200
201    static void fastNextOut(Arc& e) {
202      ++e.id;
203    }
204    void fastLastOut(Arc& e, const Node& n) const {
205      e.id = node_first_out[n.id + 1];
206    }
207
208  private:
209    int node_num;
210    int arc_num;
211    int *node_first_out;
212    int *node_first_in;
213    int *arc_source;
214    int *arc_target;
215    int *arc_next_in;
216    int *arc_next_out;
217  };
218
219  typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
220
221
222  class StaticDigraph : public ExtendedStaticDigraphBase {
223  public:
224
225    typedef ExtendedStaticDigraphBase Parent;
226
227  protected:
228
229    using Parent::fastFirstOut;
230    using Parent::fastNextOut;
231    using Parent::fastLastOut;
232   
233  public:
234
235    class OutArcIt : public Arc {
236    public:
237
238      OutArcIt() { }
239
240      OutArcIt(Invalid i) : Arc(i) { }
241
242      OutArcIt(const StaticDigraph& digraph, const Node& node) {
243        digraph.fastFirstOut(*this, node);
244        digraph.fastLastOut(last, node);
245        if (last == *this) *this = INVALID;
246      }
247
248      OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
249        if (arc != INVALID) {
250          digraph.fastLastOut(last, digraph.source(arc));
251        }
252      }
253
254      OutArcIt& operator++() {
255        StaticDigraph::fastNextOut(*this);
256        if (last == *this) *this = INVALID;
257        return *this;
258      }
259
260    private:
261      Arc last;
262    };
263
264  };
265
266}
267
268#endif
Note: See TracBrowser for help on using the repository browser.