#6680: [with patch, needs review] Flow, Matching, Connectivity, and some Hard
problems (uses Linear Programming)
--------------------------+-------------------------------------------------
Reporter: ncohen | Owner: rlm
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.1.1
Component: graph theory | Keywords:
Reviewer: | Author:
Merged: |
--------------------------+-------------------------------------------------
Description changed by ncohen:
Old description:
> 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):
>
> Those new functions all use Linear programming, so to use them you will
> have to install the patches MIP-1 to MIP-5 in #6502 along with the
> package GLPK :
>
> http://trac.sagemath.org/sage_trac/ticket/6502
>
> If you want them to be even more efficient, you can also install COIN-
> OR/CBC ( from #6603 ) with this line :
>
> sage -f http://www-sop.inria.fr/members/Nathann.Cohen/cbc-2.3.spkg
>
> I am sorry for sending a patch with so many functions at once, but most
> of them only take ten or twenty lines and the linear programs should be
> pretty elementary. Hopefully, these functions can be reviewed
> independently as most of them are not related to each other.
>
> ( I have to add that I will be absent next week, but even though I will
> be able to answer any of your questions and to post fixes until tomorrow
> evening. I chosed to post these two functions now hoping they could be
> integrated with the patch for LP into the next release of Sage )
New description:
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):
Those new functions all use Linear programming, so to use them you will
have to install the patches MIP-1 to MIP-5 in #6502 along with the package
GLPK :
http://trac.sagemath.org/sage_trac/ticket/6502
If you want them to be even more efficient, you can also install COIN-
OR/CBC ( from #6603 ) with this line :
sage -f http://www-sop.inria.fr/members/Nathann.Cohen/cbc-2.3.spkg
I am sorry for sending a patch with so many functions at once, but most of
them only take ten or twenty lines and the linear programs should be
pretty elementary. Hopefully, these functions can be reviewed
independently as most of them are not related to each other.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6680#comment:4>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
