boost Namespace Reference

Namespaces
namespace	detail
namespace	geometry
namespace	polygon

Classes
struct	graph_traits< KisMagneticGraph >
struct	property_map< KisLazyFillGraph, edge_index_t >
struct	property_map< KisLazyFillGraph, edge_reverse_t >
struct	property_map< KisLazyFillGraph, vertex_index_t >
struct	range_const_iterator< QPolygon >
struct	range_iterator< QPolygon >

Functions
template<class Graph , class CapacityEdgeMap , class ResidualCapacityEdgeMap , class ReverseEdgeMap , class ColorMap , class IndexMap >
property_traits< CapacityEdgeMap >::value_type	boykov_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)
template<class Graph , class CapacityEdgeMap , class ResidualCapacityEdgeMap , class ReverseEdgeMap , class IndexMap >
property_traits< CapacityEdgeMap >::value_type	boykov_kolmogorov_max_flow (Graph &g, CapacityEdgeMap cap, ResidualCapacityEdgeMap res_cap, ReverseEdgeMap rev, IndexMap idx, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink)
template<class Graph , class CapacityEdgeMap , class ResidualCapacityEdgeMap , class ReverseEdgeMap , class PredecessorMap , class ColorMap , class DistanceMap , class IndexMap >
property_traits< CapacityEdgeMap >::value_type	boykov_kolmogorov_max_flow (Graph &g, CapacityEdgeMap cap, ResidualCapacityEdgeMap res_cap, ReverseEdgeMap rev_map, PredecessorMap pre_map, ColorMap color, DistanceMap dist, IndexMap idx, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink)
template<class Graph >
property_traits< typenameproperty_map< Graph, edge_capacity_t >::const_type >::value_type	boykov_kolmogorov_max_flow (Graph &g, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink)
template<class Graph , class P , class T , class R >
property_traits< typenameproperty_map< Graph, edge_capacity_t >::const_type >::value_type	boykov_kolmogorov_max_flow (Graph &g, typename graph_traits< Graph >::vertex_descriptor src, typename graph_traits< Graph >::vertex_descriptor sink, const bgl_named_params< P, T, R > &params)

Function Documentation

boykov_kolmogorov_max_flow() [1/5]

template<class Graph , class CapacityEdgeMap , class ResidualCapacityEdgeMap , class ReverseEdgeMap , class ColorMap , class IndexMap >

property_traits< CapacityEdgeMap >::value_type boost::boykov_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 )

non-named-parameter version, some given: capacity, residual_capacity, reverse_edges, color_map and an index map. Use this if you are interested in the minimum cut, as the color map provides that info.

Definition at line 797 of file patched_boykov_kolmogorov_max_flow.hpp.

{
  typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
  std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
  std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
  return
    boykov_kolmogorov_max_flow(
      g, cap, res_cap, rev,
      make_iterator_property_map(predecessor_vec.begin(), idx),
      color,
      make_iterator_property_map(distance_vec.begin(), idx),
      idx, src, sink);
}

References boykov_kolmogorov_max_flow().

boykov_kolmogorov_max_flow() [2/5]

template<class Graph , class CapacityEdgeMap , class ResidualCapacityEdgeMap , class ReverseEdgeMap , class IndexMap >

property_traits< CapacityEdgeMap >::value_type boost::boykov_kolmogorov_max_flow	(	Graph &	g,
		CapacityEdgeMap	cap,
		ResidualCapacityEdgeMap	res_cap,
		ReverseEdgeMap	rev,
		IndexMap	idx,
		typename graph_traits< Graph >::vertex_descriptor	src,
		typename graph_traits< Graph >::vertex_descriptor	sink )

non-named-parameter version, given capacity, residual_capacity, reverse_edges, and an index map.

Definition at line 764 of file patched_boykov_kolmogorov_max_flow.hpp.

{
  typename graph_traits<Graph>::vertices_size_type n_verts = num_vertices(g);
  std::vector<typename graph_traits<Graph>::edge_descriptor> predecessor_vec(n_verts);
  std::vector<default_color_type> color_vec(n_verts);
  std::vector<typename graph_traits<Graph>::vertices_size_type> distance_vec(n_verts);
  return
    boykov_kolmogorov_max_flow(
      g, cap, res_cap, rev,
      make_iterator_property_map(predecessor_vec.begin(), idx),
      make_iterator_property_map(color_vec.begin(), idx),
      make_iterator_property_map(distance_vec.begin(), idx),
      idx, src, sink);
}

