[ALGO] Edmonds-Karp Algorithm for Maximum Flow

[bobluppes]

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a greedy algorithm which computes the maximum flow in a flow network. See the wikipedia entry for a more detailed description.

It would be interesting to investigate if we can re-use the existing breadth_first_traverse method for the BFS part of the algorithm.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Computes the maximum flow in a flow network using the Edmonds-Karp algorithm.
 * 
 * This algorithm finds the maximum flow in a flow network from a source vertex to a sink vertex.
 * 
 * @param graph The flow network graph.
 * @param source The source vertex.
 * @param sink The sink vertex.
 * @return The maximum flow value.
 */
template <typename V, typename E, typename WEIGHT_T = decltype(get_weight(std::declval<E>()))>
[[nodiscard]] WEIGHT_T edmonds_karp_max_flow(
    const graph<V, E, graph_type::DIRECTED>& graph,
    vertex_id_t source, vertex_id_t sink);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/maximum_flow.

Definition of Done

This issue is done when:

• The algorithm is implemented
• The new function has a javadoc-style comment explaining the interface
• Appropriate tests are added under test/graaflib/algorithm/maximum_flow_test.cpp
• A test coverage of at least 95% is reached
• A documentation entry is added under docs/docs/algorithms under the appropriate category
  • Just adding a short description and the algorithm syntax here is fine
  • See the wiki on how to build the documentation locally
• The algorithm is added to the list of algorithms in README.md

[ndcroos]

I'd like to do this after A* search. Can you assign it to me?

[bobluppes]

I'd like to do this after A* search. Can you assign it to me?

Hi, sorry for the late reply, of course! If you are still up for it I will assign it to you

[ndcroos]

Thanks for assigning it to me. I am still up for it and I have begun working on it. But it takes somewhat longer this time due to other duties.

[bobluppes]

Thanks for assigning it to me. I am still up for it and I have begun working on it. But it takes somewhat longer this time due to other duties.

No problem, thanks for the update :)

[github-actions]

Stale issue message