EdmondsKarpAlgorithm#

class EdmondsKarpAlgorithm#

Bases: FordFulkersonAlgorithm

Edmonds-Karp’s algorithm for finding the maximum flow within a flow network.

__init__()#

Methods

`__init__`()
`get_worst_case_arguments`(input_size)	Generate a flow network with input_size.edges or (input_size.edges + 1) edges which will be a split-merge graph with source pointing to every intermediate and every intermediate pointing to sink.
`increment_n_ops`([increment])	Convenience method to increment n_ops count of the given complexity object.
`reset_n_ops`()	Convenience method to reset n_ops count of the given complexity object.
`run_algorithm`(input_instance[, ...])	Run function of Ford-Fulkerson's maximum flow algorithm.

Attributes

`algorithm_family`	rtype: `AlgorithmFamily`
`algorithm_properties`	rtype: `AlgorithmProperties`
`average_case_time_complexity`	rtype: `str`
`best_case_description`	rtype: `str`
`best_case_time_complexity`	rtype: `str`
`is_deterministic`	rtype: `bool`
`n_ops`	rtype: `int`
`name`	rtype: `str`
`space_complexity`	rtype: `str`
`worst_case_description`	rtype: `str`
`worst_case_time_complexity`	rtype: `str`

property algorithm_family: AlgorithmFamily#

Return type:: AlgorithmFamily

property algorithm_properties: AlgorithmProperties#

Return type:: AlgorithmProperties

property average_case_time_complexity: str#

Return type:: str

property best_case_description: str#

Return type:: str

property best_case_time_complexity: str#

Return type:: str

get_worst_case_arguments(input_size)#

Generate a flow network with input_size.edges or (input_size.edges + 1) edges which will be a split-merge graph with source pointing to every intermediate and every intermediate pointing to sink.

Parameters:: input_size (FordFulkersonGraphSize) – Tuple of n_edges, max_capacity with desired flow network size and maximum edge capacity. Number of edges is expected to be at least 2 and the network will have (2 + n_edges // 2) nodes. Note that maximum flow edge capacity does not influence the runtime complexity of the edmonds-karp’s algorithm.
Returns:: run_algorithm_kwargs – A dictionary with the created flow network as ‘input_instance’ value, which also stores the source and sink nodes as the first and last node in the chain.
Return type:: dict[str, Any]

increment_n_ops(increment=1)#

Convenience method to increment n_ops count of the given complexity object.

Return type:: None

property is_deterministic: bool#

Return type:: bool

property n_ops: int#

Return type:: int

property name: str#

Return type:: str

reset_n_ops()#

Convenience method to reset n_ops count of the given complexity object.

Return type:: None

run_algorithm(input_instance, verbosity_level=0, find_initial_feasible=True, *args, **kwargs)#

Run function of Ford-Fulkerson’s maximum flow algorithm.

Parameters:

input_instance (FlowNetwork[Node]) – Flow network within which to find the maximum flow. Also stores source and sink values.
verbosity_level (int (default 0)) – Select the amount of information to print throughout run of the algorithm. One of 0, 1, 2 with 0 referring to no printing, 1 leading to print the flow in the beginning and in the end and 2 meaning also print the maximum flow after each augmentation along with the augmentation path found.
find_initial_feasible (bool (default True)) – If True, start the algorithm by finding an initial feasible flow. Initial feasible flow is a prerequisite for the Ford-Fulkerson’s algorithm and if this parameter is set to False, it is assumed that the input_instance FlowNetwork object already has a feasible flow assigned to it. If that is not the case, setting this to False may lead to incorrect results.
*args (Any) – Additional arguments passed to the algorithm.
**kwargs (Any) – Additional keyword arguments passed to the algorithm.

Returns:

result – Returns True in the first index after termination (always terminates with integer capacities) and FlowNetwork with all edge flows set in the second index.

Return type:

tuple[bool, FlowNetwork[Node]]

property space_complexity: str#

Return type:: str

property worst_case_description: str#

Return type:: str

property worst_case_time_complexity: str#

Return type:: str