feedback_vertex_set for graphs #14434

nathanncohen · 2013-04-10T08:13:52Z

Apply :

attachment: trac_14434-ALL.patch

Depends on #14435

CC: @sagetrac-tmonteil @videlec @dimpase @kini

Component: graph theory

Author: Nathann Cohen

Reviewer: Vincent Delecroix

Merged: sage-5.12.beta2

Issue created by migration from https://trac.sagemath.org/ticket/14434

nathanncohen · 2013-04-10T08:16:49Z

Attachment: trac_14434-move.patch.gz

nathanncohen · 2013-04-10T13:16:26Z

Dependencies: #14435

videlec · 2013-06-03T18:38:56Z

Work Issues: doctest

videlec · 2013-06-03T18:38:56Z

comment:2

Attachment: trac_14434.patch.gz

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]
**********************************************************************

nathanncohen · 2013-06-03T21:36:18Z

comment:3

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

Nathann

videlec · 2013-06-04T04:58:14Z

comment:4

Replying to @nathanncohen:

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

Nope. And patchbot neither.

nathanncohen · 2013-06-04T18:27:51Z

comment:5

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

Nathann

nathanncohen · 2013-06-04T18:32:53Z

comment:6

Updated. Sorryyyyyyyyyyyyyyyyyyyyyyyyyyyyy ^^;

Nathann

videlec · 2013-06-05T06:44:37Z

Attachment: trac_14434-clean_doc.patch.gz

videlec · 2013-06-05T06:46:03Z

Changed work issues from doctest to none

videlec · 2013-06-05T06:46:03Z

comment:7

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.]

nathanncohen · 2013-06-05T07:54:43Z

comment:8

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

nathanncohen · 2013-06-05T08:01:19Z

Attachment: trac_14434-doctest.patch.gz

nathanncohen · 2013-06-05T08:03:19Z

comment:9

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

videlec · 2013-06-05T08:19:22Z

comment:10

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

jdemeyer · 2013-06-12T07:48:58Z

comment:14

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
**********************************************************************

jdemeyer · 2013-06-12T07:48:58Z

Changed merged from sage-5.11.beta1 to none

nathanncohen · 2013-06-12T07:59:25Z

comment:15

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

jdemeyer · 2013-06-12T09:15:19Z

comment:16

Replying to @nathanncohen:

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.

nathanncohen · 2013-06-13T09:33:28Z

comment:17

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

Nathann

jdemeyer · 2013-06-13T09:39:41Z

comment:18

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

nathanncohen · 2013-06-13T09:42:37Z

comment:19

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

Nathann

jdemeyer · 2013-06-13T09:47:44Z

comment:20

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

nathanncohen · 2013-06-13T10:06:04Z

comment:21

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

Nathann

dimpase · 2013-06-13T10:54:07Z

comment:22

Replying to @nathanncohen:

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...

nathanncohen · 2013-06-13T14:11:55Z

comment:23

Attachment: trac_14434-bugfix.patch.gz

I'm an idiot >_<

Nathann

dimpase · 2013-06-13T18:24:29Z

comment:24

Attachment: trac_14434-ALL.patch.gz

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

nathanncohen · 2013-06-13T22:18:09Z

comment:25

Apply trac_14434-ALL.patch

videlec · 2013-07-07T17:03:29Z

comment:27

Good to go!

nathanncohen · 2013-07-07T17:04:26Z

comment:28

Cool ! Thank you for the review :-)

Nathann

jdemeyer · 2013-08-19T06:44:54Z

Merged: sage-5.12.beta2

nathanncohen mannequin added this to the sage-5.10 milestone Apr 10, 2013

nathanncohen mannequin added c: graph theory labels Apr 10, 2013

nathanncohen mannequin assigned jasongrout, nathanncohen and rlmill Apr 10, 2013

nathanncohen mannequin added the s: needs review label Apr 10, 2013

videlec added s: needs work and removed s: needs review labels Jun 3, 2013