CPP/Boost/BGL/MaxFlow - Revision history

Daviddoria: Created page with '==MaxFlow.cpp== #include #include #include #include
2012-05-03T21:01:46Z

Created page with '==MaxFlow.cpp== <source lang="cpp"> #include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/boykov_kolmogorov_max_flow.hpp> #include <boost/graph/push…'

New page
==MaxFlow.cpp==
<source lang="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)
{
*/

</source>

==CMakeLists.txt==
<source lang="cmake">
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)

</source>