Opened 8 years ago
Closed 20 months ago
#14614 closed enhancement (fixed)
Improved is_triangle_free using bitfields
Reported by:  azi  Owned by:  jason, ncohen, rlm 

Priority:  major  Milestone:  sage9.0 
Component:  graph theory  Keywords:  
Cc:  Slani, Stefan, azi, dimpase, ncohen  Merged in:  
Authors:  David Coudert  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  302036c (Commits, GitHub, GitLab)  Commit:  302036c771bb0dd05ca797ad7933bd38fb22717c 
Dependencies:  Stopgaps: 
Description
Test (and potentially) implement a faster is_triangle_free method using the data structure from #14589
Attachments (1)
Change History (28)
comment:1 Changed 8 years ago by
Changed 8 years ago by
comment:2 Changed 8 years ago by
Here's a patch. But it's almost like what we already have, sooooooooo...Fail :P
Nathann
comment:3 Changed 8 years ago by
(it's not documented, but that's because I don't see a reason to include it in Sage)
Nathann
comment:4 Changed 8 years ago by
So what are the timings now?
comment:5 Changed 8 years ago by
Btw why you need three nested loops? Is there no way to have a row of neighbors for each vector?
comment:6 Changed 8 years ago by
The same... Give it a try ! I don't really know what to test this on, though :)
There's a small difference for those ones... But honestly... :P
sage: g = graphs.Grid2dGraph(20,20) sage: %time g.is_triangle_free() CPU times: user 0.14 s, sys: 0.00 s, total: 0.14 s Wall time: 0.15 s True sage: %time g.is_triangle_free(algorithm="dense_graph") CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s Wall time: 0.01 s True
Nathann
comment:7 Changed 8 years ago by
Well, do you see a way around ? Each row is a sequence of "long" fields...
Nathann
comment:8 followup: ↓ 9 Changed 8 years ago by
Oh, I thought that was somehow abstractly packed to allow arbitrarily long rows..
Anyways, I think the main reason this is not faster is that we first need to build the matrix and then do the checking...
It would be neat if our new backend had bitsets of neihbors (along whatever data structure we may choose to keep). I think this would then constitute a major improvement, perhaps by having a method neighbors_intersection(v_1,...,v_k) to the new list of backend functions..
comment:9 in reply to: ↑ 8 Changed 8 years ago by
Helloooooooooooo !!
Oh, I thought that was somehow abstractly packed to allow arbitrarily long rows..
Anyways, I think the main reason this is not faster is that we first need to build the matrix and then do the checking...
Hmmm... Yeah, probably. It would be nice to have instances in which the algorithm really has n^3
complexity.
....
Stupid guy. Ok, I'll give it a try on a complete bipartite graph :P
sage: g = graphs.CompleteBipartiteGraph(200,200) sage: %time g.is_triangle_free() CPU times: user 0.68 s, sys: 0.00 s, total: 0.68 s Wall time: 0.69 s True sage: %time g.is_triangle_free(algorithm="dense_graph") CPU times: user 0.18 s, sys: 0.00 s, total: 0.18 s Wall time: 0.18 s True
Well, ...
It would be neat if our new backend had bitsets of neihbors (along whatever data structure we may choose to keep). I think this would then constitute a major improvement, perhaps by having a method neighbors_intersection(v_1,...,v_k) to the new list of backend functions..
I really like to have access to a thing as basic as an array of "long" fields, though. But we could definitely has something similar, at a slightly higher level. An array of Python bitsets ?...
The problem of this data structure is addition/removal of vertices.
Nathann
comment:10 Changed 8 years ago by
 Cc changed from Slani, Stefan, azi, dimpase,ncohen to Slani, Stefan, azi, dimpase, ncohen
 Milestone changed from sage5.11 to sage5.12
comment:11 Changed 7 years ago by
 Summary changed from Improved is_triangle_free using bitfileds? to Improved is_triangle_free using bitfields
comment:12 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:13 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:14 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:15 Changed 20 months ago by
 Branch set to public/graphs/14614_is_triangle_free
 Commit set to 7f903608febbeaff6bd5ba92b63eb49189fe54be
 Milestone changed from sage6.4 to sage9.0
 Status changed from new to needs_review
Another proposal using static_dense_graph
that is significantly faster than other methods.
sage: g = graphs.Grid2dGraph(20,20) sage: %time g.is_triangle_free(algorithm='dense_graph') CPU times: user 994 µs, sys: 50 µs, total: 1.04 ms Wall time: 1.05 ms True sage: %time g.is_triangle_free(algorithm='bitset') CPU times: user 70 ms, sys: 1.1 ms, total: 71.1 ms Wall time: 70.6 ms True sage: %time g.is_triangle_free(algorithm='matrix') CPU times: user 84.1 ms, sys: 2.45 ms, total: 86.6 ms Wall time: 85.8 ms True
sage: g = graphs.CompleteBipartiteGraph(200,200) sage: %time g.is_triangle_free(algorithm='dense_graph') CPU times: user 16.1 ms, sys: 140 µs, total: 16.2 ms Wall time: 16.2 ms True sage: %time g.is_triangle_free(algorithm='bitset') CPU times: user 102 ms, sys: 1.5 ms, total: 104 ms Wall time: 103 ms True sage: %time g.is_triangle_free(algorithm='matrix') CPU times: user 130 ms, sys: 11.6 ms, total: 141 ms Wall time: 141 ms True
New commits:
7f90360  trac #14614: faster is_triangle_free using static_dense_graph

comment:16 Changed 20 months ago by
 Commit changed from 7f903608febbeaff6bd5ba92b63eb49189fe54be to 27e04f7cd32a49395b8855aa00d31af711ec33b6
Branch pushed to git repo; I updated commit sha1. New commits:
27e04f7  trac #14614: return certificate

comment:17 Changed 20 months ago by
Allow to return a certificate when algorithm
is dense_graph
or bitset
, and improve method bitset
(faster but still slower than dense_graph
).
sage: g = graphs.Grid2dGraph(20,20) sage: %time g.is_triangle_free(algorithm='dense_graph') CPU times: user 903 µs, sys: 48 µs, total: 951 µs Wall time: 955 µs True sage: %time g.is_triangle_free(algorithm='bitset') CPU times: user 2.17 ms, sys: 48 µs, total: 2.22 ms Wall time: 2.23 ms True sage: %time g.is_triangle_free(algorithm='matrix') CPU times: user 84.7 ms, sys: 5.37 ms, total: 90 ms Wall time: 86.4 ms True sage: g = graphs.CompleteBipartiteGraph(200,200) sage: %time g.is_triangle_free(algorithm='dense_graph') CPU times: user 15.6 ms, sys: 178 µs, total: 15.8 ms Wall time: 15.8 ms True sage: %time g.is_triangle_free(algorithm='bitset') CPU times: user 51.6 ms, sys: 1.23 ms, total: 52.8 ms Wall time: 52.2 ms True sage: %time g.is_triangle_free(algorithm='matrix') CPU times: user 131 ms, sys: 11.4 ms, total: 143 ms Wall time: 142 ms True
comment:18 Changed 20 months ago by
looks good  I'm slightly concerned by warnings emitted by C compiler.
comment:19 Changed 20 months ago by
I see 3 warnings when I compile without this branch, but I'm not sure where these warnings come from. How can I find them ? the messages are not so clear.
comment:20 Changed 20 months ago by
if you look at the C file in src/build/... mentioned there, they contain (in comments next to the C code lines) the cython code that it was obtained from.
comment:21 Changed 20 months ago by
the following gets rid of one of them:

src/sage/data_structures/bitset.pxi
a b cdef inline long bitset_first_in_complement(bitset_t a): 426 426 Calculate the index of the first element not in the set. If the set 427 427 is full, returns 1. 428 428 """ 429 cdef mp_size_t i, j 429 cdef mp_size_t i 430 cdef mp_bitcnt_t j 430 431 for i from 0 <= i < a.limbs: 431 432 if ~a.bits[i]: 432 433 j = (i << index_shift)  _bitset_first_in_limb_nonzero(~a.bits[i]) 433 434 if j >= a.size: 434 j =1435 return j435 return 1 436 return <mp_size_t>j 436 437 return 1 437 438 438 439 cdef inline long bitset_pop(bitset_t a) except 1:
Should I appy this and get rid of the remaining ones too?
comment:22 Changed 20 months ago by
Sure. Thank you.
comment:23 Changed 20 months ago by
 Commit changed from 27e04f7cd32a49395b8855aa00d31af711ec33b6 to 302036c771bb0dd05ca797ad7933bd38fb22717c
Branch pushed to git repo; I updated commit sha1. New commits:
302036c  correct signed/unsigned types in bitset.pxi

comment:24 Changed 20 months ago by
OK, done. Does this supress these warnings on MacOS too?
comment:25 Changed 20 months ago by
Yes, I don't see warnings anymore for static_dense_graph
. However, among the 40 files that are compiled, I have warnings in 19 of them (many in graphs...). May be we should make a specific ticket ?
comment:26 Changed 20 months ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_review to positive_review
OK, let's do the rest elsewhere.
comment:27 Changed 20 months ago by
 Branch changed from public/graphs/14614_is_triangle_free to 302036c771bb0dd05ca797ad7933bd38fb22717c
 Resolution set to fixed
 Status changed from positive_review to closed
Nathann, you're probably in the best position to test this?