Flow, cut, and min-cost-flow result types, wrappers, and aliases. More...

#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/find_flow_cost.hpp>
#include <boost/graph/successive_shortest_path_nonnegative_weights.hpp>
#include <set>
#include "attributes.hpp"
#include "multigraph.hpp"

Include dependency graph for flow.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	nxpp::MaximumFlowResult< NodeID >
	Result of a maximum-flow computation. More...

struct	nxpp::MinCostMaxFlowResult< NodeID >
	Result of a min-cost max-flow computation. More...

struct	nxpp::detail::FlowEdgeRecord< NodeID, FlowEdgeDesc >

struct	nxpp::detail::MinCostFlowState< NodeID >

struct	nxpp::detail::MinCostFlowCacheHooks< Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector > >

struct	nxpp::MinimumCutResult< NodeID >
	Result of a minimum-cut computation. More...

Functions
template<typename NodeID , typename FlowEdgeDesc , typename CapacityMap , typename ResidualMap >
void	nxpp::detail::fill_flow_views (const std::vector< FlowEdgeRecord< NodeID, FlowEdgeDesc > > &original_edges, const CapacityMap &capacity, const ResidualMap &residual, std::map< std::pair< NodeID, NodeID >, long > &endpoint_flows, std::map< std::size_t, long > &edge_flows_by_id)

template<typename GraphWrapper >
auto &	nxpp::detail::min_cost_flow_cache ()

template<typename GraphWrapper >
auto &	nxpp::detail::invalidated_min_cost_flow_graphs ()

