Acyclic orientations of graphs #35075
Conversation
This class enumerate all acyclic orientations of a (di)graph. Added the method to call it in graph.
|
There is already a module |
Codecov ReportBase: 88.60% // Head: 88.57% // Decreases project coverage by
Additional details and impacted files@@ Coverage Diff @@
## develop #35075 +/- ##
===========================================
- Coverage 88.60% 88.57% -0.03%
===========================================
Files 2136 2136
Lines 396141 396206 +65
===========================================
- Hits 351009 350959 -50
- Misses 45132 45247 +115
Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here. ☔ View full report at Codecov. |
|
Could you describe the algorithm you are implementing and give a reference (if any). Algorithm 4 of 10.1016/j.dam.2017.08.002 should not be difficult to implement and it seems rather efficient. |
Maybe also 10.1006/jagm.1997.0891 which seems to have a reasonable amortized delay? |
sagemathgh-37272: enable the generation of acyclic orientations with `nauty_directg` Since version 2.8, nauty's `directg` has a new option `-a` to generate only acyclic orientations. This option was already working but not documented. This PR documents this functionality. This partially answer issue sagemath#37253 and is related to PR sagemath#35075. ### 📝 Checklist <!-- Put an `x` in all the boxes that apply. --> <!-- If your change requires a documentation PR, please link it appropriately --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> <!-- Feel free to remove irrelevant items. --> - [x] The title is concise, informative, and self-explanatory. - [x] The description explains in detail what this PR is about. - [x] I have linked a relevant issue or discussion. - [x] I have created tests covering the changes. - [x] I have updated the documentation accordingly. ### ⌛ Dependencies <!-- List all open PRs that this PR logically depends on - sagemath#12345: short description why this is a dependency - sagemath#34567: ... --> <!-- If you're unsure about any of these, don't hesitate to ask. We're here to help! --> URL: sagemath#37272 Reported by: David Coudert Reviewer(s): Martin Rubey
|
Now that #37345 has been merged, may be we can close this PR. |
Added a class to enumerate all acyclic orientations of a graph.
Added class AcyclicOrientations and a method .acyclic_orientations in graphs.graph.
The method just call the class.
The algorithm is non trivial: backtracks through the orientations of the graph without go through all of them.
Solve ticket #22468, I think (I'm not use to trac, feel free to explain me how it works)?
📝 Checklist
⌛ Dependencies