Opened 8 years ago
Last modified 8 years ago
#13808 closed enhancement
Gromov hyperbolicity of graphs — at Version 5
Reported by: | dcoudert | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.6 |
Component: | graph theory | Keywords: | graph, hyperbolicity |
Cc: | ncohen | Merged in: | |
Authors: | David Coudert | Reviewers: | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This patch implements algorithms for computing the Gromov hyperbolicity of a graph. Although the worst case time complexity is in O(n^4)
, the proposed implementation performs quite well in practice. It has been used on graphs with more than 10.000 vertices.
APPLY:
Change History (5)
comment:1 Changed 8 years ago by
- Cc ncohen added
- Keywords graph hyperbolicity added
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 8 years ago by
- Status changed from needs_review to needs_work
Here is my current patch, and two comments :
- It would be nice if
sage -coverage hyperbolicity.pyx
returned "100% coverage". I hate to say it, because it often means adding useless tests just to fit to the metrics
-_-
- What is the use of _reduce_biconnected_graph compared to goodcores ? The docstring says that this function, by removing degree 2 vertices whose neighborhood is an edge, would reduce a complete bipartite graph to an edge... But no vertex of a complete bipartite graph is adjacent to two adjacent vertices (a triangle). I do not see how (as the docstring says) this function does anything different from the good core decomposition method above.
It would also be better to set this ticket to need_work
until your have found out where the bug you found comes from.
Tell me what you think of the changes I made ! They should make the html doc nicer !
Nathann
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 8 years ago by
Replying to ncohen:
Here is my current patch, and two comments :
- It would be nice if
sage -coverage hyperbolicity.pyx
returned "100% coverage". I hate to say it, because it often means adding useless tests just to fit to the metrics
-_-
OK, I will work on this.
- What is the use of _reduce_biconnected_graph compared to goodcores ?
Useless, but since it is very fast (linear) it can be used for all methods, while goodcores is only for cuts+.
The docstring says that this function, by removing degree 2 vertices whose neighborhood is an edge, would reduce a complete bipartite graph to an edge... But no vertex of a complete bipartite graph is adjacent to two adjacent vertices (a triangle). I do not see how (as the docstring says) this function does anything different from the good core decomposition method above.
Oups. We must add an edge to get many triangles.
It would also be better to set this ticket to
need_work
until your have found out where the bug you found comes from.
Sure.
Tell me what you think of the changes I made ! They should make the html doc nicer !
That's perfect. Thanks.
Nathann
comment:4 in reply to: ↑ 3 Changed 8 years ago by
Useless, but since it is very fast (linear) it can be used for all methods, while goodcores is only for cuts+.
Oh. But what is the difference between this function and the other one, what is it that _reduce_biconnected_graph
can do and that the core decomposition can't ? Is their running time very different for the same purposes ? Why do you need two functions ?
Nathann
comment:5 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Hello,
I have fully revised the patch. I have merged both patches into a new one to simplify the process. I have removed the _reduce_biconnected_graph
and good_core_decomposition
methods and added a new one: elimination_buckets
, where a bucket is understood as a set of vertices that can be eliminated as soon as the lower equals the index of the bucket. So far, this new function only identifies vertices that can be eliminated as soon as we know that the lower bound is 1. The code contains all the machinery to handle larger values, but I don't have good heuristic/algorithm ready to identify vertices that can be eliminated for 2 (only slow and not efficient methods). I propose to let this part for a future patch. This one is already huge...
The doc coverage is now 100%.
Should be better now.
I did my best to put comments inside the patch and sufficient documentation. I hope one will be able to review this patch ;-)
Thanks.