ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 04 Mar 2015 10:33:49 -0600treewidth()https://ask.sagemath.org/question/26011/treewidth/Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property?
To illustrate with a concrete example (not the one above):
M = Matrix([[0, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()
This returns:
[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]
Clearly (0,2) is an edge of the original graph
but the answer above does not have a bag
that contains both 0 and 2.
Mon, 02 Mar 2015 19:41:25 -0600https://ask.sagemath.org/question/26011/treewidth/Comment by Nathann for <p>Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property? </p>
<p>To illustrate with a concrete example (not the one above):</p>
<pre><code>M = Matrix([[0, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()
</code></pre>
<p>This returns:</p>
<pre><code>[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]
</code></pre>
<p>Clearly (0,2) is an edge of the original graph
but the answer above does not have a bag
that contains both 0 and 2.</p>
https://ask.sagemath.org/question/26011/treewidth/?comment=26016#post-id-26016Give us the tree please.Tue, 03 Mar 2015 05:49:10 -0600https://ask.sagemath.org/question/26011/treewidth/?comment=26016#post-id-26016Answer by Nathann for <p>Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property? </p>
<p>To illustrate with a concrete example (not the one above):</p>
<pre><code>M = Matrix([[0, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()
</code></pre>
<p>This returns:</p>
<pre><code>[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]
</code></pre>
<p>Clearly (0,2) is an edge of the original graph
but the answer above does not have a bag
that contains both 0 and 2.</p>
https://ask.sagemath.org/question/26011/treewidth/?answer=26034#post-id-26034Here it is ! This is now ticket #17893. There was a problem indeed, but not in the actual computations. I was trying to simplify the final tree too much, and well. To the point that some things that had their importance actually vanished :-P
It is updated. Very very slightly more time-consuming, but a clearer code. Good deal.
By the way it is in 'needs_review', i.e. somebody (anybody) needs to double check it before it makes it into Sage.
[1] http://trac.sagemath.org/ticket/17893Wed, 04 Mar 2015 10:33:49 -0600https://ask.sagemath.org/question/26011/treewidth/?answer=26034#post-id-26034Answer by storm for <p>Is there a bug with the treewidth function? I let G be a tree on 5 nodes and calculate a tree decomposition. However, the answer I get does not seem to be correct as the set of vertices returned are {0},{1},{2,3},{3},{3,4}. The definition of a tree decomposition requires that if (i,j) is an edge in G then there is a bag that contains both i and j. But clearly the above tree decomposition does not have satisfy this property? </p>
<p>To illustrate with a concrete example (not the one above):</p>
<pre><code>M = Matrix([[0, 0, 1, 0, 1],
[0, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 0],
[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()
</code></pre>
<p>This returns:</p>
<pre><code>[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]
</code></pre>
<p>Clearly (0,2) is an edge of the original graph
but the answer above does not have a bag
that contains both 0 and 2.</p>
https://ask.sagemath.org/question/26011/treewidth/?answer=26018#post-id-26018Hello Nathan. Thanks for your reply. I do not have the specific example, but here is another one.
M = Matrix([[0, 0, 1, 0, 1],[0, 0, 1, 0, 0],[1, 1, 0, 1, 0],[0, 0, 1, 0, 0],[1, 0, 0, 0, 0]])
g = Graph(M)
T = g.treewidth(certificate=True)
T.vertices()
The comand T.vertices() returns
[{0}, {2}, {2, 3}, {0, 4}, {1, 2}]
Clearly (0,2) is an edge of the original graph but the answer above does not have a bag that contains both 0 and 2.
Tue, 03 Mar 2015 09:39:17 -0600https://ask.sagemath.org/question/26011/treewidth/?answer=26018#post-id-26018