Hi Nathann,
I extracted the modified is_chordal function, it is shown below.
Regards, Jan
==========
def is_chordal(self, certificate = False):
r"""
Tests whether the given graph is chordal.
A Graph `G` is said to be chordal if it contains no induced hole
(a
cycle of length at least 4).
Alternatively, chordality can be defined using a Perfect
Elimination
Order :
A Perfect Elimination Order of a graph `G` is an ordering
`v_1,...,v_n`
of its vertex set such that for all `i`, the neighbors of `v_i`
whose
index is greater that `i` induce a complete subgraph in `G`.
Hence, the
graph `G` can be totally erased by successively removing vertices
whose
neighborhood is a clique (also called *simplicial* vertices)
[Fulkerson65]_.
(It can be seen that if `G` contains an induced hole, then it can
not
have a perfect elimination order. Indeed, if we write
`h_1,...,h_k` the
`k` vertices of such a hole, then the first of those vertices to
be
removed would have two non-adjacent neighbors in the graph.)
A Graph is then chordal if and only if it has a Perfect
Elimination
Order.
INPUT:
- ``certificate`` (boolean) -- Whether to return a certificate.
* If ``certificate = False`` (default), returns ``True`` or
``False`` accordingly.
* If ``certificate = True``, returns :
* ``(True, peo)`` when the graph is chordal, where ``peo``
is a
perfect elimination order of its vertices.
* ``(False, Hole)`` when the graph is not chordal, where
``Hole`` (a ``Graph`` object) is an induced subgraph of
``self`` isomorphic to a hole.
ALGORITHM:
This algorithm works through computing a Lex BFS on the graph,
then
checking whether the order is a Perfect Elimination Order by
computing
for each vertex `v` the subgraph induces by its non-deleted
neighbors,
then testing whether this graph is complete.
This problem can be solved in `O(m)` [Rose75]_ ( where `m` is the
number
of edges in the graph ) but this implementation is not linear
because of
the complexity of Lex BFS. Improving Lex BFS to linear complexity
would
make this algorithm linear.
The complexity of this algorithm is equal to the complexity of the
implementation of Lex BFS.
EXAMPLES:
The lexicographic product of a Path and a Complete Graph
is chordal ::
sage: g =
graphs.PathGraph(5).lexicographic_product(graphs.CompleteGraph(3))
sage: g.is_chordal()
True
The same goes with the product of a random lobster
( which is a tree ) and a Complete Graph ::
sage: g =
graphs.RandomLobster(10,.5,.5).lexicographic_product(graphs.CompleteGraph(3))
sage: g.is_chordal()
True
The disjoint union of chordal graphs is still chordal::
sage: (2*g).is_chordal()
True
Let us check the certificate given by Sage is indeed a perfect
elimintion order::
sage: (_, peo) = g.is_chordal(certificate = True)
sage: for v in peo:
... if not g.subgraph(g.neighbors(v)).is_clique():
... print "This should never happen !"
... g.delete_vertex(v)
sage: print "Everything is fine !"
Everything is fine !
Of course, the Petersen Graph is not chordal as it has girth 5 ::
sage: g = graphs.PetersenGraph()
sage: g.girth()
5
sage: g.is_chordal()
False
We can even obtain such a cycle as a certificate ::
sage: (_, hole) = g.is_chordal(certificate = True)
sage: hole
Subgraph of (Petersen graph): Graph on 5 vertices
sage: hole.is_isomorphic(graphs.CycleGraph(5))
True
REFERENCES:
.. [Rose75] Rose, D.J. and Tarjan, R.E.,
Algorithmic aspects of vertex elimination,
Proceedings of seventh annual ACM symposium on Theory of
computing
Page 254, ACM 1975
.. [Fulkerson65] Fulkerson, D.R. and Gross, OA
Incidence matrices and interval graphs
Pacific J. Math 1965
Vol. 15, number 3, pages 835--855
TESTS:
Trac Ticket #11735::
sage: g = Graph({3:[2,1,4],2:[1],4:[1],5:[2,1,4]})
sage: _, g1 = g.is_chordal(certificate=True); g1.is_chordal()
False
sage: g1.is_isomorphic(graphs.CycleGraph(g1.order()))
True
"""
# If the graph is not connected, we are computing the result on
each component
if not self.is_connected():
# If the user wants a certificate, we had no choice but to
# collect the perfect elimination orders... But we return
# a hole immediately if we find any !
if certificate:
peo = []
for gg in self.connected_components_subgraphs():
b, certif = gg.is_chordal(certificate = True)
if not b:
return certif
else:
peo.extend(certif)
return True, peo
# One line if no certificate is requested
else:
return all( gg.is_chordal() for gg in
self.connected_components_subgraphs() )
peo,t_peo = self.lex_BFS(reverse=True, tree=True)
g = self.copy()
# Remembering the (closed) neighborhoods of each vertex
from sage.combinat.subset import Subsets
neighbors_subsets = dict([(v,Subsets(self.neighbors(v)+[v])) for v
in self.vertex_iterator()])
pos_in_peo = dict(zip(peo, range(self.order())))
# Iteratively removing vertices and checking everything is fine.
for v in reversed(peo):
if t_peo.out_degree(v)>0 and [v1 for v1 in g.neighbors(v) if
pos_in_peo[v1] > pos_in_peo[v]] not in
neighbors_subsets[t_peo.neighbor_out_iterator(v).next()]:
# Do we need to return a hole ?
if certificate:
# In this case, let us take two nonadjacent neighbors
of
# v. In order to do so, we pick a vertex y which is a
# neighbor of v but is not adjacent to x, which we
know
# exists by the test written two lines above.
max_tup = (-1, 0)
nb1 = [u for u in g.neighbors(v) if pos_in_peo[u] >
pos_in_peo[v]]
for xi in nb1:
for yi in nb1:
if not [yi] in neighbors_subsets[xi]:
new_tup = (pos_in_peo[xi], pos_in_peo[yi])
if max_tup < new_tup:
max_tup = new_tup
x, y = xi, yi
g.delete_vertices([vv for vv in g.vertices() if
pos_in_peo[vv] < pos_in_peo[v]])
g.delete_vertices([vv for vv in g.neighbors(v) if vv !
= y and vv != x])
g.delete_vertex(v)
# Our hole is v + (a shortest path between x and y not
# containing v or any of its neighbors).
hole = self.subgraph([v] + g.shortest_path(x,y))
# There was a bug there once, so it's better to check
the
# answer is valid, especally when it is so cheap ;-)
if hole.order() <= 3 or not hole.is_regular(k=2):
raise Exception("The graph is not chordal, and
something went wrong in the computation of the certificate. Please
report this bug, providing the graph if possible !")
return (False, hole)
else:
return False
if certificate:
return True, peo
else:
return True
--
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-support
URL: http://www.sagemath.org
