CoCalc -- graph_to_ideal_three

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_v], a polynomial ring over F2 with one variable per vertex
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]^3+1)
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]^2+x[i]*x[j]+x[j]^2)
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(QQ, 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
        for i in range(0, g.order()): # for each vertex in the graph
64
            I.append(x[i]^3-1)
65
            for j in range(i+1, g.order()):
66
                if A[i,j] == 1:
67
                    I.append(x[i]^2+x[i]*x[j]+x[j]^2)
68
                    #
69
                    #endif
70
                #end for ee
71
            #endif
72
        #end for edges
73
    #end for vertices
74

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

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

130
    if o==2 and r==1:
131
        P = PolynomialRing(QQ, g.order(), 'x', order="degrevlex")
132
        x = P.gens();
133
        print str(type(P))
134
        I = list(); # create an empty list
135
        for i in range(0, g.order()): # for each vertex in the graph
136
            I.append(x[i]^3-1)
137
            for j in range(i+1, g.order()):
138
                if A[i,j] == 1:
139
                    I.append(x[i]^2+x[i]*x[j]+x[j]^2)
140
            #print("ideal: ") + str(I)      #
141
                    #endif
142
                #end for ee
143
            #endif
144
        #end for edges
145
    #end for vertices
146

147

148
    # use the "dictionary" method return the variables
149
    return {'P':P, 'I':I}
150
#enddef graph_to_ideal
151