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, 13 Jan 2022 04:28:11 +0100- tutte_polynomial (sage, matroid theory) gives the wrong resulthttps://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/I have been using Sage in my research recently.
I am not sure which part is wrong but the following code
gives the wrong results. The code is long, but I think you may
only need to read the last four rows to understand my question.
All the rows before that generate a matrix `D`
where the columns are the cycles of the complete graph `K_5`
(each cycle is a vector in `Z^10`, 10 is the number of edges.)
Then I produce a linear matroid from `D` and calculate `T(2, 0)`
using `tutte_polynomial()`. The weird thing is that the result
is an odd number, which is impossible because the Tutte polynomial
has no constant term. The more weird thing is that if I repeat the
order again, I get a different result.
If I run the code for the graph `K_4`, nothing is wrong,
which is why I need to give the complete code.
The code is run by CoCalc.
import numpy as np
from sage.matroids.advanced import *
graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return False
C = np.zeros(nv*(nv-1)/2) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = np.zeros((ne,ncycle*2)) # D is all directed cycles
X = 0
for list in allcycles:
array = np.array(list)
if len(array) > 3:
D[:, X] = cycle(array).transpose()
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = np.delete(D, Y, 1)
print(D)
M = Matroid(Matrix(D))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
The results are
[[ 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0.]
[-1. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 0. 1. 1.
1. 1. 0. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 1. 1. 1. 1. 0. 0.]
[ 0. -1. 0. -1. 0. 1. 0. 0. 0. 0. -1. 0. 0. 0. 0. -1. -1. 0.
0. -1. 1. 1. 0. 0. 0. 0. -1. 0. 0. -1. 0. 0. -1. 0. -1. 1. 1.]
[ 0. 0. -1. 0. -1. -1. 0. 0. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1.
-1. 0. -1. -1. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1. 0. -1. 0. -1. -1.]
[ 1. 0. 0. 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 0. 0. -1. -1.
0. 0. 0. 0. 1. 1. 0. 1. 1. 0. 0. 0. 0. -1. -1. 0. 0. 1. -1.]
[ 0. 1. 0. 0. 0. 0. -1. 0. 1. 0. 0. 0. 1. 1. 0. 0. 1. 0.
0. 0. -1. 0. 0. -1. 1. 0. 0. 1. 1. 0. 0. 1. 0. -1. 1. -1. 0.]
[ 0. 0. 1. 0. 0. 0. 0. -1. -1. 0. 0. 0. 0. 0. 1. 1. 0. 1.
0. 0. 1. 0. -1. 0. -1. 0. 0. 0. 0. 1. 1. 0. 1. 1. -1. 0. 1.]
[ 0. 0. 0. 1. 0. 0. 1. 0. 0. 1. 1. 0. -1. 0. 0. 0. 0. 0.
1. 0. 0. -1. 1. 0. -1. 1. 0. -1. 0. 1. -1. 0. 0. 1. 0. 0. -1.]
[ 0. 0. 0. 0. 1. 0. 0. 1. 0. -1. 0. 1. 0. 0. -1. 0. 0. 0.
0. 1. 0. 1. 0. 1. 1. 0. 1. 1. -1. -1. 0. 0. 0. 0. 1. 1. 0.]
[ 0. 0. 0. 0. 0. 1. 0. 0. 1. 1. 0. 0. 0. 1. 0. -1. 0. 0.
1. -1. 0. 0. 1. -1. 0. 1. -1. 0. 1. 0. -1. 1. -1. 0. 0. 0. 0.]]
M.tutte_polynomial(2, 0) = 46229
M.tutte_polynomial(2, 0) = 52640Tue, 11 Jan 2022 20:06:59 +0100https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/
- Comment by dingchangxin for <p>I have been using Sage in my research recently.</p>
<p>I am not sure which part is wrong but the following code
gives the wrong results. The code is long, but I think you may
only need to read the last four rows to understand my question.</p>
<p>All the rows before that generate a matrix <code>D</code>
where the columns are the cycles of the complete graph <code>K_5</code>
(each cycle is a vector in <code>Z^10</code>, 10 is the number of edges.)</p>
<p>Then I produce a linear matroid from <code>D</code> and calculate <code>T(2, 0)</code>
using <code>tutte_polynomial()</code>. The weird thing is that the result
is an odd number, which is impossible because the Tutte polynomial
has no constant term. The more weird thing is that if I repeat the
order again, I get a different result.</p>
<p>If I run the code for the graph <code>K_4</code>, nothing is wrong,
which is why I need to give the complete code.
The code is run by CoCalc. </p>
<pre><code>import numpy as np
from sage.matroids.advanced import *
graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return False
C = np.zeros(nv*(nv-1)/2) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = np.zeros((ne,ncycle*2)) # D is all directed cycles
X = 0
for list in allcycles:
array = np.array(list)
if len(array) > 3:
D[:, X] = cycle(array).transpose()
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = np.delete(D, Y, 1)
print(D)
M = Matroid(Matrix(D))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
</code></pre>
<p>The results are</p>
<pre><code>[[ 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0.]
[-1. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 0. 1. 1.
1. 1. 0. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 1. 1. 1. 1. 0. 0.]
[ 0. -1. 0. -1. 0. 1. 0. 0. 0. 0. -1. 0. 0. 0. 0. -1. -1. 0.
0. -1. 1. 1. 0. 0. 0. 0. -1. 0. 0. -1. 0. 0. -1. 0. -1. 1. 1.]
[ 0. 0. -1. 0. -1. -1. 0. 0. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1.
-1. 0. -1. -1. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1. 0. -1. 0. -1. -1.]
[ 1. 0. 0. 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 0. 0. -1. -1.
0. 0. 0. 0. 1. 1. 0. 1. 1. 0. 0. 0. 0. -1. -1. 0. 0. 1. -1.]
[ 0. 1. 0. 0. 0. 0. -1. 0. 1. 0. 0. 0. 1. 1. 0. 0. 1. 0.
0. 0. -1. 0. 0. -1. 1. 0. 0. 1. 1. 0. 0. 1. 0. -1. 1. -1. 0.]
[ 0. 0. 1. 0. 0. 0. 0. -1. -1. 0. 0. 0. 0. 0. 1. 1. 0. 1.
0. 0. 1. 0. -1. 0. -1. 0. 0. 0. 0. 1. 1. 0. 1. 1. -1. 0. 1.]
[ 0. 0. 0. 1. 0. 0. 1. 0. 0. 1. 1. 0. -1. 0. 0. 0. 0. 0.
1. 0. 0. -1. 1. 0. -1. 1. 0. -1. 0. 1. -1. 0. 0. 1. 0. 0. -1.]
[ 0. 0. 0. 0. 1. 0. 0. 1. 0. -1. 0. 1. 0. 0. -1. 0. 0. 0.
0. 1. 0. 1. 0. 1. 1. 0. 1. 1. -1. -1. 0. 0. 0. 0. 1. 1. 0.]
[ 0. 0. 0. 0. 0. 1. 0. 0. 1. 1. 0. 0. 0. 1. 0. -1. 0. 0.
1. -1. 0. 0. 1. -1. 0. 1. -1. 0. 1. 0. -1. 1. -1. 0. 0. 0. 0.]]
M.tutte_polynomial(2, 0) = 46229
M.tutte_polynomial(2, 0) = 52640
</code></pre>
https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60659#post-id-60659Thank you for editing my question so that it looks neat. This is a wonderful place.Thu, 13 Jan 2022 04:28:11 +0100https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60659#post-id-60659
- Comment by slelievre for <p>I have been using Sage in my research recently.</p>
<p>I am not sure which part is wrong but the following code
gives the wrong results. The code is long, but I think you may
only need to read the last four rows to understand my question.</p>
<p>All the rows before that generate a matrix <code>D</code>
where the columns are the cycles of the complete graph <code>K_5</code>
(each cycle is a vector in <code>Z^10</code>, 10 is the number of edges.)</p>
<p>Then I produce a linear matroid from <code>D</code> and calculate <code>T(2, 0)</code>
using <code>tutte_polynomial()</code>. The weird thing is that the result
is an odd number, which is impossible because the Tutte polynomial
has no constant term. The more weird thing is that if I repeat the
order again, I get a different result.</p>
<p>If I run the code for the graph <code>K_4</code>, nothing is wrong,
which is why I need to give the complete code.
The code is run by CoCalc. </p>
<pre><code>import numpy as np
from sage.matroids.advanced import *
graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return False
C = np.zeros(nv*(nv-1)/2) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = np.zeros((ne,ncycle*2)) # D is all directed cycles
X = 0
for list in allcycles:
array = np.array(list)
if len(array) > 3:
D[:, X] = cycle(array).transpose()
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = np.delete(D, Y, 1)
print(D)
M = Matroid(Matrix(D))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
</code></pre>
<p>The results are</p>
<pre><code>[[ 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0.]
[-1. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 0. 1. 1.
1. 1. 0. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 1. 1. 1. 1. 0. 0.]
[ 0. -1. 0. -1. 0. 1. 0. 0. 0. 0. -1. 0. 0. 0. 0. -1. -1. 0.
0. -1. 1. 1. 0. 0. 0. 0. -1. 0. 0. -1. 0. 0. -1. 0. -1. 1. 1.]
[ 0. 0. -1. 0. -1. -1. 0. 0. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1.
-1. 0. -1. -1. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1. 0. -1. 0. -1. -1.]
[ 1. 0. 0. 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 0. 0. -1. -1.
0. 0. 0. 0. 1. 1. 0. 1. 1. 0. 0. 0. 0. -1. -1. 0. 0. 1. -1.]
[ 0. 1. 0. 0. 0. 0. -1. 0. 1. 0. 0. 0. 1. 1. 0. 0. 1. 0.
0. 0. -1. 0. 0. -1. 1. 0. 0. 1. 1. 0. 0. 1. 0. -1. 1. -1. 0.]
[ 0. 0. 1. 0. 0. 0. 0. -1. -1. 0. 0. 0. 0. 0. 1. 1. 0. 1.
0. 0. 1. 0. -1. 0. -1. 0. 0. 0. 0. 1. 1. 0. 1. 1. -1. 0. 1.]
[ 0. 0. 0. 1. 0. 0. 1. 0. 0. 1. 1. 0. -1. 0. 0. 0. 0. 0.
1. 0. 0. -1. 1. 0. -1. 1. 0. -1. 0. 1. -1. 0. 0. 1. 0. 0. -1.]
[ 0. 0. 0. 0. 1. 0. 0. 1. 0. -1. 0. 1. 0. 0. -1. 0. 0. 0.
0. 1. 0. 1. 0. 1. 1. 0. 1. 1. -1. -1. 0. 0. 0. 0. 1. 1. 0.]
[ 0. 0. 0. 0. 0. 1. 0. 0. 1. 1. 0. 0. 0. 1. 0. -1. 0. 0.
1. -1. 0. 0. 1. -1. 0. 1. -1. 0. 1. 0. -1. 1. -1. 0. 0. 0. 0.]]
M.tutte_polynomial(2, 0) = 46229
M.tutte_polynomial(2, 0) = 52640
</code></pre>
https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60640#post-id-60640Welcome to Ask Sage! Thank you for your question.Wed, 12 Jan 2022 10:24:42 +0100https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60640#post-id-60640
- Answer by rburing for <p>I have been using Sage in my research recently.</p>
<p>I am not sure which part is wrong but the following code
gives the wrong results. The code is long, but I think you may
only need to read the last four rows to understand my question.</p>
<p>All the rows before that generate a matrix <code>D</code>
where the columns are the cycles of the complete graph <code>K_5</code>
(each cycle is a vector in <code>Z^10</code>, 10 is the number of edges.)</p>
<p>Then I produce a linear matroid from <code>D</code> and calculate <code>T(2, 0)</code>
using <code>tutte_polynomial()</code>. The weird thing is that the result
is an odd number, which is impossible because the Tutte polynomial
has no constant term. The more weird thing is that if I repeat the
order again, I get a different result.</p>
<p>If I run the code for the graph <code>K_4</code>, nothing is wrong,
which is why I need to give the complete code.
The code is run by CoCalc. </p>
<pre><code>import numpy as np
from sage.matroids.advanced import *
graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return False
C = np.zeros(nv*(nv-1)/2) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = np.zeros((ne,ncycle*2)) # D is all directed cycles
X = 0
for list in allcycles:
array = np.array(list)
if len(array) > 3:
D[:, X] = cycle(array).transpose()
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = np.delete(D, Y, 1)
print(D)
M = Matroid(Matrix(D))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
</code></pre>
<p>The results are</p>
<pre><code>[[ 1. 1. 1. 0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0.
0. 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 0. 0. 0. 0. 0. 0.]
[-1. 0. 0. 1. 1. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 0. 1. 1.
1. 1. 0. 0. 0. 0. 0. 0. 0. 0. -1. 0. -1. 1. 1. 1. 1. 0. 0.]
[ 0. -1. 0. -1. 0. 1. 0. 0. 0. 0. -1. 0. 0. 0. 0. -1. -1. 0.
0. -1. 1. 1. 0. 0. 0. 0. -1. 0. 0. -1. 0. 0. -1. 0. -1. 1. 1.]
[ 0. 0. -1. 0. -1. -1. 0. 0. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1.
-1. 0. -1. -1. 0. 0. 0. -1. 0. -1. 0. 0. 0. -1. 0. -1. 0. -1. -1.]
[ 1. 0. 0. 0. 0. 0. 1. 1. 0. 0. 1. 1. 0. 0. 0. 0. -1. -1.
0. 0. 0. 0. 1. 1. 0. 1. 1. 0. 0. 0. 0. -1. -1. 0. 0. 1. -1.]
[ 0. 1. 0. 0. 0. 0. -1. 0. 1. 0. 0. 0. 1. 1. 0. 0. 1. 0.
0. 0. -1. 0. 0. -1. 1. 0. 0. 1. 1. 0. 0. 1. 0. -1. 1. -1. 0.]
[ 0. 0. 1. 0. 0. 0. 0. -1. -1. 0. 0. 0. 0. 0. 1. 1. 0. 1.
0. 0. 1. 0. -1. 0. -1. 0. 0. 0. 0. 1. 1. 0. 1. 1. -1. 0. 1.]
[ 0. 0. 0. 1. 0. 0. 1. 0. 0. 1. 1. 0. -1. 0. 0. 0. 0. 0.
1. 0. 0. -1. 1. 0. -1. 1. 0. -1. 0. 1. -1. 0. 0. 1. 0. 0. -1.]
[ 0. 0. 0. 0. 1. 0. 0. 1. 0. -1. 0. 1. 0. 0. -1. 0. 0. 0.
0. 1. 0. 1. 0. 1. 1. 0. 1. 1. -1. -1. 0. 0. 0. 0. 1. 1. 0.]
[ 0. 0. 0. 0. 0. 1. 0. 0. 1. 1. 0. 0. 0. 1. 0. -1. 0. 0.
1. -1. 0. 0. 1. -1. 0. 1. -1. 0. 1. 0. -1. 1. -1. 0. 0. 0. 0.]]
M.tutte_polynomial(2, 0) = 46229
M.tutte_polynomial(2, 0) = 52640
</code></pre>
https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?answer=60641#post-id-60641Don't use floating point numbers, vectors or matrices (here: numpy arrays) if you want to do an exact computation.
graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return None
C = zero_vector(ZZ, ne) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = matrix(ZZ, ne, ncycle*2) # D is all directed cycles
X = 0
for array in allcycles:
if len(array) > 3:
D.set_column(X, cycle(array))
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = D.delete_columns([Y])
print(D)
M = Matroid(D)
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
Output:
[ 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0]
[-1 0 0 1 1 0 0 0 0 0 0 0 -1 0 -1 0 1 1 1 1 0 0 0 0 0 0 0 0 -1 0 -1 1 1 1 1 0 0]
[ 0 -1 0 -1 0 1 0 0 0 0 -1 0 0 0 0 -1 -1 0 0 -1 1 1 0 0 0 0 -1 0 0 -1 0 0 -1 0 -1 1 1]
[ 0 0 -1 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 0 -1 -1 0 -1 -1 0 0 0 -1 0 -1 0 0 0 -1 0 -1 0 -1 -1]
[ 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 0 0 0 0 1 1 0 1 1 0 0 0 0 -1 -1 0 0 1 -1]
[ 0 1 0 0 0 0 -1 0 1 0 0 0 1 1 0 0 1 0 0 0 -1 0 0 -1 1 0 0 1 1 0 0 1 0 -1 1 -1 0]
[ 0 0 1 0 0 0 0 -1 -1 0 0 0 0 0 1 1 0 1 0 0 1 0 -1 0 -1 0 0 0 0 1 1 0 1 1 -1 0 1]
[ 0 0 0 1 0 0 1 0 0 1 1 0 -1 0 0 0 0 0 1 0 0 -1 1 0 -1 1 0 -1 0 1 -1 0 0 1 0 0 -1]
[ 0 0 0 0 1 0 0 1 0 -1 0 1 0 0 -1 0 0 0 0 1 0 1 0 1 1 0 1 1 -1 -1 0 0 0 0 1 1 0]
[ 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 -1 0 0 1 -1 0 0 1 -1 0 1 -1 0 1 0 -1 1 -1 0 0 0 0]
M.tutte_polynomial(2, 0) = 89280
M.tutte_polynomial(2, 0) = 89280
Wed, 12 Jan 2022 11:17:49 +0100https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?answer=60641#post-id-60641
- Comment by dingchangxin for <p>Don't use floating point numbers, vectors or matrices (here: numpy arrays) if you want to do an exact computation.</p>
<pre><code>graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return None
C = zero_vector(ZZ, ne) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = matrix(ZZ, ne, ncycle*2) # D is all directed cycles
X = 0
for array in allcycles:
if len(array) > 3:
D.set_column(X, cycle(array))
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = D.delete_columns([Y])
print(D)
M = Matroid(D)
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
</code></pre>
<p>Output:</p>
<pre><code>[ 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0]
[-1 0 0 1 1 0 0 0 0 0 0 0 -1 0 -1 0 1 1 1 1 0 0 0 0 0 0 0 0 -1 0 -1 1 1 1 1 0 0]
[ 0 -1 0 -1 0 1 0 0 0 0 -1 0 0 0 0 -1 -1 0 0 -1 1 1 0 0 0 0 -1 0 0 -1 0 0 -1 0 -1 1 1]
[ 0 0 -1 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 0 -1 -1 0 -1 -1 0 0 0 -1 0 -1 0 0 0 -1 0 -1 0 -1 -1]
[ 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 0 0 0 0 1 1 0 1 1 0 0 0 0 -1 -1 0 0 1 -1]
[ 0 1 0 0 0 0 -1 0 1 0 0 0 1 1 0 0 1 0 0 0 -1 0 0 -1 1 0 0 1 1 0 0 1 0 -1 1 -1 0]
[ 0 0 1 0 0 0 0 -1 -1 0 0 0 0 0 1 1 0 1 0 0 1 0 -1 0 -1 0 0 0 0 1 1 0 1 1 -1 0 1]
[ 0 0 0 1 0 0 1 0 0 1 1 0 -1 0 0 0 0 0 1 0 0 -1 1 0 -1 1 0 -1 0 1 -1 0 0 1 0 0 -1]
[ 0 0 0 0 1 0 0 1 0 -1 0 1 0 0 -1 0 0 0 0 1 0 1 0 1 1 0 1 1 -1 -1 0 0 0 0 1 1 0]
[ 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 -1 0 0 1 -1 0 0 1 -1 0 1 -1 0 1 0 -1 1 -1 0 0 0 0]
M.tutte_polynomial(2, 0) = 89280
M.tutte_polynomial(2, 0) = 89280
</code></pre>
https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60658#post-id-60658Thank you so much for your answer! You have even corrected the code, which saves me a lot of time.Thu, 13 Jan 2022 04:21:56 +0100https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60658#post-id-60658
- Comment by rburing for <p>Don't use floating point numbers, vectors or matrices (here: numpy arrays) if you want to do an exact computation.</p>
<pre><code>graph = graphs.CompleteGraph(5)
g = graph.to_directed()
allcycles = g.all_simple_cycles()
nv = g.order() # nv is number of vertices
ne = nv*(nv-1)/2 # ne is the number of edges
ncycle = (len(allcycles)-g.size()/2)/2 # ncycle is number of simple cycles
def cycle(array): # array is a cycle in vertices notation eg. [0,1,2,3,0]
l = len(array) - 1 # l is the length of the cycle
if l <= 2:
return None
C = zero_vector(ZZ, ne) # C is to be a cycle in Z^E
for X in range(l):
i = array[X] + 1
j = array[X+1] + 1
if i < j:
C[(2*nv-i)*(i-1)/2+j-i-1] = 1
else:
C[(2*nv-j)*(j-1)/2+i-j-1] = -1
return(C)
D = matrix(ZZ, ne, ncycle*2) # D is all directed cycles
X = 0
for array in allcycles:
if len(array) > 3:
D.set_column(X, cycle(array))
X = X + 1
for X in range(ncycle): # reduce D so that D is all cycles with one orientation
positivecolumn = D[:, X]
Y = X + 1
while any(D[:, Y] + positivecolumn):
Y = Y + 1
D = D.delete_columns([Y])
print(D)
M = Matroid(D)
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
print("M.tutte_polynomial(2, 0) =", M.tutte_polynomial(2, 0))
</code></pre>
<p>Output:</p>
<pre><code>[ 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0]
[-1 0 0 1 1 0 0 0 0 0 0 0 -1 0 -1 0 1 1 1 1 0 0 0 0 0 0 0 0 -1 0 -1 1 1 1 1 0 0]
[ 0 -1 0 -1 0 1 0 0 0 0 -1 0 0 0 0 -1 -1 0 0 -1 1 1 0 0 0 0 -1 0 0 -1 0 0 -1 0 -1 1 1]
[ 0 0 -1 0 -1 -1 0 0 0 0 0 -1 0 -1 0 0 0 -1 -1 0 -1 -1 0 0 0 -1 0 -1 0 0 0 -1 0 -1 0 -1 -1]
[ 1 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 -1 -1 0 0 0 0 1 1 0 1 1 0 0 0 0 -1 -1 0 0 1 -1]
[ 0 1 0 0 0 0 -1 0 1 0 0 0 1 1 0 0 1 0 0 0 -1 0 0 -1 1 0 0 1 1 0 0 1 0 -1 1 -1 0]
[ 0 0 1 0 0 0 0 -1 -1 0 0 0 0 0 1 1 0 1 0 0 1 0 -1 0 -1 0 0 0 0 1 1 0 1 1 -1 0 1]
[ 0 0 0 1 0 0 1 0 0 1 1 0 -1 0 0 0 0 0 1 0 0 -1 1 0 -1 1 0 -1 0 1 -1 0 0 1 0 0 -1]
[ 0 0 0 0 1 0 0 1 0 -1 0 1 0 0 -1 0 0 0 0 1 0 1 0 1 1 0 1 1 -1 -1 0 0 0 0 1 1 0]
[ 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 -1 0 0 1 -1 0 0 1 -1 0 1 -1 0 1 0 -1 1 -1 0 0 0 0]
M.tutte_polynomial(2, 0) = 89280
M.tutte_polynomial(2, 0) = 89280
</code></pre>
https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60642#post-id-60642Maybe the `Matroid` constructor should give a warning or an error when a matrix with floating point entries is passed.Wed, 12 Jan 2022 11:25:09 +0100https://ask.sagemath.org/question/60626/tutte_polynomial-sage-matroid-theory-gives-the-wrong-result/?comment=60642#post-id-60642