NetworkFlow Class Reference

Represents a algorithm to determine the maximum network flow of a graph. More...

#include <NetworkFlow.h>

Collaboration diagram for NetworkFlow:

Public Member Functions
	NetworkFlow (Graph &startingGraph, Vertex source, Vertex sink)
	Constructor to create a flow analyzer. More...
bool	findAugmentingPath (Vertex source, Vertex sink, std::vector< Vertex > &path, std::set< Vertex > &visited)
	Create an initial residual graph. More...
bool	findAugmentingPath (Vertex source, Vertex sink, std::vector< Vertex > &path)
	findAugmentingPath - use DFS to find a path in the residual graph with leftover capacity. More...
int	pathCapacity (const std::vector< Vertex > &path) const
	pathCapacity - Determine the capacity of a path in the residual graph. More...
const Graph &	calculateFlow ()
	calculuateFlow - Determine the capacity of a path in the residual graph. More...
const Graph &	getGraph () const
	Returns a constant reference to the state space graph. More...
const Graph &	getFlowGraph () const
const Graph &	getResidualGraph () const
int	getMaxFlow () const

Private Attributes
Graph &	g_
Graph	residual_
Graph	flow_
Vertex	source_
Vertex	sink_
int	maxFlow_

Detailed Description

Represents a algorithm to determine the maximum network flow of a graph.

Constructor & Destructor Documentation

NetworkFlow()

NetworkFlow::NetworkFlow	(	Graph &	startingGraph,
		Vertex	source,
		Vertex	sink
	)

Constructor to create a flow analyzer.

Parameters

startingGraph	The initial graph.
source	The source vertex.
sink	The sink vertex.

Member Function Documentation

calculateFlow()

const Graph & NetworkFlow::calculateFlow

(

)

calculuateFlow - Determine the capacity of a path in the residual graph.

Sets the member function maxFlow_ to be the flow, and updates the residual graph and flow graph according to the algorithm.

Returns

The network flow graph.

findAugmentingPath() [1/2]

bool NetworkFlow::findAugmentingPath	(	Vertex	source,
		Vertex	sink,
		std::vector< Vertex > &	path,
		std::set< Vertex > &	visited
	)

Create an initial residual graph.

findAugmentingPath - use DFS to find a path in the residual graph with leftover capacity.

Find an augmenting path from the source to the sink.

Returns

A vector of the vertices from source to sink with greater than zero flow. Returns an empty vector if no such path exists.

This version is the helper function.

Parameters

source	The starting (current) vertex
sink	The destination vertex
path	The vertices in the path
visited	A set of vertices we have visited

findAugmentingPath() [2/2]

bool NetworkFlow::findAugmentingPath	(	Vertex	source,
		Vertex	sink,
		std::vector< Vertex > &	path
	)

findAugmentingPath - use DFS to find a path in the residual graph with leftover capacity.

This version is the main function. It initializes a set to keep track of visited vertices.

Parameters

source	The starting (current) vertex
sink	The destination vertex
path	The vertices in the path

getGraph()

const Graph & NetworkFlow::getGraph

(

)

const

Returns a constant reference to the state space graph.

Returns

A constant reference to the state space graph.

pathCapacity()

int NetworkFlow::pathCapacity

(

const std::vector< Vertex > &

path

)

const

pathCapacity - Determine the capacity of a path in the residual graph.

Parameters

path	The vertices in the path

---

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

• NetworkFlow.h
• NetworkFlow.cpp