#All positive edges in columns have a 1 and -1 entry. Standardize makes any
#positive edge column have the 1 come before the -1 when reading the column
#top to bottom. All negative edges in columns have two 1 entries or two -1 entries.
#Standardize makes any negative edge column have two 1s. A negative loops has
#one 1 or -1 entry in its edge column. Standardize makes all negative loop
#columns have one 1. Standardizing our edges into one convention makes finding a
#positive edge to delete-contract more efficient.
def standardize(G):
G_rows=G.nrows()
G_cols=G.ncols()
for j in range(0,G_cols):
for i in range(0,G_rows):
if G[i,j] == 1:
break
if G[i,j] == -1:
G.add_multiple_of_column(j,j,-2)
break
return G
#If there is a mutiedge in the Peterson graph, meaning a column is repeated, then
#delete the column and return a new incidence matrix.
def check(Gin):
G=standardize(Gin) #
G_cols=G.ncols()
G_rows=G.nrows()
l=G.columns()
for i in range(0,G_cols-1):
for j in range(i+1,G_cols):
if G.column(G_cols-1-i)== G.column(G_cols-1-j):
l.pop(G_cols-1-i)
break
B=matrix(l)
C=B.transpose()
return C
#Returns an ordered pair of the incidence matrix of the graph with an edge
#deleted and the incidence matrix of the graph with an edge contracted.
def DC(G):
rows=G.nrows()
cols=G.ncols()
#If a single edge, return an empty graph with the same number of vertices for
#the graph with the edge deleted. Return an empty graph with one
#less vertex for the graph with the edge contracted.
if cols == 1:
C=matrix(QQ,rows,1,range(0))
H=matrix(QQ,rows-1,1,range(0))
return (C,H)
#Else, find the first positive edge in the matrix when reading the matrix
#from left to right. Delete and contract this edge returning new incidence matrices.
else:
j=0
#Increment through the columsn looking for a positive edge
while j