ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 24 May 2018 02:05:53 +0200A linkage problemhttps://ask.sagemath.org/question/42389/a-linkage-problem/Hi there,
I wonder how I can use Sage to solve the following problem, without implementing a full-blown backtracking.
Let $G$ be an undirected simple graph with at least $2k$ vertices. The graph $G$ would need to be $2k-1$-vertex-connected for the problem to hope to have a solution, but this is perhaps beside the point. Let $X$ be a set of $2k$ distinct vertices $s_1,...,s_k,t_1,...,t_k$ of G. Pair these $2k$ vertices arbitrarily into k pairs $(s_i,t_i)$. The pair $(s_i,t_i)$ means that the vertex $s_i$ has been paired with the vertex $t_i$. This pairing doesn't altered the graph $G$ in any way. The problem consists of finding k pairwise vertex-disjoint paths between $s_i$ and $t_i$ for each i, or returns that it is not possible to do so.
A graph for which you can find the $k$ vertex-disjoint paths for any possible set $X$ is called *$k$-linked*.
Let me give you an example. Suppose I take the 3-cube graph. I am gonna see it as a graph of the polytope 3-cube because the image is better.
`P3=polytopes.hypercube(3)`
`Q3=P3.graph()`
`Q3.show()`
Let me choose 4 vertices arbitrary vertices for my set $X$, say $s_1=(1,1,1)$, $t_1=(-1,-1,1)$, $s_2=(1,-1,1)$ and $t_2=(-1,1,1)$. Pair the vertices as $(s_i,t_i)$. Then we cannot find 2 vertex-disjoint paths, one connecting $s_1$ to $t_1$ and another $s_2$ to $t_2$. However, if I choose $X$ to be $s_1=(1,1,1)$, $t_1=(-1,-1,1)$ and $s_2=(-1,-1,-1)$ and $t_2=(1,1,-1)$ we can.
As an aside this shows that the 3-CubeGraph is not *2-linked*.
Hope this is a bit clearer now.
Thank you in advance, and regards,
GuillermoTue, 22 May 2018 13:44:14 +0200https://ask.sagemath.org/question/42389/a-linkage-problem/Comment by dan_fulea for <p>Hi there,</p>
<p>I wonder how I can use Sage to solve the following problem, without implementing a full-blown backtracking. </p>
<p>Let $G$ be an undirected simple graph with at least $2k$ vertices. The graph $G$ would need to be $2k-1$-vertex-connected for the problem to hope to have a solution, but this is perhaps beside the point. Let $X$ be a set of $2k$ distinct vertices $s_1,...,s_k,t_1,...,t_k$ of G. Pair these $2k$ vertices arbitrarily into k pairs $(s_i,t_i)$. The pair $(s_i,t_i)$ means that the vertex $s_i$ has been paired with the vertex $t_i$. This pairing doesn't altered the graph $G$ in any way. The problem consists of finding k pairwise vertex-disjoint paths between $s_i$ and $t_i$ for each i, or returns that it is not possible to do so.</p>
<p>A graph for which you can find the $k$ vertex-disjoint paths for any possible set $X$ is called <em>$k$-linked</em>. </p>
<p>Let me give you an example. Suppose I take the 3-cube graph. I am gonna see it as a graph of the polytope 3-cube because the image is better.</p>
<p><code>P3=polytopes.hypercube(3)</code></p>
<p><code>Q3=P3.graph()</code> </p>
<p><code>Q3.show()</code></p>
<p>Let me choose 4 vertices arbitrary vertices for my set $X$, say $s_1=(1,1,1)$, $t_1=(-1,-1,1)$, $s_2=(1,-1,1)$ and $t_2=(-1,1,1)$. Pair the vertices as $(s_i,t_i)$. Then we cannot find 2 vertex-disjoint paths, one connecting $s_1$ to $t_1$ and another $s_2$ to $t_2$. However, if I choose $X$ to be $s_1=(1,1,1)$, $t_1=(-1,-1,1)$ and $s_2=(-1,-1,-1)$ and $t_2=(1,1,-1)$ we can.</p>
<p>As an aside this shows that the 3-CubeGraph is not <em>2-linked</em>.</p>
<p>Hope this is a bit clearer now.</p>
<p>Thank you in advance, and regards,
Guillermo</p>
https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42397#post-id-42397Please give the code for an explicit graph $G$. Also, form the context it is hard to understand what is given, and what should be found. (The index $i$ is used for the "pairs". What are the edges of $G$? Are the $(s_i,t_i)$ for $i\in ?$ **all** edges of $G$. An example, with the expected solution to be found, possibly one among many, would be helpful.)
To start with, consider in the sage interpreter
sage: ?Graph
to see how to initialize a graph.Tue, 22 May 2018 20:37:34 +0200https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42397#post-id-42397Comment by guillermo for <p>Hi there,</p>
<p>I wonder how I can use Sage to solve the following problem, without implementing a full-blown backtracking. </p>
<p>Let $G$ be an undirected simple graph with at least $2k$ vertices. The graph $G$ would need to be $2k-1$-vertex-connected for the problem to hope to have a solution, but this is perhaps beside the point. Let $X$ be a set of $2k$ distinct vertices $s_1,...,s_k,t_1,...,t_k$ of G. Pair these $2k$ vertices arbitrarily into k pairs $(s_i,t_i)$. The pair $(s_i,t_i)$ means that the vertex $s_i$ has been paired with the vertex $t_i$. This pairing doesn't altered the graph $G$ in any way. The problem consists of finding k pairwise vertex-disjoint paths between $s_i$ and $t_i$ for each i, or returns that it is not possible to do so.</p>
<p>A graph for which you can find the $k$ vertex-disjoint paths for any possible set $X$ is called <em>$k$-linked</em>. </p>
<p>Let me give you an example. Suppose I take the 3-cube graph. I am gonna see it as a graph of the polytope 3-cube because the image is better.</p>
<p><code>P3=polytopes.hypercube(3)</code></p>
<p><code>Q3=P3.graph()</code> </p>
<p><code>Q3.show()</code></p>
<p>Let me choose 4 vertices arbitrary vertices for my set $X$, say $s_1=(1,1,1)$, $t_1=(-1,-1,1)$, $s_2=(1,-1,1)$ and $t_2=(-1,1,1)$. Pair the vertices as $(s_i,t_i)$. Then we cannot find 2 vertex-disjoint paths, one connecting $s_1$ to $t_1$ and another $s_2$ to $t_2$. However, if I choose $X$ to be $s_1=(1,1,1)$, $t_1=(-1,-1,1)$ and $s_2=(-1,-1,-1)$ and $t_2=(1,1,-1)$ we can.</p>
<p>As an aside this shows that the 3-CubeGraph is not <em>2-linked</em>.</p>
<p>Hope this is a bit clearer now.</p>
<p>Thank you in advance, and regards,
Guillermo</p>
https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42403#post-id-42403Hi Dan,
Thank you for your comment. I have explained the problem a bit more.
Regards,
GuillermoWed, 23 May 2018 02:22:11 +0200https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42403#post-id-42403Answer by Sébastien for <p>Hi there,</p>
<p>I wonder how I can use Sage to solve the following problem, without implementing a full-blown backtracking. </p>
<p>Let $G$ be an undirected simple graph with at least $2k$ vertices. The graph $G$ would need to be $2k-1$-vertex-connected for the problem to hope to have a solution, but this is perhaps beside the point. Let $X$ be a set of $2k$ distinct vertices $s_1,...,s_k,t_1,...,t_k$ of G. Pair these $2k$ vertices arbitrarily into k pairs $(s_i,t_i)$. The pair $(s_i,t_i)$ means that the vertex $s_i$ has been paired with the vertex $t_i$. This pairing doesn't altered the graph $G$ in any way. The problem consists of finding k pairwise vertex-disjoint paths between $s_i$ and $t_i$ for each i, or returns that it is not possible to do so.</p>
<p>A graph for which you can find the $k$ vertex-disjoint paths for any possible set $X$ is called <em>$k$-linked</em>. </p>
<p>Let me give you an example. Suppose I take the 3-cube graph. I am gonna see it as a graph of the polytope 3-cube because the image is better.</p>
<p><code>P3=polytopes.hypercube(3)</code></p>
<p><code>Q3=P3.graph()</code> </p>
<p><code>Q3.show()</code></p>
<p>Let me choose 4 vertices arbitrary vertices for my set $X$, say $s_1=(1,1,1)$, $t_1=(-1,-1,1)$, $s_2=(1,-1,1)$ and $t_2=(-1,1,1)$. Pair the vertices as $(s_i,t_i)$. Then we cannot find 2 vertex-disjoint paths, one connecting $s_1$ to $t_1$ and another $s_2$ to $t_2$. However, if I choose $X$ to be $s_1=(1,1,1)$, $t_1=(-1,-1,1)$ and $s_2=(-1,-1,-1)$ and $t_2=(1,1,-1)$ we can.</p>
<p>As an aside this shows that the 3-CubeGraph is not <em>2-linked</em>.</p>
<p>Hope this is a bit clearer now.</p>
<p>Thank you in advance, and regards,
Guillermo</p>
https://ask.sagemath.org/question/42389/a-linkage-problem/?answer=42401#post-id-42401You may use the [dancing links solver](http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/matrices/dancing_links.html) 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.Tue, 22 May 2018 23:28:46 +0200https://ask.sagemath.org/question/42389/a-linkage-problem/?answer=42401#post-id-42401Comment by guillermo for <p>You may use the <a href="http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/matrices/dancing_links.html">dancing links solver</a> in Sage to do this:</p>
<pre><code>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]]
</code></pre>
<p>or just search for a matching:</p>
<pre><code>sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
</code></pre>
<p>... if I understand your question correctly.</p>
<p><strong>EDIT:</strong> </p>
<p>Okay, I see now that you updated the question. I think you want to use the method <code>disjoint_routed_paths</code> :</p>
<pre><code>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.
</code></pre>
<p>and here it works:</p>
<pre><code>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)]
</code></pre>
<p>So you want to write a function like this maybe :</p>
<pre><code>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
</code></pre>
<p>I do not have time now to debug this further now.</p>
https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42402#post-id-42402HI Sebastien,
Thank you for your code. I fail to understand how this solve the linkage problem. I have explained the problem a bit more.
Regards,
GuillermoWed, 23 May 2018 02:21:42 +0200https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42402#post-id-42402Comment by guillermo for <p>You may use the <a href="http://doc.sagemath.org/html/en/reference/combinat/sage/combinat/matrices/dancing_links.html">dancing links solver</a> in Sage to do this:</p>
<pre><code>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]]
</code></pre>
<p>or just search for a matching:</p>
<pre><code>sage: G.matching()
[(0, 5, None), (1, 4, None), (2, 3, None)]
</code></pre>
<p>... if I understand your question correctly.</p>
<p><strong>EDIT:</strong> </p>
<p>Okay, I see now that you updated the question. I think you want to use the method <code>disjoint_routed_paths</code> :</p>
<pre><code>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.
</code></pre>
<p>and here it works:</p>
<pre><code>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)]
</code></pre>
<p>So you want to write a function like this maybe :</p>
<pre><code>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
</code></pre>
<p>I do not have time now to debug this further now.</p>
https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42415#post-id-42415Thank you very much Sebastien. The method `disjoint_routed_paths` was what I was after.
I believe the problem with your code is that, once you have the k-sets L and R, you need to permute one of them, say L, to consider all the possible pairings for these two sets.
Regards,
GuillermoThu, 24 May 2018 02:05:53 +0200https://ask.sagemath.org/question/42389/a-linkage-problem/?comment=42415#post-id-42415