import itertools
def get_edge_index(G, i, j):
count = 0;
for e in G.edge_iterator():
if (i in e) and (j in e):
return count;
count = count + 1;
return (-1)
g = Graph();
g.add_edges([(0,2),(0,5),(0,4), (1,5),(2,3),(2,5),]);
n = 4;
k = 2;
g = graphs.CompleteGraph(n);
g.show()
print "Graph has " + str(g.order()) + " vertices and " + str(g.size()) + " edges"
print "Display variable -> edge dictionary"
count = 0
for e in g.edge_iterator():
print "x[" + str(count) + "] = (" + str(e[0]) + "," + str(e[1]) + ")"
count = count + 1;
P = PolynomialRing(QQ, g.size(), 'x', order="lex")
x = P.gens()
I = list();
for e in range(0, g.size()):
I.append( x[e]^2 - x[e] );
ilist = list(IntegerRange(g.order()))
L = list(itertools.combinations((ilist), k))
tp = 1;
for si in range(0, len(L)):
curset = L[si]
in_s = 0;
for i in range(0,g.order()):
if i not in curset:
in_p = 1;
for j in range(0, g.order()):
if j in curset:
ein = get_edge_index(g, i, j)
if (ein >= 0):
in_p = in_p*(x[ein] - 1);
if in_p != 1:
in_s = in_s + in_p;
if in_s != 0:
tp = tp*in_s;
I.append(tp);
myI = ideal(I);
print "Beginning grobner basis calculation..."
B = myI.groebner_basis();
for i in range(0, len(B)):
print str(factor(B[i]))
Graph has 4 vertices and 6 edges
Display variable -> edge dictionary
x[0] = (0,1)
x[1] = (0,2)
x[2] = (0,3)
x[3] = (1,2)
x[4] = (1,3)
x[5] = (2,3)
Beginning grobner basis calculation...
x0 * (x0 - 1)
(x4 - 1) * (x3 - 1) * (x2 - 1) * (x1 - 1) * (x0 - 1)
(x5 - 1) * (x3 - 1) * (x2 - 1) * (x1 - 1) * (x0 - 1)
(x5 - 1) * (x4 - 1) * (x2 - 1) * (x1 - 1) * (x0 - 1)
(x5 - 1) * (x4 - 1) * (x3 - 1) * (x1 - 1) * (x0 - 1)
(x5 - 1) * (x4 - 1) * (x3 - 1) * (x2 - 1) * (x0 - 1)
x1 * (x1 - 1)
(x5 - 1) * (x4 - 1) * (x3 - 1) * (x2 - 1) * (x1 - 1)
x2 * (x2 - 1)
x3 * (x3 - 1)
x4 * (x4 - 1)
x5 * (x5 - 1)