Skip to content
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

Implement a function to generate the acyclic orientations of an undirected graph #37253

Closed
1 task done
saatvikraoIITGN opened this issue Feb 7, 2024 · 4 comments · Fixed by #37345
Closed
1 task done

Implement a function to generate the acyclic orientations of an undirected graph #37253

saatvikraoIITGN opened this issue Feb 7, 2024 · 4 comments · Fixed by #37345
Labels
c: graph theory t: enhancement
Milestone
sage-10.4

Comments

@saatvikraoIITGN
Copy link
Contributor

saatvikraoIITGN commented Feb 7, 2024 •
edited
Loading

Problem Description

In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation. Currently, SageMath lacks a built-in functionality to find acyclic orientations of undirected graphs. The absence of this feature limits users who require such computations for graph-related research and applications.

Proposed Solution

We will be referring to a research paper by Matthew B. Squire https://www.sciencedirect.com/science/article/abs/pii/S0196677497908919

The proposed solution involves introducing a new function to address the current lack of a dedicated feature for computing acyclic orientations in SageMath.
The function would take an undirected graph as input and implement a multi-step process:

  • first, it would reorder the vertices using a greedy approach based on degree centrality, ensuring efficient computation.
  • Then, the edges would be labeled according to the reordering of vertices.
  • Following this, the function would utilize a recursive algorithm to explore subsets of the graph's edges and generate acyclic orientations by considering a partially ordered set.

The proposed solution encapsulates the essential logic demonstrated in the provided Python code, offering a seamless and integrated way for users to obtain acyclic orientations within the SageMath environment.

Alternatives Considered

Manual Implementation: Users can manually implement the logic provided in the example code, but a built-in function would simplify the process and promote code reusability.

Additional Information

No response

Is there an existing issue for this?

  • I have searched the existing issues for a bug report that matches the one I want to file, without success.
@mantepse
Copy link
Collaborator

mantepse commented Feb 7, 2024

you should compare the timing with self.tutte_polynomial().subs(x=2, y=0).

@saatvikraoIITGN saatvikraoIITGN changed the title Implement a function to find the number of acyclic orientations of an undirected graph Implement a function to find the acyclic orientations of an undirected graph Feb 8, 2024
@saatvikraoIITGN saatvikraoIITGN changed the title Implement a function to find the acyclic orientations of an undirected graph Implement a function to generate the acyclic orientations of an undirected graph Feb 8, 2024
@dcoudert
Copy link
Contributor

dcoudert commented Feb 9, 2024

For information, there is an open pull request on this question: #35075

@dcoudert dcoudert mentioned this issue Feb 9, 2024
Merged
5 tasks
@dcoudert
Copy link
Contributor

dcoudert commented Feb 9, 2024

See also #37272 for the generation of non-isomorphic acyclic orientations using nauty_directg.

@saatvikraoIITGN
Copy link
Contributor Author

saatvikraoIITGN commented Feb 11, 2024 •
edited
Loading

Sure! I will mention these issues when I submit a PR and we can close both issues then?

vbraun pushed a commit to vbraun/sage that referenced this issue Feb 11, 2024
sagemathgh-37272: enable the generation of acyclic orientations with …
36bf4af 
…`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
@saatvikraoIITGN saatvikraoIITGN mentioned this issue Feb 14, 2024
Merged
5 tasks
vbraun pushed a commit to vbraun/sage that referenced this issue Mar 24, 2024
sagemathgh-37345: implemented function for acyclic orientations
8daac35 
    
<!-- ^^^^^
Please provide a concise, informative and self-explanatory title.
Don't put issue numbers in there, do this in the PR body below.
For example, instead of "Fixes sagemath#1234" use "Introduce new method to
calculate 1+1"
-->
**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 sagemath#37253

### 📝 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.
- [ ] 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#37345
Reported by: saatvikraoIITGN
Reviewer(s): David Coudert, grhkm21, saatvikraoIITGN
@mkoeppe mkoeppe added this to the sage-10.4 milestone Mar 25, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
c: graph theory t: enhancement
Projects
None yet
Milestone
sage-10.4
Development

Successfully merging a pull request may close this issue.

implemented function for acyclic orientations saatvikraoIITGN/sage
4 participants
@mkoeppe @mantepse @dcoudert @saatvikraoIITGN