#include <patched_boykov_kolmogorov_max_flow.hpp>

Public Member Functions
	bk_max_flow (Graph &g, EdgeCapacityMap cap, ResidualCapacityEdgeMap res, ReverseEdgeMap rev, PredecessorMap pre, ColorMap color, DistanceMap dist, IndexMap idx, vertex_descriptor src, vertex_descriptor sink)

tEdgeVal	max_flow ()

Protected Member Functions
void	add_active_node (vertex_descriptor v)

void	adopt ()

void	augment (edge_descriptor e)

void	augment_direct_paths ()

tEdgeVal	find_bottleneck (edge_descriptor e)

void	finish_node (vertex_descriptor v)

edge_descriptor	get_edge_to_parent (vertex_descriptor v) const

vertex_descriptor	get_next_active_node ()

tColorValue	get_tree (vertex_descriptor v) const

std::pair< edge_descriptor, bool >	grow ()

bool	has_parent (vertex_descriptor v) const

bool	has_sink_connect (vertex_descriptor v)

bool	has_source_connect (vertex_descriptor v)

bool	is_closer_to_terminal (vertex_descriptor p, vertex_descriptor q)

void	remove_active_node (vertex_descriptor v)

void	set_edge_to_parent (vertex_descriptor v, edge_descriptor f_edge_to_parent)

void	set_no_parent (vertex_descriptor v)

void	set_tree (vertex_descriptor v, tColorValue t)

Protected Attributes
tQueue	m_active_nodes

EdgeCapacityMap	m_cap_map

tQueue	m_child_orphans

DistanceMap	m_dist_map

tEdgeVal	m_flow

Graph &	m_g

iterator_property_map< std::vector< bool >::iterator, IndexMap >	m_has_parent_map

std::vector< bool >	m_has_parent_vec

iterator_property_map< std::vector< bool >::iterator, IndexMap >	m_in_active_list_map

std::vector< bool >	m_in_active_list_vec

IndexMap	m_index_map

out_edge_iterator	m_last_grow_edge_end

out_edge_iterator	m_last_grow_edge_it

vertex_descriptor	m_last_grow_vertex

std::list< vertex_descriptor >	m_orphans

PredecessorMap	m_pre_map

ResidualCapacityEdgeMap	m_res_cap_map

ReverseEdgeMap	m_rev_edge_map

vertex_descriptor	m_sink

vertex_descriptor	m_source

long	m_time

iterator_property_map< std::vector< long >::iterator, IndexMap >	m_time_map

std::vector< long >	m_time_vec

ColorMap	m_tree_map

Private Types
typedef tGraphTraits::edge_descriptor	edge_descriptor

typedef tGraphTraits::edge_iterator	edge_iterator

typedef tGraphTraits::out_edge_iterator	out_edge_iterator

typedef color_traits< tColorValue >	tColorTraits

typedef property_traits< ColorMap >::value_type	tColorValue

typedef property_traits< DistanceMap >::value_type	tDistanceVal

typedef property_traits< EdgeCapacityMap >::value_type	tEdgeVal

typedef graph_traits< Graph >	tGraphTraits

typedef boost::queue< vertex_descriptor >	tQueue

typedef tGraphTraits::vertex_descriptor	vertex_descriptor

typedef tGraphTraits::vertex_iterator	vertex_iterator

Detailed Description

template<class Graph, class EdgeCapacityMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class PredecessorMap, class ColorMap, class DistanceMap, class IndexMap>
class boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >

Definition at line 51 of file patched_boykov_kolmogorov_max_flow.hpp.

Member Typedef Documentation

◆ edge_descriptor

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

typedef tGraphTraits::edge_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::edge_descriptor

private

Definition at line 56 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ edge_iterator

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

typedef tGraphTraits::edge_iterator boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::edge_iterator

private

Definition at line 57 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ out_edge_iterator

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

typedef tGraphTraits::out_edge_iterator boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::out_edge_iterator

private

Definition at line 58 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ tColorTraits

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

typedef color_traits<tColorValue> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::tColorTraits

private

Definition at line 61 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ tColorValue

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

typedef property_traits<ColorMap>::value_type boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::tColorValue

private

Definition at line 60 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ tDistanceVal

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

typedef property_traits<DistanceMap>::value_type boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::tDistanceVal

private

Definition at line 62 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ tEdgeVal

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

typedef property_traits<EdgeCapacityMap>::value_type boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::tEdgeVal

private

Definition at line 52 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ tGraphTraits

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

typedef graph_traits<Graph> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::tGraphTraits