template<typename GraphWrapper >
auto	nxpp::edmonds_karp_maximum_flow (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity")
	Deprecated free-function alias for `G.edmonds_karp_maximum_flow(...)`.

template<typename GraphWrapper >
auto	nxpp::push_relabel_maximum_flow_result (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity")
	Deprecated free-function alias for `G.push_relabel_maximum_flow_result(...)`.

template<typename GraphWrapper >
auto	nxpp::maximum_flow (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity")
	Deprecated free-function alias for `G.maximum_flow(...)`.

template<typename GraphWrapper >
auto	nxpp::minimum_cut (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity")
	Deprecated free-function alias for `G.minimum_cut(...)`.

template<typename GraphWrapper >
auto	nxpp::max_flow_min_cost_cycle_canceling (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity", const std::string &weight_attr="weight")
	Deprecated free-function alias for `G.max_flow_min_cost_cycle_canceling(...)`.

template<typename GraphWrapper >
long	nxpp::push_relabel_maximum_flow (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity", const std::string &weight_attr="weight")
	Deprecated free-function alias for `G.push_relabel_maximum_flow(...)`.

template<typename GraphWrapper >
auto	nxpp::cycle_canceling (const GraphWrapper &G, const std::string &weight_attr="weight")
	Deprecated free-function alias for `G.cycle_canceling(weight_attr)`.

template<typename GraphWrapper >
auto	nxpp::successive_shortest_path_nonnegative_weights (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity", const std::string &weight_attr="weight")
	Deprecated free-function alias for `G.successive_shortest_path_nonnegative_weights(...)`.

template<typename GraphWrapper >
auto	nxpp::max_flow_min_cost_successive_shortest_path (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity", const std::string &weight_attr="weight")
	Deprecated free-function alias for `G.max_flow_min_cost_successive_shortest_path(...)`.

template<typename GraphWrapper >
auto	nxpp::max_flow_min_cost (const GraphWrapper &G, const typename GraphWrapper::NodeType &source_id, const typename GraphWrapper::NodeType &target_id, const std::string &capacity_attr="capacity", const std::string &weight_attr="weight")
	Deprecated free-function alias for `G.max_flow_min_cost(...)`.

Detailed Description

Flow, cut, and min-cost-flow result types, wrappers, and aliases.

Function Documentation

◆ cycle_canceling()

template<typename GraphWrapper >

auto nxpp::cycle_canceling	(	const GraphWrapper &	G,
		const std::string &	weight_attr = `"weight"`
	)

Deprecated free-function alias for G.cycle_canceling(weight_attr).

Parameters

G	Graph wrapper whose staged min-cost-flow state should be finalized.
weight_attr	Name of the numeric edge attribute used as cost.

Returns: The same min-cost value returned by G.cycle_canceling(weight_attr).

References nxpp::cycle_canceling().

Referenced by nxpp::cycle_canceling().

◆ edmonds_karp_maximum_flow()

template<typename GraphWrapper >

auto nxpp::edmonds_karp_maximum_flow	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`
	)

Deprecated free-function alias for G.edmonds_karp_maximum_flow(...).

Parameters

G	Graph wrapper on which to compute the max-flow result.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.

Returns: The same MaximumFlowResult<NodeID>-style result returned by G.edmonds_karp_maximum_flow(...).

References nxpp::edmonds_karp_maximum_flow().

Referenced by nxpp::edmonds_karp_maximum_flow(), and nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::maximum_flow().

◆ max_flow_min_cost()

template<typename GraphWrapper >

auto nxpp::max_flow_min_cost	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`,
		const std::string &	weight_attr = `"weight"`
	)

Deprecated free-function alias for G.max_flow_min_cost(...).

Parameters

G	Graph wrapper on which to compute the default min-cost max-flow result.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.
weight_attr	Name of the numeric edge attribute used as cost.

Returns: The same MinCostMaxFlowResult<NodeID>-style result returned by G.max_flow_min_cost(...).

References nxpp::max_flow_min_cost().

Referenced by nxpp::max_flow_min_cost().

◆ max_flow_min_cost_cycle_canceling()

template<typename GraphWrapper >

auto nxpp::max_flow_min_cost_cycle_canceling	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`,
		const std::string &	weight_attr = `"weight"`
	)

Deprecated free-function alias for G.max_flow_min_cost_cycle_canceling(...).

Parameters

G	Graph wrapper on which to compute min-cost max-flow.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.
weight_attr	Name of the numeric edge attribute used as cost.

Returns: The same MinCostMaxFlowResult<NodeID>-style result returned by G.max_flow_min_cost_cycle_canceling(...).

References nxpp::max_flow_min_cost_cycle_canceling().

Referenced by nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::max_flow_min_cost(), and nxpp::max_flow_min_cost_cycle_canceling().

◆ max_flow_min_cost_successive_shortest_path()

template<typename GraphWrapper >

auto nxpp::max_flow_min_cost_successive_shortest_path	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`,
		const std::string &	weight_attr = `"weight"`
	)

Deprecated free-function alias for G.max_flow_min_cost_successive_shortest_path(...).

Parameters

G	Graph wrapper on which to compute the SSP alias result.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.
weight_attr	Name of the numeric edge attribute used as cost.

Returns: The same MinCostMaxFlowResult<NodeID>-style result returned by G.max_flow_min_cost_successive_shortest_path(...).

References nxpp::max_flow_min_cost_successive_shortest_path().

Referenced by nxpp::max_flow_min_cost_successive_shortest_path().

◆ maximum_flow()

template<typename GraphWrapper >

auto nxpp::maximum_flow	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`
	)

Deprecated free-function alias for G.maximum_flow(...).

Parameters

G	Graph wrapper on which to compute the default max-flow result.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.

Returns: The same MaximumFlowResult<NodeID>-style result returned by G.maximum_flow(...).

References nxpp::maximum_flow().

Referenced by nxpp::maximum_flow().

◆ minimum_cut()

template<typename GraphWrapper >

auto nxpp::minimum_cut	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`
	)

Deprecated free-function alias for G.minimum_cut(...).

Parameters

G	Graph wrapper on which to compute the minimum cut.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.

Returns: The same MinimumCutResult<NodeID>-style result returned by G.minimum_cut(...).

References nxpp::minimum_cut().

Referenced by nxpp::minimum_cut().

◆ push_relabel_maximum_flow()

template<typename GraphWrapper >

long nxpp::push_relabel_maximum_flow	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`,
		const std::string &	weight_attr = `"weight"`
	)

Deprecated free-function alias for G.push_relabel_maximum_flow(...).

Parameters

G	Graph wrapper on which to stage the push-relabel residual state.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.
weight_attr	Name of the numeric edge attribute used as cost.

Returns: The same staged max-flow value returned by G.push_relabel_maximum_flow(...).

References nxpp::push_relabel_maximum_flow().

Referenced by nxpp::push_relabel_maximum_flow().

◆ push_relabel_maximum_flow_result()

template<typename GraphWrapper >

auto nxpp::push_relabel_maximum_flow_result	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`
	)

Deprecated free-function alias for G.push_relabel_maximum_flow_result(...).

Parameters

G	Graph wrapper on which to compute the push-relabel flow result.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.

Returns: The same MaximumFlowResult<NodeID>-style result returned by G.push_relabel_maximum_flow_result(...).

References nxpp::push_relabel_maximum_flow_result().

Referenced by nxpp::push_relabel_maximum_flow_result().

◆ successive_shortest_path_nonnegative_weights()

template<typename GraphWrapper >

auto nxpp::successive_shortest_path_nonnegative_weights	(	const GraphWrapper &	G,
		const typename GraphWrapper::NodeType &	source_id,
		const typename GraphWrapper::NodeType &	target_id,
		const std::string &	capacity_attr = `"capacity"`,
		const std::string &	weight_attr = `"weight"`
	)

Deprecated free-function alias for G.successive_shortest_path_nonnegative_weights(...).

Parameters

G	Graph wrapper on which to compute the SSP min-cost max-flow result.
source_id	Source node ID.
target_id	Sink node ID.
capacity_attr	Name of the numeric edge attribute used as capacity.
weight_attr	Name of the numeric edge attribute used as cost.

Returns: The same MinCostMaxFlowResult<NodeID>-style result returned by G.successive_shortest_path_nonnegative_weights(...).

References nxpp::successive_shortest_path_nonnegative_weights().

Referenced by nxpp::Graph< NodeID, EdgeWeight, Directed, Multi, Weighted, OutEdgeSelector, VertexSelector >::max_flow_min_cost_successive_shortest_path(), and nxpp::successive_shortest_path_nonnegative_weights().

Classes

Functions

Detailed Description

Function Documentation

◆ cycle_canceling()

◆ edmonds_karp_maximum_flow()

◆ max_flow_min_cost()

◆ max_flow_min_cost_cycle_canceling()

◆ max_flow_min_cost_successive_shortest_path()

◆ maximum_flow()

◆ minimum_cut()

◆ push_relabel_maximum_flow()

◆ push_relabel_maximum_flow_result()

◆ successive_shortest_path_nonnegative_weights()