Opened 7 years ago

Closed 6 years ago

#14434 closed enhancement (fixed)

feedback_vertex_set for graphs

Reported by: ncohen Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.12
Component: graph theory Keywords:
Cc: tmonteil, vdelecroix, dimpase, kini Merged in: sage-5.12.beta2
Authors: Nathann Cohen Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14435 Stopgaps:

Attachments (6)

trac_14434-move.patch (16.3 KB) - added by ncohen 7 years ago.
trac_14434.patch (7.5 KB) - added by ncohen 7 years ago.
trac_14434-clean_doc.patch (5.8 KB) - added by vdelecroix 7 years ago.
trac_14434-doctest.patch (4.4 KB) - added by ncohen 7 years ago.
trac_14434-bugfix.patch (1.5 KB) - added by ncohen 7 years ago.
trac_14434-ALL.patch (22.8 KB) - added by ncohen 7 years ago.

Download all attachments as: .zip

Change History (36)

Changed 7 years ago by ncohen

comment:1 Changed 7 years ago by ncohen

  • Dependencies set to #14435
  • Status changed from new to needs_review

Changed 7 years ago by ncohen

comment:2 Changed 7 years ago by vdelecroix

  • Status changed from needs_review to needs_work
  • Work issues set to doctest
sage -t graphs/generic_graph.py
**********************************************************************
File "graphs/generic_graph.py", line 6137, in sage.graphs.generic_graph.GenericGraph.feedback_vertex_set
Failed example:
    g.feedback_vertex_set()
Expected:
    [1, 3, 5]
Got:
    [0, 3, 6]
**********************************************************************

comment:3 follow-up: Changed 7 years ago by ncohen

Did you by any chance install CPLEX or a LP solver which is not GLPK ? :-P

Nathann

comment:4 in reply to: ↑ 3 Changed 7 years ago by vdelecroix

Replying to ncohen:

Did you by any chance install CPLEX or a LP solver which is not GLPK ? :-P

Nope. And patchbot neither.

comment:5 Changed 7 years ago by ncohen

Yep. Most probably because I am the one who installed it, and I did not remember >_<

Nathann

comment:6 Changed 7 years ago by ncohen

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Updated. Sorryyyyyyyyyyyyyyyyyyyyyyyyyyyyy ^^;

Nathann

Changed 7 years ago by vdelecroix

comment:7 follow-up: Changed 7 years ago by vdelecroix

  • Description modified (diff)
  • Work issues doctest deleted

I update a patch with several corrections in the documentation. If you are happy, make it positive review.

Two curiosities:

I just learn that for verbosity, there is sage.misc.misc.verbose.

Why

[v for v in self if p.get_values(b[v]) < .5]

instead of

[v for v in self if p.get_values(b[v]) == 0.]

comment:8 in reply to: ↑ 7 Changed 7 years ago by ncohen

Yoooooooooooooooo !!!

I just learn that for verbosity, there is sage.misc.misc.verbose.

>_<

Yeah... Right >_<

Pretty good idea... But this will require a LARGE patch :-PPPPPP

I have one thousand different functions with a verbosity level, though most of them are LP-related. I wonder if it's a good idea to have a global function to do that rather than a flag for each function... HMmmmmmm O_o

Why

[v for v in self if p.get_values(b[v]) < .5]

instead of

[v for v in self if p.get_values(b[v]) == 0.]

Because this is old code, written before integer values were automatically rounded. I will update this in a second.

Nathann

Changed 7 years ago by ncohen

comment:9 Changed 7 years ago by ncohen

Here it is ! Patch updated to fix a couple of .5 that remained. Could you give it a final check, and set the ticket to positive review if you agree ? Thanks for your changes to the doc !

Nathann

comment:10 Changed 7 years ago by vdelecroix

  • Milestone changed from sage-5.10 to sage-5.11
  • Status changed from needs_review to positive_review

To twist the alphabetic logic of patchbot:

apply trac_14434-move.patch trac_14434.patch trac_14434-doctest.patch trac_14434-clean_doc.patch Download

comment:11 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:12 Changed 7 years ago by jdemeyer

  • Reviewers set to Vincent Delecroix

comment:13 Changed 7 years ago by jdemeyer

  • Merged in set to sage-5.11.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:14 Changed 7 years ago by jdemeyer

  • Merged in sage-5.11.beta1 deleted
  • Resolution fixed deleted
  • Status changed from closed to new

This breaks on some 32-bit systems, in particular arando (Linux Ubuntu 13.04 i686):

