Changeset 83:efafe79a88d3 in lemon-0.x for src/work/jacint/preflow_push_hl.h
- Timestamp:
- 02/17/04 09:59:49 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@110
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/preflow_push_hl.h
r78 r83 1 1 // -*- C++ -*- 2 2 /* 3 preflow_push_hl.h h3 preflow_push_hl.h 4 4 by jacint. 5 5 Runs the highest label variant of the preflow push algorithm with … … 14 14 T maxflow() : returns the value of a maximum flow 15 15 16 T flowon Edge(Edge_iteratore) : for a fixed maximum flow x it returns x(e)17 18 EdgeMap<graph_type,T> allflow() : returns the fixed maximum flow x19 20 NodeMap<graph_type,bool> mincut() : returns a16 T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e) 17 18 Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x 19 20 Graph::NodeMap<bool> mincut() : returns a 21 21 characteristic vector of a minimum cut. (An empty level 22 22 in the algorithm gives a minimum cut.) … … 30 30 #include <stack> 31 31 32 #include <list_graph.hh> 32 33 #include <reverse_bfs.h> 33 34 … … 42 43 typedef typename Graph::OutEdgeIt OutEdgeIt; 43 44 typedef typename Graph::InEdgeIt InEdgeIt; 44 typedef typename Graph::EachEdgeIt EachEdgeIt; 45 46 45 47 46 Graph& G; 48 47 NodeIt s; … … 53 52 typename Graph::NodeMap<bool> mincutvector; 54 53 55 56 54 public: 57 55 58 56 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, 59 57 typename Graph::EdgeMap<T>& _capacity) : 60 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { } 61 62 58 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), 59 mincutvector(_G, true) { } 63 60 64 61 … … 69 66 void run() { 70 67 71 typename Graph::NodeMap<int> level(G); //level of Node 72 typename Graph::NodeMap<T> excess(G); //excess of Node 68 int i=0;//DELME 69 70 typename Graph::NodeMap<int> level(G); 71 typename Graph::NodeMap<T> excess(G); 73 72 74 int n=G.nodeNum(); //number of Nodes 75 int b=n; 76 /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/ 77 78 std::vector<std::stack<NodeIt> > stack(2*n-1); //Stack of the active Nodes in level i. 79 80 73 int n=G.nodeNum(); 74 int b=n-2; 75 /* 76 b is a bound on the highest level of an active node. 77 In the beginning it is at most n-2. 78 */ 79 80 std::vector<std::stack<NodeIt> > stack(2*n-1); 81 //Stack of the active nodes in level i. 81 82 82 83 83 84 /*Reverse_bfs from t, to find the starting level.*/ 84 85 85 reverse_bfs<Graph> bfs(G, t); 86 86 bfs.run(); 87 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) { 88 level.set(v, bfs.dist(v)); 89 //std::cout << "the level of " << v << " is " << bfs.dist(v); 90 } 91 92 /*The level of s is fixed to n*/ 87 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 88 { 89 level.set(v, bfs.dist(v)); 90 } 91 92 std::cout << "the level of t is " << bfs.dist(t);//delme 93 93 94 level.set(s,n); 94 95 95 96 96 97 98 99 /* Starting flow. It is everywhere 0 at the moment. */ 100 101 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) 97 /* Starting flow. It is everywhere 0 at the moment. */ 98 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 102 99 { 103 NodeIt w=G.head(i); 104 flow.set(i, capacity.get(i)); 105 stack[bfs.dist(w)].push(w); 106 excess.set(w, capacity.get(i)); 100 if ( capacity.get(e) > 0 ) { 101 NodeIt w=G.head(e); 102 flow.set(e, capacity.get(e)); 103 stack[level.get(w)].push(w); 104 excess.set(w, excess.get(w)+capacity.get(e)); 105 } 107 106 } 108 107 … … 146 145 if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 147 146 /*v becomes active.*/ 147 148 //std::cout<<++i; 148 149 149 150 flow.set(e, flow.get(e)+excess.get(w)); … … 164 165 if (excess.get(w)==0) break; 165 166 /*If w is not active any more, then we go on to the next Node.*/ 167 168 //std::cout<<++i; 166 169 167 170 } // if (capacity.get(e)-flow.get(e) > excess.get(w))
Note: See TracChangeset
for help on using the changeset viewer.