Revision history [back]
 | 1 | initial version |
You may use the dancing links solver in Sage to do this:
sage: G = graphs.CompleteGraph(6)
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: rows = [[a,b] for (a,b,label) in G.edges()]
sage: dlx = dlx_solver(rows)
sage: indices = dlx.one_solution()
sage: indices
[2, 5, 14]
sage: [rows[i] for i in indices]
[[0, 3], [1, 2], [4, 5]]
or just use matching:
sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
... if I understand your question correctly.
| | 2 | No.2 Revision |
You may use the dancing links solver in Sage to do this:
sage: G = graphs.CompleteGraph(6)
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: rows = [[a,b] for (a,b,label) in G.edges()]
sage: dlx = dlx_solver(rows)
sage: indices = dlx.one_solution()
sage: indices
[2, 5, 14]
sage: [rows[i] for i in indices]
[[0, 3], [1, 2], [4, 5]]
or just use search for a matching:
sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
... if I understand your question correctly.
| | 3 | No.3 Revision |
You may use the dancing links solver in Sage to do this:
sage: G = graphs.CompleteGraph(6)
sage: G.vertices()
[0, 1, 2, 3, 4, 5]
sage: rows = [[a,b] for (a,b,label) in G.edges()]
sage: dlx = dlx_solver(rows)
sage: indices = dlx.one_solution()
sage: indices
[2, 5, 14]
sage: [rows[i] for i in indices]
[[0, 3], [1, 2], [4, 5]]
or just search for a matching:
sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
... if I understand your question correctly.
EDIT:
Okay, I see now that you updated the question. I think you want to use the method disjoint_routed_paths :
sage: G = polytopes.hypercube(3).graph()
sage: edges = [(tuple(u.vector()), tuple(v.vector())) for (u,v,label) in G.edges()]
sage: G = Graph(edges, format='list_of_edges')
sage: s1=(1,1,1); t1=(-1,-1,1); s2=(1,-1,1); t2=(-1,1,1)
sage: pairs = [(s1,t1), (s2,t2)]
sage: G.disjoint_routed_paths(pairs)
Traceback (most recent call last):
...
EmptySetError: The disjoint routed paths do not exist.
and here it works:
sage: pairs = [((1,1,1), (-1,-1,1)), ((-1,-1,-1), (1,1,-1))]
sage: paths = G.disjoint_routed_paths(pairs)
sage: paths
[Subgraph of (): Graph on 3 vertices, Subgraph of (): Graph on 3 vertices]
sage: paths[0].edges()
[((-1, -1, 1), (1, -1, 1), 1), ((1, -1, 1), (1, 1, 1), 1)]
sage: paths[1].edges()
[((-1, -1, -1), (-1, 1, -1), 1), ((-1, 1, -1), (1, 1, -1), 1)]
So you want to write a function like this maybe :
sage: def is_k_linked(G, k):
....: V = G.vertices()
....: for S in Subsets(range(len(V)), 2*k):
....: for R in Subsets(S, k):
....: L = S.difference(R)
....: pairs = [(V[a],V[b]) for (a,b) in zip(L,R)]
....: try:
....: G.disjoint_routed_paths(pairs)
....: except EmptySetError:
....: return False
....: return True
....:
sage: is_k_linked(G,2) # something is wrong in my code, as it should return False
True
I do not have time now to debug this further now.
