Revision history [back]
 | 1 | initial version |
There is the object IndependentSets in sage.graphs.independent_sets that can help you (as the complement of an independent set is a vertex cover).
{{{
sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.PetersenGraph()
sage: V = set(G.vertices())
sage: for I in IndependentSets(G, maximal=True):
....: print(V.difference(I))
set([1, 3, 4, 5, 7, 8, 9])
set([1, 3, 4, 5, 6, 7])
set([1, 2, 4, 5, 8, 9])
...
set([0, 1, 2, 4, 7, 8, 9])
set([0, 1, 2, 3, 5, 8, 9])
}}}
To add further restriction, you can just filter. If it is not efficient enough, you will have to implement your own backtracker.
| | 2 | No.2 Revision |
There is the object IndependentSets in sage.graphs.independent_sets that can help you (as the complement of an independent set is a vertex cover).
{{{
cover).
sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.PetersenGraph()
sage: V = set(G.vertices())
sage: for I in IndependentSets(G, maximal=True):
....: print(V.difference(I))
set([1, 3, 4, 5, 7, 8, 9])
set([1, 3, 4, 5, 6, 7])
set([1, 2, 4, 5, 8, 9])
...
set([0, 1, 2, 4, 7, 8, 9])
set([0, 1, 2, 3, 5, 8, 9])
}}}
To add further restriction, you can just filter. If it is not efficient enough, you will have to implement your own backtracker.
