CPP/Boost/BGL/MaxFlow

From ProgrammingExamples
< CPP
Jump to: navigation, search

MaxFlow.cpp

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>
 
 
using namespace boost;
 
typedef int EdgeWeightType;
 
typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
typedef adjacency_list < vecS, vecS, directedS,
  property < vertex_name_t, std::string,
    property < vertex_index_t, long,
      property < vertex_color_t, boost::default_color_type,
        property < vertex_distance_t, long,
          property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
 
  property < edge_capacity_t, EdgeWeightType,
    property < edge_residual_capacity_t, EdgeWeightType,
      property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
 
Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1,
                                Traits::vertex_descriptor &v2,
                                property_map < Graph, edge_reverse_t >::type &rev,
                                const double capacity,
                                Graph &g);
 
int main(int, char*[])
{
  Graph g; //a graph with 0 vertices
 
  property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
 
  //add a source and sink node, and store them in s and t, respectively
  Traits::vertex_descriptor v0 = add_vertex(g);
  Traits::vertex_descriptor v1 = add_vertex(g);
  Traits::vertex_descriptor v2 = add_vertex(g);
  Traits::vertex_descriptor v3 = add_vertex(g);
 
  /*
  AddEdge(v0, v1, rev, 6.0, g);
  AddEdge(v0, v2, rev, 5.0, g);
  AddEdge(v1, v2, rev, 8.0, g);
  AddEdge(v2, v3, rev, 7.0, g);
  */
  AddEdge(v0, v1, rev, 6, g);
  AddEdge(v0, v2, rev, 5, g);
  AddEdge(v1, v3, rev, 8, g);
  AddEdge(v2, v3, rev, 7, g);
 
  //find min cut
  EdgeWeightType flow = boykov_kolmogorov_max_flow(g, v0, v3); // a list of sources will be returned in s, and a list of sinks will be returned in t
  //EdgeWeightType flow = push_relabel_max_flow(g, v0, v3); // a list of sources will be returned in s, and a list of sinks will be returned in t
  //EdgeWeightType flow = edmunds_karp_max_flow(g, v0, v3); // a list of sources will be returned in s, and a list of sinks will be returned in t
 
  std::cout << "Max flow is: " << flow << std::endl;
 
  property_map<Graph, edge_capacity_t>::type
		  capacity = get(edge_capacity, g);
  property_map<Graph, edge_residual_capacity_t>::type
		  residual_capacity = get(edge_residual_capacity, g);
 
 
  graph_traits<Graph>::vertex_iterator u_iter, u_end;
  graph_traits<Graph>::out_edge_iterator ei, e_end;
  for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
	  for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
		  if (capacity[*ei] > 0)
			  std::cout << "Source: " << *u_iter << " destination: " << target(*ei, g) << " capacity: "  << capacity[*ei] << "residual cap: " << residual_capacity[*ei] << " used capacity: "
					  << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
 
 return 0;
}
 
Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1, Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type &rev, const double capacity, Graph &g)
{
  Traits::edge_descriptor e1 = add_edge(v1, v2, g).first;
  Traits::edge_descriptor e2 = add_edge(v2, v1, g).first;
  put(edge_capacity, g, e1, capacity);
  put(edge_capacity, g, e2, capacity);
 
  rev[e1] = e2;
  rev[e2] = e1;
}
 
  /*
  //find min cut
  kolmogorov_max_flow
		  (Graph& g,
		    CapacityEdgeMap cap,
    ResidualCapacityEdgeMap res_cap,
    ReverseEdgeMap rev,
    ColorMap color,
    IndexMap idx,
    typename graph_traits<Graph>::vertex_descriptor src,
    typename graph_traits<Graph>::vertex_descriptor sink)
  {
  */

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
 
project(MaxFlow)
 
set(Boost_USE_MULTITHREADED ON) # which is the default
find_package(Boost 1.46)
 
include_directories(${Boost_INCLUDE_DIRS})
 
add_executable(MaxFlow MaxFlow.cpp)