[ALGO] Borůvka's algorithm

[bobluppes]

Borůvka's algorithm

Borůvka's algorithm, also known as Sollin's algorithm, is a classic approach to find the Minimum Spanning Tree (MST) of a graph. It works well for disconnected graphs by finding a Minimum Spanning Forest. This algorithm is unique in the way it handles edge selections, and it can be highly efficient for sparse graphs.

More details can be found on the wikipedia entry.

Syntax

The algorithm should have the following syntax:

/**
 * @brief Finds the Minimum Spanning Tree (MST) using Borůvka's algorithm.
 *
 * Borůvka's algorithm is efficient for sparse graphs and can also find the
 * Minimum Spanning Forest for disconnected graphs. This algorithm returns
 * a vector containing edge IDs that make up the MST.
 *
 * @tparam GRAPH The graph type.
 * @param graph The input graph.
 * 
 * @return A std::vector of edge IDs that make up the MST.
 *         Returns an empty vector if the MST cannot be formed.
 */
template <typename GRAPH>
std::vector<edge_id_t> boruvka_minimum_spanning_tree(
    const GRAPH& graph);

This should live in the graaf::algorithm namespace under include/graaflib/algorithm/minimum_spanning_tree/boruvka.h.

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/minimum_spanning_tree/boruvka_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

[HarryHeres]

Hi, I have some experience with C++ and would like to tak a part in this project! I find this a good first issue since it’s fairly known what needs to be done and since I’m Czech, I have access to many original materials about Borůvka. Therefore, I’d like to try and implement this, if possible. I’m also taking part as a Hacktoberfest attendee

[bobluppes]

Hi, I have some experience with C++ and would like to tak a part in this project! I find this a good first issue since it’s fairly known what needs to be done and since I’m Czech, I have access to many original materials about Borůvka. Therefore, I’d like to try and implement this, if possible. I’m also taking part as a Hacktoberfest attendee

Hi Harry, welcome to Graaf!
Of course, happy to assign this to you. Looking forward to your contribution :)

[HarryHeres]

Awesome, thank you!

[HarryHeres]

Hi @bobluppes, just wanted to make an update. I've been busy with work and studies so I haven't been able to get to this yet, but I hope to get to it at the end of the upcoming week.

Just wanted to inform that I indeed am thinking about this, just haven't had much time to fully get into it yet. Sorry for that!

[bobluppes]

Hi @bobluppes, just wanted to make an update. I've been busy with work and studies so I haven't been able to get to this yet, but I hope to get to it at the end of the upcoming week.

Just wanted to inform that I indeed am thinking about this, just haven't had much time to fully get into it yet. Sorry for that!

Hi @HarryHeres, no problem!
Thanks for the update and let me know if you have any questions/issues

[HarryHeres]

@bobluppes I finally got some time to realize this. As I'm working, I had an idea. Wouldn't it be better to differentiate the return values a bit? For example, we could return a NULL value if the provided graph is invalid (e.g. null pointer or 0 vertices or 0 edges). Otherwise, if the MST just was not computable, we could then return an empty vector. I believe this would benefit the user of a bit more knowledge of what happend?

Also, under the type GRAPH, what do we expect the user to put in? I suppose something like graph<V,E,graph_type>? Why not expect the exact graph typename, just like in Prim's or Kruskal's implementations?

I'm not a C++ dev mainly so I might have a completely wrong view on this.

[bobluppes]

@bobluppes I finally got some time to realize this. As I'm working, I had an idea. Wouldn't it be better to differentiate the return values a bit? For example, we could return a NULL value if the provided graph is invalid (e.g. null pointer or 0 vertices or 0 edges). Otherwise, if the MST just was not computable, we could then return an empty vector. I believe this would benefit the user of a bit more knowledge of what happend?

Also, under the type GRAPH, what do we expect the user to put in? I suppose something like graph<V,E,graph_type>? Why not expect the exact graph typename, just like in Prim's or Kruskal's implementations?

I'm not a C++ dev mainly so I might have a completely wrong view on this.

Hi @HarryHeres, these are some good remarks! Regarding the GRAPH type, you are correct that changing the interface to something like graph<V, E, graph_type> is more precise. This should avoid the user from passing in any arbitrary type.

Regarding the return value, the reasoning for the proposed interface is that we can either compute a MST for the graph, or there is no MST (for example due to the graph not being spannable). Therefore we either return a non-empty vector or an empty one.

Do you see a different reason as to why we can not compute a MST? If we want to make it more explicit that we did not find a MST we could indeed differentiate this in the return value as you suggested. We could do this by returning an std::optional<std::vector<edge_id_t>>, which is the modern equivalent of a nullptr 😉

[HarryHeres]

Awesome, thank you for your input!

Regarding the return values - std::optional is definitely an interesting choice. You do have a point with the MST calculation being basically either possible or not. For the time being, I will leave it as it was intended, if there's any other state I would run into, we could discuss further if we should introduce a more sophisticated pattern :) Does that sound OK?

[bobluppes]

Awesome, thank you for your input!

Regarding the return values - std::optional is definitely an interesting choice. You do have a point with the MST calculation being basically either possible or not. For the time being, I will leave it as it was intended, if there's any other state I would run into, we could discuss further if we should introduce a more sophisticated pattern :) Does that sound OK?

Thanks, that sounds fine by me! I think it would make sense to do a follow up and change the interface of the MST functions to return an empty optional if no tree was found. Then the return value semantics are more clear for the user.

But let’s continue like this and discuss further in a follow up 👍🏻

[github-actions]

Stale issue message

[HarryHeres]

@bobluppes Can we reopen? I was quite busy lately

[github-actions]

Stale issue message

[HarryHeres]

Unstale

[github-actions]

Stale issue message