private

Definition at line 53 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ tQueue

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

typedef boost::queue<vertex_descriptor> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::tQueue

private

Definition at line 59 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ vertex_descriptor

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

typedef tGraphTraits::vertex_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::vertex_descriptor

private

Definition at line 55 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ vertex_iterator

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

typedef tGraphTraits::vertex_iterator boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::vertex_iterator

private

Definition at line 54 of file patched_boykov_kolmogorov_max_flow.hpp.

Constructor & Destructor Documentation

◆ bk_max_flow()

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

boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::bk_max_flow	(	Graph &	g,
		EdgeCapacityMap	cap,
		ResidualCapacityEdgeMap	res,
		ReverseEdgeMap	rev,
		PredecessorMap	pre,
		ColorMap	color,
		DistanceMap	dist,
		IndexMap	idx,
		vertex_descriptor	src,
		vertex_descriptor	sink )

inline

Definition at line 65 of file patched_boykov_kolmogorov_max_flow.hpp.

                                         :
      m_g(g),
      m_index_map(idx),
      m_cap_map(cap),
      m_res_cap_map(res),
      m_rev_edge_map(rev),
      m_pre_map(pre),
      m_tree_map(color),
      m_dist_map(dist),
      m_source(src),
      m_sink(sink),
      m_active_nodes(),
      m_in_active_list_vec(num_vertices(g), false),
      m_in_active_list_map(make_iterator_property_map(m_in_active_list_vec.begin(), m_index_map)),
      m_has_parent_vec(num_vertices(g), false),
      m_has_parent_map(make_iterator_property_map(m_has_parent_vec.begin(), m_index_map)),
      m_time_vec(num_vertices(g), 0),
      m_time_map(make_iterator_property_map(m_time_vec.begin(), m_index_map)),
      m_flow(0),
      m_time(1),
      m_last_grow_vertex(graph_traits<Graph>::null_vertex()){
        // initialize the color-map with gray-values
        vertex_iterator vi, v_end;
        for(boost::tie(vi, v_end) = vertices(m_g); vi != v_end; ++vi){
          set_tree(*vi, tColorTraits::gray());
        }
        // Initialize flow to zero which means initializing
        // the residual capacity equal to the capacity
        edge_iterator ei, e_end;
        for(boost::tie(ei, e_end) = edges(m_g); ei != e_end; ++ei) {
          put(m_res_cap_map, *ei, get(m_cap_map, *ei));
          BOOST_ASSERT(get(m_rev_edge_map, get(m_rev_edge_map, *ei)) == *ei); //check if the reverse edge map is build up properly
        }
        //init the search trees with the two terminals
        set_tree(m_source, tColorTraits::black());
        set_tree(m_sink, tColorTraits::white());
        put(m_time_map, m_source, 1);
        put(m_time_map, m_sink, 1);
      }

Member Function Documentation

◆ add_active_node()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::add_active_node ( vertex_descriptor v )

inlineprotected

adds v as an active vertex, but only if its not in the list already

