Opened 9 years ago

Closed 8 years ago

#7662 closed enhancement (fixed)

Update is_chordal to return certificates

Reported by: ncohen Owned by: rlm
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:

Description (last modified by ncohen)

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 ncohen 8 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by ncohen

  • Status changed from new to needs_work

comment:3 Changed 8 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Summary changed from Chordal Graphs to Update is_chordal to return certificates

comment:4 Changed 8 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to needs_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 follow-up: Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_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 8 years ago by rlm

  • Status changed from needs_info to needs_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 8 years ago by ncohen

comment:7 Changed 8 years ago by ncohen

  • Status changed from needs_work to needs_review

What about this one, then ?

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

Nathann

comment:8 Changed 8 years ago by rlm

  • Status changed from needs_review to positive_review

Much better! :)

comment:9 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:10 Changed 8 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.