[FEATURE REQUEST] Proposal: Add Edmonds's Algorithm for Minimum Spanning Arborescence

[sairamsharan]

What would you like to Propose?

I would like to propose adding an implementation of Edmonds's algorithm (also known as the Chu–Liu/Edmonds algorithm) for finding a Minimum Spanning Arborescence.

Issue details

A Minimum Spanning Arborescence (MSA) is the directed graph equivalent of a Minimum Spanning Tree (MST). It is a tree rooted at a specific vertex r that reaches all other vertices, such that the sum of the weights of its edges is minimized. Edmonds's algorithm is a classic approach to solving this problem.

Additional Information

Why this is useful:

This algorithm is a fundamental concept in advanced graph theory and has applications in areas like computational linguistics for parsing sentences. The repository currently has excellent MST algorithms for undirected graphs (Kruskal, Prim), but lacks this important equivalent for directed graphs. Adding it would be a valuable educational addition.

Proposed Implementation:

I will implement Edmonds's algorithm in Java. The implementation will:

1. Take a directed, weighted graph and a root vertex as input.
2. Use a greedy approach to select the cheapest incoming edge for each vertex.
3. Detect and contract cycles that may form.
4. Recursively solve for the contracted graph and then expand the cycles to find the final MSA.
5. Return the total weight of the MSA.
6. Be accompanied by clear Javadoc documentation and comprehensive test cases.

I have searched the repository and have not found an existing implementation of this specific algorithm. I would like to work on this for Hacktoberfest.

[Microindole]

I would like to work on this issue for Hacktoberfest. Please assign it to me.

[Microindole]

I would like to work on this issue for Hacktoberfest. Please assign it to me.

Just took a closer look at the CONTRIBUTING.md file and realized issues aren't assigned here, my mistake!