# Changeset 109:fc5982b39e10 in lemon-0.x for src/work

Ignore:
Timestamp:
02/21/04 22:01:22 (17 years ago)
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@144
Message:

Flows with test files. The best is preflow.h

Location:
src/work/jacint
Files:
12 added
4 deleted
3 edited

Unmodified
Added
Removed
• ## src/work/jacint/preflow_hl2.h

 r105 by jacint. Runs the highest label variant of the preflow push algorithm with running time O(n^2\sqrt(m)), with the 'empty level' and with the heuristic that the bound b on the active nodes is not increased only when b=0, when we put b=2*n-2. 'A' is a parameter for the empty_level heuristic Member functions: void run() : runs the algorithm The following functions should be used after run() was already run. T maxflow() : returns the value of a maximum flow T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) FlowMap allflow() : returns the fixed maximum flow x void mincut(CutMap& M) : sets M to the characteristic vector of a running time O(n^2\sqrt(m)). Heuristics: gap: we iterate through the nodes for finding the nodes above the gap and under level n. So it is quite slow. numb: we maintain the number of nodes in level i. highest label 'A' is a parameter for the gap, we only upgrade the nodes to level n, if the gap is under A*n. The constructor runs the algorithm. Members: T maxFlow() : returns the value of a maximum flow T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) FlowMap Flow() : returns the fixed maximum flow x void minCut(CutMap& M) : sets M to the characteristic vector of a minimum cut. M should be a map of bools initialized to false. void min_mincut(CutMap& M) : sets M to the characteristic vector of the void minMinCut(CutMap& M) : sets M to the characteristic vector of the minimum min cut. M should be a map of bools initialized to false. void max_mincut(CutMap& M) : sets M to the characteristic vector of the void maxMinCut(CutMap& M) : sets M to the characteristic vector of the maximum min cut. M should be a map of bools initialized to false. #define PREFLOW_HL2_H #define A 1 #define A .9 #include template , typename CapMap=typename Graph::EdgeMap, typename IntMap=typename Graph::NodeMap, typename TMap=typename Graph::NodeMap > typename FlowMap=typename Graph::EdgeMap, typename CapMap=typename Graph::EdgeMap > class preflow_hl2 { preflow_hl2(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } void run() { bool no_end=true; G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { int n=G.nodeNum(); int b=n-2; /* b is a bound on the highest level of an active node. In the beginning it is at most n-2. */ IntMap level(G,n); TMap excess(G); typename Graph::NodeMap level(G,n); typename Graph::NodeMap excess(G); std::vector numb(n); /* } } level.set(s,n); } } /* End of preprocessing /* Push/relabel on the highest level active nodes. */ */ /*While there exists an active node.*/ while (b) { if ( stack[b].empty() ) { if ( b==1 ) { if ( !no_end ) break; else { b=2*n-2; no_end=false; } } if ( stack[b].empty() ) { --b; } else { no_end=true; NodeIt w=stack[b].top();        //w is a highest label active node. stack[b].pop(); int lev=level.get(w); int exc=excess.get(w); int newlevel=2*n;      //In newlevel we bound the next level of w. //  if ( level.get(w) < n ) { //Nem tudom ez mukodik-e continue; } NodeIt w=stack[b].top(); stack[b].pop(); int lev=level.get(w); T exc=excess.get(w); int newlevel=2*n;      //In newlevel we bound the next level of w. for(OutEdgeIt e=G.template first(w); e.valid(); ++e) { /*v becomes active.*/ int cap=capacity.get(e); int flo=flow.get(e); int remcap=cap-flo; T cap=capacity.get(e); T flo=flow.get(e); T remcap=cap-flo; if ( remcap >= exc ) { /*v becomes active.*/ int flo=flow.get(e); T flo=flow.get(e); if ( flo >= exc ) { } // if w still has excess after the out edge for cycle excess.set(w, exc); excess.set(w, exc); /* Relabel */ if ( exc > 0 ) { //now 'lev' is the old level of w level.set(w,++newlevel); /* Relabel */ if ( lev < n ) { --numb[lev]; if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. for (EachNodeIt v=G.template first(); v.valid() ; ++v) { if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); } for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; if ( newlevel < n ) newlevel=n; } else { if ( newlevel < n ) ++numb[newlevel]; } } if ( exc > 0 ) { //now 'lev' is the old level of w level.set(w,++newlevel); if ( lev < n ) { --numb[lev]; if ( !numb[lev] && lev < A*n ) {  //If the level of w gets empty. for (EachNodeIt v=G.template first(); v.valid() ; ++v) { if (level.get(v) > lev && level.get(v) < n ) level.set(v,n); } for (int i=lev+1 ; i!=n ; ++i) numb[i]=0; if ( newlevel < n ) newlevel=n; } else { if ( newlevel < n ) ++numb[newlevel]; } } stack[newlevel].push(w); } } // if stack[b] is nonempty stack[newlevel].push(w); b=newlevel; } } // while(b) value = excess.get(t); /*Max flow value.*/ */ T maxflow() { T maxFlow() { return value; } /* For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). For the maximum flow x found by the algorithm, it returns the flow value on edge e, i.e. x(e). */ T flowonedge(EdgeIt e) { T flowOnEdge(const EdgeIt e) { return flow.get(e); } */ FlowMap allflow() { FlowMap Flow() { return flow; } template void mincut(CutMap& M) { void minCut(CutMap& M) { std::queue queue; NodeIt w=queue.front(); queue.pop(); for(OutEdgeIt e=G.template first(w) ; e.valid(); ++e) { NodeIt v=G.head(e); M.set(v, true); } } } } } template void max_mincut(CutMap& M) { void maxMinCut(CutMap& M) { std::queue queue; template void min_mincut(CutMap& M) { mincut(M); void minMinCut(CutMap& M) { minCut(M); } }; }//namespace hugo }//namespace marci #endif
