class Graphlb::Algorithms::FordFulkerson

Overview

in the graph, to find the maximum possible flow from s to t with following constraints needs to be true:

a) Flow on an edge doesn’t exceed the given capacity of the edge.

b) Incoming flow is equal to outgoing flow for every vertex except s and t.

In ford Fulkerson algorithm An augmenting path is a simple path from source to sink which do not include any cycles and that pass only through positive weighted edges. A residual network graph indicates how much more flow is allowed in each edge in the network graph. If there are no augmenting paths possible from source to sink, then the flow is maximum. The result i.e. the maximum flow will be the total flow out of source node which is also equal to total flow in to the sink node.

Defined in:

graphlb/algorithms/ford_fulkerson.cr

Instance Method Summary

Instance Method Detail

def run(graph, source, sink) #

Finds the maximum flow in the flow network graph

Given a source, sink and flow network the ford fulkerson algorithm runs on the graph. The algorithm starts form the source vetex and finds the maximum flow. This algorithm uses BFS to go to traverse the graph.

@param : graph, a directed graph with edge capacities,

@param : source, a source node where the algorithm starts,

@param : sink, a sink where the flow ends

@return : max_flow[Float64], the maximum flow in the flow network


[View source]