Changes between Initial Version and Version 5 of Ticket #13808


Ignore:
Timestamp:
12/15/12 15:06:57 (8 years ago)
Author:
dcoudert
Comment:

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.

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #13808

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

  • Ticket #13808 – Description

    initial v5  
    11This 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.
     2
     3
     4APPLY:
     5* [attachment:trac_13808-v2.patch]