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:

Status badges

Description (last modified by dcoudert)

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 dcoudert

  • Cc ncohen added
  • Keywords graph hyperbolicity added
  • Status changed from new to needs_review

I did my best to put comments inside the patch and sufficient documentation. I hope one will be able to review this patch ;-)

Thanks.

comment:2 follow-up: Changed 8 years ago by ncohen

  • 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: Changed 8 years ago by dcoudert

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 ncohen

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 dcoudert

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

Note: See TracTickets for help on using tickets.