Changeset 83:efafe79a88d3 in lemon0.x
 Timestamp:
 02/17/04 09:59:49 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@110
 Location:
 src/work/jacint
 Files:

 2 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 n2.*/ 77 78 std::vector<std::stack<NodeIt> > stack(2*n1); //Stack of the active Nodes in level i. 79 80 73 int n=G.nodeNum(); 74 int b=n2; 75 /* 76 b is a bound on the highest level of an active node. 77 In the beginning it is at most n2. 78 */ 79 80 std::vector<std::stack<NodeIt> > stack(2*n1); 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)) 
src/work/jacint/preflow_push_max_flow.h
r78 r83 3 3 by jacint. 4 4 Runs a preflow push algorithm with the modification, 5 that we do not push on Nodes with level at least n.6 Moreover, if a level gets empty, we .set all Nodes above that5 that we do not push on nodes with level at least n. 6 Moreover, if a level gets empty, we set all nodes above that 7 7 level to level n. Hence, in the end, we arrive at a maximum preflow 8 8 with value of a max flow value. An empty level gives a minimum cut. … … 16 16 T maxflow() : returns the value of a maximum flow 17 17 18 NodeMap< Graph,bool> mincut(): returns a18 NodeMap<bool> mincut(): returns a 19 19 characteristic vector of a minimum cut. 20 20 */ … … 52 52 public: 53 53 54 preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { } 54 preflow_push_max_flow ( Graph& _G, NodeIt _s, NodeIt _t, 55 typename Graph::EdgeMap<T>& _capacity) : 56 G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { } 55 57 56 58 57 59 /* 58 The run() function runs a modified version of the highest label preflowpush, which only 60 The run() function runs a modified version of the 61 highest label preflowpush, which only 59 62 finds a maximum preflow, hence giving the value of a maximum flow. 60 63 */ 61 64 void run() { 62 65 63 typename Graph::EdgeMap<T> flow(G, 0); //the flow value, 0 everywhere64 typename Graph::NodeMap<int> level(G); //level of Node65 typename Graph::NodeMap<T> excess(G); //excess of Node66 typename Graph::EdgeMap<T> flow(G, 0); 67 typename Graph::NodeMap<int> level(G); 68 typename Graph::NodeMap<T> excess(G); 66 69 67 int n=G.nodeNum(); //number of Nodes70 int n=G.nodeNum(); 68 71 int b=n2; 69 /*b is a bound on the highest level of an active Node. In the beginning it is at most n2.*/ 70 71 std::vector<int> numb(n); //The number of Nodes on level i < n. 72 73 std::vector<std::stack<NodeIt> > stack(2*n1); //Stack of the active Nodes in level i. 74 75 72 /* 73 b is a bound on the highest level of an active Node. 74 In the beginning it is at most n2. 75 */ 76 77 std::vector<int> numb(n); //The number of Nodes on level i < n. 78 std::vector<std::stack<NodeIt> > stack(2*n1); 79 //Stack of the active Nodes in level i. 76 80 77 81 /*Reverse_bfs from t, to find the starting level.*/ 78 79 82 reverse_bfs<Graph> bfs(G, t); 80 83 bfs.run(); … … 86 89 } 87 90 88 /*The level of s is fixed to n*/89 91 level.set(s,n); 90 92 91 92 93 /* Starting flow. It is everywhere 0 at the moment. */ 93 94 for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) 94 for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e) 95 95 { 96 NodeIt w=G.head(i); 97 flow.set(i, capacity.get(i)); 98 stack[bfs.dist(w)].push(w); 99 excess.set(w, capacity.get(i)); 96 if ( capacity.get(e) > 0 ) { 97 NodeIt w=G.head(e); 98 flow.set(e, capacity.get(e)); 99 stack[level.get(w)].push(w); 100 excess.set(w, excess.get(w)+capacity.get(e)); 101 } 100 102 } 101 102 103 103 104 /* 104 105 End of preprocessing 105 106 */ 106 107 107 108 108 … … 115 115 while (b) { 116 116 117 /*We decrease the bound if there is no active Node of level b.*/117 /*We decrease the bound if there is no active node of level b.*/ 118 118 if (stack[b].empty()) { 119 119 b;
Note: See TracChangeset
for help on using the changeset viewer.