Reconfiguration graph code for zero forcing and power domination

481 days ago by hogben

#################################### # This Sage worksheet was compiled by Leslie Hogben hogben@aimath.org # using code written by numerous other people. # The reconfiuration code was primarily written by Chassidy Bozeman. # The focus of this worksheet is token addition and removal (TAR) and token jumping (TJ) # reconfiguration graphs for zero forcing and power domination. # # To run computations, you must first enter the function F- cells at the beginning ################################### 
       
# Functions 
       
# F-1 load main minimum rank/maximum nullity and zero forcing functions # zero forcing, PSD forcing, and minimum rank code # developed by S. Butler, L. DeLoss, J. Grout, H.T. Hall, J. LaGrange, J.C.-H. Lin,T. McKay, J. Smith, G. Tims # updated and maintained by Jephian C.-H. Lin 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/0/.sage/temp/sage.math.iastate.edu/14931/tmp_KhiRdA.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/0/.sage/temp/sage.math.iastate.edu/14931/tmp_Z_h38G.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/0/.sage/temp/sage.math.iastate.edu/14931/tmp_fV9lOn.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading Zq_c.pyx...
Compiling /home/sageuser/0/.sage/temp/sage.math.iastate.edu/14931/tmp_KhiRdA.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/0/.sage/temp/sage.math.iastate.edu/14931/tmp_Z_h38G.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/0/.sage/temp/sage.math.iastate.edu/14931/tmp_fV9lOn.pyx...
Loading minrank.py...
Loading inertia.py...
# F-2 other zero forcing functions (Leslie Hogben) # # Zero forcing number Z(G) def Z(g): z=len(zero_forcing_set_bruteforce(g)) return z # # All zero forcing sets of G of size k # input: a graph G and a positive integer k # output: a list of all zero forcing sets G of size k def ZFsets(G,k): ord=G.order() V = G.vertices() S = subsets(V,k) ZFS=[] for s in S: A=zerosgame(G,s) if len(A)==ord: ZFS.append(s) return ZFS 
       
# F-R1 Zero Forcing Reconfiguration graph functions # adapted from code by Chassidy Bozeman # input: A graph G and a positive integer k # output: All zero forcing sets G up to size k def ZFS_up_to_size_k(G,k): S=[] for i in [Z(G)..k]: ZFS_size_i=ZFsets(G,i) S=S+ZFS_size_i return S # input: A graph G and a positive integer k # output: The TAR ZF reconfiguration graph on zero forcing sets up to size k. def ZTAR_reconfig(G,k): S=ZFS_up_to_size_k(G,k) # creates a list of all zf sets up to size k. H=Graph() # creates empty graph H.add_vertices(S) # add zf sets up to size k to the vertices of H # The following part determines if the size of two zero forcing sets differ # by one and if one is a subset of the other. If both are true, an edge is added. for i in range(len(S)): for j in range(i+1, len(S)): if len(S[i])-len(S[j]) in {-1,1}: if set(S[i]).issubset(set(S[j])): H.add_edge(S[i],S[j]) else: if set(S[j]).issubset(set(S[i])): H.add_edge(S[i],S[j]) return H #input: A graph G #output: The TE=TJ Z reconfiguration graph on zero forcing of size Z(G) def ZTE_reconfig(G): z=Z(G) S=ZFsets(G,z) #creates a list of all zf sets of size k. H=Graph() #creates empty graph H.add_vertices(S) # add minimum zero forcing sets to the vertices of H # The part below is for token exchange (toke jumping). If two zero forcing sets have the # same size and they differ by one element, then an edge is added between them. for i in range(len(S)): for j in range(i+1, len(S)): if len(S[i])==len(S[j]): if len(set(S[i]).difference(set(S[j])))==1: H.add_edge(S[i],S[j]) return H 
       
# F-2 Power domination functions # by Brian Wissman # input: a graph G and a subset of its vertices V # output: true/false depending if V is a power dominating set of G def isPowerDominatingSet(G,V): N=[] for i in V: N+=G.neighbors(i) NVert=uniq(N+list(V)) A=zerosgame(G,NVert) if len(A)==G.order(): return True else: return False # 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: if isPowerDominatingSet(G,s): return s # input: a graph G # output: the power domination number of G def PowerDom(G): V = G.vertices() for i in range(1,len(V)+1): S = subsets(V,i) for s in S: if isPowerDominatingSet(G,s): p=len(s) return p 
       
# F-3 power dominating sets # input: a graph G and a positive integer k # output: a list of all power dominating sets G of size k def PDsets(G,k): ord=G.order() V = G.vertices() S = subsets(V,k) PDS=[] for s in S: if isPowerDominatingSet(G,s): PDS.append(s) return PDS 
       
# F-R2 Token Addition and TAR and # by Chassidy Bozeman edited by Leslie Hogben # input: A graph G and a positive integer k #output: All power dominating sets G up to size k def PDS_up_to_size_k(G,k): S=[] for i in range(1,k+1): PDS_size_i=PDsets(G,i) S=S+PDS_size_i return S #input: A graph G and a positive integer k #output: The TAR PD reconfiguration graph on power dominating set up to size k. def PDTAR_reconfig(G,k): S=PDS_up_to_size_k(G,k) #creates a list of all dominating sets up to size k. H=Graph() #creates empty graph H.add_vertices(S) # add power dom sets up to size k to the vertices of H # The following part determines if the size of two power dominating sets differ # by one and if one is a subset of the other. If both are true, an edge is added. for i in range(len(S)): for j in range(i+1, len(S)): if len(S[i])-len(S[j]) in {-1,1}: if set(S[i]).issubset(set(S[j])): H.add_edge(S[i],S[j]) else: if set(S[j]).issubset(set(S[i])): H.add_edge(S[i],S[j]) return H # Token Jumping = Token Exchange #input: A graph G and integer k #output: The TAR PD reconfiguration graph on PDS of size up to k def PDTE_reconfig(G): p=PowerDom(G) S=PDsets(G,p) #creates a list of all dominating sets of size p=PD(G). H=Graph() #creates empty graph H.add_vertices(S) # add power dom sets of size k to the vertices of H # The part below is for token exchange. If two power dominating sets have the # same size and they differ by one element, then an edge is added between them. for i in range(len(S)): for j in range(i+1, len(S)): if len(S[i])==len(S[j]): if len(set(S[i]).difference(set(S[j])))==1: H.add_edge(S[i],S[j]) return H 
       
# Examples 
       
# star graph 
       
K13=graphs.CompleteBipartiteGraph(1,3) show(K13) 
       
# zero forcing token exchange 
       
g=ZTE_reconfig(K13) show(g) 
       
g=ZTAR_reconfig(K13,4) show(g) 
       
# power domination token addition and removal 
       
g=PDTAR_reconfig(K13,2) show(g) 
       
g=PDTAR_reconfig(K13,3) show(g) 
       
g=PDTAR_reconfig(K13,4) show(g) 
       
# Path graph 
       
P5=graphs.PathGraph(5) show(P5) 
       
g=ZTAR_reconfig(P5,2) show(g) 
       
g=ZTAR_reconfig(P5,3) show(g) 
       
g=PDTAR_reconfig(P5,2) show(g)