Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# cython: binding=True r""" Weakly chordal graphs
This module deals with everything related to weakly chordal graphs. It currently contains the following functions:
.. csv-table:: :class: contentstable :widths: 30, 70 :delim: |
:meth:`~sage.graphs.weakly_chordal.is_long_hole_free` | Tests whether ``g`` contains an induced cycle of length at least 5. :meth:`~sage.graphs.weakly_chordal.is_long_antihole_free` | Tests whether ``g`` contains an induced anticycle of length at least 5. :meth:`~sage.graphs.weakly_chordal.is_weakly_chordal` | Tests whether ``g`` is weakly chordal.
Author:
- Birk Eisermann (initial implementation) - Nathann Cohen (some doc and optimization)
REFERENCES:
.. [NikolopoulosPalios07] Nikolopoulos, S.D. and Palios, L. Detecting holes and antiholes in graphs Algorithmica, 2007 Vol. 47, number 2, pages 119--138 http://www.cs.uoi.gr/~stavros/C-Papers/C-2004-SODA.pdf
Methods ------- """
############################################################################## # Copyright (C) 2012 Birk Eisermann <eisermbi@fastmail.fm> # Distributed under the terms of the GNU General Public License (GPL) # The full text of the GPL is available at: # http://www.gnu.org/licenses/ ##############################################################################
include "sage/data_structures/bitset.pxi"
cdef inline int has_edge(bitset_t bs, int u, int v, int n):
def is_long_hole_free(g, certificate=False): r""" Tests whether ``g`` contains an induced cycle of length at least 5.
INPUT:
- ``certificate`` -- boolean (default: ``False``)
Whether to return a certificate. When ``certificate = True``, then the function returns
* ``(True, [])`` if ``g`` does not contain such a cycle. For this case, it is not known how to provide a certificate. * ``(False, Hole)`` if ``g`` contains an induced cycle of length at least 5. ``Hole`` returns this cycle.
If ``certificate = False``, the function returns just ``True`` or ``False`` accordingly.
ALGORITHM:
This algorithm tries to find a cycle in the graph of all induced `P_4` of `g`, where two copies `P` and `P'` of `P_4` are adjacent if there exists a (not necessarily induced) copy of `P_5=u_1u_2u_3u_4u_5` such that `P=u_1u_2u_3u_4` and `P'=u_2u_3u_4u_5`.
This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.
The run time of this algorithm is `O(m^2)` [NikolopoulosPalios07]_ ( where `m` is the number of edges of the graph ) .
EXAMPLES:
The Petersen Graph contains a hole::
sage: g = graphs.PetersenGraph() sage: g.is_long_hole_free() False
The following graph contains a hole, which we want to display::
sage: g = graphs.FlowerSnark() sage: r,h = g.is_long_hole_free(certificate=True) sage: r False sage: Graph(h).is_isomorphic(graphs.CycleGraph(h.order())) True
TESTS:
Another graph with vertices 2, ..., 8, 10::
sage: g = Graph({2:[3,8],3:[2,4],4:[3,8,10],5:[6,10],6:[5,7],7:[6,8],8:[2,4,7,10],10:[4,5,8]}) sage: r,hole = g.is_long_hole_free(certificate=True) sage: r False sage: hole Subgraph of (): Graph on 5 vertices sage: hole.is_isomorphic(graphs.CycleGraph(hole.order())) True
sage: graphs.EmptyGraph().is_long_hole_free() True """
cdef int a,b,c,i,u,v,d
g = g.copy(immutable=False)
# relabel the graph on 0...n-1
# A dense copy of our graph cdef bitset_t dense_graph
# a-b-c-d form an induced path P_4
# d is already contained in InPath # HOLE FOUND !!!
# At this step C[0]C[1]..... is a cycle such that any 4 # consecutive vertices induce a P4. C may not be an # induced cycle, so we extract one from it.
# To do so, we look for the *shortest* edge C[i]C[j] # between two nonconsecutive vertices of C, where the # length is the difference |i-j|. # # C[i]...C[j] is necessarily an induced cycle.⇧
# Return the answer, and relabel it on-the-fly with the # vertices' real name
else:
# search for another P_4
# main algorithm # For all triples u,v,w of vertices such that uvw is a P_3 # We relabel the graph before returning the result # Free the dense graph
else:
# We relabel the graph before returning the result # Free the dense graph
return True, [] else:
def is_long_antihole_free(g, certificate = False): r""" Tests whether the given graph contains an induced subgraph that is isomorphic to the complement of a cycle of length at least 5.
INPUT:
- ``certificate`` -- boolean (default: ``False``)
Whether to return a certificate. When ``certificate = True``, then the function returns
* ``(False, Antihole)`` if ``g`` contains an induced complement of a cycle of length at least 5 returned as ``Antihole``. * ``(True, [])`` if ``g`` does not contain an induced complement of a cycle of length at least 5. For this case it is not known how to provide a certificate.
When ``certificate = False``, the function returns just ``True`` or ``False`` accordingly.
ALGORITHM:
This algorithm tries to find a cycle in the graph of all induced `\overline{P_4}` of `g`, where two copies `\overline{P}` and `\overline{P'}` of `\overline{P_4}` are adjacent if there exists a (not necessarily induced) copy of `\overline{P_5}=u_1u_2u_3u_4u_5` such that `\overline{P}=u_1u_2u_3u_4` and `\overline{P'}=u_2u_3u_4u_5`.
This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.
The run time of this algorithm is `O(m^2)` [NikolopoulosPalios07]_ ( where `m` is the number of edges of the graph ) .
EXAMPLES:
The Petersen Graph contains an antihole::
sage: g = graphs.PetersenGraph() sage: g.is_long_antihole_free() False
The complement of a cycle is an antihole::
sage: g = graphs.CycleGraph(6).complement() sage: r,a = g.is_long_antihole_free(certificate=True) sage: r False sage: a.complement().is_isomorphic( graphs.CycleGraph(6) ) True
TESTS:
Further tests::
sage: g = Graph({0:[6,7],1:[7,8],2:[8,9],3:[9,10],4:[10,11],5:[11,6],6:[0,5,7],7:[0,1,6],8:[1,2,9],9:[2,3,8],10:[3,4,11],11:[4,5,10]}).complement() sage: r,a = g.is_long_antihole_free(certificate=True) sage: r False sage: a.complement().is_isomorphic( graphs.CycleGraph(9) ) True
sage: graphs.EmptyGraph().is_long_hole_free() True """
return (True, []) if certificate else True
cdef int a,b,c,i,u,v,d
g = g.copy(immutable=False)
# relabel the graph on 0...n-1
# A dense copy of our graph cdef bitset_t dense_graph
# At this step C[0]C[1]..... is an anticycle such that # any 4 consecutive vertices induce the complement of a # P_4. C may not be an induced anticycle, so we extract one # from it.
# To do so, we look for the *shortest* nonedge C[i]C[j] # between two nonconsecutive vertices of C, where the # length is the difference |i-j|. # # C[i]...C[j] is necessarily an induced anticycle.⇧
# Return the answer, and relabel it on-the-fly with the # vertices' real name
else:
# main algorithm # For all triples u,v,w of vertices such that uvw is a complement of P_3 # We relabel the graph before returning the result # Free the dense graph
else: del InPath[v]
# We relabel the graph before returning the result # Free the dense graph
return True, [] else:
def is_weakly_chordal(g, certificate = False): r""" Tests whether the given graph is weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5.
INPUT:
- ``certificate`` -- Boolean value (default: ``False``) whether to return a certificate. If ``certificate = False``, return ``True`` or ``False`` according to the graph. If ``certificate = True``, return
* ``(False, forbidden_subgraph)`` when the graph contains a forbidden subgraph H, this graph is returned. * ``(True, [])`` when the graph is weakly chordal. For this case, it is not known how to provide a certificate.
ALGORITHM:
This algorithm checks whether the graph ``g`` or its complement contain an induced cycle of length at least 5.
Using is_long_hole_free() and is_long_antihole_free() yields a run time of `O(m^2)` (where `m` is the number of edges of the graph).
EXAMPLES:
The Petersen Graph is not weakly chordal and contains a hole::
sage: g = graphs.PetersenGraph() sage: r,s = g.is_weakly_chordal(certificate = True) sage: r False sage: l = len(s.vertices()) sage: s.is_isomorphic( graphs.CycleGraph(l) ) True
TESTS::
sage: graphs.EmptyGraph().is_weakly_chordal() True
"""
return g.is_long_antihole_free(certificate=True) else:
|