Push-Relabel Algorithm for computing the maximum s-t-flow of a Digraph. More...

#include <max-flow.hxx>

Public Types
typedef GRAPH	GraphType
typedef FLOW	Flow
typedef GraphType::VertexIterator	VertexIterator
typedef GraphType::EdgeIterator	EdgeIterator
typedef GraphType::AdjacencyIterator	AdjacencyIterator

Public Member Functions
	MaxFlowPushRelabel ()
	Construct an instance of the push-relabel algorithm.
void	clear ()
	Clear all members.
Flow	maxFlow () const
	Return the maximum flow through the graph.
Flow	flow (const std::size_t) const
	Return the flow in a certain edge.
std::size_t	numberOfPushes () const
	Return the total number of pushes executed.
std::size_t	numberOfRelabels () const
	Return the total number of relabels executed.
template<class EDGE_WEIGHT_ITERATOR >
	MaxFlowPushRelabel (const GraphType &, EDGE_WEIGHT_ITERATOR, const std::size_t, const std::size_t)
	Construct an instance of the push-relabel algorithm.
template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >
	MaxFlowPushRelabel (const GraphType &, const SUBGRAPH_MASK &, EDGE_WEIGHT_ITERATOR, const std::size_t, const std::size_t)
	Construct an instance of the push-relabel algorithm.
template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >
Flow	operator() (const GraphType &, const SUBGRAPH_MASK &, EDGE_WEIGHT_ITERATOR, const std::size_t, const std::size_t)
	Initialize members and execute push-relabel algorithm.

Detailed Description

template<class GRAPH, class FLOW>
class andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >

Push-Relabel Algorithm for computing the maximum s-t-flow of a Digraph.

With FIFO vertex selection rule.

Reference: A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM 35(4):921-940. 1988

Definition at line 28 of file max-flow.hxx.

Member Typedef Documentation

template<class GRAPH, class FLOW>

typedef GraphType::AdjacencyIterator andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::AdjacencyIterator

Definition at line 34 of file max-flow.hxx.

template<class GRAPH, class FLOW>

typedef GraphType::EdgeIterator andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::EdgeIterator

Definition at line 33 of file max-flow.hxx.

template<class GRAPH, class FLOW>

typedef FLOW andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::Flow

Definition at line 31 of file max-flow.hxx.

template<class GRAPH, class FLOW>

typedef GRAPH andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::GraphType

Definition at line 30 of file max-flow.hxx.

template<class GRAPH, class FLOW>

typedef GraphType::VertexIterator andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::VertexIterator

Definition at line 32 of file max-flow.hxx.

Constructor & Destructor Documentation

template<class GRAPH , class FLOW >

andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::MaxFlowPushRelabel ( )

inline

Construct an instance of the push-relabel algorithm.

Definition at line 76 of file max-flow.hxx.

template<class GRAPH , class FLOW >

template<class EDGE_WEIGHT_ITERATOR >

andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::MaxFlowPushRelabel	(	const GraphType &	graph,
		EDGE_WEIGHT_ITERATOR	edgeWeightIterator,
		const std::size_t	sourceVertexIndex,
		const std::size_t	sinkVertexIndex
	)

inline

Construct an instance of the push-relabel algorithm.

Parameters

graph	A graph.
edgeWeightIterator	Iterator to the beginning of a sequence of edge weights.
sourceVertexIndex	Index of the source vertex.
sinkVertexIndex	Index of the sink vertex.

Definition at line 99 of file max-flow.hxx.

template<class GRAPH , class FLOW >

template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >

andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::MaxFlowPushRelabel	(	const GraphType &	graph,
		const SUBGRAPH_MASK &	mask,
		EDGE_WEIGHT_ITERATOR	edgeWeightIterator,
		const std::size_t	sourceVertexIndex,
		const std::size_t	sinkVertexIndex
	)

inline

Construct an instance of the push-relabel algorithm.

Parameters

graph	A graph.
mask	A subgraph mask.
edgeWeightIterator	Iterator to the beginning of a sequence of edge weights.
sourceVertexIndex	Index of the source vertex.
sinkVertexIndex	Index of the sink vertex.

Definition at line 130 of file max-flow.hxx.

Member Function Documentation

template<class GRAPH , class FLOW >

void andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::clear ( )

inline

Clear all members.

Definition at line 155 of file max-flow.hxx.

template<class GRAPH , class FLOW >

MaxFlowPushRelabel< GRAPH, FLOW >::Flow andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::flow ( const std::size_t edgeIndex ) const

inline

Return the flow in a certain edge.

Parameters

edgeIndex Index of an edge.

Returns: The flow in the edge given by edgeIndex.

Definition at line 186 of file max-flow.hxx.

template<class GRAPH , class FLOW >

MaxFlowPushRelabel< GRAPH, FLOW >::Flow andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::maxFlow ( ) const

inline

Return the maximum flow through the graph.

Returns: The excess flow at the sink vertex, which is equal to the max flow.

Definition at line 175 of file max-flow.hxx.

template<class GRAPH , class FLOW >

std::size_t andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::numberOfPushes ( ) const

inline

Return the total number of pushes executed.

Returns: The number of pushes.

Definition at line 199 of file max-flow.hxx.

template<class GRAPH , class FLOW >

std::size_t andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::numberOfRelabels ( ) const

inline

Return the total number of relabels executed.

Returns: The number of relabels.

Definition at line 209 of file max-flow.hxx.

template<class GRAPH , class FLOW >

template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >

MaxFlowPushRelabel< GRAPH, FLOW >::Flow andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >::operator()	(	const GraphType &	graph,
		const SUBGRAPH_MASK &	mask,
		EDGE_WEIGHT_ITERATOR	edgeWeightIterator,
		const std::size_t	sourceVertexIndex,
		const std::size_t	sinkVertexIndex
	)

inline

Initialize members and execute push-relabel algorithm.

Parameters

graph	A graph.
mask	A subgraph mask.
edgeWeightIterator	Iterator to the beginning of a sequence of edge weights.
sourceVertexIndex	Index of the source vertex.
sinkVertexIndex	Index of the sink vertex.

Definition at line 224 of file max-flow.hxx.

Public Types

Public Member Functions

Detailed Description

template<class GRAPH, class FLOW> class andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class GRAPH, class FLOW>
class andres::graph::MaxFlowPushRelabel< GRAPH, FLOW >