Skip to content

adding has_subgraph_decomposition method to GenericGraph #39598

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 6 commits into from
Jun 14, 2025
Merged

adding has_subgraph_decomposition method to GenericGraph #39598

merged 6 commits into from
Jun 14, 2025

Conversation

seblabbe
Copy link
Contributor

Following the question https://ask.sagemath.org/question/81610/test-if-a-graph-has-a-claw-decomposition/,
the current PR is adding a has_subgraph_decomposition method to the GenericGraph class.

It also adds a _subgraph_decomposition_dlx method allowing to enumerate/count the decompositions.

📝 Checklist

  • The title is concise and informative.
  • 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 and checked the documentation preview.

@seblabbe seblabbe force-pushed the graph_decomposition branch from 041554b to 40cbaf3 Compare February 27, 2025 11:55
@seblabbe seblabbe requested a review from dcoudert February 27, 2025 11:56
@seblabbe
Copy link
Contributor Author

A question I still have is whether a method has_subgraph_decomposition is the best choice. Should it rather be a method subgraph_decomposition returning a decomposition? Should it be a method subgraph_decompositions returning an iterator over all decomposition?

@seblabbe seblabbe mentioned this pull request Feb 27, 2025
Closed
2 tasks
@seblabbe
Copy link
Contributor Author

seblabbe commented Feb 27, 2025 •
edited
Loading

While I was writing the code, I observed a bug in the current subgraph search which yield duplicate copies of the same subgraph. This is why I first need to create a set of rows to avoid duplicates.

I created #39599 for this issue.

@github-actions GitHub Actions
Copy link

github-actions bot commented Feb 27, 2025 •
edited
Loading

Documentation preview for this PR (built with commit 352a390; changes) is ready! 🎉
This preview will update shortly after each push to this PR.

@dcoudert
Copy link
Contributor

Some comments

  • It seems that the method is currently for undirected graphs only. If so, it should be in graph.py or in a new module devoted to subgraph search and subgraph partition/covering.
  • I like the idea of an iterator subgraph_decompositions.
  • I don't see the need for method _subgraph_decomposition_dlx. Unless you plan to implement several methods, it can be included in the main method.
  • Concerning subgraph_search_iterator, I don't know how to avoid returning several times the same graph. If you have an algorithm in mind, we could at its implementation to the list of GSoC'25 project proposals.
  • Add a warning in the method that the memory consumption can be huge, and a todo statement to recall to improve the implementation when subgraph_search_iterator will be improved

dcoudert
dcoudert suggested changes Feb 27, 2025
View reviewed changes
@seblabbe seblabbe force-pushed the graph_decomposition branch from 40cbaf3 to 041554b Compare March 6, 2025 17:41
@seblabbe
Copy link
Contributor Author

seblabbe commented Mar 6, 2025

I just made changes to the branch. I could not push on my own github branch (because it was based on beta6), so I did a forced push. I don't know why commits do not appear here?

@seblabbe seblabbe force-pushed the graph_decomposition branch from 041554b to 352a390 Compare March 6, 2025 17:46
@seblabbe
Copy link
Contributor Author

seblabbe commented Mar 6, 2025

Ok, looks better now

@dcoudert
Copy link
Contributor

dcoudert commented Mar 7, 2025

I'm trying to get a better understanding of the definition of the problem. The current description of the method is not enough. A reference might be welcome.
If I understand well, a valid solution is a covering of the set of vertices of the graph $G$ into isometric copies of $H$. A vertex of $G$ may appear in multiple copies of $H$. However, an edge of $G$ appears in a single copy.

Is is possible to get a valid solution such that some edges of $G$ are not included in any copy of $H$ ?
If not, you can start checking if the number of edges of $G$ is a multiple of the number of edges of $H$.

Since the graph must be simple, add a call to self._scream_if_not_simple() at the beginning of the method.

It as no -> It has no

@seblabbe
Copy link
Contributor Author

seblabbe commented May 22, 2025 •
edited
Loading

I finished writting my HDR... and could now come back to this ticket:)

I made the changes asked by the reviewer.

Except, that I did not add the self._scream_if_not_simple() at the beginning of the method, because self._scream_if_not_simple() is already called by self.subgraph_search_iterator. If one day, the method self.subgraph_search_iterator is changed to be able to handle non simple graphs, then, the current new method would also automatically handle them. Therefore, I prefer not to add the assumption because there is no assumption of simplicity in the code of the method itself.