sage -t --long devel/sage/sage/graphs/generic_graph.py
**********************************************************************
File "devel/sage/sage/graphs/generic_graph.py", line 6219, in sage.graphs.generic_graph.GenericGraph.feedback_vertex_set
Failed example:
    fvs = g.feedback_vertex_set()
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 475, in _run
        self.execute(example, compiled, test.globs)
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 834, in execute
        exec compiled in globs
      File "<doctest sage.graphs.generic_graph.GenericGraph.feedback_vertex_set[1]>", line 1, in <module>
        fvs = g.feedback_vertex_set()
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 6311, in feedback_vertex_set
        isok, certificate = h.is_forest(certificate = True)
    TypeError: 'NoneType' object is not iterable
**********************************************************************
File "devel/sage/sage/graphs/generic_graph.py", line 6220, in sage.graphs.generic_graph.GenericGraph.feedback_vertex_set
Failed example:
    len(fvs)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 475, in _run
        self.execute(example, compiled, test.globs)
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 834, in execute
        exec compiled in globs
      File "<doctest sage.graphs.generic_graph.GenericGraph.feedback_vertex_set[2]>", line 1, in <module>
        len(fvs)
    NameError: name 'fvs' is not defined
**********************************************************************
File "devel/sage/sage/graphs/generic_graph.py", line 6222, in sage.graphs.generic_graph.GenericGraph.feedback_vertex_set
Failed example:
    g.delete_vertices(fvs)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 475, in _run
        self.execute(example, compiled, test.globs)
      File "/var/lib/buildbot/build/sage/arando-1/arando_full/build/sage-5.11.beta1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 834, in execute
        exec compiled in globs
      File "<doctest sage.graphs.generic_graph.GenericGraph.feedback_vertex_set[3]>", line 1, in <module>
        g.delete_vertices(fvs)
    NameError: name 'fvs' is not defined
**********************************************************************
File "devel/sage/sage/graphs/generic_graph.py", line 6223, in sage.graphs.generic_graph.GenericGraph.feedback_vertex_set
Failed example:
    g.is_forest()
Expected:
    True
Got:
    False
**********************************************************************

comment:15 follow-up: Changed 7 years ago by ncohen

Is there a way for me to get access to this machine ? I really have no idea what's happening and I cannot reproduce the bug O_o

Nathann

comment:16 in reply to: ↑ 15 Changed 7 years ago by jdemeyer

  • Cc dimpase kini added

Replying to ncohen:

Is there a way for me to get access to this machine ? I really have no idea what's happening and I cannot reproduce the bug O_o

Ask Dima or Keshav.

comment:17 Changed 7 years ago by ncohen

Well... Guys ? Do you have any idea ? O_o

Nathann

comment:18 Changed 7 years ago by jdemeyer

Nathann, do you access to any 32-bit machine? Because this looks like a 32/64 bit issue, nothing particular to arando.

comment:19 Changed 7 years ago by ncohen

No I don't, and I don't see why this code would react to something like that either :-/

Nathann

comment:20 Changed 7 years ago by jdemeyer

It could also be a hashing issue, do you use a dict somewhere and rely on its order for example?

comment:21 follow-up: Changed 7 years ago by ncohen

Looks like it is a problem in Graph.is_tree(). But if I can't test it, it's hard to debug... :-/

Nathann

comment:22 in reply to: ↑ 21 Changed 7 years ago by dimpase

Replying to ncohen:

Looks like it is a problem in Graph.is_tree(). But if I can't test it, it's hard to debug... :-/

Nathann

I'll make you an account. The only way to get to that 32-bit machine is by reverse ssh, so you will have to ssh to boxen first...

Changed 7 years ago by ncohen

comment:23 Changed 7 years ago by ncohen

  • Description modified (diff)
  • Status changed from new to needs_review

I'm an idiot >_<

Nathann

Changed 7 years ago by ncohen

comment:24 Changed 7 years ago by dimpase

  • Description modified (diff)

just to make sure that patchbot does not get confused, I removed "Or..." part.

comment:25 Changed 7 years ago by ncohen

Apply trac_14434-ALL.patch

comment:26 Changed 6 years ago by ncohen

  • Summary changed from Implement feedback_vertex_set for graphs to feedback_vertex_set for graphs

comment:27 Changed 6 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_review to positive_review

Good to go!

comment:28 Changed 6 years ago by ncohen

Cool ! Thank you for the review :-)

Nathann

comment:29 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:30 Changed 6 years ago by jdemeyer

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