Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#6962 closed enhancement (fixed)

Feedback vertex set, Feedback arc set

Reported by: ncohen Owned by: rlm
Priority: major Milestone: sage-4.3
Component: graph theory Keywords:
Cc: Merged in: sage-4.3.rc1
Authors: Nathann Cohen Reviewers: Robert Miller
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by ncohen)

Adds the functions :

You will find a full description of the problem in the docstrings, or there :

The functions use Linear Programming, which needs one of the two optional packages GLPK

sage: install_package('cbc')

or CBC

sage: install_package('glpk') 

installed. You will find a helpful documentation about the construction of the Linear Program in the docstring.

One of the docstrings uses the function vertex_cover from #7600 and #7721

Nathann

Attachments (2)

trac_6962.patch (9.0 KB) - added by ncohen 9 years ago.
trac_6962-doctest-fixes.patch (2.0 KB) - added by rlm 9 years ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 9 years ago by ncohen

  • Description modified (diff)

comment:2 Changed 9 years ago by jason

We've used the terminology "edge" with a DiGraph?, with the understanding that direction matters when you have a DiGraph?. Is it a possibility to change "feedback_arc_set" to "feedback_edge_set"?

comment:3 Changed 9 years ago by ncohen

I mix them up myself sometimes, this distinction can almost always be deduced from the context, even outside of Sage... And anyway the word "feedback" is enough for anybody interested in the function to read its documentation, so I think it is OK. We can write "feedback arc set" in the documentation in case someones looks for this special string, besides !

The thing is that I will be going for one week in something like 10 minutes and will not have any access to any computer during this time. Could a reviewer fix this while reviewing the whole patch ? If this patch is not reviewed when I get back, I will do it myself, though... And I will remember that you already settled this question :-)

Nathann

comment:4 Changed 9 years ago by ncohen

Done ! :-)

( the patch now is written according to the changes brought to class MIP in #7012 )

comment:5 Changed 9 years ago by rlm

  • Report Upstream set to N/A
  • Status changed from needs_review to needs_work
  • Summary changed from [with patch, needs review] Feedback vertex set, Feedback arc set to Feedback vertex set, Feedback arc set

This patch still applies ok, but none of the doctests work:

sage: cycle=graphs.CycleGraph(5)
sage: dcycle=DiGraph(cycle)
sage: cycle.size()
5
sage: dcycle.feedback_edge_set(value_only=True)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Users/rlmill/.sage/temp/rlm_book.local/96266/_Users_rlmill__sage_init_sage_0.py in <module>()

/Users/rlmill/sage-4.3.rc0/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in feedback_edge_set(self, value_only)
  12540         from sage.numerical.mip import MixedIntegerLinearProgram
  12541         
> 12542         p=MixedIntegerLinearProgram(sense=-1)
  12543         
  12544         b=p.new_variable()

/Users/rlmill/sage-4.3.rc0/local/lib/python2.6/site-packages/sage/numerical/mip.so in sage.numerical.mip.MixedIntegerLinearProgram.__init__ (sage/numerical/mip.c:866)()

TypeError: __init__() got an unexpected keyword argument 'sense'
sage: cycle.min_vertex_cover()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)

/Users/rlmill/.sage/temp/rlm_book.local/96266/_Users_rlmill__sage_init_sage_0.py in <module>()

AttributeError: 'Graph' object has no attribute 'min_vertex_cover'
sage: dcycle.feedback_vertex_set(value_only=True)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Users/rlmill/.sage/temp/rlm_book.local/96266/_Users_rlmill__sage_init_sage_0.py in <module>()

/Users/rlmill/sage-4.3.rc0/local/lib/python2.6/site-packages/sage/graphs/graph.pyc in feedback_vertex_set(self, value_only)
  12632         from sage.numerical.mip import MixedIntegerLinearProgram
  12633         
> 12634         p=MixedIntegerLinearProgram(sense=-1)
  12635         
  12636         b=p.new_variable()

/Users/rlmill/sage-4.3.rc0/local/lib/python2.6/site-packages/sage/numerical/mip.so in sage.numerical.mip.MixedIntegerLinearProgram.__init__ (sage/numerical/mip.c:866)()

TypeError: __init__() got an unexpected keyword argument 'sense'

There are two issues:

  1. __init__() got an unexpected keyword argument 'sense'
  1. 'Graph' object has no attribute 'min_vertex_cover'

comment:6 Changed 9 years ago by ncohen

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

comment:7 Changed 9 years ago by ncohen

  • Status changed from needs_review to needs_work

comment:8 Changed 9 years ago by ncohen

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

Updated !

Changed 9 years ago by ncohen

Changed 9 years ago by rlm

comment:9 Changed 9 years ago by rlm

  • Authors set to Nathann Cohen
  • Reviewers set to Robert Miller
  • Status changed from needs_review to positive_review

comment:10 Changed 9 years ago by mhansen

  • Merged in set to sage-4.3.rc1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:11 Changed 9 years ago by mhansen

  • Milestone changed from sage-4.3.1 to sage-4.3
Note: See TracTickets for help on using tickets.