#13073: recognition of weakly chordal graphs
--------------------------------------------------+-------------------------
Reporter: eisermbi | Owner: jason,
ncohen, rlm
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-5.1
Component: graph theory | Resolution:
Keywords: weakly chordal, hole, antihole | Work issues:
Report Upstream: N/A | Reviewers: Nathann
Cohen
Authors: Birk Eisermann | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Comment (by ncohen):
Hellooooooo Birk !!!
I just uploaded another patch that makes a Cython file from your module,
and caches the graph as a dense bitset for faster has_edge queries. It
turns out that the resulting algorithm is actually *slower* on random GNP
Before :
{{{
sage: g = graphs.RandomGNP(200,.2)
sage: %timeit g.is_weakly_chordal()
25 loops, best of 3: 17.6 ms per loop
sage: g = graphs.RandomGNP(200,.2)
sage: %timeit g.is_weakly_chordal()
25 loops, best of 3: 17.3 ms per loop
}}}
After :
{{{
sage: g = graphs.RandomGNP(200,.2)
sage: %timeit g.is_weakly_chordal()
25 loops, best of 3: 35.3 ms per loop
sage: g = graphs.RandomGNP(200,.2)
sage: %timeit g.is_weakly_chordal()
25 loops, best of 3: 37.2 ms per loop
}}}
I was quite surprised at that, and then noticed that the RandomGNP graphs
have so many long holes that the algorithm is almost linear in this case.
Hence I looked for graphs in which long holes may be hard to find (for
instance if there are none), but which is not a clique as they should
contain many induced P4. Well. Chordal graphs, then `:-)`
Hence I tried both implementations with our RandomIntervalGraph generator.
Before:
{{{
sage: g = graphs.RandomInterval(50)
sage: %timeit g.is_weakly_chordal()
5 loops, best of 3: 2.67 s per loop
sage: g = graphs.RandomInterval(50)
sage: %timeit g.is_weakly_chordal()
5 loops, best of 3: 3.12 s per loop
sage: g = graphs.RandomInterval(100)
sage: time g.is_weakly_chordal()
True
Time: CPU 39.91 s, Wall: 40.03 s
}}}
After
{{{
sage: g = graphs.RandomInterval(50)
sage: %timeit g.is_weakly_chordal()
5 loops, best of 3: 715 ms per loop
sage: g = graphs.RandomInterval(50)
sage: %timeit g.is_weakly_chordal()
5 loops, best of 3: 775 ms per loop
sage: g = graphs.RandomInterval(100)
sage: time g.is_weakly_chordal()
True
Time: CPU 8.75 s, Wall: 8.76 s
}}}
Which makes sense, as in this case the algorithm will enumerate all P4
--that takes times and requires many has_edge queries.
Of course, it is easy to fix this. I will upload in a split second yet
another patch that first checks whether the graph is chordal, in which
case there is no point in running a (potentially very expensive) search.
The runtime on interval graphs should be almost instantaneous afterwards.
Well... I feel a bit awkward because I think this optimization (and
caching) patch is a good thing, but of course it is slower on the graphs
we used as examples until now. as I think I understand why, and as it is
much faster on other instances, I think that it should be merged anyway.
What do you think ?
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13073#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