References boykov_kolmogorov_max_flow().

boykov_kolmogorov_max_flow() [3/5]

template<class Graph , class CapacityEdgeMap , class ResidualCapacityEdgeMap , class ReverseEdgeMap , class PredecessorMap , class ColorMap , class DistanceMap , class IndexMap >

property_traits< CapacityEdgeMap >::value_type boost::boykov_kolmogorov_max_flow	(	Graph &	g,
		CapacityEdgeMap	cap,
		ResidualCapacityEdgeMap	res_cap,
		ReverseEdgeMap	rev_map,
		PredecessorMap	pre_map,
		ColorMap	color,
		DistanceMap	dist,
		IndexMap	idx,
		typename graph_traits< Graph >::vertex_descriptor	src,
		typename graph_traits< Graph >::vertex_descriptor	sink )

non-named-parameter version, given everything this is the catch all version

Definition at line 719 of file patched_boykov_kolmogorov_max_flow.hpp.

{
  typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
  typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor;
 
  //as this method is the last one before we instantiate the solver, we do the concept checks here
  BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); //to have vertices(), num_vertices(),
  BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> )); //to have edges()
  BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> )); //to have source(), target() and out_edges()
  BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<CapacityEdgeMap, edge_descriptor> )); //read flow-values from edges
  BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ResidualCapacityEdgeMap, edge_descriptor> )); //write flow-values to residuals
  BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<ReverseEdgeMap, edge_descriptor> )); //read out reverse edges
  BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<PredecessorMap, vertex_descriptor> )); //store predecessor there
  BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<ColorMap, vertex_descriptor> )); //write corresponding tree
  BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<DistanceMap, vertex_descriptor> )); //write distance to source/sink
  BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<IndexMap, vertex_descriptor> )); //get index 0...|V|-1
  BOOST_ASSERT(num_vertices(g) >= 2 && src != sink);
 
  detail::bk_max_flow<
    Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap,
    PredecessorMap, ColorMap, DistanceMap, IndexMap
  > algo(g, cap, res_cap, rev_map, pre_map, color, dist, idx, src, sink);
 
  return algo.max_flow();
}

boykov_kolmogorov_max_flow() [4/5]

template<class Graph >

property_traits< typenameproperty_map< Graph, edge_capacity_t >::const_type >::value_type boost::boykov_kolmogorov_max_flow	(	Graph &	g,
		typename graph_traits< Graph >::vertex_descriptor	src,
		typename graph_traits< Graph >::vertex_descriptor	sink )

named-parameter version, none given

Definition at line 846 of file patched_boykov_kolmogorov_max_flow.hpp.

{
  bgl_named_params<int, buffer_param_t> params(0); // bogus empty param
  return boykov_kolmogorov_max_flow(g, src, sink, params);
}

References boykov_kolmogorov_max_flow().

boykov_kolmogorov_max_flow() [5/5]

template<class Graph , class P , class T , class R >

property_traits< typenameproperty_map< Graph, edge_capacity_t >::const_type >::value_type boost::boykov_kolmogorov_max_flow	(	Graph &	g,
		typename graph_traits< Graph >::vertex_descriptor	src,
		typename graph_traits< Graph >::vertex_descriptor	sink,
		const bgl_named_params< P, T, R > &	params )

named-parameter version, some given

Definition at line 823 of file patched_boykov_kolmogorov_max_flow.hpp.

{
  return
  boykov_kolmogorov_max_flow(
    g,
    choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
    choose_pmap(get_param(params, edge_residual_capacity), g, edge_residual_capacity),
    choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
    choose_pmap(get_param(params, vertex_predecessor), g, vertex_predecessor),
    choose_pmap(get_param(params, vertex_color), g, vertex_color),
    choose_pmap(get_param(params, vertex_distance), g, vertex_distance),
    choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
    src, sink);
}

References boykov_kolmogorov_max_flow().