Revision history [back]
 | 1 | initial version |
Let me answer your first point:
If s is a graph6-string representation of some graph, you can transform it into a Sage graph as follows:
sage: s = 'Jsa@IchDIS_' # this is the graph6 representation of the GroetzschgGraph
sage: G = Graph(s)
sage: G
Graph on 11 vertices
You can check:
sage: H = graphs.GrotzschGraph()
sage: G == H
True
To go further, you shoud provide an explicit sample of a graph6 file, so that we can understand how to load it.
| | 2 | No.2 Revision |
Let me answer your first point:
If s is a graph6-string representation of some graph, you can transform it into a Sage graph as follows:
sage: s = 'Jsa@IchDIS_' # this is the graph6 representation of the GroetzschgGraph
sage: G = Graph(s)
sage: G
Graph on 11 vertices
You can check:
sage: H = graphs.GrotzschGraph()
sage: G == H
True
To go further, you shoud provide an explicit sample of a graph6 file, so that we can understand how to load it.
Regarding your secnod point, since your graph is small, you can get the list of independent sets as follows:
- put a boolean (0 or 1) variable on each vertex
- add the constraint that for each edge, the sum of the values iof the vertices defining the edge is at most 1
You get a polytope whose integer points are the independent sets of your graph. In Sage, you can do this:
sage: p = MixedIntegerLinearProgram()
sage: x = p.new_variable(binary=True)
sage: for a,b in G.edges(labels=False):
....: p.add_constraint(x[a]+x[b]<=1)
sage: P = p.polyhedron()
sage: L = P.integral_points() ; L
((0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
(0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
(0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
(0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0),
(0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0),
(0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1),
(0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1),
(0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0),
(0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0),
(0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0),
(0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0),
(0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0),
(0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1),
(0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0),
(0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0),
(0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0),
(0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1),
(0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0),
(0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0),
(0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0),
(0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1),
(0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0),
(0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0),
(0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1),
(0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0),
(0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0),
(0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0),
(0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1),
(0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1),
(0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1),
(1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1),
(1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0),
(1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0),
(1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0),
(1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1),
(1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0))
sage: len(L)
103
So, you have a list of 103 independent sets.
