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 sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org