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 #include<lemon/bits/invalid.h>
20 #include<lemon/topology.h>
23 /// \ingroup graph_prop
27 ///This file provides an Euler tour iterator and ways to check
28 ///if a graph is euler.
33 ///Euler iterator for directed graphs.
35 /// \ingroup graph_prop
36 ///This iterator converts to the \c Edge type of the graph and using
37 ///operator ++ it provides an Euler tour of a \e directed
38 ///graph (if there exists).
41 ///if the given graph if Euler (i.e it has only one nontrivial component
42 ///and the in-degree is equal to the out-degree for all nodes),
43 ///the following code will put the edges of \c g
44 ///to the vector \c et according to an
45 ///Euler tour of \c g.
47 /// std::vector<ListGraph::Edge> et;
48 /// for(EulerIt<ListGraph> e(g),e!=INVALID;++e)
51 ///If \c g is not Euler then the resulted tour will not be full or closed.
53 ///\todo Test required
57 typedef typename Graph::Node Node;
58 typedef typename Graph::NodeIt NodeIt;
59 typedef typename Graph::Edge Edge;
60 typedef typename Graph::EdgeIt EdgeIt;
61 typedef typename Graph::OutEdgeIt OutEdgeIt;
62 typedef typename Graph::InEdgeIt InEdgeIt;
65 typename Graph::template NodeMap<OutEdgeIt> nedge;
66 std::list<Edge> euler;
72 ///\param _g A directed graph.
73 ///\param start The starting point of the tour. If it is not given
74 /// the tour will start from the first node.
75 EulerIt(const Graph &_g,typename Graph::Node start=INVALID)
78 if(start==INVALID) start=NodeIt(g);
79 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
80 while(nedge[start]!=INVALID) {
81 euler.push_back(nedge[start]);
82 Node next=g.target(nedge[start]);
89 operator Edge() { return euler.empty()?INVALID:euler.front(); }
90 bool operator==(Invalid) { return euler.empty(); }
91 bool operator!=(Invalid) { return !euler.empty(); }
93 ///Next edge of the tour
94 EulerIt &operator++() {
95 Node s=g.target(euler.front());
97 //This produces a warning.Strange.
98 //std::list<Edge>::iterator next=euler.begin();
99 typename std::list<Edge>::iterator next=euler.begin();
100 while(nedge[s]!=INVALID) {
101 euler.insert(next,nedge[s]);
102 Node n=g.target(nedge[s]);
108 ///Postfix incrementation
110 ///\warning This incrementation
111 ///returns an \c Edge, not an \ref EulerIt, as one may
121 ///Euler iterator for undirected graphs.
123 /// \ingroup graph_prop
124 ///This iterator converts to the \c Edge (or \c UEdge)
125 ///type of the graph and using
126 ///operator ++ it provides an Euler tour of an undirected
127 ///graph (if there exists).
130 ///if the given graph if Euler (i.e it has only one nontrivial component
131 ///and the degree of each node is even),
132 ///the following code will print the edge IDs according to an
133 ///Euler tour of \c g.
135 /// for(UEulerIt<ListUGraph> e(g),e!=INVALID;++e) {
136 /// std::cout << g.id(UEdge(e)) << std::eol;
139 ///Although the iterator provides an Euler tour of an undirected graph,
140 ///in order to indicate the direction of the tour, UEulerIt
141 ///returns directed edges (that convert to the undirected ones, of course).
143 ///If \c g is not Euler then the resulted tour will not be full or closed.
145 ///\todo Test required
146 template<class Graph>
149 typedef typename Graph::Node Node;
150 typedef typename Graph::NodeIt NodeIt;
151 typedef typename Graph::Edge Edge;
152 typedef typename Graph::UEdge UEdge;
153 typedef typename Graph::EdgeIt EdgeIt;
154 typedef typename Graph::OutEdgeIt OutEdgeIt;
155 typedef typename Graph::InEdgeIt InEdgeIt;
158 typename Graph::template NodeMap<OutEdgeIt> nedge;
159 typename Graph::template UEdgeMap<bool> visited;
160 std::list<Edge> euler;
166 ///\param _g An undirected graph.
167 ///\param start The starting point of the tour. If it is not given
168 /// the tour will start from the first node.
169 UEulerIt(const Graph &_g,typename Graph::Node start=INVALID)
170 : g(_g), nedge(g), visited(g,false)
172 if(start==INVALID) start=NodeIt(g);
173 for(NodeIt n(g);n!=INVALID;++n) nedge[n]=OutEdgeIt(g,n);
174 while(nedge[start]!=INVALID) {
175 euler.push_back(nedge[start]);
176 visited[nedge[start]]=true;
177 Node next=g.target(nedge[start]);
180 while(nedge[start]!=INVALID && visited[nedge[start]]) ++nedge[start];
185 operator Edge() const { return euler.empty()?INVALID:euler.front(); }
187 operator UEdge() const { return euler.empty()?INVALID:euler.front(); }
189 bool operator==(Invalid) const { return euler.empty(); }
191 bool operator!=(Invalid) const { return !euler.empty(); }
193 ///Next edge of the tour
194 UEulerIt &operator++() {
195 Node s=g.target(euler.front());
197 typename std::list<Edge>::iterator next=euler.begin();
199 while(nedge[s]!=INVALID) {
200 while(nedge[s]!=INVALID && visited[nedge[s]]) ++nedge[s];
201 if(nedge[s]==INVALID) break;
203 euler.insert(next,nedge[s]);
204 visited[nedge[s]]=true;
205 Node n=g.target(nedge[s]);
213 ///Postfix incrementation
215 ///\warning This incrementation
216 ///returns an \c Edge, not an \ref UEulerIt, as one may
227 ///Checks if the graph is Euler
229 /// \ingroup graph_prop
230 ///Checks if the graph is Euler. It works for both directed and
231 ///undirected graphs.
232 ///\note By definition, a directed graph is called \e Euler if
233 ///and only if connected and the number of it is incoming and outgoing edges
234 ///are the same for each node.
235 ///Similarly, an undirected graph is called \e Euler if
236 ///and only if it is connected and the number of incident edges is even
237 ///for each node. <em>Therefore, there are graphs which are not Euler, but
238 ///still have an Euler tour</em>.
239 ///\todo Test required
240 template<class Graph>
244 typename enable_if<UndirectedTagIndicator<Graph>,bool>::type
245 euler(const Graph &g)
247 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
248 if(countIncEdges(g,n)%2) return false;
251 template<class Graph>
252 typename disable_if<UndirectedTagIndicator<Graph>,bool>::type
254 euler(const Graph &g)
256 for(typename Graph::NodeIt n(g);n!=INVALID;++n)
257 if(countInEdges(g,n)!=countOutEdges(g,n)) return false;