Add Edmond's algorithm

[czgdp1807]

Description of the problem

In graph theory, Edmonds' algorithm or Chu–Liu/Edmonds' algorithm is an algorithm for finding a spanning arborescence of minimum weight (sometimes called an optimum branching). It is the directed analog of the minimum spanning tree problem.

Example of the problem

References/Other comments

.. [1] https://en.wikipedia.org/wiki/Edmonds%27_algorithm

[ka1shi]

@czgdp1807 I would like to work on it as part of GSSOC'20. Please assign it to me. Thank You.

[kichloo]

@czgdp1807 Can I take up this issue?

[czgdp1807]

Yes you can. Start with some use cases and design an API which can be used to access the implementation of this algorithm. Go through, https://github.com/codezonediitj/pydatastructs/wiki/Guidelines-for-Summer-Winter-Projects

[kichloo]

@czgdp1807 Function mst will have 2 parameters:

• root
• G

Then,we will have function load having 2 parameters:

• arcs
• weights

Then function reverse having the parameters:

• graph

Function getCycle having 4 parameters:

• n
• g
• visited
• cycle

Function mergeCycles having 5 parameters:

• cycle
• G
• RG
• g
• rg

[czgdp1807]

API for minimum spanning trees are already there in master. Why do you need load, reverse, getCycle, and mergeCycles? Can you please explain the use of each one of them?

[kichloo]

@czgdp1807 Actually, this is my first contribution to this project, so I didnt know about which functions are already present, thats why I mentioned all the functions of the program

[kichloo]

@czgdp1807 load function will be used to set the value of g depending on the source.
reverse function will be used to set the value of g based on the destination. getCycle function will be used to set the value of the visited variable and the cycle variable. The mergeCycle will be used to find the minimal internal edge weight

[robotjellyzone]

Any update @kichloo ?

[kichloo]

@robotjellyzone I had submitted the API for it and was waiting for reply by czdp. Why have you unassigned it?