Redesigned CapacityScaling algorithm with almost the same interface.
The new version does not use the ResidualGraphAdaptor for performance reasons.
Scaling can be enabled and disabled with a parameter of the run() function.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
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
22 #include <lemon/bits/graph_extender.h>
23 #include <lemon/graph_utils.h>
27 class StaticGraphBase {
31 : node_num(-1), edge_num(0),
32 node_first_out(0), node_first_in(0),
33 edge_source(0), edge_target(0),
34 edge_next_in(0), edge_next_out(0) {}
38 delete[] node_first_out;
39 delete[] node_first_in;
42 delete[] edge_next_out;
43 delete[] edge_next_in;
48 friend class StaticGraphBase;
51 Node(int _id) : id(_id) {}
54 Node (Invalid) : id(-1) {}
55 bool operator==(const Node& node) const {return id == node.id;}
56 bool operator!=(const Node& node) const {return id != node.id;}
57 bool operator<(const Node& node) const {return id < node.id;}
61 friend class StaticGraphBase;
64 Edge(int _id) : id(_id) {}
67 Edge (Invalid) { id = -1; }
68 bool operator==(const Edge& edge) const {return id == edge.id;}
69 bool operator!=(const Edge& edge) const {return id != edge.id;}
70 bool operator<(const Edge& edge) const {return id < edge.id;}
73 Node source(const Edge& e) const { return Node(edge_source[e.id]); }
74 Node target(const Edge& e) const { return Node(edge_target[e.id]); }
76 void first(Node& n) const { n.id = node_num - 1; }
77 void next(Node& n) const { --n.id; }
79 void first(Edge& n) const { n.id = edge_num - 1; }
80 void next(Edge& n) const { --n.id; }
82 void firstOut(Edge& e, const Node& n) const {
83 e.id = node_first_out[n.id] != node_first_out[n.id + 1] ?
84 node_first_out[n.id] : -1;
86 void nextOut(Edge& e) const { e.id = edge_next_out[e.id]; }
88 void firstIn(Edge& e, const Node& n) const { e.id = node_first_in[n.id]; }
89 void nextIn(Edge& e) const { e.id = edge_next_in[e.id]; }
92 int id(const Node& n) const { return n.id; }
93 Node nodeFromId(int id) const { return Node(id); }
94 int maxNodeId() const { return node_num - 1; }
96 int id(const Edge& e) const { return e.id; }
97 Edge edgeFromId(int id) const { return Edge(id); }
98 int maxEdgeId() const { return edge_num - 1; }
100 typedef True NodeNumTag;
101 int nodeNum() const { return node_num; }
102 typedef True EdgeNumTag;
103 int edgeNum() const { return edge_num; }
107 template <typename Graph, typename NodeRefMap>
110 typedef typename Graph::Edge Edge;
112 EdgeLess(const Graph &_graph, const NodeRefMap& _nodeRef)
113 : graph(_graph), nodeRef(_nodeRef) {}
115 bool operator()(const Edge& left, const Edge& right) const {
116 return nodeRef[graph.target(left)] < nodeRef[graph.target(right)];
120 const NodeRefMap& nodeRef;
125 typedef True BuildTag;
127 template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
128 void build(const Graph& graph, NodeRefMap& nodeRef, EdgeRefMap& edgeRef) {
130 if (node_num != -1) {
131 delete[] node_first_out;
132 delete[] node_first_in;
133 delete[] edge_source;
134 delete[] edge_target;
135 delete[] edge_next_out;
136 delete[] edge_next_in;
139 typedef typename Graph::Node GNode;
140 typedef typename Graph::Edge GEdge;
142 node_num = countNodes(graph);
143 edge_num = countEdges(graph);
145 node_first_out = new int[node_num + 1];
146 node_first_in = new int[node_num];
148 edge_source = new int[edge_num];
149 edge_target = new int[edge_num];
150 edge_next_out = new int[edge_num];
151 edge_next_in = new int[edge_num];
154 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
155 nodeRef[n] = Node(node_index);
156 node_first_in[node_index] = -1;
160 EdgeLess<Graph, NodeRefMap> edgeLess(graph, nodeRef);
163 for (typename Graph::NodeIt n(graph); n != INVALID; ++n) {
164 int source = nodeRef[n].id;
165 std::vector<GEdge> edges;
166 for (typename Graph::OutEdgeIt e(graph, n); e != INVALID; ++e) {
169 if (!edges.empty()) {
170 node_first_out[source] = edge_index;
171 std::sort(edges.begin(), edges.end(), edgeLess);
172 for (typename std::vector<GEdge>::iterator it = edges.begin();
173 it != edges.end(); ++it) {
174 int target = nodeRef[graph.target(*it)].id;
175 edgeRef[*it] = Edge(edge_index);
176 edge_source[edge_index] = source;
177 edge_target[edge_index] = target;
178 edge_next_in[edge_index] = node_first_in[target];
179 node_first_in[target] = edge_index;
180 edge_next_out[edge_index] = edge_index + 1;
183 edge_next_out[edge_index - 1] = -1;
185 node_first_out[source] = edge_index;
188 node_first_out[node_num] = edge_num;
193 void fastFirstOut(Edge& e, const Node& n) const {
194 e.id = node_first_out[n.id];
197 static void fastNextOut(Edge& e) {
200 void fastLastOut(Edge& e, const Node& n) const {
201 e.id = node_first_out[n.id + 1];
215 typedef GraphExtender<StaticGraphBase> ExtendedStaticGraphBase;
218 class StaticGraph : public ExtendedStaticGraphBase {
221 typedef ExtendedStaticGraphBase Parent;
225 using Parent::fastFirstOut;
226 using Parent::fastNextOut;
227 using Parent::fastLastOut;
231 class OutEdgeIt : public Edge {
236 OutEdgeIt(Invalid i) : Edge(i) { }
238 OutEdgeIt(const StaticGraph& graph, const Node& node) {
239 graph.fastFirstOut(*this, node);
240 graph.fastLastOut(last, node);
241 if (last == *this) *this = INVALID;
244 OutEdgeIt(const StaticGraph& graph, const Edge& edge) : Edge(edge) {
245 graph.fastLastOut(last, graph.source(edge));
248 OutEdgeIt& operator++() {
249 StaticGraph::fastNextOut(*this);
250 if (last == *this) *this = INVALID;