minFlow Class Reference

Collaboration diagram for minFlow:

List of all members.

Public Member Functions
	minFlow (Mflograph &, int &)
	Find maximum flow in flow graph with min capacity constraints.
Protected Member Functions
bool	findPath ()
	Find an augmenting path from the source to the sink.
int	augment ()
	Saturate the augmenting path defined by the pEdge values.
bool	findCycle (edge)
	Find a cycle that passes through a given edge.
int	add2cycle (edge)
	Add flow to a cycle.
Protected Attributes
Mflograph *	fg
edge *	pEdge

---

Detailed Description

Definition at line 15 of file minFlow.h.

---

Constructor & Destructor Documentation

minFlow::minFlow	(	Mflograph &	fg1,
		int &	floVal
	)

Find maximum flow in flow graph with min capacity constraints.

Parameters:

fg	is the flow graph
floVal	on return, floVal is the total amount of flow that was added to the flow graph; if there is no feasible flow for the given min capacities, -1 is returned. Normally, fg is expected to have 0 flow on all its edges, but this method will work correctly even if there is an initial non-zero flow. This method may modify the edge numbers in fg1. It will have all the same edges, but they may be identified by different edge numbers, upon return.
fg	is the flow graph
floVal	on return, floVal is the total amount of flow that was added to the flow graph; if there is no feasible flow for the given min capacities, -1 is returned. Normally, fg is expected to have 0 flow on all its edges, but this method will work correctly even if there is an initial non-zero flow

Definition at line 14 of file minFlow.cpp.

Here is the call graph for this function:

---

Member Function Documentation

int minFlow::add2cycle

(

edge

e

)

[protected]

Add flow to a cycle.

This method adds flow to the cycle defined by the edge e and the path defined by pEdge.

Parameters:

e	is an edge

Returns:

the amount of flow added to the cycle

This method adds flow to the cycle defined by the edge e and the path defined by pEdge. For the purposes of this method, the source and sink are viewed as a single node.

Parameters:

e	is an edge

Returns:

the amount of flow added to the cycle

Definition at line 153 of file minFlow.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

int minFlow::augment

(

)

[protected]

Saturate the augmenting path defined by the pEdge values.

When augment is called, pEdge should contain pointers that define a sequence of edges from the sink back to the source. The method adds enough flow to the path defined by this edge sequence to saturate the path.

Returns:

the amount of flow added to the path.

Definition at line 97 of file minFlow.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool minFlow::findCycle

(

edge

e

)

[protected]

Find a cycle that passes through a given edge.

This method searches for a simple cycle with positive residual capacity in *fg that includes the given edge e. If a cycle is found, then on return the pEdge values will define a path with positive residual capacity from head(e) to tail(e). Combining this path with e gives the desired cycle.

Parameters:

e	is an edge

Returns:

true if a cycle is found, else false

This method searches for a simple cycle that includes the given edge e. For the purposes of this method, the source and sink are viewed as a single vertex. If a cycle is found, then on return the pEdge values will define a path with positive residual capacity from head(e) to tail(e). Combining this path with e gives the desired cycle.

Parameters:

e	is an edge

Returns:

true if a cycle is found, else false

Definition at line 128 of file minFlow.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bool minFlow::findPath

(

)

[protected]

Find an augmenting path from the source to the sink.

If a path is found, the pEdge data structure contains "parent pointers" that define the path. More precisely, pEdge[u] is the edge on the path that connects u to its predecessor. So we can construct the path by following the pEdge values from the sink back to the source.

Returns:

true if a path found, else false

Definition at line 69 of file minFlow.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

---

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

• /Users/jst/src/grafalgo/cpp/include/minFlow.h
• /Users/jst/src/grafalgo/cpp/graphAlgorithms/maxFlo/minFlow.cpp
• /Users/jst/src/grafalgo/cpp/graphAlgorithms/maxFlo/minFlowx.cpp