Class FlowNetwork

• Defined in File MaxFlow.h

Nested Relationships

Nested Types

• Struct FlowNetwork::Edge

Class Documentation

class FlowNetwork

a network of flow with integer capacities

Public Functions

explicit FlowNetwork(int n)

the network of the nodes 0 , … , n - 1, with no edge

Pre:

n >= 0

inline int n(void) const

int addEdge(int u, int v, long long c)

the edge ( u , v ) of capacity c, and its number

Pre:

u and v are nodes, c >= 0

long long flow(int e) const

the flow on the edge number e

Pre:

e is the number of an edge

long long capacity(int e) const

the capacity of the edge number e

Pre:

e is the number of an edge

long long maxFlow(int s, int t, Augment how = Augment::DINIC, long long *paths = nullptr)

the maximum flow from s to t, starting from the flow there is; the augmenting paths found go to *paths, if given

Pre:

s and t are distinct nodes

Post:

no augmenting path from s to t (audit)

std::vector<bool> minCut(int s) const

the side S of a minimum cut, the nodes reached from s in the residual network, after maxFlow()

Pre:

s is a node