#6680 closed enhancement (duplicate)
Flow, Matching, Connectivity, and some Hard problems
Reported by: | ncohen | Owned by: | rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | graph theory | Keywords: | |
Cc: | tombuc | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
Hello everybody !!!
Here are several new functions for the Graph class in Sage :
- def min_dominating_set(g, value_only=False,log=0):
- def min_independent_dominating_set(g, value_only=False,log=0):
- def min_vertex_cover(g,value_only=False,log=0):
- def max_matching(g,value_only=False, use_edge_labels=True):
- def max_flow(g,x,y,value_only=True,integer=False, use_edge_labels=True):
- def min_edge_cut(g,s,t,value_only=True,use_edge_labels=True):
- def min_vertex_cut(g,s,t,value_only=True):
- def edge_connectivity(g,value_only=True,use_edge_labels=True):
- def vertex_connectivity(g,value_only=True):
If you have no LP Solver installed, you can download GLPK or CBC from this address : http://www.sagemath.org/packages/optional/
Attachments (1)
Change History (17)
comment:1 Changed 12 years ago by
- Description modified (diff)
comment:2 Changed 12 years ago by
comment:3 Changed 12 years ago by
- Summary changed from [with patch, needs review] (uses Linear Programming) to [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems (uses Linear Programming)
comment:4 Changed 12 years ago by
- Description modified (diff)
comment:5 Changed 12 years ago by
- Description modified (diff)
comment:6 Changed 12 years ago by
- Description modified (diff)
comment:7 Changed 12 years ago by
- Summary changed from [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems (uses Linear Programming) to [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems
comment:8 Changed 12 years ago by
- Summary changed from [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems to [with patch, needs work] Flow, Matching, Connectivity, and some Hard problems
As the functions dealing with LP have not been reviewed, I prefer to rewrite the MIP class for Sage to make it easier to use. I will post a new version of the MIP patch as soon as possible, along with all the patches for functions using it.
Sorry for the trouble, I'll try to make it quick !
Nathann
comment:9 Changed 12 years ago by
- Description modified (diff)
- Summary changed from [with patch, needs work] Flow, Matching, Connectivity, and some Hard problems to [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems
New version attached !! Will put some energy into Sage's graph library ! ;-)
comment:10 Changed 12 years ago by
- Cc tombuc added
comment:11 Changed 12 years ago by
- Description modified (diff)
comment:12 Changed 12 years ago by
- Description modified (diff)
Changed 12 years ago by
comment:13 Changed 12 years ago by
- Report Upstream set to N/A
I am splitting this ticket into smallers ones
comment:14 Changed 12 years ago by
- Resolution set to duplicate
- Status changed from needs_review to closed
comment:15 Changed 12 years ago by
comment:16 Changed 12 years ago by
- Milestone changed from sage-4.3 to sage-duplicate/invalid/wontfix
- Summary changed from [with patch, needs review] Flow, Matching, Connectivity, and some Hard problems to Flow, Matching, Connectivity, and some Hard problems
test