Skip to content

direct implementations of some cliques related methods in sage/graphs/graph.py #37954

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
May 12, 2024
Merged

direct implementations of some cliques related methods in sage/graphs/graph.py #37954

merged 6 commits into from
May 12, 2024

Conversation

dcoudert
Copy link
Contributor

@dcoudert dcoudert commented May 7, 2024

We propose direct implementations of the some methods related to maximal cliques to avoid calls to networkx.

📝 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.

⌛ Dependencies

@dcoudert dcoudert self-assigned this May 7, 2024
@github-actions GitHub Actions
Copy link

github-actions bot commented May 8, 2024 •
edited
Loading

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

tscrim
tscrim reviewed May 9, 2024
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

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

Should we leave an option to run the networkx implementation? In particular, how do the timings compare?

@dcoudert
Copy link
Contributor Author

I did some tests and its surprising. This PR improves the situation for cliques_get_max_clique_graph but it is way slower for cliques_get_clique_bipartite. This is due to methods add_edge and add_edges of BipartiteGraph which are very slow (too many checks). So I should certainly revert changes in cliques_get_clique_bipartite.

sage: import networkx
sage: C = graphs.ChvatalGraph()
sage: F = graphs.FuzzyBallGraph([3,1],2)
sage: G = graphs.RandomBarabasiAlbert(100, 2)
sage: 
sage: %timeit C.cliques_get_max_clique_graph()
38.5 µs ± 109 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit Graph(networkx.make_max_clique_graph(C.networkx_graph(), create_using=networkx.MultiGraph()), multiedges=False)
214 µs ± 1.82 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit F.cliques_get_max_clique_graph()
16.2 µs ± 22 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
sage: %timeit Graph(networkx.make_max_clique_graph(F.networkx_graph(), create_using=networkx.MultiGraph()), multiedges=False)
43.7 µs ± 158 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit G.cliques_get_max_clique_graph()
425 µs ± 1.48 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit Graph(networkx.make_max_clique_graph(G.networkx_graph(), create_using=networkx.MultiGraph()), multiedges=False)
2.84 ms ± 7.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: 
sage: %timeit C.cliques_get_clique_bipartite()
371 µs ± 581 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
sage: %timeit BipartiteGraph(networkx.make_clique_bipartite(C.networkx_graph()))
144 µs ± 272 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit F.cliques_get_clique_bipartite()
59 µs ± 149 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit BipartiteGraph(networkx.make_clique_bipartite(F.networkx_graph()))
68.9 µs ± 108 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit G.cliques_get_clique_bipartite()
13.4 ms ± 24.7 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
sage: %timeit BipartiteGraph(networkx.make_clique_bipartite(G.networkx_graph()))
993 µs ± 4.53 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

@dcoudert
Copy link
Contributor Author

Clearly the slow down is due to method add_edges of BipartiteGraph. If I do as follows on the same graphs, I observe improvements.

sage: def clique_bipartite(X):
....:     G = Graph([X, []], format='vertices_and_edge')
....:     for i, clique in enumerate(IndependentSets(X, maximal=True, complement=True)):
....:         idx = - i - 1
....:         G.add_vertex(idx)
....:         G.add_edges((u, idx) for u in clique)
....:     return BipartiteGraph(G)
sage:
sage: %timeit clique_bipartite(C)
98.4 µs ± 550 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit clique_bipartite(F)
42.6 µs ± 287 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
sage: %timeit clique_bipartite(G)
727 µs ± 4.21 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

tscrim
tscrim reviewed May 10, 2024
View reviewed changes
@dcoudert @tscrim
Update src/sage/graphs/graph.py
8b2d167 
suggested change

Co-authored-by: Travis Scrimshaw <clfrngrown@aol.com>
tscrim
tscrim approved these changes May 11, 2024
View reviewed changes
Copy link
Collaborator

@tscrim tscrim left a comment

Choose a reason for hiding this comment

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

Thanks. LGTM.

@dcoudert
Copy link
Contributor Author

Thanks for the review.

vbraun pushed a commit to vbraun/sage that referenced this pull request May 11, 2024
f1d8f08 
sagemathgh-37954: direct implementations of some cliques related methods in `sage/graphs/graph.py`
    
We propose direct implementations of the some methods related to maximal
cliques to avoid calls to networkx.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37954
Reported by: David Coudert
Reviewer(s): Travis Scrimshaw
vbraun pushed a commit to vbraun/sage that referenced this pull request May 12, 2024
051ea95 
sagemathgh-37954: direct implementations of some cliques related methods in `sage/graphs/graph.py`
    
We propose direct implementations of the some methods related to maximal
cliques to avoid calls to networkx.

### 📝 Checklist

<!-- Put an `x` in all the boxes that apply. -->

- [x] The title is concise and informative.
- [x] The description explains in detail what this PR is about.
- [ ] I have linked a relevant issue or discussion.
- [x] I have created tests covering the changes.
- [x] I have updated the documentation and checked the documentation
preview.

### ⌛ Dependencies

<!-- List all open PRs that this PR logically depends on. For example,
-->
<!-- - sagemath#12345: short description why this is a dependency -->
<!-- - sagemath#34567: ... -->
    
URL: sagemath#37954
Reported by: David Coudert
Reviewer(s): Travis Scrimshaw
@vbraun vbraun merged commit d9695cb into sagemath:develop May 12, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@tscrim tscrim tscrim approved these changes

Assignees

@dcoudert dcoudert

Labels
c: graph theory t: enhancement t: performance
Projects
None yet
Milestone
sage-10.4
Development

Successfully merging this pull request may close these issues.
4 participants
@dcoudert @tscrim @vbraun @mkoeppe