| Download
Perfect Matching Graph To Ideal
Project: Algebraic Optimization
Path: 2017-03-22-180741.sage
Views: 91# this file ONLY contains graph_to_ideal, and is meant to be1# loaded from other files2# via the command load('func_graph_to_ideal.sage')3# see the file experiments.sagews for an example4#5# DESC: graph_to_ideal takes as input a graph (and related information)6# and returns as output the associated perfect matching ideal7#8# INPUT:9# g: a object of sage graph class10#11# OUTPUT:12# P: a F_2[x_1,...x_e], a polynomial ring over F2 with one variable per edge13# I: a list of the polynomials in the perfect matching ideal14#15def graph_to_ideal(g,o,r):16#print "Entering graph_to_ideal... "17#print "G: " + str(G)18#print "num_vertices = " + str(g.order())19#print "num_edges = " + str(g.size())2021if o==0 and r==0:22# establish the ring containing the ideal (this will be returned)23# number of variables is number of edges24P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F225#P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over the rationals26x = P.gens();27#print str(type(P))28I = list(); # create an empty list29#print "Constructing boolean polynomials, one per edge"30# for each edge, create the polynomial eij^2 - eij31for e in range(0, g.size()):32I.append( x[e]^2 - x[e] );33#end for34#print "Ideal = " + str(I)35#endif3637if o==0 and r==1:38# establish the ring containing the ideal (this will be returned)39# number of variables is number of edges40#P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F241P = PolynomialRing(CC, g.size(), 'x', order="lex") # over the rationals42x = P.gens();43#print str(type(P))44I = list(); # create an empty list45#print "Constructing boolean polynomials, one per edge"46# for each edge, create the polynomial eij^2 - eij47for e in range(0, g.size()):48I.append( x[e]^2 - x[e] );49#end for50#print "Ideal = " + str(I)51#endif5253if o==1 and r==0:54# establish the ring containing the ideal (this will be returned)55# number of variables is number of edges56P = PolynomialRing(FiniteField(2), g.size(), 'x', order="deglex") # over F257#P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over the rationals58x = P.gens();59#print str(type(P))60I = list(); # create an empty list61#print "Constructing boolean polynomials, one per edge"62# for each edge, create the polynomial eij^2 - eij63for e in range(0, g.size()):64I.append( x[e]^2 - x[e] );65#end for66#print "Ideal = " + str(I)67#endif6869if o==1 and r==1:70# establish the ring containing the ideal (this will be returned)71# number of variables is number of edges72#P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F273P = PolynomialRing(CC, g.size(), 'x', order="deglex") # over the rationals74x = P.gens();75#print str(type(P))76I = list(); # create an empty list77#print "Constructing boolean polynomials, one per edge"78# for each edge, create the polynomial eij^2 - eij79for e in range(0, g.size()):80I.append( x[e]^2 - x[e] );81#end for82#print "Ideal = " + str(I)83#endif84if o==2 and r==0:85# establish the ring containing the ideal (this will be returned)86# number of variables is number of edges87P = PolynomialRing(FiniteField(2), g.size(), 'x', order="degrevlex") # over F288#P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over the rationals89x = P.gens();90#print str(type(P))91I = list(); # create an empty list92#print "Constructing boolean polynomials, one per edge"93# for each edge, create the polynomial eij^2 - eij94for e in range(0, g.size()):95I.append( x[e]^2 - x[e] );96#end for97#print "Ideal = " + str(I)98#endif99100if o==2 and r==1:101# establish the ring containing the ideal (this will be returned)102# number of variables is number of edges103#P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F2104P = PolynomialRing(CC, g.size(), 'x', order="degrevlex") # over the rationals105x = P.gens();106#print str(type(P))107I = list(); # create an empty list108#print "Constructing boolean polynomials, one per edge"109# for each edge, create the polynomial eij^2 - eij110for e in range(0, g.size()):111I.append( x[e]^2 - x[e] );112#end for113#print "Ideal = " + str(I)114#endif115116# the incidence matrix is a (# of vertices) x (# of edges matrix)117# where A(i,j) = 1 if vertex i is incident on edge j, and 0 otherwise118A = g.incidence_matrix()119#print str(A)120# this is just for debugging121debug = 1122if debug == 1:123count = 0;124for e in g.edge_iterator():125#print "x[" + str(count) + "]: " + str(e)126count = count + 1;127#end for128#end if debug129130# construct the polynomial vi = 1 + sum_{j \in neighborhood(i)} x_ij131for i in range(0, g.order()): # for each vertex in the graph132f = -1;133#print "Constructing polynomial for vertex = " + str(i)134for e in range(0, g.size()): # find the neighbors135#print "e = " + str(e)136if A[i,e] == 1:137# vertex i is incident on edge e138f = f + x[e]139#endif140#end for edges141#print "f = " + str(f)142I.append(f); # append vertex polynomial to ideal143#end for vertices144145# having constructed the vertex polynomials, now construct the edge polynomial146for i in range(0, g.order()): # for each vertex in the graph147for e in range(0, g.size()): # find the first edge incident on vertex i148if A[i,e] == 1:149# vertex i is incident on edge e150e_base = e;151for ee in range(e_base + 1, g.size()):152if A[i,ee] == 1: # find the next incident edge153I.append(x[e_base]*x[ee]);154#print "Adding edge pair (" + str(e_base) + ", " + str(ee) + ")"155#endif156#end for ee157#endif158#end for edges159#end for vertices160161# use the "dictionary" method return the variables162return {'P':P, 'I':I}163#enddef graph_to_ideal164165