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: |
Description (last modified by )
Apply :
Attachments (6)
Change History (36)
Changed 7 years ago by
comment:1 Changed 7 years ago by
- Dependencies set to #14435
- Status changed from new to needs_review
Changed 7 years ago by
comment:2 Changed 6 years ago by
- Status changed from needs_review to needs_work
- Work issues set to doctest
comment:3 follow-up: ↓ 4 Changed 6 years ago by
Did you by any chance install CPLEX or a LP solver which is not GLPK ? :-P
Nathann
comment:4 in reply to: ↑ 3 Changed 6 years ago by
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 6 years ago by
Yep. Most probably because I am the one who installed it, and I did not remember >_<
Nathann
comment:6 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Updated. Sorryyyyyyyyyyyyyyyyyyyyyyyyyyyyy ^^;
Nathann
Changed 6 years ago by
comment:7 follow-up: ↓ 8 Changed 6 years ago by
- 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 6 years ago by
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 6 years ago by
comment:9 Changed 6 years ago by
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 6 years ago by
- 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 6 years ago by
- Description modified (diff)
comment:12 Changed 6 years ago by
- Reviewers set to Vincent Delecroix
comment:13 Changed 6 years ago by
- Merged in set to sage-5.11.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:14 Changed 6 years ago by
- 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: ↓ 16 Changed 6 years ago by
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 6 years ago by
- 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 6 years ago by
Well... Guys ? Do you have any idea ? O_o
Nathann
comment:18 Changed 6 years ago by
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 6 years ago by
No I don't, and I don't see why this code would react to something like that either :-/
Nathann
comment:20 Changed 6 years ago by
It could also be a hashing issue, do you use a dict
somewhere and rely on its order for example?
comment:21 follow-up: ↓ 22 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
comment:23 Changed 6 years ago by
- Description modified (diff)
- Status changed from new to needs_review
I'm an idiot >_<
Nathann
Changed 6 years ago by
comment:24 Changed 6 years ago by
- Description modified (diff)
just to make sure that patchbot does not get confused, I removed "Or..." part.
comment:25 Changed 6 years ago by
Apply trac_14434-ALL.patch
comment:26 Changed 6 years ago by
- Summary changed from Implement feedback_vertex_set for graphs to feedback_vertex_set for graphs
comment:27 Changed 6 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
Good to go!
comment:28 Changed 6 years ago by
Cool ! Thank you for the review :-)
Nathann
comment:29 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:30 Changed 6 years ago by
- Merged in set to sage-5.12.beta2
- Resolution set to fixed
- Status changed from positive_review to closed