Definition at line 509 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                      {
        BOOST_ASSERT(get_tree(v) != tColorTraits::gray());
        if(get(m_in_active_list_map, v)){
          if (m_last_grow_vertex == v) {
              m_last_grow_vertex = graph_traits<Graph>::null_vertex();
          }
          return;
        } else{
          put(m_in_active_list_map, v, true);
          m_active_nodes.push(v);
        }
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_tree(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_active_nodes, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_in_active_list_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_last_grow_vertex, put(), and v.

◆ adopt()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::adopt ( )

inlineprotected

rebuild search trees empty the queue of orphans, and find new parents for them or just drop them from the search trees

Definition at line 390 of file patched_boykov_kolmogorov_max_flow.hpp.

                  {
        while(!m_orphans.empty() || !m_child_orphans.empty()){
          vertex_descriptor current_node;
          if(m_child_orphans.empty()){
            //get the next orphan from the main-queue  and remove it
            current_node = m_orphans.front();
            m_orphans.pop_front();
          } else{
            current_node = m_child_orphans.front();
            m_child_orphans.pop();
          }
          if(get_tree(current_node) == tColorTraits::black()){
            //we're in the source-tree
            tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
            edge_descriptor new_parent_edge;
            out_edge_iterator ei, e_end;
            for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
              const edge_descriptor in_edge = get(m_rev_edge_map, *ei);
              BOOST_ASSERT(target(in_edge, m_g) == current_node); //we should be the target of this edge
              if(get(m_res_cap_map, in_edge) > 0){
                vertex_descriptor other_node = source(in_edge, m_g);
                if(get_tree(other_node) == tColorTraits::black() && has_source_connect(other_node)){
                  if(get(m_dist_map, other_node) < min_distance){
                    min_distance = get(m_dist_map, other_node);
                    new_parent_edge = in_edge;
                  }
                }
              }
            }
            if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
              set_edge_to_parent(current_node, new_parent_edge);
              put(m_dist_map, current_node, min_distance + 1);
              put(m_time_map, current_node, m_time);
            } else{
              put(m_time_map, current_node, 0);
              for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
                edge_descriptor in_edge = get(m_rev_edge_map, *ei);
                vertex_descriptor other_node = source(in_edge, m_g);
                if(get_tree(other_node) == tColorTraits::black() && other_node != m_source){
                  if(get(m_res_cap_map, in_edge) > 0){
                    add_active_node(other_node);
                  }
                  if(has_parent(other_node) && source(get_edge_to_parent(other_node), m_g) == current_node){
                    //we are the parent of that node
                    //it has to find a new parent, too
                    set_no_parent(other_node);
                    m_child_orphans.push(other_node);
                  }
                }
              }
              set_tree(current_node, tColorTraits::gray());
            } //no parent found
          } //source-tree-adoption
          else{
            //now we should be in the sink-tree, check that...
            BOOST_ASSERT(get_tree(current_node) == tColorTraits::white());
            out_edge_iterator ei, e_end;
            edge_descriptor new_parent_edge;
            tDistanceVal min_distance = (std::numeric_limits<tDistanceVal>::max)();
            for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
              const edge_descriptor out_edge = *ei;
              if(get(m_res_cap_map, out_edge) > 0){
                const vertex_descriptor other_node = target(out_edge, m_g);
                if(get_tree(other_node) == tColorTraits::white() && has_sink_connect(other_node))
                  if(get(m_dist_map, other_node) < min_distance){
                    min_distance = get(m_dist_map, other_node);
                    new_parent_edge = out_edge;
                  }
              }
            }
            if(min_distance != (std::numeric_limits<tDistanceVal>::max)()){
              set_edge_to_parent(current_node, new_parent_edge);
              put(m_dist_map, current_node, min_distance + 1);
              put(m_time_map, current_node, m_time);
            } else{
              put(m_time_map, current_node, 0);
              for(boost::tie(ei, e_end) = out_edges(current_node, m_g); ei != e_end; ++ei){
                const edge_descriptor out_edge = *ei;
                const vertex_descriptor other_node = target(out_edge, m_g);
                if(get_tree(other_node) == tColorTraits::white() && other_node != m_sink){
                  if(get(m_res_cap_map, out_edge) > 0){
                    add_active_node(other_node);
                  }
                  if(has_parent(other_node) && target(get_edge_to_parent(other_node), m_g) == current_node){
                    //we were it's parent, so it has to find a new one, too
                    set_no_parent(other_node);
                    m_child_orphans.push(other_node);
                  }
                }
              }
              set_tree(current_node, tColorTraits::gray());
            } //no parent found
          } //sink-tree adoption
        } //while !orphans.empty()
      } //adopt

◆ augment()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::augment ( edge_descriptor e )

inlineprotected

augments path from s->t and updates residual graph source(e, m_g) is the end of the path found in the source-tree target(e, m_g) is the beginning of the path found in the sink-tree this phase generates orphans on saturated edges, if the attached verts are from different search-trees orphans are ordered in distance to sink/source. first the farthest from the source are front_inserted into the orphans list, and after that the sink-tree-orphans are front_inserted. when going to adoption stage the orphans are popped_front, and so we process the nearest verts to the terminals first

