#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.2
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.
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 patch AllMIP-2.flattened in #6502 along with the
package GLPK :
http://www.sagemath.org/packages/optional/
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:5>
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
-~----------~----~----~----~------~----~------~--~---
