#Beth Bjorkman
#Iowa State University
#April 2020
|
|
URL='https://raw.githubusercontent.com/jephianlin/mr_JG/py2/'
files=['Zq_c.pyx','Zq.py','zero_forcing_64.pyx','zero_forcing_wavefront.pyx','minrank.py', 'inertia.py']
for f in files:
print("Loading %s..."%f);
load(URL+f)
Loading Zq_c.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/15333/tmp_Y1c4e_.pyx..\ . Loading Zq.py... Loading zero_forcing_64.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/15333/tmp_9rwF2T.pyx..\ . Loading zero_forcing_wavefront.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/15333/tmp_sikxe_.pyx..\ . Loading minrank.py... Loading inertia.py... Loading Zq_c.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/15333/tmp_Y1c4e_.pyx... Loading Zq.py... Loading zero_forcing_64.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/15333/tmp_9rwF2T.pyx... Loading zero_forcing_wavefront.pyx... Compiling /home/sageuser/7/.sage/temp/sage.math.iastate.edu/15333/tmp_sikxe_.pyx... Loading minrank.py... Loading inertia.py... |
# Fixed versions of Jephian's code below (with FIX removed) #
###################################################################################
# input: a graph G
# output: a power dominating set of G that achieves the power domination number
def minPowerDominatingSet(G):
V = G.vertices()
for i in range(1,len(V)+1):
S = subsets(V,i)
for s in S:
#print s
if isPowerDominatingSet(G,s):
return s
# input: a graph G
# output: the power domination number of G
def PowerDomNum(G):
V = G.vertices()
for i in range(1,len(V)+1):
S = subsets(V,i)
for s in S:
#print s
if isPowerDominatingSet(G,s):
p=len(s)
return p
# input: a graph G and a subset of its vertices V
# ouput: true/false depending if V is a power dominating set of G
def isPowerDominatingSet(G,V):
N=[]
for i in V:
#print "S=", V
N+=G.neighbors(i)
NVert=uniq(N+list(V))
#print "N closed neighbors", NVert
A=zerosgame(G,NVert)
if len(A)==G.order():
return True
else:
return False
|
|
# krPDS #
###################################################################################
# input: a graph G, integer k>=0
# output: a k-robust power dominating set of G that achieves the krPDS number
def kPowDomSet(G,k):
V=G.vertices()
#print V
powdomnum = PowerDomNum(G)
uppbound = powdomnum*(k+1)
lowbound = k+powdomnum
multilist = V*(k+1)
#print "lowbound: ", lowbound, " uppbound: ", uppbound
for setsize in range(lowbound,uppbound+1):
goodpmus=setsize-k
#print "goodpmus is", goodpmus
PossibleS = list(Subsets(multilist, setsize, submultiset=True)) #all possible multisets for size setsize
for S in PossibleS:
#print "S is ", S
SminusRlist=list(Subsets(S, goodpmus, submultiset=True))
#print "SminusRlist is ", SminusRlist
goodsets=0
for SminusR in SminusRlist:
if isPowerDominatingSet(G,list(uniq(SminusR))):
goodsets+=1
if goodsets==len(SminusRlist):
#print "got one!"
return len(S), S, powdomnum
# Faster Version of My krPDS Code #
###################################################################################
# input: a graph G, integer k>=0, power domination number of the graph, lower bound uses gp(k-1) value directly
# output: a k-robust power dominating set of G that achieves the krPDS number
def FASTkPowDomSet(G,k,powdomnum,gpkminus1):
V=G.vertices()
uppbound = powdomnum*(k+1)
lowbound = gpkminus1+1
multilist = V*(k+1)
#print "lowbound: ", lowbound, " uppbound: ", uppbound
for setsize in range(lowbound,uppbound+1):
goodpmus=setsize-k
#print "goodpmus is", goodpmus
PossibleS = list(Subsets(multilist, setsize, submultiset=True)) #all possible multisets for size setsize
for S in PossibleS:
#print "S is ", S
SminusRlist=list(Subsets(S, goodpmus, submultiset=True))
#print "SminusRlist is ", SminusRlist
goodsets=0
for SminusR in SminusRlist:
if isPowerDominatingSet(G,list(uniq(SminusR))):
goodsets+=1
if goodsets==len(SminusRlist):
#print "got one!"
return len(S), S, powdomnum
|
|
G = graphs.GridGraph([4,4])
G.show()
|
####################### Square Grids ###########################
#Loop is too large for ISU's sage server to handle for given n vales, but this shows what could be done
#for n in range(4,20):
# print "------------------------------"
# print "Grid is ", n, "by",n
# graph=graphs.GridGraph([n,n])
# for k in range(0,13):
# kpowdomnum, S, powdomnum = kPowDomSet(graph,k)
# print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
|
|
####################### Square Grids 3x3 ###########################
n=3
print "Grid is ", n, "by",n
graph=graphs.GridGraph([n,n])
for k in range(0,10):
kpowdomnum, S, powdomnum = kPowDomSet(graph,k)
print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
Grid is 3 by 3 k= 0 powdomnum= 1 gpk= 1 S= [(0, 1)] k= 1 powdomnum= 1 gpk= 2 S= [(0, 1), (0, 1)] k= 2 powdomnum= 1 gpk= 3 S= [(0, 1), (0, 1), (0, 1)] k= 3 powdomnum= 1 gpk= 4 S= [(0, 1), (0, 1), (0, 1), (0, 1)] k= 4 powdomnum= 1 gpk= 5 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 5 powdomnum= 1 gpk= 6 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 6 powdomnum= 1 gpk= 7 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 7 powdomnum= 1 gpk= 8 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 8 powdomnum= 1 gpk= 9 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 9 powdomnum= 1 gpk= 10 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] Grid is 3 by 3 k= 0 powdomnum= 1 gpk= 1 S= [(0, 1)] k= 1 powdomnum= 1 gpk= 2 S= [(0, 1), (0, 1)] k= 2 powdomnum= 1 gpk= 3 S= [(0, 1), (0, 1), (0, 1)] k= 3 powdomnum= 1 gpk= 4 S= [(0, 1), (0, 1), (0, 1), (0, 1)] k= 4 powdomnum= 1 gpk= 5 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 5 powdomnum= 1 gpk= 6 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 6 powdomnum= 1 gpk= 7 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 7 powdomnum= 1 gpk= 8 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 8 powdomnum= 1 gpk= 9 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] k= 9 powdomnum= 1 gpk= 10 S= [(0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1), (0, 1)] |
####################### Square Grids 4x4 ###########################
n=4
print "Grid is ", n, "by",n
graph=graphs.GridGraph([n,n])
for k in range(0,8):
kpowdomnum, S, powdomnum = kPowDomSet(graph,k)
print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
Grid is 4 by 4 k= 0 powdomnum= 2 gpk= 2 S= [(0, 1), (1, 2)] k= 1 powdomnum= 2 gpk= 3 S= [(0, 1), (1, 2), (3, 1)] k= 2 powdomnum= 2 gpk= 4 S= [(0, 1), (1, 2), (3, 1), (2, 2)] k= 3 powdomnum= 2 gpk= 6 S= [(0, 1), (0, 1), (1, 2), (1, 2), (3, 1), (3, 1)] k= 4 powdomnum= 2 gpk= 7 S= [(0, 1), (0, 1), (1, 2), (1, 2), (3, 1), (3, 1), (2, 2)] k= 5 powdomnum= 2 gpk= 8 S= [(0, 1), (0, 1), (1, 2), (1, 2), (3, 1), (3, 1), (2, 2), (2, 2)] k= 6 powdomnum= 2 gpk= 10 S= [(0, 1), (0, 1), (0, 1), (1, 2), (1, 2), (1, 2), (3, 1), (3, 1), (3, 1), (2, 2)] k= 7 powdomnum= 2 gpk= 11 S= [(0, 1), (0, 1), (0, 1), (1, 2), (1, 2), (1, 2), (3, 1), (3, 1), (3, 1), (2, 2), (2, 2)] Grid is 4 by 4 k= 0 powdomnum= 2 gpk= 2 S= [(0, 1), (1, 2)] k= 1 powdomnum= 2 gpk= 3 S= [(0, 1), (1, 2), (3, 1)] k= 2 powdomnum= 2 gpk= 4 S= [(0, 1), (1, 2), (3, 1), (2, 2)] k= 3 powdomnum= 2 gpk= 6 S= [(0, 1), (0, 1), (1, 2), (1, 2), (3, 1), (3, 1)] k= 4 powdomnum= 2 gpk= 7 S= [(0, 1), (0, 1), (1, 2), (1, 2), (3, 1), (3, 1), (2, 2)] k= 5 powdomnum= 2 gpk= 8 S= [(0, 1), (0, 1), (1, 2), (1, 2), (3, 1), (3, 1), (2, 2), (2, 2)] k= 6 powdomnum= 2 gpk= 10 S= [(0, 1), (0, 1), (0, 1), (1, 2), (1, 2), (1, 2), (3, 1), (3, 1), (3, 1), (2, 2)] k= 7 powdomnum= 2 gpk= 11 S= [(0, 1), (0, 1), (0, 1), (1, 2), (1, 2), (1, 2), (3, 1), (3, 1), (3, 1), (2, 2), (2, 2)] |
####################### Square Grids 4x4 ###########################
#Attempted to run to find higher values of k for 4x4 grid, but insufficient memory/time to run on sage cloud
#n=4
#print "Grid is ", n, "by",n
#graph=graphs.GridGraph([n,n])
#for k in range(8,11):
# kpowdomnum, S, powdomnum = kPowDomSet(graph,k)
# print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
|
|
####################### Square Grids 5x5 ###########################
n=5
print "Grid is ", n, "by",n
graph=graphs.GridGraph([n,n])
for k in range(0,4):
kpowdomnum, S, powdomnum = kPowDomSet(graph,k)
print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
Grid is 5 by 5 k= 0 powdomnum= 2 gpk= 2 S= [(1, 3), (2, 1)] k= 1 powdomnum= 2 gpk= 3 S= [(1, 3), (2, 1), (1, 0)] k= 2 powdomnum= 2 gpk= 5 S= [(1, 3), (1, 3), (2, 1), (2, 1), (1, 0)] k= 3 powdomnum= 2 gpk= 6 S= [(1, 3), (1, 3), (2, 1), (2, 1), (1, 0), (1, 0)] Grid is 5 by 5 k= 0 powdomnum= 2 gpk= 2 S= [(1, 3), (2, 1)] k= 1 powdomnum= 2 gpk= 3 S= [(1, 3), (2, 1), (1, 0)] k= 2 powdomnum= 2 gpk= 5 S= [(1, 3), (1, 3), (2, 1), (2, 1), (1, 0)] k= 3 powdomnum= 2 gpk= 6 S= [(1, 3), (1, 3), (2, 1), (2, 1), (1, 0), (1, 0)] |
####################### Square Grids 6x6 ###########################
n=6
print "Grid is ", n, "by",n
graph=graphs.GridGraph([n,n])
for k in range(0,4):
kpowdomnum, S, powdomnum = kPowDomSet(graph,k)
print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
Grid is 6 by 6 k= 0 powdomnum= 2 gpk= 2 S= [(1, 3), (2, 1)] k= 1 powdomnum= 2 gpk= 4 S= [(1, 3), (1, 3), (2, 1), (2, 1)] k= 2 powdomnum= 2 gpk= 5 S= [(1, 3), (5, 4), (1, 2), (3, 3), (1, 5)] k= 3 powdomnum= 2 gpk= 7 S= [(1, 3), (1, 3), (5, 4), (2, 1), (1, 2), (3, 3), (1, 5)] Grid is 6 by 6 k= 0 powdomnum= 2 gpk= 2 S= [(1, 3), (2, 1)] k= 1 powdomnum= 2 gpk= 4 S= [(1, 3), (1, 3), (2, 1), (2, 1)] k= 2 powdomnum= 2 gpk= 5 S= [(1, 3), (5, 4), (1, 2), (3, 3), (1, 5)] k= 3 powdomnum= 2 gpk= 7 S= [(1, 3), (1, 3), (5, 4), (2, 1), (1, 2), (3, 3), (1, 5)] |
####################### Square Grids 6x6 ###########################
#Running 6 again with FASTkPowDomSet instead
#n=6
#print "Grid is ", n, "by",n
#graph=graphs.GridGraph([n,n])
#powdomnumber= PowerDomNum(graph)
#kpowdomnumlist=[powdomnumber]
#for k in range(0,4):
# kpowdomnum, S, powdomnum = FASTkPowDomSet(graph,k,powdomnumber,kpowdomnumlist[-1])
# print "k=",k, "powdomnum=", powdomnum, "gpk=", kpowdomnum, "S=", S
# kpowdomnumlist.append(kpowdomnum)
|
|
|
|