#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 )
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)
Change History (13)
comment:1 Changed 10 years ago by
- Description modified (diff)
comment:2 Changed 10 years ago by
comment:3 Changed 10 years ago by
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 10 years ago by
Done ! :-)
( the patch now is written according to the changes brought to class MIP in #7012 )
comment:5 Changed 10 years ago by
- 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:
__init__() got an unexpected keyword argument 'sense'
'Graph' object has no attribute 'min_vertex_cover'
comment:6 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
comment:7 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:8 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to needs_review
Updated !
Changed 10 years ago by
Changed 10 years ago by
comment:9 Changed 10 years ago by
- Reviewers set to Robert Miller
- Status changed from needs_review to positive_review
comment:10 Changed 10 years ago by
- Merged in set to sage-4.3.rc1
- Resolution set to fixed
- Status changed from positive_review to closed
comment:11 Changed 10 years ago by
- Milestone changed from sage-4.3.1 to sage-4.3
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"?