Definition at line 310 of file patched_boykov_kolmogorov_max_flow.hpp.

                                      {
        BOOST_ASSERT(get_tree(target(e, m_g)) == tColorTraits::white());
        BOOST_ASSERT(get_tree(source(e, m_g)) == tColorTraits::black());
        BOOST_ASSERT(m_orphans.empty());
 
        const tEdgeVal bottleneck = find_bottleneck(e);
        //now we push the found flow through the path
        //for each edge we saturate we have to look for the verts that belong to that edge, one of them becomes an orphans
        //now process the connecting edge
        put(m_res_cap_map, e, get(m_res_cap_map, e) - bottleneck);
        BOOST_ASSERT(get(m_res_cap_map, e) >= 0);
        put(m_res_cap_map, get(m_rev_edge_map, e), get(m_res_cap_map, get(m_rev_edge_map, e)) + bottleneck);
 
        //now we follow the path back to the source
        vertex_descriptor current_node = source(e, m_g);
        while(current_node != m_source){
          edge_descriptor pred = get_edge_to_parent(current_node);
          const tEdgeVal new_pred_cap = get(m_res_cap_map, pred) - bottleneck;
          put(m_res_cap_map, pred, new_pred_cap);
          BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
 
          const edge_descriptor pred_rev = get(m_rev_edge_map, pred);
          put(m_res_cap_map, pred_rev, get(m_res_cap_map, pred_rev) + bottleneck);
 
          if(new_pred_cap == 0){
            set_no_parent(current_node);
            m_orphans.push_front(current_node);
          }
          current_node = source(pred, m_g);
        }
        //then go forward in the sink-tree
        current_node = target(e, m_g);
        while(current_node != m_sink){
          edge_descriptor pred = get_edge_to_parent(current_node);
          const tEdgeVal new_pred_cap = get(m_res_cap_map, pred) - bottleneck;
          put(m_res_cap_map, pred, new_pred_cap);
          BOOST_ASSERT(get(m_res_cap_map, pred) >= 0);
 
          const edge_descriptor pred_rev = get(m_rev_edge_map, pred);
          put(m_res_cap_map, pred_rev, get(m_res_cap_map, pred_rev) + bottleneck);
 
          if(new_pred_cap == 0){
            set_no_parent(current_node);
            m_orphans.push_front(current_node);
          }
          current_node = target(pred, m_g);
        }
        //and add it to the max-flow
        m_flow += bottleneck;
      }

◆ augment_direct_paths()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::augment_direct_paths ( )

inlineprotected

Definition at line 136 of file patched_boykov_kolmogorov_max_flow.hpp.

                                 {
        // in a first step, we augment all direct paths from source->NODE->sink
        // and additionally paths from source->sink. This improves especially
        // graphcuts for segmentation, as most of the nodes have source/sink
        // connects but shouldn't have an impact on other maxflow problems
        // (this is done in grow() anyway)
        out_edge_iterator ei, e_end;
        for(boost::tie(ei, e_end) = out_edges(m_source, m_g); ei != e_end; ++ei){
          edge_descriptor from_source = *ei;
          vertex_descriptor current_node = target(from_source, m_g);
          if(current_node == m_sink){
            tEdgeVal cap = get(m_res_cap_map, from_source);
            put(m_res_cap_map, from_source, 0);
            m_flow += cap;
            continue;
          }
          edge_descriptor to_sink;
          bool is_there;
          boost::tie(to_sink, is_there) = lookup_edge(current_node, m_sink, m_g);
          if(is_there){
            tEdgeVal cap_from_source = get(m_res_cap_map, from_source);
            tEdgeVal cap_to_sink = get(m_res_cap_map, to_sink);
            if(cap_from_source > cap_to_sink){
              set_tree(current_node, tColorTraits::black());
              add_active_node(current_node);
              set_edge_to_parent(current_node, from_source);
              put(m_dist_map, current_node, 1);
              put(m_time_map, current_node, 1);
              // add stuff to flow and update residuals. we don't need to
              // update reverse_edges, as incoming/outgoing edges to/from
              // source/sink don't count for max-flow
              put(m_res_cap_map, from_source, get(m_res_cap_map, from_source) - cap_to_sink);
              put(m_res_cap_map, to_sink, 0);
              m_flow += cap_to_sink;
            } else if(cap_to_sink > 0){
              set_tree(current_node, tColorTraits::white());
              add_active_node(current_node);
              set_edge_to_parent(current_node, to_sink);
              put(m_dist_map, current_node, 1);
              put(m_time_map, current_node, 1);
              // add stuff to flow and update residuals. we don't need to update
              // reverse_edges, as incoming/outgoing edges to/from source/sink
              // don't count for max-flow
              put(m_res_cap_map, to_sink, get(m_res_cap_map, to_sink) - cap_from_source);
              put(m_res_cap_map, from_source, 0);
              m_flow += cap_from_source;
            }
          } else if(get(m_res_cap_map, from_source)){
            // there is no sink connect, so we can't augment this path, but to
            // avoid adding m_source to the active nodes, we just activate this
            // node and set the appropriate things
            set_tree(current_node, tColorTraits::black());
            set_edge_to_parent(current_node, from_source);
            put(m_dist_map, current_node, 1);
            put(m_time_map, current_node, 1);
            add_active_node(current_node);
          }
        }
        for(boost::tie(ei, e_end) = out_edges(m_sink, m_g); ei != e_end; ++ei){
          edge_descriptor to_sink = get(m_rev_edge_map, *ei);
          vertex_descriptor current_node = source(to_sink, m_g);
          if(get(m_res_cap_map, to_sink)){
            set_tree(current_node, tColorTraits::white());
            set_edge_to_parent(current_node, to_sink);
            put(m_dist_map, current_node, 1);
            put(m_time_map, current_node, 1);
            add_active_node(current_node);
          }
        }
      }

