1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/alpar/f_ed_ka.h	Mon Feb 16 10:57:01 2004 +0000
     1.3 @@ -0,0 +1,113 @@
     1.4 +// -*- mode:c++ -*-
     1.5 +
     1.6 +#ifndef EDMONDS_KARP_HH
     1.7 +#define EDMONDS_KARP_HH
     1.8 +
     1.9 +#include <queue>
    1.10 +
    1.11 +//#include <marci_property_vector.hh>
    1.12 +
    1.13 +#include <algorithm>
    1.14 +
    1.15 +//#include <bfs_iterator.hh>
    1.16 +
    1.17 +namespace marci {
    1.18 +  template <typename Graph, typename FlowMap, typename CapacityMap>
    1.19 +  typename FlowMap::ValueType maxFlow(Graph &G,
    1.20 +				      FlowMap &f,
    1.21 +				      CapacityMap &c,
    1.22 +				      typename Graph::NodeIt s,
    1.23 +				      typename Graph::NodeIt t)
    1.24 +  { 
    1.25 +    typedef typename Graph::NodeIt NodeIt;
    1.26 +    typedef typename Graph::EdgeIt EdgeIt;
    1.27 +    typedef typename Graph::EachEdgeIt EachEdgeIt;
    1.28 +    typedef typename Graph::OutEdgeIt OutEdgeIt;
    1.29 +    typedef typename Graph::InEdgeIt InEdgeIt;
    1.30 +    typedef typename FlowMap::ValueType T;
    1.31 +    
    1.32 +    T flow_val = 0;
    1.33 +    T aug_val;
    1.34 +
    1.35 +    for(EachEdgeIt e(G);G.valid(e);G.next(e))
    1.36 +      f.set(e,0);
    1.37 +    
    1.38 +    std::queue<NodeIt> bfs_queue;
    1.39 +    typename Graph::NodeMap<int> visited(G); //0: unvisited,
    1.40 +                                             //1: reached by a forward edge
    1.41 +                                             //2: reached by a backward edge
    1.42 +                                             //3: it is node s
    1.43 +    typename Graph::NodeMap<EdgeIt> tree(G);
    1.44 +    
    1.45 +    NodeIt gn;  //FIXME: it might be too global for some people...
    1.46 +    
    1.47 +  augment:
    1.48 +    
    1.49 +    for(NodeIt n(G);G.valid(n);G.next(n))
    1.50 +      visited.set(n,0);
    1.51 +    
    1.52 +    visited.set(s,3);
    1.53 +    
    1.54 +    //There must be a better way to do this:
    1.55 +    while(!bfs_queue.empty()) bfs_queue.pop();
    1.56 +    
    1.57 +    bfs_queue.push(s);
    1.58 +    
    1.59 +    while(!bfs_queue.empty() && !visited.get(t))
    1.60 +      {
    1.61 +	NodeIt n(bfs_queue.front());
    1.62 +	for(OutEdgeIt e(G,n);G.valid(e);G.next(e))
    1.63 +	  if(f.get(e)<c.get(e) &&   //FIXME: <
    1.64 +	     !visited.get(G.bNode(e))) 
    1.65 +	    {
    1.66 +	      tree.set(G.bNode(e),e);
    1.67 +	      visited.set(G.bNode(e),1);
    1.68 +	    }
    1.69 +	for(InEdgeIt e(G,n);G.valid(e);G.next(e))
    1.70 +	  if(f.get(e)>0 &&   //FIXME: >
    1.71 +	     !visited.get(G.bNode(e))) 
    1.72 +	    {
    1.73 +	      tree.set(G.bNode(e),e);
    1.74 +	      visited.set(G.bNode(e),2);
    1.75 +	    }
    1.76 +      }
    1.77 +    
    1.78 +    if(!visited.get(t)) return flow_val;
    1.79 +
    1.80 +    // Augmenting value computation
    1.81 +    aug_val = visited.get(t)==2 ?
    1.82 +      c.get(tree.get(t))-f.get(tree.get(t)) : f.get(tree.get(t));
    1.83 +    //FIXME: I would need 'G.opposite(e,n)'
    1.84 +    gn = visited.get(t)==2 ? G.from(tree.get(t)) : G.to(tree.get(t));
    1.85 +    while(gn!=s) if(visited.get(gn)==2)
    1.86 +      {
    1.87 +	//FIXME: nonstandars. gcc extension!
    1.88 +	aug_val <?= c.get(tree.get(gn))-f.get(tree.get(gn));
    1.89 +	gn=G.from(tree.get(gn));
    1.90 +      }
    1.91 +    else {
    1.92 +      //FIXME: nonstandars. gcc extension!
    1.93 +      aug_val <?= f.get(tree.get(gn));
    1.94 +      gn=G.from(tree.get(gn));
    1.95 +    }
    1.96 +	
    1.97 +    // The augmentation itself
    1.98 +    gn = t;
    1.99 +    while(gn!=s) if(visited.get(gn)==2)
   1.100 +      {
   1.101 +	f.set(tree.get(gn),f.get(tree.get(gn))+aug_val);
   1.102 +	gn=G.from(tree.get(gn));
   1.103 +      }
   1.104 +    else {
   1.105 +      f.set(tree.get(gn),f.get(tree.get(gn))-aug_val);
   1.106 +      gn=G.from(tree.get(gn));
   1.107 +    }
   1.108 +
   1.109 +    flow_val+=aug_val;
   1.110 +
   1.111 +    goto augment;   // Vivat goto forever!
   1.112 +  }
   1.113 +  
   1.114 +} // namespace marci
   1.115 +
   1.116 +#endif //EDMONDS_KARP_HH

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/work/alpar/f_ed_ka_demo.cc	Mon Feb 16 10:57:01 2004 +0000
     2.3 @@ -0,0 +1,39 @@
     2.4 +#include <iostream>
     2.5 +#include <fstream>
     2.6 +
     2.7 +#include "../list_graph.hh"
     2.8 +#include "../marci/dimacs.hh"
     2.9 +#include "f_ed_ka.h"
    2.10 +#include "../marci/time_measure.h"
    2.11 +
    2.12 +using namespace marci;
    2.13 +
    2.14 +// Use a DIMACS max flow file as stdin.
    2.15 +// read_dimacs_demo < dimacs_max_flow_file
    2.16 +
    2.17 +int main(int, char **) {
    2.18 +  typedef ListGraph::NodeIt NodeIt;
    2.19 +  typedef ListGraph::EachEdgeIt EachEdgeIt;
    2.20 +
    2.21 +  ListGraph G;
    2.22 +  NodeIt s, t;
    2.23 +  ListGraph::EdgeMap<int> cap(G);
    2.24 +  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2.25 +
    2.26 +  std::cout << "edmonds karp demo..." << std::endl;
    2.27 +  ListGraph::EdgeMap<int> flow(G); //0 flow
    2.28 +  
    2.29 +  int ret;
    2.30 +  double pre_time=currTime();
    2.31 +  ret = maxFlow(G,flow,cap,s,t);
    2.32 +  double post_time=currTime();
    2.33 +  //std::cout << "maximum flow: "<< std::endl;
    2.34 +  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
    2.35 +  //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    2.36 +  //}
    2.37 +  //std::cout<<std::endl;
    2.38 +  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl; 
    2.39 +  std::cout << "flow value: "<< ret << std::endl;
    2.40 +
    2.41 +  return 0;
    2.42 +}