.. _f-edmondskarp: module ``td_2a.edmonds_karp`` ============================= .. inheritance-diagram:: ensae_teaching_cs.td_2a.edmonds_karp Short summary +++++++++++++ module ``ensae_teaching_cs.td_2a.edmonds_karp`` Implements the `Edmonds-Karp algorithm `_ inspired from Wikipedia (same page). :githublink:`%|py|6` Classes +++++++ +-----------------------------------------------------------------------------------+-------------------------------------------------------------------------------+ | class | truncated documentation | +===================================================================================+===============================================================================+ | :class:`EdmondsKarpGraph ` | This class represents a directed graph using adjacency matrix representation. | +-----------------------------------------------------------------------------------+-------------------------------------------------------------------------------+ Methods +++++++ +-------------------------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------+ | method | truncated documentation | +===========================================================================================+=====================================================================================================================+ | :py:meth:`__init__ ` | The graph is defined as a list of tuple (n1, n2, capacity). is the capacity of the graph. | +-------------------------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------+ | :meth:`bfs ` | Returns True if there is a path from source *s* to sink *t* in residual graph. Also fills *parent* to store the ... | +-------------------------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------+ | :meth:`edmonds_karp ` | Returns the maximum flow from *s* to *t* in the given graph. | +-------------------------------------------------------------------------------------------+---------------------------------------------------------------------------------------------------------------------+ Documentation +++++++++++++ .. automodule:: ensae_teaching_cs.td_2a.edmonds_karp :members: :special-members: __init__ :show-inheritance: