id,summary,reporter,owner,description,type,status,priority,milestone,component,resolution,keywords,cc,merged,author,reviewer,upstream,work_issues,branch,commit,dependencies,stopgaps
18250,G.triangles_count speedup,ncohen,,"I thought that we had a decent implementation of `G.triangles_count`. Turns out that we did not.
Here is what the branch does:
- Exception on non-simple graphs. The digraph version can handle loops (it
cannot handle multiple edges) and the graph version cannot handle any of the
two.
- (obvious) speedup in the 'iter' algorithm. Before:
{{{
sage: %timeit _=g.triangles_count(algorithm='iter')
1 loops, best of 3: 10.2 s per loop
}}}
After:
{{{
sage: g=graphs.RandomGNP(700,.3)
sage: %timeit _=g.triangles_count(algorithm='iter')
1 loops, best of 3: 6.37 s per loop
}}}
- Added `triangles_count` in `static_sparse_graph` and another one in
`static_dense_graph`. They first copy the graph in a proper data structure and
count the triangles on the copy. They can take require more memory (though
they are 100000x cheaper than the default data structure)
- The default algorithm is 'iter' in the code but 'matrix' in the doc. Fixed:
`sparse_copy` is now the default.
Overall, comparing default implementations:
Before
{{{
sage: g = graphs.RandomGNP(500,.5)
sage: %timeit g.triangles_count()
1 loops, best of 3: 9.78 s per loop
}}}
After
{{{
sage: g = graphs.RandomGNP(500,.5)
sage: %timeit g.triangles_count()
10 loops, best of 3: 162 ms per loop
}}}",enhancement,closed,major,sage-6.7,graph theory,fixed,,azi vdelecroix dcoudert,,Nathann Cohen,Vincent Delecroix,N/A,,fd88c98cfc2fee8d0750cd9b6f88d1d7b8177ed4,fd88c98cfc2fee8d0750cd9b6f88d1d7b8177ed4,,