networkx icon indicating copy to clipboard operation
networkx copied to clipboard

Add new function `generate_peo` to the chordal module

Open axif0 opened this issue 1 year ago • 2 comments

Description

This PR adds a new function generate_peo to the networkx.algorithms.chordal module. Additionally, it includes corresponding unit tests for the function.

Changes Made

  • Added the generate_peo function to calculate a Perfect Elimination Ordering (PEO) of a graph.
  • Included unit tests for the generate_peo function.

Related Issues

#6873

axif0 avatar Oct 24 '23 07:10 axif0

Thanks for your contribution! Some thoughts:

  • How slow/fast is this algorithm? Is the problem NP-hard? If so, it may be wise to mention that in the doc_string. How is this function related to complete_to_chordal_graph ?
  • The name of the new function isn't particularly instructive to me. Is there a better name?
  • Your example doesn't show the expected output
  • Is this algorithm implemented for directed, multigraphs, directed multigraph and disconnected graphs? It isn't mentioned in the docs, nor it is implemented. Don't forget to add tests as well.
  • Move the text under "Notes" to the second line of the documentation. This is crucial information to understand what the function does. I'm no expert in this field, so I don't understand what it means, but try to make it as easy to read as possible
  • In the Notes it is mentioned that the input graph should be chordal. Why isn't that tested?
  • Add another non-Wikipedia reference, if available
  • Add more tests, covering edge cases, like disconnected graphs, graphs with only 1 node, etc.
  • As mentioned before, you may consider answering the questions raised in #6873 if you have the time and expertise

ghost avatar Oct 31 '23 09:10 ghost

@rossbar i would like to work on this issue but I am unable to edit this PR can I raise a separate PR for this

akshayamadhuri avatar Nov 16 '23 08:11 akshayamadhuri