Opened 13 years ago

Closed 12 years ago

#7662 closed enhancement (fixed)

Update is_chordal to return certificates

Reported by: Nathann Cohen Owned by: Robert Miller
Priority: major Milestone: sage-4.6.2
Component: graph theory Keywords:
Cc: Merged in: sage-4.6.2.alpha0
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by Nathann Cohen)

This patch lets is_chordal return a certificate when asked to do so. The former algorithm is kept, and several lines are added to collect the certificate on the way and return it.

Nathann

Attachments (1)

trac_7662.patch (7.7 KB) - added by Nathann Cohen 12 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 13 years ago by Nathann Cohen

Description: modified (diff)

comment:2 Changed 13 years ago by Nathann Cohen

Status: newneeds_work

comment:3 Changed 12 years ago by Nathann Cohen

Description: modified (diff)
Status: needs_workneeds_review
Summary: Chordal GraphsUpdate is_chordal to return certificates

comment:4 Changed 12 years ago by Robert Miller

Authors: Nathann Cohen
Reviewers: Robert Miller
Status: needs_reviewneeds_work

You should define what a "perfect elimination order" and a "hole" are in the documentation.

sage -t -long ./sage/graphs/generic_graph.py
**********************************************************************
File "/home/rlmill/sage-4.6/devel/sage-main/sage/graphs/generic_graph.py", line 8758:
    sage: (_, peo) = g.is_chordal(certificate = True)
Exception raised:
    Traceback (most recent call last):
      File "/home/rlmill/sage-4.6/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/rlmill/sage-4.6/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/rlmill/sage-4.6/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_135[7]>", line 1, in <module>
        (_, peo) = g.is_chordal(certificate = True)###line 8758:
    sage: (_, peo) = g.is_chordal(certificate = True)
      File "/home/rlmill/sage-4.6/local/lib/python/site-packages/sage/graphs/generic_graph.py", line 8854, in is_chordal
        return True, peo_copy
    NameError: global name 'peo_copy' is not defined
**********************************************************************
File "/home/rlmill/sage-4.6/devel/sage-main/sage/graphs/generic_graph.py", line 8759:
    sage: for v in peo:
          if not g.subgraph(g.neighbors(v)).is_clique():
               print "This should never happen !"
          g.delete_vertex(v)
Exception raised:
    Traceback (most recent call last):
      File "/home/rlmill/sage-4.6/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/rlmill/sage-4.6/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/rlmill/sage-4.6/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_135[8]>", line 1, in <module>
        for v in peo:###line 8759:
    sage: for v in peo:
    NameError: name 'peo' is not defined
**********************************************************************

comment:5 Changed 12 years ago by Nathann Cohen

Status: needs_workneeds_info

Hello ! I added a short definition of what a hole is (a cycle of length at least 4), and replaced peo_copy by peo (sorry for that O_o).

What about my Such an ordering is called a Perfect Elimination Order ? Would you like something more formal instead ?

Nathann

comment:6 in reply to:  5 Changed 12 years ago by Robert Miller

Status: needs_infoneeds_work

Replying to ncohen:

What about my Such an ordering is called a Perfect Elimination Order ? Would you like something more formal instead ?

I'm not sure whether this is enough. Imagine a user who knows what the definition of chordal is, but not much else. You still want the documentation for this function to make sense to that user. Granted, it is not Sage's job to educate people about all of mathematics, but it certainly should be able to make clear what the input and output of each function is. Perhaps in this case it could do a better job of informing the user of what it is returning.

As long as you say what an elimination order is, then I think that's enough, but right now it is an undefined term.

Changed 12 years ago by Nathann Cohen

Attachment: trac_7662.patch added

comment:7 Changed 12 years ago by Nathann Cohen

Status: needs_workneeds_review

What about this one, then ?

It was a good idea to explain it... I quite liked writing it :-)

Nathann

comment:8 Changed 12 years ago by Robert Miller

Status: needs_reviewpositive_review

Much better! :)

comment:9 Changed 12 years ago by Jeroen Demeyer

Milestone: sage-4.6.1sage-4.6.2

comment:10 Changed 12 years ago by Jeroen Demeyer

Merged in: sage-4.6.2.alpha0
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.