All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
NetworKit::EdmondsKarp Class Reference

The EdmondsKarp class implements the maximum flow algorithm by Edmonds and Karp. More...

#include <EdmondsKarp.h>

Public Member Functions

 EdmondsKarp (const Graph &graph, node source, node sink)
 Constructs an instance of the EdmondsKarp algorithm for the given graph, source and sink. More...
 
void run ()
 Computes the maximum flow, executes the EdmondsKarp algorithm. More...
 
edgeweight getMaxFlow () const
 Returns the value of the maximum flow from source to sink. More...
 
std::vector< nodegetSourceSet () const
 Returns the set of the nodes on the source side of the flow/minimum cut. More...
 
edgeweight getFlow (node u, node v) const
 Get the flow value between two nodes u and v. More...
 
edgeweight getFlow (edgeid eid) const
 Get the flow value of an edge. More...
 
std::vector< edgeweightgetFlowVector () const
 Return a copy of the flow values of all edges. More...
 

Detailed Description

The EdmondsKarp class implements the maximum flow algorithm by Edmonds and Karp.

Constructor & Destructor Documentation

NetworKit::EdmondsKarp::EdmondsKarp ( const Graph graph,
node  source,
node  sink 
)

Constructs an instance of the EdmondsKarp algorithm for the given graph, source and sink.

Parameters
graphThe graph.
sourceThe source node.
sinkThe sink node.

Member Function Documentation

edgeweight NetworKit::EdmondsKarp::getFlow ( node  u,
node  v 
) const

Get the flow value between two nodes u and v.

Warning
The running time of this function is linear in the degree of u.
Parameters
uThe first node
vThe second node
Returns
The flow between node u and v.
edgeweight NetworKit::EdmondsKarp::getFlow ( edgeid  eid) const
inline

Get the flow value of an edge.

Parameters
eidThe id of the edge
Returns
The flow on the edge identified by eid
std::vector< edgeweight > NetworKit::EdmondsKarp::getFlowVector ( ) const

Return a copy of the flow values of all edges.

Note
Instead of copying all values you can also use the inline function "getFlow(edgeid)" in order to access the values efficiently.
Returns
The flow values of all edges
edgeweight NetworKit::EdmondsKarp::getMaxFlow ( ) const

Returns the value of the maximum flow from source to sink.

Returns
The maximum flow value
std::vector< node > NetworKit::EdmondsKarp::getSourceSet ( ) const

Returns the set of the nodes on the source side of the flow/minimum cut.

Returns
The set of nodes that form the (smallest) source side of the flow/minimum cut.
void NetworKit::EdmondsKarp::run ( )

Computes the maximum flow, executes the EdmondsKarp algorithm.


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