COIN-OR::LEMON - Graph Library

Changeset 374:0fc9cd9b854a in lemon-0.x for src


Ignore:
Timestamp:
04/22/04 17:56:05 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@504
Message:
 
Location:
src/work/jacint
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/preflow.cc

    r372 r374  
    2525 
    2626  Graph::EdgeMap<int> flow(G);
    27   Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
     27  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1,1);
    2828  ts.reset();
    2929  max_flow_test.run();
     30  std::cout << "elapsed time with res: " << ts << std::endl;
     31 
     32  std::cout << "preflow demo ..." << std::endl;
     33 
     34  Graph::EdgeMap<int> flow2(G);
     35  Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow, 1,0);
     36  ts.reset();
     37  max_flow_test2.run();
    3038  std::cout << "elapsed time: " << ts << std::endl;
    3139 
  • src/work/jacint/preflowproba.h

    r372 r374  
    7171    T value;
    7272    bool constzero;
     73    bool res;
    7374
    7475    typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW;
     
    7980  public:
    8081    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
    81             FlowMap& _flow, bool _constzero ) :
    82       G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
     82            FlowMap& _flow, bool _constzero, bool _res ) :
     83      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero), res(_res) {}
    8384   
    8485   
     
    303304              int l=level[v]+1;
    304305             
    305               /*              ResInEdgeIt e;
    306               for(res_graph.first(e,s); res_graph.valid(e);
    307                   res_graph.next(e)) {
    308                 Node u=res_graph.tail(e);
    309                 if ( level[u] >= n ) {
    310                   bfs_queue.push(u);
    311                   level.set(u, l);
    312                   if ( excess[u] > 0 ) {
    313                     next.set(u,active[l]);
    314                     active[l]=u;
     306              if (res){
     307                ResInEdgeIt e;
     308                for(res_graph.first(e,v); res_graph.valid(e);
     309                    res_graph.next(e)) {
     310                  Node u=res_graph.tail(e);
     311                  if ( level[u] >= n ) {
     312                    bfs_queue.push(u);
     313                    level.set(u, l);
     314                    if ( excess[u] > 0 ) {
     315                      next.set(u,active[l]);
     316                      active[l]=u;
     317                    }
    315318                  }
    316319                }
    317                 }*/
    318                     InEdgeIt e;
    319               for(G.first(e,v); G.valid(e); G.next(e)) {
    320                 if ( capacity[e] == flow[e] ) continue;
    321                 Node u=G.tail(e);
    322                 if ( level[u] >= n ) {
    323                   bfs_queue.push(u);
    324                   level.set(u, l);
    325                   if ( excess[u] > 0 ) {
    326                     next.set(u,active[l]);
    327                     active[l]=u;
     320              } else {
     321                InEdgeIt e;
     322                for(G.first(e,v); G.valid(e); G.next(e)) {
     323                  if ( capacity[e] == flow[e] ) continue;
     324                  Node u=G.tail(e);
     325                  if ( level[u] >= n ) {
     326                    bfs_queue.push(u);
     327                    level.set(u, l);
     328                    if ( excess[u] > 0 ) {
     329                      next.set(u,active[l]);
     330                      active[l]=u;
     331                    }
     332                  }
     333                }
     334               
     335                OutEdgeIt f;
     336                for(G.first(f,v); G.valid(f); G.next(f)) {
     337                  if ( 0 == flow[f] ) continue;
     338                  Node u=G.head(f);
     339                  if ( level[u] >= n ) {
     340                    bfs_queue.push(u);
     341                    level.set(u, l);
     342                    if ( excess[u] > 0 ) {
     343                      next.set(u,active[l]);
     344                      active[l]=u;
     345                    }
    328346                  }
    329347                }
    330348              }
    331            
    332               OutEdgeIt f;
    333               for(G.first(f,v); G.valid(f); G.next(f)) {
    334                 if ( 0 == flow[f] ) continue;
    335                 Node u=G.head(f);
    336                 if ( level[u] >= n ) {
    337                   bfs_queue.push(u);
    338                   level.set(u, l);
    339                   if ( excess[u] > 0 ) {
    340                     next.set(u,active[l]);
    341                     active[l]=u;
    342                   }
    343                 }
    344                 }
    345349            }
    346350            b=n-2;
Note: See TracChangeset for help on using the changeset viewer.