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: sage-9.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:

Status badges

Description

Test (and potentially) implement a faster is_triangle_free method using the data structure from #14589

Attachments (1)

trac_14614.patch (3.3 KB) - added by ncohen 8 years ago.

Download all attachments as: .zip

Change History (28)

comment:1 Changed 8 years ago by azi

Nathann, you're probably in the best position to test this?

Changed 8 years ago by ncohen

comment:2 Changed 8 years ago by ncohen

Here's a patch. But it's almost like what we already have, sooooooooo...Fail :-P

Nathann

comment:3 Changed 8 years ago by ncohen

(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 azi

So what are the timings now?

comment:5 Changed 8 years ago by azi

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 ncohen

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 ncohen

Well, do you see a way around ? Each row is a sequence of "long" fields...

Nathann

comment:8 follow-up: Changed 8 years ago by azi

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 ncohen

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 jdemeyer

  • Cc changed from Slani, Stefan, azi, dimpase,ncohen to Slani, Stefan, azi, dimpase, ncohen
  • Milestone changed from sage-5.11 to sage-5.12

comment:11 Changed 7 years ago by jdemeyer

  • Summary changed from Improved is_triangle_free using bitfileds? to Improved is_triangle_free using bitfields

comment:12 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:13 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:14 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 20 months ago by dcoudert

  • Authors set to David Coudert
  • Branch set to public/graphs/14614_is_triangle_free
  • Commit set to 7f903608febbeaff6bd5ba92b63eb49189fe54be
  • Milestone changed from sage-6.4 to sage-9.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:

7f90360trac #14614: faster is_triangle_free using static_dense_graph

comment:16 Changed 20 months ago by git

  • Commit changed from 7f903608febbeaff6bd5ba92b63eb49189fe54be to 27e04f7cd32a49395b8855aa00d31af711ec33b6

Branch pushed to git repo; I updated commit sha1. New commits:

27e04f7trac #14614: return certificate

comment:17 Changed 20 months ago by dcoudert

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 dimpase

looks good - I'm slightly concerned by warnings emitted by C compiler.

comment:19 Changed 20 months ago by dcoudert

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 dimpase

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 dimpase

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): 
    426426    Calculate the index of the first element not in the set. If the set
    427427    is full, returns -1.
    428428    """
    429     cdef mp_size_t i, j
     429    cdef mp_size_t i
     430    cdef mp_bitcnt_t j
    430431    for i from 0 <= i < a.limbs:
    431432        if ~a.bits[i]:
    432433            j = (i << index_shift) | _bitset_first_in_limb_nonzero(~a.bits[i])
    433434            if j >= a.size:
    434                 j = -1
    435             return j
     435                return -1
     436            return <mp_size_t>j
    436437    return -1
    437438
    438439cdef 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 dcoudert

Sure. Thank you.

comment:23 Changed 20 months ago by git

  • Commit changed from 27e04f7cd32a49395b8855aa00d31af711ec33b6 to 302036c771bb0dd05ca797ad7933bd38fb22717c

Branch pushed to git repo; I updated commit sha1. New commits:

302036ccorrect signed/unsigned types in bitset.pxi

comment:24 Changed 20 months ago by dimpase

OK, done. Does this supress these warnings on MacOS too?

comment:25 Changed 20 months ago by dcoudert

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 dimpase

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

  • Branch changed from public/graphs/14614_is_triangle_free to 302036c771bb0dd05ca797ad7933bd38fb22717c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.