|
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 |
|
29 namespace 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 |