andres::graph::MaxFlowEdmondsKarp< GRAPH, FLOW > Class Template Reference

Edmonds-Karp Algorithm for computing the maximum s-t-flow of a Digraph. More...

#include <max-flow.hxx>

Classes
class	ResidualMask

Public Types
typedef GRAPH	GraphType
typedef FLOW	Flow

Public Member Functions
	MaxFlowEdmondsKarp ()
	Construct an instance of the Edmonds-Karp algorithm.
template<class EDGE_WEIGHT_ITERATOR >
	MaxFlowEdmondsKarp (const GraphType &, EDGE_WEIGHT_ITERATOR, const std::size_t, const std::size_t)
	Construct an instance of the Edmonds-Karp algorithm.
template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >
	MaxFlowEdmondsKarp (const GraphType &, const SUBGRAPH_MASK &, EDGE_WEIGHT_ITERATOR, const std::size_t, const std::size_t)
	Construct an instance of the Edmonds-Karp 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.
template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >
Flow	operator() (const GraphType &, const SUBGRAPH_MASK &, const EDGE_WEIGHT_ITERATOR, const std::size_t, const std::size_t)
	Initialize members and execute Edmonds-Karp algorithm.

Detailed Description

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

Edmonds-Karp Algorithm for computing the maximum s-t-flow of a Digraph.

Reference: J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19(2):248-264. 1972

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

Member Typedef Documentation

template<class GRAPH, class FLOW>

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

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

template<class GRAPH, class FLOW>

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

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

Constructor & Destructor Documentation

template<class GRAPH , class FLOW >

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

inline

Construct an instance of the Edmonds-Karp algorithm.

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

template<class GRAPH , class FLOW >

template<class EDGE_WEIGHT_ITERATOR >

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

inline

Construct an instance of the Edmonds-Karp 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 552 of file max-flow.hxx.

template<class GRAPH , class FLOW >

template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >

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

inline

Construct an instance of the Edmonds-Karp algorithm.

Parameters

graph	A graph.
subgraphMask	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 579 of file max-flow.hxx.

Member Function Documentation

template<class GRAPH , class FLOW >

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

inline

Clear all members.

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

template<class GRAPH , class FLOW >

MaxFlowEdmondsKarp< GRAPH, FLOW >::Flow andres::graph::MaxFlowEdmondsKarp< 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 626 of file max-flow.hxx.

template<class GRAPH , class FLOW >

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

inline

Return the maximum flow through the graph.

Returns

The max flow.

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

template<class GRAPH , class FLOW >

template<class EDGE_WEIGHT_ITERATOR , class SUBGRAPH_MASK >

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

Initialize members and execute Edmonds-Karp algorithm.

Parameters

graph	A graph.
subgraphMask	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 644 of file max-flow.hxx.