lemon-0.x: comparison src/work/athos/preflow

equal deleted inserted replaced

-:5a721b2fe626
+:bf79ebbdb5ea
 #include <algorithm>
 #include <list>
 #include <vector>
 //#include "pf_hiba.hh"
 //#include <marci_list_graph.hh>
-#include <marci_graph_traits.hh>
+//#include <marci_graph_traits.hh>
 #include "reverse_bfs.hh"
 using namespace std;
 namespace marci {
 template <typename graph_type, typename T>
 class preflow_push {
 //Hasznos typedef-ek
+typedef typename graph_type::NodeIt NodeIt;
+typedef typename graph_type::EdgeIt EdgeIt;
+typedef typename graph_type::EachNodeIt EachNodeIt;
+typedef typename graph_type::EachEdgeIt EachEdgeIt;
+typedef typename graph_type::OutEdgeIt OutEdgeIt;
+typedef typename graph_type::InEdgeIt InEdgeIt;
+typedef typename graph_type::SymEdgeIt SymEdgeIt;
+/*
 typedef graph_traits<graph_type>::node_iterator node_iterator;
-typedef graph_traits<graph_type>::edge_iterator edge_iterator;
+typedef graph_traits<graph_type>::EdgeIt EdgeIt;
 typedef graph_traits<graph_type>::each_node_iterator each_node_iterator;
-typedef graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
+typedef graph_traits<graph_type>::each_EdgeIt each_EdgeIt;
-typedef graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
+typedef graph_traits<graph_type>::out_EdgeIt out_EdgeIt;
-typedef graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
+typedef graph_traits<graph_type>::InEdgeIt InEdgeIt;
-typedef graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
+typedef graph_traits<graph_type>::sym_EdgeIt sym_EdgeIt;
+*/
 //---------------------------------------------
 //Parameters of the algorithm
 //---------------------------------------------
 //Fully examine an active node until excess becomes 0
 //---------------------------------------------
 private:
 //input
 graph_type& G;
-node_iterator s;
+NodeIt s;
-node_iterator t;
+NodeIt t;
-edge_property_vector<graph_type, T> &capacity;
+typename graph_type::EdgeMap<T> &capacity;
+//typename graph_type::EdgeMap<T>  &capacity;
 //output
-edge_property_vector<graph_type, T> preflow;
+//typename graph_type::EdgeMap<T>
+typename graph_type::EdgeMap<T> preflow;
 T maxflow_value;
 //auxiliary variables for computation
 int number_of_nodes;
-node_property_vector<graph_type, int> level;
-node_property_vector<graph_type, T> excess;
+typename graph_type::NodeMap<int> level;
+typename graph_type::NodeMap<T> excess;
+//node_property_vector<graph_type, int> level;
+//node_property_vector<graph_type, T> excess;
 //Number of nodes on each level
 vector<int> num_of_nodes_on_level;
 //For the FIFO implementation
-list<node_iterator> fifo_nodes;
+list<NodeIt> fifo_nodes;
 //For 'highest label' implementation
 int highest_active;
 //int second_highest_active;
-vector< list<node_iterator> > active_nodes;
+vector< list<NodeIt> > active_nodes;
 public:
 //Constructing the object using the graph, source, sink and capacity vector
 preflow_push(
 		      graph_type& _G,
-		      node_iterator _s,
+		      NodeIt _s,
-		      node_iterator _t,
+		      NodeIt _t,
-		      edge_property_vector<graph_type, T>& _capacity)
+		      typename graph_type::EdgeMap<T> & _capacity)
 : G(_G), s(_s), t(_t),
 	capacity(_capacity),
 	preflow(_G),
 	//Counting the number of nodes
-	number_of_nodes(number_of(G.first_node())),
+	//number_of_nodes(count(G.first<EachNodeIt>())),
+	number_of_nodes(G.nodeNum()),
 	level(_G),
 	excess(_G)//,
 // Default constructor: active_nodes()
 {
 //Simplest parameter settings
 }
 //Returns the value of a maximal flow
 T run();
-edge_property_vector<graph_type, T> getmaxflow(){
+typename graph_type::EdgeMap<T>  getmaxflow(){
 return preflow;
 }
 private:
 //For testing purposes only
 //Lists the node_properties
-void write_property_vector(node_property_vector<graph_type, T> a,
+void write_property_vector(typename graph_type::NodeMap<T> a,
+			       //node_property_vector<graph_type, T> a,
 			       char* prop_name="property"){
-for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
 	cout<<"Node id.: "<<G.id(i)<<", "<<prop_name<<" value: "<<a.get(i)<<endl;
 }
 cout<<endl;
 }
 //Modifies the excess of the node and makes sufficient changes
-void modify_excess(const node_iterator& a ,T v){
+void modify_excess(const NodeIt& a ,T v){
 	T old_value=excess.get(a);
-	excess.put(a,old_value+v);
+	excess.set(a,old_value+v);
 }
 //This private procedure is supposed to modify the preflow on edge j
 //by value v (which can be positive or negative as well)
 //and maintain the excess on the head and tail
 //Here we do not check whether this is possible or not
-void modify_preflow(edge_iterator j, const T& v){
+void modify_preflow(EdgeIt j, const T& v){
 //Auxiliary variable
 T old_value;
 //Modifiyng the edge
 old_value=preflow.get(j);
-preflow.put(j,old_value+v);
+preflow.set(j,old_value+v);
 //Modifiyng the head
 modify_excess(G.head(j),v);
 }
 //Gives the active node to work with
 //(depending on the implementation to be used)
-node_iterator get_active_node(){
+NodeIt get_active_node(){
 //cout<<highest_active<<endl;
 switch(implementation) {
 case impl_highest_label : {
 	while( highest_active>=0 && active_nodes[highest_active].empty() ){
 	  --highest_active;
 	}
 	if( highest_active>=0) {
-	  node_iterator a=active_nodes[highest_active].front();
+	  NodeIt a=active_nodes[highest_active].front();
 	  active_nodes[highest_active].pop_front();
 	  return a;
 	}
 	else {
-	  return node_iterator();
+	  return NodeIt();
 	}
 	break;
 }
 case impl_fifo : {
 	if( ! fifo_nodes.empty() ) {
-	  node_iterator a=fifo_nodes.front();
+	  NodeIt a=fifo_nodes.front();
 	  fifo_nodes.pop_front();
 	  return a;
 	}
 	else {
-	  return node_iterator();
+	  return NodeIt();
 	}
 	break;
 }
 }
 //
-return node_iterator();
+return NodeIt();
 }
 //Puts node 'a' among the active nodes
-void make_active(const node_iterator& a){
+void make_active(const NodeIt& a){
 //s and t never become active
 if (a!=s && a!= t){
 	switch(implementation){
 	case impl_highest_label :
 	  active_nodes[level.get(a)].push_back(a);
 }
 }
 //Changes the level of node a and make sufficent changes
-void change_level_to(node_iterator a, int new_value){
+void change_level_to(NodeIt a, int new_value){
 int seged = level.get(a);
-level.put(a,new_value);
+level.set(a,new_value);
 --num_of_nodes_on_level[seged];
 ++num_of_nodes_on_level[new_value];
 }
 //Collection of things useful (or necessary) to do before running
 void preprocess(){
 //---------------------------------------
 //Initialize parameters
 //---------------------------------------
 //Setting starting preflow, level and excess values to zero
 //This can be important, if the algorithm is run more then once
-for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
-level.put(i,0);
+level.set(i,0);
-excess.put(i,0);
+excess.set(i,0);
-	for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
+	for(OutEdgeIt j=G.template first<OutEdgeIt>(i); j.valid(); ++j)
-	  preflow.put(j, 0);
+	  preflow.set(j, 0);
 }
 num_of_nodes_on_level[0]=number_of_nodes;
 highest_active=0;
 //---------------------------------------
 //Initialize parameters
 //------------------------------------
 //Setting starting level values using reverse bfs
 reverse_bfs<graph_type> rev_bfs(G,t);
 rev_bfs.run();
 //write_property_vector(rev_bfs.dist,"rev_bfs");
-for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) {
 change_level_to(i,rev_bfs.dist(i));
 	//level.put(i,rev_bfs.dist.get(i));
 }
 //------------------------------------
 //This is the only part that uses BFS
 change_level_to(s,number_of_nodes);
 //level.put(s,number_of_nodes);
 //we push as much preflow from s as possible to start with
-for(out_edge_iterator j=G.first_out_edge(s); j.valid(); ++j){
+for(OutEdgeIt j=G.template first<OutEdgeIt>(s); j.valid(); ++j){
 	modify_preflow(j,capacity.get(j) );
 	make_active(G.head(j));
 	int lev=level.get(G.head(j));
 	if(highest_active<lev){
 	  highest_active=lev;
 }
 //If the preflow is less than the capacity on the given edge
 //then it is an edge in the residual graph
-bool is_admissible_forward_edge(out_edge_iterator j, int& new_level){
+bool is_admissible_forward_edge(OutEdgeIt j, int& new_level){
 if (capacity.get(j)>preflow.get(j)){
 	if(level.get(G.tail(j))==level.get(G.head(j))+1){
 	  return true;
 	}
 	else{
 return false;
 }
 //If the preflow is greater than 0 on the given edge
 //then the edge reversd is an edge in the residual graph
-bool is_admissible_backward_edge(in_edge_iterator j, int& new_level){
+bool is_admissible_backward_edge(InEdgeIt j, int& new_level){
 if (0<preflow.get(j)){
 	if(level.get(G.tail(j))==level.get(G.head(j))-1){
 	  return true;
 	}
 	else{
 T preflow_push<graph_type, T>::run() {
 preprocess();
 T e,v;
-node_iterator a;
+NodeIt a;
 while (a=get_active_node(), a.valid()){
 //cout<<G.id(a)<<endl;
 //write_property_vector(excess,"excess");
 //write_property_vector(level,"level");
-//Initial value for the new level for the active node we are dealing with
-int new_level=2*number_of_nodes;
 bool go_to_next_node=false;
 e = excess.get(a);
 while (!go_to_next_node){
+	//Initial value for the new level for the active node we are dealing with
+	int new_level=2*number_of_nodes;
+	//write_property_vector(excess,"excess");
+	//write_property_vector(level,"level");
+	//cout<<G.id(a)<<endl;
 	//Out edges from node a
 	{
-	  out_edge_iterator j=G.first_out_edge(a);
+	  OutEdgeIt j=G.template first<OutEdgeIt>(a);
 	  while (j.valid() && e){
 	    if (is_admissible_forward_edge(j,new_level)){
 	      v=min(e,capacity.get(j) - preflow.get(j));
 	      e -= v;
 	    ++j;
 	  }
 	}
 	//In edges to node a
 	{
-	  in_edge_iterator j=G.first_in_edge(a);
+	  InEdgeIt j=G.template first<InEdgeIt>(a);
 	  while (j.valid() && e){
 	    if (is_admissible_backward_edge(j,new_level)){
 	      v=min(e,preflow.get(j));
 	      e -= v;
 	      //New node might become active
 	if (0==e){
 	  //Saturating push
 	  go_to_next_node=true;
 	}
 	else{//If there is still excess in node a
+	  //change_level_to(a,new_level+1);
 	  //Level remains empty
 	  if (num_of_nodes_on_level[level.get(a)]==1){
 	    change_level_to(a,number_of_nodes);
 	    //go_to_next_node=True;
 	  }
 	  else{
 	    change_level_to(a,new_level+1);
 	    //increase_level(a);
 	  }
 	  switch(node_examination){
 	  case examine_to_relabel:

changeset 99	f26897fb91fd
parent 36	7d539ea6ad26
child 105	a3c73e9b9b2e