3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_STATIC_GRAPH_H
20 #define LEMON_STATIC_GRAPH_H
24 ///\brief StaticDigraph class.
26 #include <lemon/core.h>
27 #include <lemon/bits/graph_extender.h>
31 class 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) {}
40 ~StaticDigraphBase() {
42 delete[] node_first_out;
43 delete[] node_first_in;
46 delete[] arc_next_out;
52 friend class StaticDigraphBase;
55 Node(int _id) : id(_id) {}
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; }
65 friend class StaticDigraphBase;
68 Arc(int _id) : id(_id) {}
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; }
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]); }
80 void first(Node& n) const { n.id = node_num - 1; }
81 static void next(Node& n) { --n.id; }
83 void first(Arc& e) const { e.id = arc_num - 1; }
84 static void next(Arc& e) { --e.id; }
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;
90 void nextOut(Arc& e) const { e.id = arc_next_out[e.id]; }
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]; }
95 static int id(const Node& n) { return n.id; }
96 static Node nodeFromId(int id) { return Node(id); }
97 int maxNodeId() const { return node_num - 1; }
99 static int id(const Arc& e) { return e.id; }
100 static Arc arcFromId(int id) { return Arc(id); }
101 int maxArcId() const { return arc_num - 1; }
103 typedef True NodeNumTag;
104 typedef True ArcNumTag;
106 int nodeNum() const { return node_num; }
107 int arcNum() const { return arc_num; }
111 template <typename Digraph, typename NodeRefMap>
114 typedef typename Digraph::Arc Arc;
116 ArcLess(const Digraph &_graph, const NodeRefMap& _nodeRef)
117 : digraph(_graph), nodeRef(_nodeRef) {}
119 bool operator()(const Arc& left, const Arc& right) const {
120 return nodeRef[digraph.target(left)] < nodeRef[digraph.target(right)];
123 const Digraph& digraph;
124 const NodeRefMap& nodeRef;
129 typedef True BuildTag;
133 delete[] node_first_out;
134 delete[] node_first_in;
137 delete[] arc_next_out;
138 delete[] arc_next_in;
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;
152 node_num = countNodes(digraph);
153 arc_num = countArcs(digraph);
155 node_first_out = new int[node_num + 1];
156 node_first_in = new int[node_num];
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];
164 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
165 nodeRef[n] = Node(node_index);
166 node_first_in[node_index] = -1;
170 ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
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) {
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;
193 arc_next_out[arc_index - 1] = -1;
195 node_first_out[source] = arc_index;
198 node_first_out[node_num] = arc_num;
203 void fastFirstOut(Arc& e, const Node& n) const {
204 e.id = node_first_out[n.id];
207 static void fastNextOut(Arc& e) {
210 void fastLastOut(Arc& e, const Node& n) const {
211 e.id = node_first_out[n.id + 1];
226 typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
231 /// \brief A static directed graph class.
233 /// \ref StaticDigraph is a highly efficient digraph implementation,
234 /// but it is fully static.
235 /// It stores only two \c int values for each node and only four \c int
236 /// values for each arc. Moreover it provides faster item iteration than
237 /// \ref ListDigraph and \ref SmartDigraph, especially using \c OutArcIt
238 /// iterators, since its arcs are stored in an appropriate order.
239 /// However it only provides build() and clear() functions and does not
240 /// support any other modification of the digraph.
242 /// Since this digraph structure is completely static, its nodes and arcs
243 /// can be indexed with integers from the ranges <tt>[0..nodeNum()-1]</tt>
244 /// and <tt>[0..arcNum()-1]</tt>, respectively.
245 /// The index of an item is the same as its ID, it can be obtained
246 /// using the corresponding \ref index() or \ref concepts::Digraph::id()
247 /// "id()" function. A node or arc with a certain index can be obtained
248 /// using node() or arc().
250 /// This type fully conforms to the \ref concepts::Digraph "Digraph concept".
251 /// Most of its member functions and nested classes are documented
252 /// only in the concept class.
254 /// \sa concepts::Digraph
255 class StaticDigraph : public ExtendedStaticDigraphBase {
258 typedef ExtendedStaticDigraphBase Parent;
262 /// \brief Constructor
264 /// Default constructor.
265 StaticDigraph() : Parent() {}
267 /// \brief The node with the given index.
269 /// This function returns the node with the given index.
271 static Node node(int ix) { return Parent::nodeFromId(ix); }
273 /// \brief The arc with the given index.
275 /// This function returns the arc with the given index.
277 static Arc arc(int ix) { return Parent::arcFromId(ix); }
279 /// \brief The index of the given node.
281 /// This function returns the index of the the given node.
283 static int index(Node node) { return Parent::id(node); }
285 /// \brief The index of the given arc.
287 /// This function returns the index of the the given arc.
289 static int index(Arc arc) { return Parent::id(arc); }
291 /// \brief Number of nodes.
293 /// This function returns the number of nodes.
294 int nodeNum() const { return node_num; }
296 /// \brief Number of arcs.
298 /// This function returns the number of arcs.
299 int arcNum() const { return arc_num; }
301 /// \brief Build the digraph copying another digraph.
303 /// This function builds the digraph copying another digraph of any
304 /// kind. It can be called more than once, but in such case, the whole
305 /// structure and all maps will be cleared and rebuilt.
307 /// This method also makes possible to copy a digraph to a StaticDigraph
308 /// structure using \ref DigraphCopy.
310 /// \param digraph An existing digraph to be copied.
311 /// \param nodeRef The node references will be copied into this map.
312 /// Its key type must be \c Digraph::Node and its value type must be
313 /// \c StaticDigraph::Node.
314 /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
316 /// \param arcRef The arc references will be copied into this map.
317 /// Its key type must be \c Digraph::Arc and its value type must be
318 /// \c StaticDigraph::Arc.
319 /// It must conform to the \ref concepts::WriteMap "WriteMap" concept.
321 /// \note If you do not need the arc references, then you could use
322 /// \ref NullMap for the last parameter. However the node references
323 /// are required by the function itself, thus they must be readable
325 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
326 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
327 if (built) Parent::clear();
328 Parent::build(digraph, nodeRef, arcRef);
331 /// \brief Clear the digraph.
333 /// This function erases all nodes and arcs from the digraph.
340 using Parent::fastFirstOut;
341 using Parent::fastNextOut;
342 using Parent::fastLastOut;
346 class OutArcIt : public Arc {
351 OutArcIt(Invalid i) : Arc(i) { }
353 OutArcIt(const StaticDigraph& digraph, const Node& node) {
354 digraph.fastFirstOut(*this, node);
355 digraph.fastLastOut(last, node);
356 if (last == *this) *this = INVALID;
359 OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
360 if (arc != INVALID) {
361 digraph.fastLastOut(last, digraph.source(arc));
365 OutArcIt& operator++() {
366 StaticDigraph::fastNextOut(*this);
367 if (last == *this) *this = INVALID;
375 Node baseNode(const OutArcIt &arc) const {
376 return Parent::source(static_cast<const Arc&>(arc));
379 Node runningNode(const OutArcIt &arc) const {
380 return Parent::target(static_cast<const Arc&>(arc));
383 Node baseNode(const InArcIt &arc) const {
384 return Parent::target(static_cast<const Arc&>(arc));
387 Node runningNode(const InArcIt &arc) const {
388 return Parent::source(static_cast<const Arc&>(arc));