Perfect Matching Graph To Ideal

1
# this file ONLY contains graph_to_ideal, and is meant to be
2
# loaded from other files
3
# via the command load('func_graph_to_ideal.sage')
4
# see the file experiments.sagews for an example
5
#
6
# DESC: graph_to_ideal takes as input a graph (and related information)
7
#     and returns as output the associated perfect matching ideal
8
#
9
# INPUT:
10
#     g: a object of sage graph class
11
#
12
# OUTPUT:
13
#    P: a F_2[x_1,...x_e], a polynomial ring over F2 with one variable per edge
14
#    I: a list of the polynomials in the perfect matching ideal
15
#
16
def graph_to_ideal(g,o,r):
17
    #print "Entering graph_to_ideal... "
18
    #print "G: " + str(G)
19
    #print "num_vertices = " + str(g.order())
20
    #print "num_edges = " + str(g.size())
21

22
    if o==0 and r==0:
23
        # establish the ring containing the ideal (this will be returned)
24
        # number of variables is number of edges
25
        P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F2
26
        #P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over the rationals
27
        x = P.gens();
28
        #print str(type(P))
29
        I = list(); # create an empty list
30
        #print "Constructing boolean polynomials, one per edge"
31
        # for each edge, create the polynomial eij^2 - eij
32
        for e in range(0, g.size()):
33
            I.append( x[e]^2 - x[e] );
34
            #end for
35
            #print "Ideal = " + str(I)
36
        #endif
37

38
    if o==0 and r==1:
39
            # establish the ring containing the ideal (this will be returned)
40
            # number of variables is number of edges
41
            #P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F2
42
        P = PolynomialRing(CC, g.size(), 'x', order="lex") # over the rationals
43
        x = P.gens();
44
            #print str(type(P))
45
        I = list(); # create an empty list
46
            #print "Constructing boolean polynomials, one per edge"
47
            # for each edge, create the polynomial eij^2 - eij
48
        for e in range(0, g.size()):
49
            I.append( x[e]^2 - x[e] );
50
            #end for
51
            #print "Ideal = " + str(I)
52
            #endif
53

54
    if o==1 and r==0:
55
            # establish the ring containing the ideal (this will be returned)
56
            # number of variables is number of edges
57
        P = PolynomialRing(FiniteField(2), g.size(), 'x', order="deglex") # over F2
58
            #P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over the rationals
59
        x = P.gens();
60
            #print str(type(P))
61
        I = list(); # create an empty list
62
            #print "Constructing boolean polynomials, one per edge"
63
            # for each edge, create the polynomial eij^2 - eij
64
        for e in range(0, g.size()):
65
            I.append( x[e]^2 - x[e] );
66
            #end for
67
            #print "Ideal = " + str(I)
68
            #endif
69

70
    if o==1 and r==1:
71
            # establish the ring containing the ideal (this will be returned)
72
            # number of variables is number of edges
73
            #P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F2
74
        P = PolynomialRing(CC, g.size(), 'x', order="deglex") # over the rationals
75
        x = P.gens();
76
            #print str(type(P))
77
        I = list(); # create an empty list
78
            #print "Constructing boolean polynomials, one per edge"
79
            # for each edge, create the polynomial eij^2 - eij
80
        for e in range(0, g.size()):
81
            I.append( x[e]^2 - x[e] );
82
            #end for
83
            #print "Ideal = " + str(I)
84
            #endif
85
    if o==2 and r==0:
86
            # establish the ring containing the ideal (this will be returned)
87
            # number of variables is number of edges
88
        P = PolynomialRing(FiniteField(2), g.size(), 'x', order="degrevlex") # over F2
89
            #P = PolynomialRing(QQ, g.size(), 'x', order="lex") # over the rationals
90
        x = P.gens();
91
            #print str(type(P))
92
        I = list(); # create an empty list
93
            #print "Constructing boolean polynomials, one per edge"
94
            # for each edge, create the polynomial eij^2 - eij
95
        for e in range(0, g.size()):
96
            I.append( x[e]^2 - x[e] );
97
            #end for
98
            #print "Ideal = " + str(I)
99
            #endif
100

101
    if o==2 and r==1:
102
        # establish the ring containing the ideal (this will be returned)
103
            # number of variables is number of edges
104
            #P = PolynomialRing(FiniteField(2), g.size(), 'x', order="lex") # over F2
105
        P = PolynomialRing(CC, g.size(), 'x', order="degrevlex") # over the rationals
106
        x = P.gens();
107
            #print str(type(P))
108
        I = list(); # create an empty list
109
            #print "Constructing boolean polynomials, one per edge"
110
            # for each edge, create the polynomial eij^2 - eij
111
        for e in range(0, g.size()):
112
            I.append( x[e]^2 - x[e] );
113
            #end for
114
            #print "Ideal = " + str(I)
115
            #endif
116

117
    # the incidence matrix is a (# of vertices) x (# of edges matrix) 
118
    # where A(i,j) = 1 if vertex i is incident on edge j, and 0 otherwise
119
    A = g.incidence_matrix()
120
    #print str(A)
121
    # this is just for debugging
122
    debug = 1
123
    if debug == 1:
124
        count = 0;
125
        for e in g.edge_iterator():
126
            #print "x[" + str(count) + "]: " + str(e)
127
            count = count + 1;
128
        #end for
129
    #end if debug
130

131
    # construct the polynomial vi = 1 + sum_{j \in neighborhood(i)} x_ij
132
    for i in range(0, g.order()): # for each vertex in the graph
133
        f = -1;
134
        #print "Constructing polynomial for vertex = " + str(i)
135
        for e in range(0, g.size()): # find the neighbors
136
            #print "e = " + str(e)
137
            if A[i,e] == 1:
138
                # vertex i is incident on edge e
139
                f = f + x[e]
140
            #endif
141
        #end for edges
142
        #print "f = " + str(f)
143
        I.append(f); # append vertex polynomial to ideal
144
    #end for vertices
145

146
    # having constructed the vertex polynomials, now construct the edge polynomial
147
    for i in range(0, g.order()): # for each vertex in the graph
148
        for e in range(0, g.size()): # find the first edge incident on vertex i
149
            if A[i,e] == 1:
150
                # vertex i is incident on edge e
151
                e_base = e;
152
                for ee in range(e_base + 1, g.size()):
153
                    if A[i,ee] == 1: # find the next incident edge
154
                        I.append(x[e_base]*x[ee]);
155
                        #print "Adding edge pair (" + str(e_base) + ", " + str(ee) + ")"
156
                    #endif
157
                #end for ee
158
            #endif
159
        #end for edges
160
    #end for vertices
161

162
    # use the "dictionary" method return the variables
163
    return {'P':P, 'I':I}
164
#enddef graph_to_ideal
165