COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
04/05/04 16:19:02 (18 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@416
Message:

graph_wrappers ...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/experiment/edmonds_karp_1.h

    r281 r298  
    249249
    250250
    251   template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
     251  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    252252  class MaxFlow {
    253253  protected:
    254     typedef GraphWrapper GW;
    255     typedef typename GW::Node Node;
    256     typedef typename GW::Edge Edge;
    257     typedef typename GW::EdgeIt EdgeIt;
    258     typedef typename GW::OutEdgeIt OutEdgeIt;
    259     typedef typename GW::InEdgeIt InEdgeIt;
    260     //const Graph* G;
    261     //GW gw;
    262     const GW* g;
     254    typedef typename Graph::Node Node;
     255    typedef typename Graph::Edge Edge;
     256    typedef typename Graph::EdgeIt EdgeIt;
     257    typedef typename Graph::OutEdgeIt OutEdgeIt;
     258    typedef typename Graph::InEdgeIt InEdgeIt;
     259    const Graph* g;
    263260    Node s;
    264261    Node t;
    265262    FlowMap* flow;
    266263    const CapacityMap* capacity;
    267     typedef ResGraphWrapper<const GW, Number, FlowMap, CapacityMap > ResGW;
     264    typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
    268265    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    269266    typedef typename ResGW::Edge ResGWEdge;
    270267  public:
    271268
    272     MaxFlow(const GW& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
     269    MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
    273270      g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
    274271
     
    646643      return _augment;
    647644    }
    648 
    649 //     bool augmentOnBlockingFlow2() {
    650 //       bool _augment=false;
    651 
    652 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
    653 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
    654 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
    655 //       typedef typename EAugGraph::Edge EAugEdge;
    656 
    657 //       EAugGraph res_graph(*G, *flow, *capacity);
    658 
    659 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    660 //       BfsIterator5<
    661 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    662 //      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    663 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    664      
    665 //       bfs.pushAndSetReached(s);
    666 
    667 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
    668 //      NodeMap<int>& dist=res_graph.dist;
    669 
    670 //       while ( !bfs.finished() ) {
    671 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    672 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    673 //        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    674 //      }
    675 //      ++bfs; 
    676 //       } //computing distances from s in the residual graph
    677 
    678 //       bool __augment=true;
    679 
    680 //       while (__augment) {
    681 
    682 //      __augment=false;
    683 //      //computing blocking flow with dfs
    684 //      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    685 //      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    686 //        dfs(res_graph);
    687 //      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
    688 //      pred.set(s, EAugEdge(INVALID));
    689 //      //invalid iterators for sources
    690 
    691 //      typename EAugGraph::NodeMap<Number> free(res_graph);
    692 
    693 //      dfs.pushAndSetReached(s);
    694 //      while (!dfs.finished()) {
    695 //        ++dfs;
    696 //        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
    697 //          if (dfs.isBNodeNewlyReached()) {
    698          
    699 //            typename EAugGraph::Node v=res_graph.aNode(dfs);
    700 //            typename EAugGraph::Node w=res_graph.bNode(dfs);
    701 
    702 //            pred.set(w, EAugOutEdgeIt(dfs));
    703 //            if (res_graph.valid(pred.get(v))) {
    704 //              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
    705 //            } else {
    706 //              free.set(w, res_graph.free(dfs));
    707 //            }
    708              
    709 //            if (w==t) {
    710 //              __augment=true;
    711 //              _augment=true;
    712 //              break;
    713 //            }
    714 //          } else {
    715 //            res_graph.erase(dfs);
    716 //          }
    717 //        }
    718 
    719 //      }
    720 
    721 //      if (__augment) {
    722 //        typename EAugGraph::Node n=t;
    723 //        Number augment_value=free.get(t);
    724 //        while (res_graph.valid(pred.get(n))) {
    725 //          EAugEdge e=pred.get(n);
    726 //          res_graph.augment(e, augment_value);
    727 //          n=res_graph.tail(e);
    728 //          if (res_graph.free(e)==0)
    729 //            res_graph.erase(e);
    730 //        }
    731 //      }
    732      
    733 //       }
    734            
    735 //       return _augment;
    736 //     }
    737645
    738646    void run() {
Note: See TracChangeset for help on using the changeset viewer.