1.1 --- a/demo/Makefile.am Tue Feb 20 13:01:22 2007 +0000
1.2 +++ b/demo/Makefile.am Tue Feb 20 15:53:33 2007 +0000
1.3 @@ -1,10 +1,23 @@
1.4 EXTRA_DIST += \
1.5 demo/Makefile \
1.6 - demo/sub_graph_adaptor_demo.dim
1.7 -
1.8 + demo/sub_graph_adaptor_demo.dim \
1.9 + demo/circulation-input.lgf \
1.10 + demo/coloring.lgf \
1.11 + demo/dir_components.lgf \
1.12 + demo/disjoint_paths_demo.lgf \
1.13 + demo/graph_orientation.lgf \
1.14 + demo/partitions.lgf \
1.15 + demo/route.lgf \
1.16 + demo/sample.lgf \
1.17 + demo/simann_maxcut_demo.lgf \
1.18 + demo/strongly_connected_orientation.lgf \
1.19 + demo/sub_gad_input.lgf \
1.20 + demo/u_components.lgf
1.21 +
1.22 if WANT_DEMO
1.23
1.24 noinst_PROGRAMS += \
1.25 + demo/circulation_demo \
1.26 demo/csp_demo \
1.27 demo/dim_to_dot \
1.28 demo/dijkstra_demo \
1.29 @@ -39,6 +52,8 @@
1.30
1.31 demo_csp_demo_SOURCES = demo/csp_demo.cc
1.32
1.33 +demo_circulation_demo_SOURCES = demo/circulation_demo.cc
1.34 +
1.35 demo_dim_to_dot_SOURCES = demo/dim_to_dot.cc
1.36
1.37 demo_dijkstra_demo_SOURCES = demo/dijkstra_demo.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/demo/circulation-input.lgf Tue Feb 20 15:53:33 2007 +0000
2.3 @@ -0,0 +1,165 @@
2.4 +@nodeset
2.5 +coordinates_x coordinates_y delta label
2.6 +-396.638 -311.798 0 0
2.7 +154.409 -214.714 -13 1
2.8 +-378.119 -135.808 0 2
2.9 +-138.182 -58.0452 0 3
2.10 +55 -76.1018 0 4
2.11 +-167.302 169.88 0 5
2.12 +71.6876 38.7452 0 6
2.13 +-328.784 257.777 0 7
2.14 +354.242 67.9628 13 8
2.15 +147 266 0 9
2.16 +@edgeset
2.17 + label lo_cap up_cap
2.18 +0 1 0 0 20
2.19 +0 2 1 0 0
2.20 +1 1 2 0 3
2.21 +1 2 3 0 8
2.22 +1 3 4 0 8
2.23 +2 5 5 0 5
2.24 +3 2 6 0 5
2.25 +3 5 7 0 5
2.26 +3 6 8 0 5
2.27 +4 3 9 0 3
2.28 +5 7 10 0 3
2.29 +5 6 11 0 10
2.30 +5 8 12 0 10
2.31 +6 8 13 0 8
2.32 +8 9 14 0 20
2.33 +8 1 15 0 5
2.34 +9 5 16 0 5
2.35 +@gui
2.36 +<arrow_pos>
2.37 + <item>
2.38 + <first>0</first>
2.39 + <second>
2.40 + <x>-121.114</x><y>-263.256</y>
2.41 + </second>
2.42 + </item>
2.43 + <item>
2.44 + <first>1</first>
2.45 + <second>
2.46 + <x>-387.378</x><y>-223.803</y>
2.47 + </second>
2.48 + </item>
2.49 + <item>
2.50 + <first>2</first>
2.51 + <second>
2.52 + <x>253.622</x><y>-301.284</y>
2.53 + </second>
2.54 + </item>
2.55 + <item>
2.56 + <first>3</first>
2.57 + <second>
2.58 + <x>-111.855</x><y>-175.261</y>
2.59 + </second>
2.60 + </item>
2.61 + <item>
2.62 + <first>4</first>
2.63 + <second>
2.64 + <x>8.1134</x><y>-136.379</y>
2.65 + </second>
2.66 + </item>
2.67 + <item>
2.68 + <first>5</first>
2.69 + <second>
2.70 + <x>-272.71</x><y>17.0361</y>
2.71 + </second>
2.72 + </item>
2.73 + <item>
2.74 + <first>6</first>
2.75 + <second>
2.76 + <x>-258.151</x><y>-96.9267</y>
2.77 + </second>
2.78 + </item>
2.79 + <item>
2.80 + <first>7</first>
2.81 + <second>
2.82 + <x>-152.742</x><y>55.9176</y>
2.83 + </second>
2.84 + </item>
2.85 + <item>
2.86 + <first>8</first>
2.87 + <second>
2.88 + <x>-33.2474</x><y>-9.64996</y>
2.89 + </second>
2.90 + </item>
2.91 + <item>
2.92 + <first>9</first>
2.93 + <second>
2.94 + <x>-41.5912</x><y>-67.0735</y>
2.95 + </second>
2.96 + </item>
2.97 + <item>
2.98 + <first>10</first>
2.99 + <second>
2.100 + <x>-248.043</x><y>213.829</y>
2.101 + </second>
2.102 + </item>
2.103 + <item>
2.104 + <first>11</first>
2.105 + <second>
2.106 + <x>-47.8072</x><y>104.313</y>
2.107 + </second>
2.108 + </item>
2.109 + <item>
2.110 + <first>12</first>
2.111 + <second>
2.112 + <x>93.4701</x><y>118.922</y>
2.113 + </second>
2.114 + </item>
2.115 + <item>
2.116 + <first>13</first>
2.117 + <second>
2.118 + <x>212.965</x><y>53.354</y>
2.119 + </second>
2.120 + </item>
2.121 + <item>
2.122 + <first>14</first>
2.123 + <second>
2.124 + <x>250.621</x><y>166.981</y>
2.125 + </second>
2.126 + </item>
2.127 + <item>
2.128 + <first>15</first>
2.129 + <second>
2.130 + <x>254.326</x><y>-73.3755</y>
2.131 + </second>
2.132 + </item>
2.133 + <item>
2.134 + <first>16</first>
2.135 + <second>
2.136 + <x>-10.1511</x><y>217.94</y>
2.137 + </second>
2.138 + </item>
2.139 +</arrow_pos>
2.140 +<active_nodemaps>
2.141 + <item>
2.142 + <first>0</first>
2.143 + <second></second>
2.144 + </item>
2.145 + <item>
2.146 + <first>1</first>
2.147 + <second>delta</second>
2.148 + </item>
2.149 + <item>
2.150 + <first>2</first>
2.151 + <second>label</second>
2.152 + </item>
2.153 +</active_nodemaps>
2.154 +<active_edgemaps>
2.155 + <item>
2.156 + <first>0</first>
2.157 + <second>up_cap</second>
2.158 + </item>
2.159 + <item>
2.160 + <first>1</first>
2.161 + <second></second>
2.162 + </item>
2.163 + <item>
2.164 + <first>2</first>
2.165 + <second>up_cap</second>
2.166 + </item>
2.167 +</active_edgemaps>
2.168 +@end
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/demo/circulation_demo.cc Tue Feb 20 15:53:33 2007 +0000
3.3 @@ -0,0 +1,108 @@
3.4 +/* -*- C++ -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library
3.7 + *
3.8 + * Copyright (C) 2003-2006
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +///\ingroup demos
3.23 +///\file
3.24 +///\brief Demonstrating the usage of LEMON's General Flow algorithm
3.25 +///
3.26 +/// This demo program reads a general network circulation problem from the
3.27 +/// file 'circulation-input.lgf', runs the preflow based algorithm for
3.28 +/// finding a feasible solution and writes the output
3.29 +/// to 'circulation-input.lgf'
3.30 +///
3.31 +/// \include circulation_demo.cc
3.32 +
3.33 +#include <iostream>
3.34 +
3.35 +#include <lemon/list_graph.h>
3.36 +#include <lemon/circulation.h>
3.37 +#include <lemon/graph_reader.h>
3.38 +#include <lemon/graph_writer.h>
3.39 +
3.40 +using namespace lemon;
3.41 +
3.42 +
3.43 +int main (int, char*[])
3.44 +{
3.45 +
3.46 + typedef ListGraph Graph;
3.47 + typedef Graph::Node Node;
3.48 + typedef Graph::NodeIt NodeIt;
3.49 + typedef Graph::Edge Edge;
3.50 + typedef Graph::EdgeIt EdgeIt;
3.51 + typedef Graph::EdgeMap<int> EdgeMap;
3.52 + typedef Graph::NodeMap<int> NodeMap;
3.53 + typedef Graph::NodeMap<double> DNodeMap;
3.54 +
3.55 + Graph g;
3.56 + EdgeMap lo(g);
3.57 + EdgeMap up(g);
3.58 + EdgeMap x(g);
3.59 + NodeMap delta(g);
3.60 + NodeMap nid(g);
3.61 + EdgeMap eid(g);
3.62 + DNodeMap cx(g);
3.63 + DNodeMap cy(g);
3.64 +
3.65 + GraphReader<Graph>("circulation-input.lgf", g).
3.66 + readEdgeMap("lo_cap", lo).
3.67 + readEdgeMap("up_cap", up).
3.68 + readNodeMap("delta", delta).
3.69 + readEdgeMap("label", eid).
3.70 + readNodeMap("label", nid).
3.71 + readNodeMap("coordinates_x", cx).
3.72 + readNodeMap("coordinates_y", cy).
3.73 + run();
3.74 +
3.75 + Circulation<Graph,int> gen(g,lo,up,delta,x);
3.76 + int ret=gen.run();
3.77 + if(ret==-1)
3.78 + {
3.79 + std::cout << "\nA feasible flow has been found.\n";
3.80 + if(!gen.checkX(x)) std::cerr << "Oops!!!\n";
3.81 + GraphWriter<Graph>("circulation-output.lgf", g).
3.82 + writeEdgeMap("lo_cap", lo).
3.83 + writeEdgeMap("up_cap", up).
3.84 + writeEdgeMap("flow", x).
3.85 + writeNodeMap("delta", delta).
3.86 + writeEdgeMap("label", eid).
3.87 + writeNodeMap("label", nid).
3.88 + writeNodeMap("coordinates_x", cx).
3.89 + writeNodeMap("coordinates_y", cy).
3.90 + run();
3.91 + }
3.92 + else {
3.93 + std::cout << "\nThere is no such a flow\n";
3.94 + Graph::NodeMap<int> bar(g);
3.95 + gen.barrier(bar,ret);
3.96 + if(!gen.checkBarrier(bar)) std::cerr << "Dual Oops!!!\n";
3.97 +
3.98 + GraphWriter<Graph>("circulation-output.lgf", g).
3.99 + writeEdgeMap("lo_cap", lo).
3.100 + writeEdgeMap("up_cap", up).
3.101 + writeNodeMap("barrier", bar).
3.102 + writeNodeMap("delta", delta).
3.103 + writeEdgeMap("label", eid).
3.104 + writeNodeMap("label", nid).
3.105 + writeNodeMap("coordinates_x", cx).
3.106 + writeNodeMap("coordinates_y", cy).
3.107 + run();
3.108 + }
3.109 + std::cout << "The output is written to file 'circulation-output.lgf'\n\n";
3.110 +
3.111 +}
4.1 --- a/lemon/Makefile.am Tue Feb 20 13:01:22 2007 +0000
4.2 +++ b/lemon/Makefile.am Tue Feb 20 15:53:33 2007 +0000
4.3 @@ -33,6 +33,7 @@
4.4 endif
4.5
4.6 lemon_HEADERS += \
4.7 + lemon/circulation.h \
4.8 lemon/bellman_ford.h \
4.9 lemon/bfs.h \
4.10 lemon/bin_heap.h \
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/lemon/circulation.h Tue Feb 20 15:53:33 2007 +0000
5.3 @@ -0,0 +1,299 @@
5.4 +/* -*- C++ -*-
5.5 + * lemon/preflow_matching.h - Part of LEMON, a generic C++ optimization library
5.6 + *
5.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
5.9 + *
5.10 + * Permission to use, modify and distribute this software is granted
5.11 + * provided that this copyright notice appears in all copies. For
5.12 + * precise terms see the accompanying LICENSE file.
5.13 + *
5.14 + * This software is provided "AS IS" with no warranty of any kind,
5.15 + * express or implied, and with no claim as to its suitability for any
5.16 + * purpose.
5.17 + *
5.18 + */
5.19 +
5.20 +#ifndef LEMON_CIRCULATION_H
5.21 +#define LEMON_CIRCULATION_H
5.22 +
5.23 +#include <lemon/graph_utils.h>
5.24 +#include <iostream>
5.25 +#include <queue>
5.26 +#include <lemon/tolerance.h>
5.27 +#include <lemon/elevator.h>
5.28 +
5.29 +///\ingroup flowalgs
5.30 +///\file
5.31 +///\brief Push-prelabel algorithm for finding a feasible circulation.
5.32 +///
5.33 +namespace lemon {
5.34 +
5.35 + ///Preflow algorithm for the Network Circulation Problem.
5.36 +
5.37 + ///\ingroup flowalgs
5.38 + ///This class implements a preflow algorithm
5.39 + ///for the Network Circulation Problem.
5.40 + ///The exact formulation of this problem is the following.
5.41 + /// \f[\sum_{e\in\rho(v)}x(e)-\sum_{e\in\delta(v)}x(e)\leq delta(v)\quad \forall v\in V \f]
5.42 + /// \f[ lo(e)\leq x(e) \leq up(e) \quad \forall e\in E \f]
5.43 + ///
5.44 + template<class Graph,
5.45 + class Value,
5.46 + class FlowMap=typename Graph::template EdgeMap<Value>,
5.47 + class LCapMap=typename Graph::template EdgeMap<Value>,
5.48 + class UCapMap=LCapMap,
5.49 + class DeltaMap=typename Graph::template NodeMap<Value>
5.50 + >
5.51 + class Circulation {
5.52 + typedef typename Graph::Node Node;
5.53 + typedef typename Graph::NodeIt NodeIt;
5.54 + typedef typename Graph::Edge Edge;
5.55 + typedef typename Graph::EdgeIt EdgeIt;
5.56 + typedef typename Graph::InEdgeIt InEdgeIt;
5.57 + typedef typename Graph::OutEdgeIt OutEdgeIt;
5.58 +
5.59 +
5.60 + const Graph &_g;
5.61 + int _node_num;
5.62 +
5.63 + const LCapMap &_lo;
5.64 + const UCapMap &_up;
5.65 + const DeltaMap &_delta;
5.66 + FlowMap &_x;
5.67 + Tolerance<Value> _tol;
5.68 + Elevator<Graph,typename Graph::Node> _levels;
5.69 + typename Graph::template NodeMap<Value> _excess;
5.70 +
5.71 + public:
5.72 + ///\e
5.73 + Circulation(const Graph &g,const LCapMap &lo,const UCapMap &up,
5.74 + const DeltaMap &delta,FlowMap &x) :
5.75 + _g(g),
5.76 + _node_num(countNodes(g)),
5.77 + _lo(lo),_up(up),_delta(delta),_x(x),
5.78 + _levels(g,_node_num),
5.79 + _excess(g)
5.80 + {
5.81 + }
5.82 +
5.83 + private:
5.84 +
5.85 + void addExcess(Node n,Value v)
5.86 + {
5.87 + if(_tol.positive(_excess[n]+=v))
5.88 + {
5.89 + if(!_levels.active(n)) _levels.activate(n);
5.90 + }
5.91 + else if(_levels.active(n)) _levels.deactivate(n);
5.92 + }
5.93 +
5.94 + void init()
5.95 + {
5.96 +
5.97 + _x=_lo;
5.98 +
5.99 + for(NodeIt n(_g);n!=INVALID;++n) _excess[n]=-_delta[n];
5.100 +
5.101 + for(EdgeIt e(_g);e!=INVALID;++e)
5.102 + {
5.103 + _excess[_g.target(e)]+=_x[e];
5.104 + _excess[_g.source(e)]-=_x[e];
5.105 + }
5.106 +
5.107 + _levels.initStart();
5.108 + for(NodeIt n(_g);n!=INVALID;++n)
5.109 + _levels.initAddItem(n);
5.110 + _levels.initFinish();
5.111 + for(NodeIt n(_g);n!=INVALID;++n)
5.112 + if(_tol.positive(_excess[n]))
5.113 + _levels.activate(n);
5.114 + }
5.115 +
5.116 + public:
5.117 + ///Check if \c x is a feasible circulation
5.118 + template<class FT>
5.119 + bool checkX(FT &x) {
5.120 + for(EdgeIt e(_g);e!=INVALID;++e)
5.121 + if(x[e]<_lo[e]||x[e]>_up[e]) return false;
5.122 + for(NodeIt n(_g);n!=INVALID;++n)
5.123 + {
5.124 + Value dif=_delta[n];
5.125 + for(InEdgeIt e(_g,n);e!=INVALID;++e) dif-=x[e];
5.126 + for(OutEdgeIt e(_g,n);e!=INVALID;++e) dif+=x[e];
5.127 + if(_tol.negative(dif)) return false;
5.128 + }
5.129 + return true;
5.130 + };
5.131 + ///Check if the default \c x is a feasible circulation
5.132 + bool checkX() { return checkX(_x); }
5.133 +
5.134 + ///Chech if \c bar is a real barrier
5.135 +
5.136 + ///Chech if \c bar is a real barrier
5.137 + ///\sa barrier()
5.138 + template<class GT>
5.139 + bool checkBarrier(GT &bar)
5.140 + {
5.141 + Value delta=0;
5.142 + for(NodeIt n(_g);n!=INVALID;++n)
5.143 + if(bar[n])
5.144 + delta+=_delta[n];
5.145 + for(EdgeIt e(_g);e!=INVALID;++e)
5.146 + {
5.147 + Node s=_g.source(e);
5.148 + Node t=_g.target(e);
5.149 + if(bar[s]&&!bar[t]) delta+=_up[e];
5.150 + else if(bar[t]&&!bar[s]) delta-=_lo[e];
5.151 + }
5.152 + return _tol.negative(delta);
5.153 + }
5.154 + ///Chech whether or not the last execution provides a barrier
5.155 +
5.156 + ///Chech whether or not the last execution provides a barrier
5.157 + ///\sa barrier()
5.158 + bool checkBarrier()
5.159 + {
5.160 + typename Graph:: template NodeMap<bool> bar(_g);
5.161 + barrier(bar);
5.162 + return checkBarrier(bar);
5.163 + }
5.164 + ///Run the algorithm
5.165 +
5.166 + ///This function runs the algorithm.
5.167 + ///\return This function returns -1 if it found a feasible circulation.
5.168 + /// nonnegative values (including 0) mean that no feasible solution is
5.169 + /// found. In this case the return value means an "empty level".
5.170 + ///
5.171 + ///\sa barrier()
5.172 + int run()
5.173 + {
5.174 + init();
5.175 +
5.176 +#ifdef LEMON_CIRCULATION_DEBUG
5.177 + for(NodeIt n(_g);n!=INVALID;++n)
5.178 + std::cerr<< _levels[n] << ' ';
5.179 + std::cerr << std::endl;
5.180 +#endif
5.181 + Node act;
5.182 + Node bact=INVALID;
5.183 + Node last_activated=INVALID;
5.184 + while((act=_levels.highestActive())!=INVALID) {
5.185 + int actlevel=_levels[act];
5.186 + int tlevel;
5.187 + int mlevel=_node_num;
5.188 + Value exc=_excess[act];
5.189 + Value fc;
5.190 +
5.191 +#ifdef LEMON_CIRCULATION_DEBUG
5.192 + for(NodeIt n(_g);n!=INVALID;++n)
5.193 + std::cerr<< _levels[n] << ' ';
5.194 + std::cerr << std::endl;
5.195 + std::cerr << "Process node " << _g.id(act)
5.196 + << " on level " << actlevel
5.197 + << " with excess " << exc
5.198 + << std::endl;
5.199 +#endif
5.200 + for(OutEdgeIt e(_g,act);e!=INVALID; ++e)
5.201 + if((fc=_up[e]-_x[e])>0)
5.202 + if((tlevel=_levels[_g.target(e)])<actlevel)
5.203 + if(fc<=exc) {
5.204 + _x[e]=_up[e];
5.205 + addExcess(_g.target(e),fc);
5.206 + exc-=fc;
5.207 +#ifdef LEMON_CIRCULATION_DEBUG
5.208 + std::cerr << " Push " << fc
5.209 + << " toward " << _g.id(_g.target(e)) << std::endl;
5.210 +#endif
5.211 + }
5.212 + else {
5.213 + _x[e]+=exc;
5.214 + addExcess(_g.target(e),exc);
5.215 + //exc=0;
5.216 + _excess[act]=0;
5.217 + _levels.deactivate(act);
5.218 +#ifdef LEMON_CIRCULATION_DEBUG
5.219 + std::cerr << " Push " << exc
5.220 + << " toward " << _g.id(_g.target(e)) << std::endl;
5.221 + std::cerr << " Deactivate\n";
5.222 +#endif
5.223 + goto next_l;
5.224 + }
5.225 + else if(tlevel<mlevel) mlevel=tlevel;
5.226 +
5.227 + for(InEdgeIt e(_g,act);e!=INVALID; ++e)
5.228 + if((fc=_x[e]-_lo[e])>0)
5.229 + if((tlevel=_levels[_g.source(e)])<actlevel)
5.230 + if(fc<=exc) {
5.231 + _x[e]=_lo[e];
5.232 + addExcess(_g.source(e),fc);
5.233 + exc-=fc;
5.234 +#ifdef LEMON_CIRCULATION_DEBUG
5.235 + std::cerr << " Push " << fc
5.236 + << " toward " << _g.id(_g.source(e)) << std::endl;
5.237 +#endif
5.238 + }
5.239 + else {
5.240 + _x[e]-=exc;
5.241 + addExcess(_g.source(e),exc);
5.242 + //exc=0;
5.243 + _excess[act]=0;
5.244 + _levels.deactivate(act);
5.245 +#ifdef LEMON_CIRCULATION_DEBUG
5.246 + std::cerr << " Push " << exc
5.247 + << " toward " << _g.id(_g.source(e)) << std::endl;
5.248 + std::cerr << " Deactivate\n";
5.249 +#endif
5.250 + goto next_l;
5.251 + }
5.252 + else if(tlevel<mlevel) mlevel=tlevel;
5.253 +
5.254 + _excess[act]=exc;
5.255 + if(!_tol.positive(exc)) _levels.deactivate(act);
5.256 + else if(mlevel==_node_num) {
5.257 + _levels.liftHighestActiveTo(_node_num);
5.258 +#ifdef LEMON_CIRCULATION_DEBUG
5.259 + std::cerr << " Lift to level " << _node_num << std::endl;
5.260 +#endif
5.261 + return _levels.onLevel(_node_num-1)==0?_node_num-1:actlevel;
5.262 + }
5.263 + else {
5.264 + _levels.liftHighestActiveTo(mlevel+1);
5.265 +#ifdef LEMON_CIRCULATION_DEBUG
5.266 + std::cerr << " Lift to level " << mlevel+1 << std::endl;
5.267 +#endif
5.268 + if(_levels.onLevel(actlevel)==0)
5.269 + return actlevel;
5.270 + }
5.271 + next_l:
5.272 + ;
5.273 + }
5.274 +#ifdef LEMON_CIRCULATION_DEBUG
5.275 + std::cerr << "Feasible flow found.\n";
5.276 +#endif
5.277 + return -1;
5.278 + }
5.279 +
5.280 + ///Return a barrier
5.281 +
5.282 + ///Barrier is a set \e B of nodes for which
5.283 + /// \f[ \sum_{v\in B}delta(v)<\sum_{e\in\rho(B)}lo(e)-\sum_{e\in\delta(B)}up(e) \f]
5.284 + ///holds. The existence of a set with this property prooves that a feasible
5.285 + ///flow cannot exists.
5.286 + ///\pre The run() must have been executed, and its return value was -1.
5.287 + ///\sa checkBarrier()
5.288 + ///\sa run()
5.289 + template<class GT>
5.290 + void barrier(GT &bar,int empty_level=-1)
5.291 + {
5.292 + if(empty_level==-1)
5.293 + for(empty_level=0;_levels.onLevel(empty_level);empty_level++) ;
5.294 + for(NodeIt n(_g);n!=INVALID;++n)
5.295 + bar[n] = _levels[n]>empty_level;
5.296 + }
5.297 +
5.298 + };
5.299 +
5.300 +}
5.301 +
5.302 +#endif