• ## src/work/jacint/preflow_hl3.h

 r105 preflow_hl3.h by jacint. Runs the highest label variant of the preflow push algorithm with running time O(n^2\sqrt(m)), with the felszippantos 'empty level' and with the two-phase heuristic: if there is no active node of level at most n, then we go into phase 1, do a bfs from s, and flow the excess back to s. In phase 1 we shift everything downwards by n. 'A' is a parameter for the empty_level heuristic Member functions: void run() : runs the algorithm The following functions should be used after run() was already run. T maxflow() : returns the value of a maximum flow T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) FlowMap allflow() : returns the fixed maximum flow x void mincut(CutMap& M) : sets M to the characteristic vector of a Heuristics: suck gap : if there is a gap, then we put all nodes reachable from the relabelled node to level n 2 phase highest label The constructor runs the algorithm. Members: T maxFlow() : returns the value of a maximum flow T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) FlowMap Flow() : returns the fixed maximum flow x void minCut(CutMap& M) : sets M to the characteristic vector of a minimum cut. M should be a map of bools initialized to false. void min_mincut(CutMap& M) : sets M to the characteristic vector of the void minMinCut(CutMap& M) : sets M to the characteristic vector of the minimum min cut. M should be a map of bools initialized to false. void max_mincut(CutMap& M) : sets M to the characteristic vector of the void maxMinCut(CutMap& M) : sets M to the characteristic vector of the maximum min cut. M should be a map of bools initialized to false. #ifndef PREFLOW_HL3_H #define PREFLOW_HL3_H #define A 1 #include #include #include //for test namespace hugo { template , typename CapMap=typename Graph::EdgeMap, typename IntMap=typename Graph::NodeMap, typename TMap=typename Graph::NodeMap > typename FlowMap=typename Graph::EdgeMap, typename CapMap=typename Graph::EdgeMap > class preflow_hl3 { public: double time; //for test preflow_hl3(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } void run() { G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { bool phase=0; int n=G.nodeNum(); */ IntMap level(G,n); TMap excess(G); typename Graph::NodeMap level(G,n); typename Graph::NodeMap excess(G); std::vector numb(n); if ( phase ) break; phase=1; time=currTime(); level.set(s,0); else { NodeIt w=stack[b].top();        //w is a highest label active node. NodeIt w=stack[b].top(); stack[b].pop(); int lev=level.get(w); int exc=excess.get(w); int newlevel=n;                 //In newlevel we bound the next level of w. T exc=excess.get(w); int newlevel=n;          //bound on the next level of w. for(OutEdgeIt e=G.template first(w); e.valid(); ++e) { /*v becomes active.*/ int cap=capacity.get(e); int flo=flow.get(e); int remcap=cap-flo; T cap=capacity.get(e); T flo=flow.get(e); T remcap=cap-flo; if ( remcap >= exc ) { /*v becomes active.*/ int flo=flow.get(e); T flo=flow.get(e); if ( flo >= exc ) { */ T maxflow() { T maxFlow() { return value; } /* For the maximum flow x found by the algorithm, it returns the flow value on Edge e, i.e. x(e). For the maximum flow x found by the algorithm, it returns the flow value on edge e, i.e. x(e). */ T flowonedge(EdgeIt e) { T flowOnEdge(EdgeIt e) { return flow.get(e); } */ FlowMap allflow() { FlowMap Flow() { return flow; } template void mincut(CutMap& M) { void minCut(CutMap& M) { std::queue queue; template void max_mincut(CutMap& M) { void maxMinCut(CutMap& M) { std::queue queue; template void min_mincut(CutMap& M) { mincut(M); void minMinCut(CutMap& M) { minCut(M); } }; }//namespace hugo }//namespace #endif
