Opened 6 years ago

Last modified 6 years ago

#14434 closed enhancement

Implement feedback_vertex_set for graphs — at Version 7

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:
Authors: Nathann Cohen Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14435 Stopgaps:

Change History (10)

Changed 6 years ago by ncohen

comment:1 Changed 6 years ago by ncohen

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

Changed 6 years ago by ncohen

comment:2 Changed 6 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 6 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 6 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 6 years ago by ncohen

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

Nathann

comment:6 Changed 6 years ago by ncohen

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

Updated. Sorryyyyyyyyyyyyyyyyyyyyyyyyyyyyy ^^;

Nathann

Changed 6 years ago by vdelecroix

comment:7 Changed 6 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.]
Note: See TracTickets for help on using tickets.