dcoudert
dcoudert reviewed May 24, 2025
View reviewed changes
@seblabbe
Copy link
Contributor Author

Thanks for your comments. I made the changes.

dcoudert
dcoudert approved these changes May 29, 2025
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.

vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 4, 2025
bf4f03d 
sagemathgh-39598: adding has_subgraph_decomposition method to GenericGraph
    
Following the question https://ask.sagemath.org/question/81610/test-if-
a-graph-has-a-claw-decomposition/,
the current PR is adding a `has_subgraph_decomposition` method to the
GenericGraph class.

It also adds a `_subgraph_decomposition_dlx` method allowing to
enumerate/count the decompositions.

### 📝 Checklist

- [x] The title is concise and informative.
- [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 and checked the documentation
preview.
    
URL: sagemath#39598
Reported by: Sébastien Labbé
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 6, 2025
4f3844f 
sagemathgh-39598: adding has_subgraph_decomposition method to GenericGraph
    
Following the question https://ask.sagemath.org/question/81610/test-if-
a-graph-has-a-claw-decomposition/,
the current PR is adding a `has_subgraph_decomposition` method to the
GenericGraph class.

It also adds a `_subgraph_decomposition_dlx` method allowing to
enumerate/count the decompositions.

### 📝 Checklist

- [x] The title is concise and informative.
- [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 and checked the documentation
preview.
    
URL: sagemath#39598
Reported by: Sébastien Labbé
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 8, 2025
8d55b7d 
sagemathgh-39598: adding has_subgraph_decomposition method to GenericGraph
    
Following the question https://ask.sagemath.org/question/81610/test-if-
a-graph-has-a-claw-decomposition/,
the current PR is adding a `has_subgraph_decomposition` method to the
GenericGraph class.

It also adds a `_subgraph_decomposition_dlx` method allowing to
enumerate/count the decompositions.

### 📝 Checklist

- [x] The title is concise and informative.
- [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 and checked the documentation
preview.
    
URL: sagemath#39598
Reported by: Sébastien Labbé
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 9, 2025
524d177 
sagemathgh-39598: adding has_subgraph_decomposition method to GenericGraph
    
Following the question https://ask.sagemath.org/question/81610/test-if-
a-graph-has-a-claw-decomposition/,
the current PR is adding a `has_subgraph_decomposition` method to the
GenericGraph class.

It also adds a `_subgraph_decomposition_dlx` method allowing to
enumerate/count the decompositions.

### 📝 Checklist

- [x] The title is concise and informative.
- [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 and checked the documentation
preview.
    
URL: sagemath#39598
Reported by: Sébastien Labbé
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 9, 2025
28665f2 
sagemathgh-39598: adding has_subgraph_decomposition method to GenericGraph
    
Following the question https://ask.sagemath.org/question/81610/test-if-
a-graph-has-a-claw-decomposition/,
the current PR is adding a `has_subgraph_decomposition` method to the
GenericGraph class.

It also adds a `_subgraph_decomposition_dlx` method allowing to
enumerate/count the decompositions.

### 📝 Checklist

- [x] The title is concise and informative.
- [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 and checked the documentation
preview.
    
URL: sagemath#39598
Reported by: Sébastien Labbé
Reviewer(s): David Coudert
vbraun pushed a commit to vbraun/sage that referenced this pull request Jun 9, 2025
039fa25 
sagemathgh-39598: adding has_subgraph_decomposition method to GenericGraph
    
Following the question https://ask.sagemath.org/question/81610/test-if-
a-graph-has-a-claw-decomposition/,
the current PR is adding a `has_subgraph_decomposition` method to the
GenericGraph class.

It also adds a `_subgraph_decomposition_dlx` method allowing to
enumerate/count the decompositions.

### 📝 Checklist

- [x] The title is concise and informative.
- [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 and checked the documentation
preview.
    
URL: sagemath#39598
Reported by: Sébastien Labbé
Reviewer(s): David Coudert
@vbraun vbraun merged commit 85df9ff into sagemath:develop Jun 14, 2025
14 of 22 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
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
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@seblabbe @dcoudert @vbraun