◆ find_bottleneck()

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

tEdgeVal boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::find_bottleneck ( edge_descriptor e )

inlineprotected

returns the bottleneck of a s->t path (end_of_path is last vertex in source-tree, begin_of_path is first vertex in sink-tree)

Definition at line 365 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                        {
        BOOST_USING_STD_MIN();
        tEdgeVal minimum_cap = get(m_res_cap_map, e);
        vertex_descriptor current_node = source(e, m_g);
        //first go back in the source tree
        while(current_node != m_source){
          edge_descriptor pred = get_edge_to_parent(current_node);
          minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, get(m_res_cap_map, pred));
          current_node = source(pred, m_g);
        }
        //then go forward in the sink-tree
        current_node = target(e, m_g);
        while(current_node != m_sink){
          edge_descriptor pred = get_edge_to_parent(current_node);
          minimum_cap = min BOOST_PREVENT_MACRO_SUBSTITUTION(minimum_cap, get(m_res_cap_map, pred));
          current_node = target(pred, m_g);
        }
        return minimum_cap;
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_edge_to_parent(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_g, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_res_cap_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_sink, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_source, source(), and target().

◆ finish_node()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::finish_node ( vertex_descriptor v )

inlineprotected

finish_node removes a node from the front of the active queue (its called in grow phase, if no more paths can be found using this node)

Definition at line 525 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                  {
        BOOST_ASSERT(m_active_nodes.front() == v);
        m_active_nodes.pop();
        put(m_in_active_list_map, v, false);
        m_last_grow_vertex = graph_traits<Graph>::null_vertex();
      }

References boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_active_nodes, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_in_active_list_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_last_grow_vertex, put(), and v.

◆ get_edge_to_parent()

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

edge_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_edge_to_parent ( vertex_descriptor v ) const

inlineprotected

returns edge to parent vertex of v;

Definition at line 561 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                                          {
        return get(m_pre_map, v);
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_pre_map, and v.

◆ get_next_active_node()

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

vertex_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_next_active_node ( )

inlineprotected

return next active vertex if there is one, otherwise a null_vertex

Definition at line 489 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                     {
        while(true){
          if(m_active_nodes.empty())
            return graph_traits<Graph>::null_vertex();
          vertex_descriptor v = m_active_nodes.front();
 
      //if it has no parent, this node can't be active (if its not source or sink)
      if(!has_parent(v) && v != m_source && v != m_sink){
            m_active_nodes.pop();
            put(m_in_active_list_map, v, false);
          } else{
            BOOST_ASSERT(get_tree(v) == tColorTraits::black() || get_tree(v) == tColorTraits::white());
            return v;
          }
        }
      }

References boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_tree(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_parent(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_active_nodes, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_in_active_list_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_sink, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_source, put(), and v.

◆ get_tree()

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

tColorValue boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_tree ( vertex_descriptor v ) const

inlineprotected

returns the search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree

Definition at line 546 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                             {
        return get(m_tree_map, v);
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_tree_map, and v.

◆ grow()

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

std::pair< edge_descriptor, bool > boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::grow ( )

inlineprotected

Returns a pair of an edge and a boolean. if the bool is true, the edge is a connection of a found path from s->t , read "the link" and source(returnVal, m_g) is the end of the path found in the source-tree target(returnVal, m_g) is the beginning of the path found in the sink-tree

Definition at line 213 of file patched_boykov_kolmogorov_max_flow.hpp.

                                           {
        BOOST_ASSERT(m_orphans.empty());
        vertex_descriptor current_node;
        while((current_node = get_next_active_node()) != graph_traits<Graph>::null_vertex()){ //if there is one
          BOOST_ASSERT(get_tree(current_node) != tColorTraits::gray() &&
                       (has_parent(current_node) ||
                         current_node == m_source ||
                         current_node == m_sink));
 
          if(get_tree(current_node) == tColorTraits::black()){
            //source tree growing
            out_edge_iterator ei, e_end;
            if(current_node != m_last_grow_vertex){
              m_last_grow_vertex = current_node;
              boost::tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
            }
            for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it) {
              edge_descriptor out_edge = *m_last_grow_edge_it;
              if(get(m_res_cap_map, out_edge) > 0){ //check if we have capacity left on this edge
                vertex_descriptor other_node = target(out_edge, m_g);
                if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
                  set_tree(other_node, tColorTraits::black()); //acquire other node to our search tree
                  set_edge_to_parent(other_node, out_edge);   //set us as parent
                  put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);  //and update the distance-heuristic
                  put(m_time_map, other_node, get(m_time_map, current_node));
                  add_active_node(other_node);
                } else if(get_tree(other_node) == tColorTraits::black()) {
                  // we do this to get shorter paths. check if we are nearer to
                  // the source as its parent is
                  if(is_closer_to_terminal(current_node, other_node)){
                    set_edge_to_parent(other_node, out_edge);
                    put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);
                    put(m_time_map, other_node, get(m_time_map, current_node));
                  }
                } else{
                  BOOST_ASSERT(get_tree(other_node)==tColorTraits::white());
                  //kewl, found a path from one to the other search tree, return
                  // the connecting edge in src->sink dir
                  return std::make_pair(out_edge, true);
                }
              }
            } //for all out-edges
          } //source-tree-growing
          else{
            BOOST_ASSERT(get_tree(current_node) == tColorTraits::white());
            out_edge_iterator ei, e_end;
            if(current_node != m_last_grow_vertex){
              m_last_grow_vertex = current_node;
              boost::tie(m_last_grow_edge_it, m_last_grow_edge_end) = out_edges(current_node, m_g);
            }
            for(; m_last_grow_edge_it != m_last_grow_edge_end; ++m_last_grow_edge_it){
              edge_descriptor in_edge = get(m_rev_edge_map, *m_last_grow_edge_it);
              if(get(m_res_cap_map, in_edge) > 0){ //check if there is capacity left
                vertex_descriptor other_node = source(in_edge, m_g);
                if(get_tree(other_node) == tColorTraits::gray()){ //it's a free node
                  set_tree(other_node, tColorTraits::white());      //acquire that node to our search tree
                  set_edge_to_parent(other_node, in_edge);          //set us as parent
                  add_active_node(other_node);                      //activate that node
                  put(m_dist_map, other_node, get(m_dist_map, current_node) + 1); //set its distance
                  put(m_time_map, other_node, get(m_time_map, current_node));//and time
                } else if(get_tree(other_node) == tColorTraits::white()){
                  if(is_closer_to_terminal(current_node, other_node)){
                    //we are closer to the sink than its parent is, so we "adopt" him
                    set_edge_to_parent(other_node, in_edge);
                    put(m_dist_map, other_node, get(m_dist_map, current_node) + 1);
                    put(m_time_map, other_node, get(m_time_map, current_node));
                  }
                } else{
                  BOOST_ASSERT(get_tree(other_node)==tColorTraits::black());
                  //kewl, found a path from one to the other search tree,
                  // return the connecting edge in src->sink dir
                  return std::make_pair(in_edge, true);
                }
              }
            } //for all out-edges
          } //sink-tree growing
 
          //all edges of that node are processed, and no more paths were found.
          // remove if from the front of the active queue
          finish_node(current_node);
        } //while active_nodes not empty
 
        //no active nodes anymore and no path found, we're done
        return std::make_pair(edge_descriptor(), false);
      }

◆ has_parent()

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

bool boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_parent ( vertex_descriptor v ) const

inlineprotected

returns true if the edge stored in m_pre_map[v] is a valid entry

Definition at line 568 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                       {
        return get(m_has_parent_map, v);
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_has_parent_map, and v.

◆ has_sink_connect()

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

bool boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_sink_connect ( vertex_descriptor v )

inlineprotected

checks if vertex v has a connect to the sink-vertex (m_sink)

Parameters

v	the vertex which is checked

Returns: true if a path to the sink was found, false if not

Definition at line 594 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                       {
        tDistanceVal current_distance = 0;
        vertex_descriptor current_vertex = v;
        while(true){
          if(get(m_time_map, current_vertex) == m_time){
            //we found a node which was already checked this round. use it for distance calculations
            current_distance += get(m_dist_map, current_vertex);
            break;
          }
          if(current_vertex == m_sink){
            put(m_time_map, m_sink, m_time);
            break;
          }
          if(has_parent(current_vertex)){
            //it has a parent, so get it
            current_vertex = target(get_edge_to_parent(current_vertex), m_g);
            ++current_distance;
          } else{
            //no path found
            return false;
          }
        }
        current_vertex=v;
        while(get(m_time_map, current_vertex) != m_time){
          put(m_dist_map, current_vertex, current_distance);
          --current_distance;
          put(m_time_map, current_vertex, m_time);
          current_vertex = target(get_edge_to_parent(current_vertex), m_g);
        }
        return true;
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_edge_to_parent(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_parent(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_dist_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_g, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_sink, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time_map, put(), target(), and v.

◆ has_source_connect()

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

bool boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_source_connect ( vertex_descriptor v )

inlineprotected

checks if vertex v has a connect to the source-vertex (m_source)

Parameters

v	the vertex which is checked

Returns: true if a path to the source was found, false if not

Definition at line 631 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                         {
        tDistanceVal current_distance = 0;
        vertex_descriptor current_vertex = v;
        while(true){
          if(get(m_time_map, current_vertex) == m_time){
            //we found a node which was already checked this round. use it for distance calculations
            current_distance += get(m_dist_map, current_vertex);
            break;
          }
          if(current_vertex == m_source){
            put(m_time_map, m_source, m_time);
            break;
          }
          if(has_parent(current_vertex)){
            //it has a parent, so get it
            current_vertex = source(get_edge_to_parent(current_vertex), m_g);
            ++current_distance;
          } else{
            //no path found
            return false;
          }
        }
        current_vertex=v;
        while(get(m_time_map, current_vertex) != m_time){
            put(m_dist_map, current_vertex, current_distance);
            --current_distance;
            put(m_time_map, current_vertex, m_time);
            current_vertex = source(get_edge_to_parent(current_vertex), m_g);
        }
        return true;
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::get_edge_to_parent(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_parent(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_dist_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_g, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_source, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time_map, put(), source(), and v.

◆ is_closer_to_terminal()

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

bool boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::is_closer_to_terminal	(	vertex_descriptor	p,
		vertex_descriptor	q )

inlineprotected

returns true, if p is closer to a terminal than q

Definition at line 666 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                                                 {
        //checks the timestamps first, to build no cycles, and after that the real distance
        return (get(m_time_map, q) <= get(m_time_map, p) &&
                get(m_dist_map, q) > get(m_dist_map, p)+1);
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_dist_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time_map, and p.

◆ max_flow()

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

tEdgeVal boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::max_flow ( )

inline

Definition at line 114 of file patched_boykov_kolmogorov_max_flow.hpp.

                         {
        //augment direct paths from SOURCE->SINK and SOURCE->VERTEX->SINK
        augment_direct_paths();
        //start the main-loop
        while(true){
          bool path_found;
          edge_descriptor connecting_edge;
          boost::tie(connecting_edge, path_found) = grow(); //find a path from source to sink
          if(!path_found){
            //we're finished, no more paths were found
            break;
          }
          ++m_time;
          augment(connecting_edge); //augment that path
          adopt(); //rebuild search tree structure
        }
        return m_flow;
      }

References boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::adopt(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::augment(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::augment_direct_paths(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::grow(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_flow, and boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time.

◆ remove_active_node()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::remove_active_node ( vertex_descriptor v )

inlineprotected

removes a vertex from the queue of active nodes (actually this does nothing, but checks if this node has no parent edge, as this is the criteria for being no more active)

Definition at line 537 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                         {
        (void)v; // disable unused parameter warning
        BOOST_ASSERT(!has_parent(v));
      }

References boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::has_parent(), v, and void().

◆ set_edge_to_parent()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::set_edge_to_parent	(	vertex_descriptor	v,
		edge_descriptor	f_edge_to_parent )

inlineprotected

sets edge to parent vertex of v;

Definition at line 575 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                                                           {
        BOOST_ASSERT(get(m_res_cap_map, f_edge_to_parent) > 0);
        put(m_pre_map, v, f_edge_to_parent);
        put(m_has_parent_map, v, true);
      }

References get(), boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_has_parent_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_pre_map, boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_res_cap_map, put(), and v.

◆ set_no_parent()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::set_no_parent ( vertex_descriptor v )

inlineprotected

removes the edge to parent of v (this is done by invalidating the entry an additional map)

Definition at line 585 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                    {
        put(m_has_parent_map, v, false);
      }

References boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_has_parent_map, put(), and v.

◆ set_tree()

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

void boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::set_tree	(	vertex_descriptor	v,
		tColorValue	t )

inlineprotected

sets search tree of v; tColorValue::black() for source tree, white() for sink tree, gray() for no tree

Definition at line 554 of file patched_boykov_kolmogorov_max_flow.hpp.

                                                              {
        put(m_tree_map, v, t);
      }

References boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_tree_map, put(), and v.

Member Data Documentation

◆ m_active_nodes

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

tQueue boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_active_nodes

protected

Definition at line 686 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_cap_map

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

EdgeCapacityMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_cap_map

protected

Definition at line 677 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_child_orphans

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

tQueue boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_child_orphans

protected

Definition at line 691 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_dist_map

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

DistanceMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_dist_map

protected

Definition at line 682 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_flow

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

tEdgeVal boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_flow

protected

Definition at line 698 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_g

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

Graph& boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_g

protected

Definition at line 675 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_has_parent_map

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

iterator_property_map<std::vector<bool>::iterator, IndexMap> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_has_parent_map

protected

Definition at line 694 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_has_parent_vec

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

std::vector<bool> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_has_parent_vec

protected

Definition at line 693 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_in_active_list_map

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

iterator_property_map<std::vector<bool>::iterator, IndexMap> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_in_active_list_map

protected

Definition at line 688 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_in_active_list_vec

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

std::vector<bool> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_in_active_list_vec

protected

Definition at line 687 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_index_map

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

IndexMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_index_map

protected

Definition at line 676 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_last_grow_edge_end

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

out_edge_iterator boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_last_grow_edge_end

protected

Definition at line 702 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_last_grow_edge_it

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

out_edge_iterator boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_last_grow_edge_it

protected

Definition at line 701 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_last_grow_vertex

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

vertex_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_last_grow_vertex

protected

Definition at line 700 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_orphans

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

std::list<vertex_descriptor> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_orphans

protected

Definition at line 690 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_pre_map

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

PredecessorMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_pre_map

protected

Definition at line 680 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_res_cap_map

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

ResidualCapacityEdgeMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_res_cap_map

protected

Definition at line 678 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_rev_edge_map

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

ReverseEdgeMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_rev_edge_map

protected

Definition at line 679 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_sink

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

vertex_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_sink

protected

Definition at line 684 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_source

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

vertex_descriptor boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_source

protected

Definition at line 683 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_time

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

long boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time

protected

Definition at line 699 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_time_map

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

iterator_property_map<std::vector<long>::iterator, IndexMap> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time_map

protected

Definition at line 697 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_time_vec

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

std::vector<long> boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_time_vec

protected

Definition at line 696 of file patched_boykov_kolmogorov_max_flow.hpp.

◆ m_tree_map

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

ColorMap boost::detail::bk_max_flow< Graph, EdgeCapacityMap, ResidualCapacityEdgeMap, ReverseEdgeMap, PredecessorMap, ColorMap, DistanceMap, IndexMap >::m_tree_map

protected

Definition at line 681 of file patched_boykov_kolmogorov_max_flow.hpp.

The documentation for this class was generated from the following file:

libs/image/lazybrush/patched_boykov_kolmogorov_max_flow.hpp

Public Member Functions

Protected Member Functions

Protected Attributes

Private Types

Detailed Description

Member Typedef Documentation

◆ edge_descriptor

◆ edge_iterator

◆ out_edge_iterator

◆ tColorTraits

◆ tColorValue

◆ tDistanceVal

◆ tEdgeVal

◆ tGraphTraits

◆ tQueue

◆ vertex_descriptor

◆ vertex_iterator

Constructor & Destructor Documentation

◆ bk_max_flow()

Member Function Documentation

◆ add_active_node()

◆ adopt()

◆ augment()

◆ augment_direct_paths()

◆ find_bottleneck()

◆ finish_node()

◆ get_edge_to_parent()

◆ get_next_active_node()

◆ get_tree()

◆ grow()

◆ has_parent()

◆ has_sink_connect()

◆ has_source_connect()

◆ is_closer_to_terminal()

◆ max_flow()

◆ remove_active_node()

◆ set_edge_to_parent()

◆ set_no_parent()

◆ set_tree()

Member Data Documentation

◆ m_active_nodes

◆ m_cap_map

◆ m_child_orphans

◆ m_dist_map

◆ m_flow

◆ m_g

◆ m_has_parent_map

◆ m_has_parent_vec

◆ m_in_active_list_map

◆ m_in_active_list_vec

◆ m_index_map

◆ m_last_grow_edge_end

◆ m_last_grow_edge_it

◆ m_last_grow_vertex

◆ m_orphans

◆ m_pre_map

◆ m_res_cap_map

◆ m_rev_edge_map

◆ m_sink

◆ m_source

◆ m_time

◆ m_time_map

◆ m_time_vec

◆ m_tree_map