Generation of Random K-Trees and Partial K-Trees #36586
Labels
Comments
5 tasks
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Feb 18, 2024
…tial k-tree graphs
<!-- ^^^^^
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"
-->
<!-- Describe your changes here in detail -->
Implemented graph generators which produce a random k-tree and a random
partial k-tree. The k-tree algorithm first generates a complete graph,
before adding vertices one by one, creating a clique utilising random
existing vertices and the new vertex. Partial k-trees are generated by
producing a k-tree and then randomly removing edges from it.
<!-- Why is this change required? What problem does it solve? -->
Previously SageMath lacked a way to generat randomised graphs which have
a fixed treewidth value. This provides a methodology to do so .
<!-- If this PR resolves an open issue, please link to it here. For
example "Fixes sagemath#12345". -->
Addresses sagemath#36586
<!-- If your change requires a documentation PR, please link it
appropriately. -->
### 📝 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.
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
URL: sagemath#36587
Reported by: Damian Basso
Reviewer(s): Damian Basso, David Coudert
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Feb 19, 2024
…tial k-tree graphs
<!-- ^^^^^
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"
-->
<!-- Describe your changes here in detail -->
Implemented graph generators which produce a random k-tree and a random
partial k-tree. The k-tree algorithm first generates a complete graph,
before adding vertices one by one, creating a clique utilising random
existing vertices and the new vertex. Partial k-trees are generated by
producing a k-tree and then randomly removing edges from it.
<!-- Why is this change required? What problem does it solve? -->
Previously SageMath lacked a way to generat randomised graphs which have
a fixed treewidth value. This provides a methodology to do so .
<!-- If this PR resolves an open issue, please link to it here. For
example "Fixes sagemath#12345". -->
Addresses sagemath#36586
<!-- If your change requires a documentation PR, please link it
appropriately. -->
### 📝 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.
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
URL: sagemath#36587
Reported by: Damian Basso
Reviewer(s): Damian Basso, David Coudert
vbraun
pushed a commit
to vbraun/sage
that referenced
this issue
Feb 22, 2024
…tial k-tree graphs
<!-- ^^^^^
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"
-->
<!-- Describe your changes here in detail -->
Implemented graph generators which produce a random k-tree and a random
partial k-tree. The k-tree algorithm first generates a complete graph,
before adding vertices one by one, creating a clique utilising random
existing vertices and the new vertex. Partial k-trees are generated by
producing a k-tree and then randomly removing edges from it.
<!-- Why is this change required? What problem does it solve? -->
Previously SageMath lacked a way to generat randomised graphs which have
a fixed treewidth value. This provides a methodology to do so .
<!-- If this PR resolves an open issue, please link to it here. For
example "Fixes sagemath#12345". -->
Addresses sagemath#36586
<!-- If your change requires a documentation PR, please link it
appropriately. -->
### 📝 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.
<!-- If you're unsure about any of these, don't hesitate to ask. We're
here to help! -->
URL: sagemath#36587
Reported by: Damian Basso
Reviewer(s): Damian Basso, David Coudert
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Problem Description
Currently SageMath lacks a method to generate random graphs with fixed treewidth. Both k-trees and partial k-trees offer a practical solution to generate such graphs and can be produced with simple algorithms.
Proposed Solution
I've started working on algorithms which produce generate these random graphs. K-tree generation consists of first generating a complete graph, and then randomly creating a new clique of k+1 vertices as each new vertex is added to the graph.
Alternatives Considered
As far as I've seen there aren't any ways to generate graphs with fixed treewidth or graphs which are otherwise similar to k-trees within SageMath.
Additional Information
No response
Is there an existing issue for this?
The text was updated successfully, but these errors were encountered: