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?

[robotjellyzone]

Hi @kichloo i can't see your submitted api for it, please refer the guidelines to know more about API

[kichloo]

Yes you can. Start with some use cases and design an API which can be used to access the implementation of this algorithm.

This is the comment. And I want to work on this issue and was waiting to be assigned or discussed with.

[robotjellyzone]

Hi @kichloo there is no assignment here in this org, you can right away start to work on the issue but first, you need to discuss your API here regarding your solution , if you have any doubt then go to this --> https://github.com/codezonediitj/pydatastructs/wiki/Guidelines-for-Summer-Winter-Projects and also for API design go through --> https://github.com/codezonediitj/pydatastructs/wiki/Plan-of-Action-for-the-Projects

[robotjellyzone]

Also, to ensure you regarding the assignment for an issue, you can check our issue policy -> https://github.com/codezonediitj/pydatastructs/wiki/Issue-Policy

[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

That's the API I submitted a month ago

[czgdp1807]

To make things clear, the suggested API doesn't look really good. We don't use camel case for naming functions. See, https://github.com/codezonediitj/pydatastructs/issues/186#issuecomment-612346631 as well. No modifications made according to the feedback. README has all the necessary links, if needed you can go through them. P.S. A PR should be such that it requires less review for coding style and more discussion can happen on efficiency, correctness. If the case is former, then the PR will be closed. May sound harsh but we have to do that. We don't want to hang contributors and waste their time as well as ours. See merged PRs to know what all is needed. Thanks for interest and keep contributing to open source.

[Moddy2024]

i would like to work on it as part of GSSOC'20. assign it to me. Thank You.

[robotjellyzone]

Hi @Moddy2024 yes, go ahead but do remember to share its API first here !

[Moddy2024]

Hi @Moddy2024 yes, go ahead but do remember to share its API first here !

@robotjellyzone i am from GSSOC'20 please look at my PR for this