• ## src/work/jacint/preflow_hl4.h

 r105 // -*- C++ -*- /* preflow_hl4.h preflow_h5.h by jacint. Runs the two phase highest label preflow push algorithm. In phase 0 we maintain in a list the nodes in level i < n, and we maintain a bound k on the max level i < n containing a node, so we can do the gap heuristic fast. Phase 1 is the same. (The algorithm is the same as preflow.hl3, the only diff is that here we use the gap heuristic with the list of the nodes on level i, and not a bfs form the upgraded node.) In phase 1 we shift everything downwards by n. Member functions: void run() : runs the algorithm The following functions should be used after run() was already run. T maxflow() : returns the value of a maximum flow T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) FlowMap allflow() : returns a maximum flow void allflow(FlowMap& _flow ) : returns a maximum flow void mincut(CutMap& M) : sets M to the characteristic vector of a minimum cut. M should be a map of bools initialized to false. void min_mincut(CutMap& M) : sets M to the characteristic vector of the Heuristics: 2 phase gap list 'level_list' on the nodes on level i implemented by hand highest label relevel: in phase 0, after BFS*n relabels, it runs a reverse bfs from t in the res graph to relevel the nodes reachable from t. BFS is initialized to 20 Due to the last heuristic, this algorithm is quite fast on very sparse graphs, but relatively bad on even the dense graphs. 'NodeMap cut' is a member, in this way we can count it fast, after the algorithm was run. The constructor runs the algorithm. Members: T maxFlow() : returns the value of a maximum flow T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e) FlowMap Flow() : returns the fixed maximum flow x void Flow(FlowMap& _flow ) : returns the fixed maximum flow x void minMinCut(CutMap& M) : sets M to the characteristic vector of the minimum min cut. M should be a map of bools initialized to false. void max_mincut(CutMap& M) : sets M to the characteristic vector of the void maxMinCut(CutMap& M) : sets M to the characteristic vector of the maximum min cut. M should be a map of bools initialized to false. void minCut(CutMap& M) : fast function, sets M to the characteristic vector of a minimum cut. Different member from the other preflow_hl-s (here we have a member 'NodeMap cut'). CutMap minCut() : fast function, giving the characteristic vector of a minimum cut. */ #define PREFLOW_HL4_H #define BFS 20 #include #include #include #include   //for test namespace hugo { template , typename CutMap=typename Graph::NodeMap, typename CapMap=typename Graph::EdgeMap > class preflow_hl4 { FlowMap flow; CapMap& capacity; CutMap cut; T value; public: double time; preflow_hl4(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity) : G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity) { } void run() { bool phase=0; G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), cut(G, false) { bool phase=0;   //phase 0 is the 1st phase, phase 1 is the 2nd int n=G.nodeNum(); int relabel=0; int heur=(int)BFS*n; int k=n-2; int b=k; typename Graph::NodeMap level(G,n); typename Graph::NodeMap excess(G); std::vector > stack(n); std::vector active(n); typename Graph::NodeMap next(G); //Stack of the active nodes in level i < n. //We use it in both phases. for(InEdgeIt e=G.template first(v); e.valid(); ++e) { NodeIt w=G.tail(e); if ( level.get(w) == n ) { if ( level.get(w) == n && w !=s ) { bfs_queue.push(w); NodeIt first=level_list[l]; NodeIt w=G.head(e); if ( level.get(w) < n ) { if ( excess.get(w) == 0 && w!=t ) stack[level.get(w)].push(w); if ( excess.get(w) == 0 && w!=t ) { next.set(w,active[level.get(w)]); active[level.get(w)]=w; } flow.set(e, c); excess.set(w, excess.get(w)+c); */ phase=1; //Now have a min cut. for( EachNodeIt v=G.template first(); v.valid(); ++v) if (level.get(v) >= n ) cut.set(v,true); time=currTime(); level.set(s,0); std::queue bfs_queue; bfs_queue.push(u); level.set(u, l); if ( excess.get(u) > 0 ) stack[l].push(u); if ( excess.get(u) > 0 ) { next.set(u,active[l]); active[l]=u; } } } bfs_queue.push(u); level.set(u, l); if ( excess.get(u) > 0 ) stack[l].push(u); if ( excess.get(u) > 0 ) { next.set(u,active[l]); active[l]=u; } } } if ( stack[b].empty() ) --b; if ( active[b] == 0 ) --b; else { NodeIt w=stack[b].top();        //w is a highest label active node. stack[b].pop(); NodeIt w=active[b]; active[b]=next.get(w); int lev=level.get(w); T exc=excess.get(w); int newlevel=n;          //In newlevel we bound the next level of w. int newlevel=n;          //bound on the next level of w. for(OutEdgeIt e=G.template first(w); e.valid(); ++e) { /*Push is allowed now*/ if ( excess.get(v)==0 && v!=t && v!=s ) stack[level.get(v)].push(v); /*v becomes active.*/ if ( excess.get(v)==0 && v!=t && v!=s )  { int lev_v=level.get(v); next.set(v,active[lev_v]); active[lev_v]=v; } T cap=capacity.get(e); /*Push is allowed now*/ if ( excess.get(v)==0 && v!=t && v!=s ) stack[level.get(v)].push(v); /*v becomes active.*/ if ( excess.get(v)==0 && v!=t && v!=s ) { int lev_v=level.get(v); next.set(v,active[lev_v]); active[lev_v]=v; } T flo=flow.get(e); if ( phase ) { level.set(w,++newlevel); stack[newlevel].push(w); next.set(w,active[newlevel]); active[newlevel]=w; b=newlevel; } else { } } //unlacing ends level.set(w,++newlevel); stack[newlevel].push(w); next.set(w,active[newlevel]); active[newlevel]=w; b=newlevel; if ( k < newlevel ) ++k; } } ++relabel; if ( relabel >= heur ) { relabel=0; b=n-2; k=b; for ( int i=1; i!=n; ++i ) { active[i]=0; level_list[i]=0; } //bfs from t in the res graph to relevel the nodes for( EachNodeIt v=G.template first(); v.valid(); ++v) level.set(v,n); level.set(t,0); std::queue bfs_queue; bfs_queue.push(t); while (!bfs_queue.empty()) { NodeIt v=bfs_queue.front(); bfs_queue.pop(); int l=level.get(v)+1; for(InEdgeIt e=G.template first(v); e.valid(); ++e) { if ( capacity.get(e) == flow.get(e) ) continue; NodeIt u=G.tail(e); if ( level.get(u) == n ) { bfs_queue.push(u); level.set(u, l); if ( excess.get(u) > 0 ) { next.set(u,active[l]); active[l]=u; } NodeIt first=level_list[l]; if ( first != 0 ) left.set(first,w); right.set(w,first); left.set(w,0); level_list[l]=w; } } for(OutEdgeIt e=G.template first(v); e.valid(); ++e) { if ( 0 == flow.get(e) ) continue; NodeIt u=G.head(e); if ( level.get(u) == n ) { bfs_queue.push(u); level.set(u, l); if ( excess.get(u) > 0 ) { next.set(u,active[l]); active[l]=u; } NodeIt first=level_list[l]; if ( first != 0 ) left.set(first,w); right.set(w,first); left.set(w,0); level_list[l]=w; } } } level.set(s,n); } } //phase 0 } // if ( exc > 0 ) } // if stack[b] is nonempty */ T maxflow() { T maxFlow() { return value; } */ T flowonedge(EdgeIt e) { T flowOnEdge(EdgeIt e) { return flow.get(e); } FlowMap allflow() { FlowMap Flow() { return flow; } void allflow(FlowMap& _flow ) { void Flow(FlowMap& _flow ) { for(EachNodeIt v=G.template first() ; v.valid(); ++v) _flow.set(v,flow.get(v)); */ template void mincut(CutMap& M) { template void minMinCut(_CutMap& M) { std::queue queue; */ template void max_mincut(CutMap& M) { template void maxMinCut(_CutMap& M) { std::queue queue; template void min_mincut(CutMap& M) { mincut(M); } template void minCut(_CutMap& M) { for( EachNodeIt v=G.template first(); v.valid(); ++v) M.set(v, cut.get(v)); } CutMap minCut() { return cut; } }; }//namespace hugo }//namespace marci #endif
Note: See TracChangeset for help on using the changeset viewer.