Revision history [back]

Don'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