COIN-OR::LEMON - Graph Library

Changeset 83:efafe79a88d3 in lemon-0.x for src


Ignore:
Timestamp:
02/17/04 09:59:49 (16 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@110
Message:

debuggolt valtozatok

Location:
src/work/jacint
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/preflow_push_hl.h

    r78 r83  
    11// -*- C++ -*-
    22/*
    3 preflow_push_hl.hh
     3preflow_push_hl.h
    44by jacint.
    55Runs the highest label variant of the preflow push algorithm with
     
    1414T maxflow() : returns the value of a maximum flow
    1515
    16 T flowonEdge(Edge_iterator e) : for a fixed maximum flow x it returns x(e)
    17 
    18 EdgeMap<graph_type, T> allflow() : returns the fixed maximum flow x
    19 
    20 NodeMap<graph_type, bool> mincut() : returns a
     16T flowonedge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
     17
     18Graph::EdgeMap<T> allflow() : returns the fixed maximum flow x
     19
     20Graph::NodeMap<bool> mincut() : returns a
    2121     characteristic vector of a minimum cut. (An empty level
    2222     in the algorithm gives a minimum cut.)
     
    3030#include <stack>
    3131
     32#include <list_graph.hh>
    3233#include <reverse_bfs.h>
    3334
     
    4243    typedef typename Graph::OutEdgeIt OutEdgeIt;
    4344    typedef typename Graph::InEdgeIt InEdgeIt;
    44     typedef typename Graph::EachEdgeIt EachEdgeIt;
    45    
    46 
     45   
    4746    Graph& G;
    4847    NodeIt s;
     
    5352    typename Graph::NodeMap<bool> mincutvector;
    5453
    55    
    5654  public:
    5755
    5856    preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
    5957                    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) { }
    6360
    6461
     
    6966    void run() {
    7067 
    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);     
    7372           
    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.
    8182
    8283
    8384      /*Reverse_bfs from t, to find the starting level.*/
    84 
    8585      reverse_bfs<Graph> bfs(G, t);
    8686      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
    9394      level.set(s,n);
    9495
    9596
    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)
    10299        {
    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          }
    107106        }
    108107
     
    146145                  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
    147146                  /*v becomes active.*/
     147
     148                  //std::cout<<++i;
    148149                 
    149150                  flow.set(e, flow.get(e)+excess.get(w));
     
    164165                  if (excess.get(w)==0) break;
    165166                  /*If w is not active any more, then we go on to the next Node.*/
     167                 
     168                  //std::cout<<++i;
    166169                 
    167170                } // if (capacity.get(e)-flow.get(e) > excess.get(w))
  • src/work/jacint/preflow_push_max_flow.h

    r78 r83  
    33by jacint.
    44Runs 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 that
     5that we do not push on nodes with level at least n.
     6Moreover, if a level gets empty, we set all nodes above that
    77level to level n. Hence, in the end, we arrive at a maximum preflow
    88with value of a max flow value. An empty level gives a minimum cut.
     
    1616T maxflow() : returns the value of a maximum flow
    1717
    18 NodeMap<Graph, bool> mincut(): returns a
     18NodeMap<bool> mincut(): returns a
    1919     characteristic vector of a minimum cut.
    2020*/
     
    5252  public:
    5353       
    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) { }
    5557
    5658
    5759    /*
    58       The run() function runs a modified version of the highest label preflow-push, which only
     60      The run() function runs a modified version of the
     61      highest label preflow-push, which only
    5962      finds a maximum preflow, hence giving the value of a maximum flow.
    6063    */
    6164    void run() {
    6265 
    63       typename Graph::EdgeMap<T> flow(G, 0);         //the flow value, 0 everywhere 
    64       typename Graph::NodeMap<int> level(G);         //level of Node
    65       typename Graph::NodeMap<T> excess(G);          //excess of Node
     66      typename Graph::EdgeMap<T> flow(G, 0);
     67      typename Graph::NodeMap<int> level(G);   
     68      typename Graph::NodeMap<T> excess(G);   
    6669           
    67       int n=G.nodeNum();                        //number of Nodes
     70      int n=G.nodeNum();                       
    6871      int b=n-2;
    69       /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
    70      
    71       std::vector<int> numb(n);                                //The number of Nodes on level i < n.
    72 
    73       std::vector<std::stack<NodeIt> > stack(2*n-1);    //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 n-2.
     75      */
     76     
     77      std::vector<int> numb(n);     //The number of Nodes on level i < n.
     78      std::vector<std::stack<NodeIt> > stack(2*n-1);   
     79      //Stack of the active Nodes in level i.
    7680
    7781      /*Reverse_bfs from t, to find the starting level.*/
    78 
    7982      reverse_bfs<Graph> bfs(G, t);
    8083      bfs.run();
     
    8689        }
    8790
    88       /*The level of s is fixed to n*/
    8991      level.set(s,n);
    9092
    91 
    9293      /* 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)
    9595        {
    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          }
    100102        }
    101 
    102103
    103104      /*
    104105         End of preprocessing
    105106      */
    106 
    107107
    108108
     
    115115      while (b) {
    116116
    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.*/
    118118        if (stack[b].empty()) {
    119119          --b;
Note: See TracChangeset for help on using the changeset viewer.