Skip to content

implemented function for acyclic orientations #37345

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 19 commits into from
Mar 25, 2024
Merged

implemented function for acyclic orientations #37345

merged 19 commits into from
Mar 25, 2024

Conversation

saatvikraoIITGN
Copy link
Contributor

Description
This PR introduces an efficient algorithm for generating all acyclic orientations of an undirected graph based on the work by Mathew B. Squire. The algorithm utilizes a recursive approach along with concepts from posets and subsets to improve the efficiency of acyclic orientation generation significantly.

Changes Made

  1. Implemented the reorder_vertices function to efficiently reorder vertices based on a specific criterion, improving subsequent acyclic orientation generation.
  2. Created the order_edges function to assign labels to edges based on the reordered vertices, simplifying the acyclic orientation process.
  3. Introduced the generate_orientations function to efficiently generate acyclic orientations by considering subsets of edges and checking for upsets in a corresponding poset.
  4. Implemented the recursive helper function to generate acyclic orientations for smaller graphs, building up to larger graphs.
  5. Modified the main function to use SageMath for graph manipulation and incorporated the new algorithm.

Fixes #37253

📝 Checklist

  • The title is concise, informative, and self-explanatory.
  • The description explains in detail what this PR is about.
  • I have linked a relevant issue or discussion.
  • I have created tests covering the changes.
  • I have updated the documentation accordingly.

⌛ Dependencies

grhkm21
grhkm21 reviewed Feb 14, 2024
View reviewed changes
@grhkm21
Copy link
Contributor

grhkm21 commented Feb 15, 2024

Is this related to #35075? Also, lint CI is failing.

dcoudert
dcoudert reviewed Feb 15, 2024
View reviewed changes
Copy link
Contributor

@dcoudert dcoudert left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thank you for this first draft. I see that there is room for improvements. A first issue is that you implicitly assume that the vertices of the input graph are labeled 0..n-1 which is not always the case. To cope with this issue, you should use method relabel to get both a copy of the input graph with suitable vertex labels and the mapping.

Below are a few comments.

@dcoudert
Copy link
Contributor

To fix the failing doctests, you must expose the method in Graph. See the bottom of file src/sage/graphs/graph.py to understand how to do that.

dcoudert
dcoudert suggested changes Mar 3, 2024
View reviewed changes
dcoudert
dcoudert suggested changes Mar 8, 2024
View reviewed changes
Copy link
Contributor

@dcoudert dcoudert left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We still have serious issues. We also have some minor issues regarding the coding style (too many parenthesis in unnecessary places, iteration of G.vertices() when over G is enough, etc.), but this can be fixed in a separate PR.

dcoudert
dcoudert suggested changes Mar 11, 2024
View reviewed changes
dcoudert
dcoudert suggested changes Mar 11, 2024
View reviewed changes
@dcoudert
Copy link
Contributor

Can you add doctests for small cases and check that the output is consistent. I don't think it is so far.

sage: list(Graph().acyclic_orientations())
[Graph on 0 vertices]
sage: list(Graph(1).acyclic_orientations())
[Graph on 0 vertices]
sage: list(Graph(2).acyclic_orientations())
[Graph on 0 vertices]

@dcoudert
Copy link
Contributor

A graph without edge has no orientation, right ? so the method should not return an empty graph is such case.

@dcoudert
Copy link
Contributor

You could add at the beginning of the method:

if not G.size():
    # A graph without edge cannot be oriented
    return

dcoudert
dcoudert suggested changes Mar 14, 2024
View reviewed changes
@dcoudert
Copy link
Contributor

Don't forget that the output of the doctests are now DiGraph(...) and not Graph(...).

dcoudert
dcoudert suggested changes Mar 14, 2024
View reviewed changes
dcoudert
dcoudert approved these changes Mar 15, 2024
View reviewed changes
Copy link
Contributor

@dcoudert dcoudert left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM.

We can certainly improve the code to get a faster method, but in a future PR. I will think about it.

@saatvikraoIITGN saatvikraoIITGN requested a review from grhkm21 March 21, 2024 06:49
@github-actions GitHub Actions
Copy link

Documentation preview for this PR (built with commit bef9946; changes) is ready! 🎉

@vbraun vbraun merged commit 8daac35 into sagemath:develop Mar 25, 2024
@saatvikraoIITGN saatvikraoIITGN mentioned this pull request Apr 15, 2024
Open
5 tasks
This was referenced Sep 22, 2024
Open
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@grhkm21 grhkm21 Awaiting requested review from grhkm21

1 more reviewer

@dcoudert dcoudert dcoudert approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
c: graph theory p: major / 3 t: feature
Projects
None yet
Milestone
sage-10.4
Development

Successfully merging this pull request may close these issues.

Implement a function to generate the acyclic orientations of an undirected graph
5 participants
@saatvikraoIITGN @grhkm21 @dcoudert @vbraun @mkoeppe