CoCalc -- graph_to_ideal

Graph to ideal modified for two colour
Views: ⁹⁴
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
    P = PolynomialRing(FiniteField(2), g.order(), 'x', order="lex")
23
    #I = list(); # create an empty list
24
    
25
    # the incidence matrix is a (# of vertices) x (# of edges matrix)
26
    # where A(i,j) = 1 if vertex i is incident on edge j, and 0 otherwise
27
    A = g.adjacency_matrix()
28
    #print str(A)
29
    # this is just for debugging
30
    debug = 1
31
    if debug == 1:
32
        count = 0;
33
        for e in g.edge_iterator():
34
            #print "x[" + str(count) + "]: " + str(e)
35
            count = count + 1;
36
        #end for
37
    #end if debug
38

39
    if o==0 and r==0:
40
        # establish the ring containing the ideal (this will be returned)
41
        # number of variables is number of edges
42
        P = PolynomialRing(FiniteField(2), g.order(), 'x', order="lex") # over F2
43
        x = P.gens();
44
        #print str(type(P))
45
        I = list(); # create an empty list
46
        # for each vertice, create polynomial x^3-1
47
        for i in range(0, g.order()): # for each vertex in the graph, cr
48
            I.append(x[i]^2-x[i])
49
            #print("I: ") + str(I)
50
            #print "Constructing polynomials, one per vertice" + str(x[i]^3-1)
51
            for j in range(i+1, g.order()):
52
                if A[i,j] == 1:
53
                    I.append(x[i]+x[j]-1)
54
                    #print("I: ") + str(I)
55

56
    if o==0 and r==1:
57
            # establish the ring containing the ideal (this will be returned)
58
        # number of variables is number of edges
59
        P = PolynomialRing(CC, g.order(), 'x', order="lex") # over the rationals
60
        x = P.gens();
61
        #print str(type(P))
62
        I = list(); # create an empty list
63
        #print "Constructing boolean polynomials, one per edge"
64
        # for each edge, create the polynomial eij^2 - eij
65
        for i in range(0, g.order()): # for each vertex in the graph
66
            I.append(x[i]^2-x[i])
67
            for j in range(i+1, g.order()):
68
                if A[i,j] == 1:
69
                    I.append(x[i]+x[j]-1)
70
                    #
71
                    #endif
72
                #end for ee
73
            #endif
74
        #end for edges
75
    #end for vertices
76

77
    if o==1 and r==0:
78
            # establish the ring containing the ideal (this will be returned)
79
            # number of variables is number of edges
80
        P = PolynomialRing(FiniteField(2), g.order(), 'x', order="deglex") # over F2
81
        x = P.gens();
82
            #print str(type(P))
83
        I = list(); # create an empty list
84
            #print "Constructing boolean polynomials, one per edge"
85
        # for each edge, create the polynomial eij^2 - eij
86
        for i in range(0, g.order()): # for each vertex in the graph
87
            I.append(x[i]^2-x[i])
88
            for j in range(i+1, g.order()):
89
                if A[i,j] == 1:
90
                    I.append(x[i]+x[j]-1)
91
                    #
92
                    #endif
93
                #end for ee
94
            #endif
95
        #end for edges
96
    #end for vertices
97

98
    if o==1 and r==1:
99
            # establish the ring containing the ideal (this will be returned)
100
        P = PolynomialRing(CC, g.order(), 'x', order="deglex") # over the rationals
101
        x = P.gens();
102
            #print str(type(P))
103
        I = list(); # create an empty list
104
            #print "Constructing boolean polynomials, one per edge"
105
            # for each edge, create the polynomial eij^2 - eij
106
        for i in range(0, g.order()): # for each vertex in the graph
107
            I.append(x[i]^2-x[i])
108
            for j in range(i+1, g.order()):
109
                if A[i,j] == 1:
110
                    I.append(x[i]+x[j]-1)
111
                    #
112
                    #endif
113
                #end for ee
114
            #endif
115
        #end for edges
116
    #end for vertices
117
            
118
    if o==2 and r==0:
119
            # establish the ring containing the ideal (this will be returned)
120
            # number of variables is number of edges
121
        P = PolynomialRing(FiniteField(2), g.order(), 'x', order="degrevlex") # over F2
122
        x = P.gens();
123
            #print str(type(P))
124
        I = list(); # create an empty list
125
            #print "Constructing boolean polynomials, one per edge"
126
            # for each edge, create the polynomial eij^2 - eij
127
        for i in range(0, g.order()): # for each vertex in the graph
128
            I.append(x[i]^2-x[i])
129
            for j in range(i+1, g.order()):
130
                if A[i,j] == 1:
131
                    I.append(x[i]+x[j]-1)
132
                    #
133
                    #endif
134
                #end for ee
135
            #endif
136
        #end for edges
137
    #end for vertices
138

139
    if o==2 and r==1:
140
        P = PolynomialRing(CC, g.order(), 'x', order="degrevlex")
141
        x = P.gens();
142
        print str(type(P))
143
        I = list(); # create an empty list
144
        print("ideal")
145
            #print "Constructing boolean polynomials, one per edge"
146
            # for each edge, create the polynomial eij^2 - eij
147
        for i in range(0, g.order()): # for each vertex in the graph
148
            I.append(x[i]^2-x[i])
149
            for j in range(i+1, g.order()):
150
                if A[i,j] == 1:
151
                    I.append(x[i]+x[j]-1)
152
                    #
153
                    #endif
154
                #end for ee
155
            #endif
156
        #end for edges
157
    #end for vertices
158

159

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