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 : 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) {}
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;
131 template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
132 void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
134 if (node_num != -1) {
135 delete[] node_first_out;
136 delete[] node_first_in;
139 delete[] arc_next_out;
140 delete[] arc_next_in;
143 typedef typename Digraph::Node GNode;
144 typedef typename Digraph::Arc GArc;
146 node_num = countNodes(digraph);
147 arc_num = countArcs(digraph);
149 node_first_out = new int[node_num + 1];
150 node_first_in = new int[node_num];
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];
158 for (typename Digraph::NodeIt n(digraph); n != INVALID; ++n) {
159 nodeRef[n] = Node(node_index);
160 node_first_in[node_index] = -1;
164 ArcLess<Digraph, NodeRefMap> arcLess(digraph, nodeRef);
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) {
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;
187 arc_next_out[arc_index - 1] = -1;
189 node_first_out[source] = arc_index;
192 node_first_out[node_num] = arc_num;
197 void fastFirstOut(Arc& e, const Node& n) const {
198 e.id = node_first_out[n.id];
201 static void fastNextOut(Arc& e) {
204 void fastLastOut(Arc& e, const Node& n) const {
205 e.id = node_first_out[n.id + 1];
219 typedef DigraphExtender<StaticDigraphBase> ExtendedStaticDigraphBase;
222 class StaticDigraph : public ExtendedStaticDigraphBase {
225 typedef ExtendedStaticDigraphBase Parent;
229 using Parent::fastFirstOut;
230 using Parent::fastNextOut;
231 using Parent::fastLastOut;
235 class OutArcIt : public Arc {
240 OutArcIt(Invalid i) : Arc(i) { }
242 OutArcIt(const StaticDigraph& digraph, const Node& node) {
243 digraph.fastFirstOut(*this, node);
244 digraph.fastLastOut(last, node);
245 if (last == *this) *this = INVALID;
248 OutArcIt(const StaticDigraph& digraph, const Arc& arc) : Arc(arc) {
249 if (arc != INVALID) {
250 digraph.fastLastOut(last, digraph.source(arc));
254 OutArcIt& operator++() {
255 StaticDigraph::fastNextOut(*this);
256 if (last == *this) *this = INVALID;