Opened 10 years ago

Closed 10 years ago

#7966 closed enhancement (fixed)

Giving some punch to distance computations

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3.4
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.4.alpha0
Authors: Nathann Cohen Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This patch creates a function shortest_path_all_vertices in c_graphs which, given a vertex v, computes a shortest path for each other vertex.

With small other modifications, it improves the speed of many functions ( which were all calling each other )

Before :

sage: g = graphs.RandomGNP(50,.3)
sage: %timeit g.shortest_path_lengths(0)
100 loops, best of 3: 3.72 ms per loop
sage: %timeit g.average_distance()
10 loops, best of 3: 383 ms per loop
sage: %timeit g.wiener_index()
10 loops, best of 3: 384 ms per loop
sage: %timeit g.szeged_index()
10 loops, best of 3: 325 ms per loop
sage: %timeit g.eccentricity()
10 loops, best of 3: 189 ms per loop
sage: g.sparse6_string()
':q_OW_CCBb?WcOL@@`_{CGDB@pCGIF``@[WQK_`?w_QIDoo_WSJEBWGOKIDbG?CZ?@@Owwb?@?o_SOMba@X?bA@`OpKhBB@p?kX@Caq@YAACAphWn@B@po{j?@`?o_]QIeGOWMGDCqheEDB@pXMAEBa@GscYLoo__QJEBaxcvBECAPWqYNQ`gwgTKERX}?@@@@Gg[QHdBXt@?BAa@WmYNGWo[OLFCQhqCLFCRPky]POow_SLGCRHw}ca@_w_SLHCq`_u[OGg?GEDBAP_{iUJeBiYKGCbPp_qYMFbyLIea``WoYMFcA`SkXMGS[?MIFCahgw\\NP`Ww]VLfSskYMHDApcs[NHSy`R?A@pOkWMGcb@oy]TjGGKOJIEBh|QjUOox?mWLEryHIh___WOaRIDr@cu[MhTauCCBa@Gk]PHdax_w]NhCq\\Sm'

After

sage: %timeit g.shortest_path_lengths(0)
10 loops, best of 3: 430 µs per loop
sage: %timeit g.average_distance()
10 loops, best of 3: 22 ms per loop
sage: %timeit g.wiener_index()
10 loops, best of 3: 22.1 ms per loop
sage: %timeit g.szeged_index()
10 loops, best of 3: 41.5 ms per loop
sage: %timeit g.eccentricity()
10 loops, best of 3: 22 ms per loop

Nathann

Attachments (1)

trac_7966.patch (9.2 KB) - added by ncohen 10 years ago.

Download all attachments as: .zip

Change History (7)

comment:1 Changed 10 years ago by ncohen

  • Status changed from new to needs_review

comment:2 Changed 10 years ago by ncohen

Small modification to distance_graph too:

Before :

sage: %timeit g.distance_graph([2,8,9])
10 loops, best of 3: 127 ms per loop

After

sage: %timeit g.distance_graph([2,8,9])
10 loops, best of 3: 49 ms per loop

Nathann

comment:3 Changed 10 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to needs_work

The speedups are great, but I got one extra failure (against 4.3.3 on Fedora 12):

sage -t  graphs/base/c_graph.pyx
File "/usr/local/sage-4.3.3/sage/devel/sage-trac/sage/graphs/base/c_graph.pyx",\
 line 1427:
    sage: all([ len(paths[v]) == 0 or len(paths[v])-1 == g.distance(0,v) for v \
in g])
Exception raised:
    Traceback (most recent call last):
      File "/usr/local/sage-4.3.3/sage/local/bin/ncadoctest.py", line 1231, in \
run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/usr/local/sage-4.3.3/sage/local/bin/sagedoctest.py", line 38, in r\
un_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compil\
eflags)
      File "/usr/local/sage-4.3.3/sage/local/bin/ncadoctest.py", line 1172, in \
run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_43[7]>", line 1, in <module>
        all([ len(paths[v]) == Integer(0) or len(paths[v])-Integer(1) == g.dist\
ance(Integer(0),v) for v in g])###line 1427:
    sage: all([ len(paths[v]) == 0 or len(paths[v])-1 == g.distance(0,v) for v \
in g])
    KeyError: 20

Please could you look at this?

comment:4 Changed 10 years ago by ncohen

  • Status changed from needs_work to needs_review

At first, the function associated a path from v to each other vertex, possibly empty if there was none. Then I noticed the other functions in Sage expected the dictionary to only contain keys corresponding to the vertices reachable from v (which was sound, too), and changed the original function, forgetting the docstrings... Fixed now !

And I also removed the (commented) loop which was associating empty paths when needed...

Thank you again ! :-)

Nathann

Changed 10 years ago by ncohen

comment:5 Changed 10 years ago by zimmerma

  • Authors set to Nathann Cohen
  • Status changed from needs_review to positive_review

with the new patch c_graph.pyx works again:

[zimmerma@coing sage]$ sage -t  graphs/base/c_graph.pyx
sage -t  "devel/sage-7966/sage/graphs/base/c_graph.pyx"     
         [2.5 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 2.5 seconds

Thus a positive review.

Paul

comment:6 Changed 10 years ago by mvngu

  • Merged in set to sage-4.3.4.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.