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 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; }
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; }
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;
229 class StaticDigraph : public ExtendedStaticDigraphBase {
232 typedef ExtendedStaticDigraphBase Parent;
236 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
237 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
238 if (built) Parent::clear();
239 Parent::build(digraph, nodeRef, arcRef);
245 using Parent::fastFirstOut;
246 using Parent::fastNextOut;
247 using Parent::fastLastOut;
251 class OutArcIt : public Arc {
256 OutArcIt(Invalid i) : Arc(i) { }
258 OutArcIt(const StaticDigraph& digraph, const Node& node) {
259 digraph.fastFirstOut(*this, node);
260 digraph.fastLastOut(last, node);
261 if (last == *this) *this = INVALID;
264 OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
265 if (arc != INVALID) {
266 digraph.fastLastOut(last, digraph.source(arc));
270 OutArcIt& operator++() {
271 StaticDigraph::fastNextOut(*this);
272 if (last == *this) *this = INVALID;
280 Node baseNode(const OutArcIt &arc) const {
281 return Parent::source(static_cast<const Arc&>(arc));
284 Node runningNode(const OutArcIt &arc) const {
285 return Parent::target(static_cast<const Arc&>(arc));
288 Node baseNode(const InArcIt &arc) const {
289 return Parent::target(static_cast<const Arc&>(arc));
292 Node runningNode(const InArcIt &arc) const {
293 return Parent::source(static_cast<const Arc&>(arc));