lab_flow
Foreboding Flow

Represents a algorithm to determine the maximum network flow of a graph. More...
#include <NetworkFlow.h>
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_ 
Represents a algorithm to determine the maximum network flow of a graph.
Constructor to create a flow analyzer.
startingGraph  The initial graph. 
source  The source vertex. 
sink  The sink vertex. 
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.
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.
This version is the helper function.
source  The starting (current) vertex 
sink  The destination vertex 
path  The vertices in the path 
visited  A set of vertices we have visited 
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.
source  The starting (current) vertex 
sink  The destination vertex 
path  The vertices in the path 
const Graph & NetworkFlow::getGraph  (  )  const 
Returns a constant reference to the state space graph.
int NetworkFlow::pathCapacity  (  const std::vector< Vertex > &  path  )  const 
pathCapacity  Determine the capacity of a path in the residual graph.
path  The vertices in the path 