Robust PD - Grid Graphs

1674 days ago by bjorkman

#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)