#13073: recognition of weakly chordal graphs
--------------------------------------------------+-------------------------
Reporter: eisermbi | Owner: jason,
ncohen, rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-5.1
Component: graph theory | Resolution:
Keywords: weakly chordal, hole, antihole | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
--------------------------------------------------+-------------------------
Comment (by eisermbi):
Hello Nathann!!
Thank you for your comments! I have revised the patch... Now to answer the
questions:
Location / Visibility:
* The weakly chordal test (checking for !`C_k`, !`k \geq 5`) provides
similar functionality as the chordal test (checking for !`C_k`, !`k \geq
4`). Since the function is_chordal() is contained in the file
generic_graph.py, I chose this file for the new functions. You are right
that the weakly chordal test does not consider directed edges, but just
its underlying undirected graph. My previous version made an 'undirected'
copy of the (Di)Graph and thus, it yield a correct result. To gain speed,
I removed this part and because of this moved the algorithm into graph.py.
* Shall the functions be moved to an extra file?
* I think since the functions is_even_hole_free() and is_odd_hole_free()
are available, it might be useful to have the function
is_hole_free()/is_antihole_free() available as well (and not make them
private)...
Run time / speed:
* It is true that g.complement().is_long_hole_free() and
g.is_long_antihole_free() are doing the same job. But for the first
function, the complement of the graph has to be calculated while this is
not the case for the second one. Actually both algorithms should be used
in is_weakly_chordal(). That was an oversight in the first version (though
the function was still correct). Now I have done a speed comparison
between above two options. The result of `comparison1()` of attached
"comparison.py" shows that in average it is better to use both.
* Okay, I was focused on a fast algorithm. Now I wrote a function using
the subgraph_search of C_k, for k = 5,6,...,graph.order() (what does
actually the same as is_even_hole_free() and is_odd_hole_free() together
except for C_4's). I did some speed comparison. After some rounds of
profiling and optimization, the Python code runs in average several times
''faster'' than the subgraph search - as you said, subgraph search is
algorithmically bad in general. Hence, the is_long_(anti)hole_free
algorithm should be preferred. See result of `comparison2()` of attached
"comparison.py".
* Profiling the code shows that 99% of the time is spend in the
edge_iterator. Whether it is possible to improve on that further, it is
beyond my knowledge. Any improvements are welcome!
Comments:
* Actually, the algorithms are described in the mentioned paper and I
just implemented them. The description of each function is two pages long
(+ one page for the certificate) and I doubt that I can write down all as
comments. I added at least some comments...
Birk
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13073#comment:2>
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.
