ZeroForcingReconfiguration

404 days ago by hogben

#################################### # This Sage worksheet is written by Bryan Curtis and Leslie Hogben hogben@aimath.org # using code written by numerous other people. # The focus of this worksheet is token addition and removal (TAR) reconfiguration graphs # for zero forcing in support of the paper # Isomorphisms and properties of TAR reconfiguration graphs for zero forcing and other $X$-set parameters # by # Novi H. Bong, Joshua Carlson, Bryan Curtis, Ruth Haas, and Leslie Hogben # # To run computations, you must first enter the function F- cells at the end of this file ################################### 
       
################################### # Example 3.1: Graphs G and H have same zero forcing polynomial but Z-TAR(G) is not isomorphic tp Z-TAR(H). ################################### 
       
G=Graph("Epo_") G.relabel([1,2,3,4,5,6]) show(G) 
       
H=Graph("Ez[W") H.relabel([1,2,3,4,5,6]) show(H) 
       
print ZFS_poly(G), ZFS_poly(H) 
       
[0, 0, 8, 13, 6, 1] [0, 0, 8, 13, 6, 1]
[0, 0, 8, 13, 6, 1] [0, 0, 8, 13, 6, 1]
ZF_min_sets(G) 
       
[{1, 2, 4},
 {1, 2, 6},
 {1, 4, 5},
 {1, 5, 6},
 {2, 4, 5},
 {2, 4, 6},
 {2, 5, 6},
 {4, 5, 6}]
[{1, 2, 4},
 {1, 2, 6},
 {1, 4, 5},
 {1, 5, 6},
 {2, 4, 5},
 {2, 4, 6},
 {2, 5, 6},
 {4, 5, 6}]
ZF_min_sets(H) 
       
[{1, 2, 4},
 {1, 2, 5},
 {1, 3, 4},
 {1, 3, 5},
 {2, 4, 6},
 {2, 5, 6},
 {3, 4, 6},
 {3, 5, 6},
 {2, 3, 4, 5}]
[{1, 2, 4},
 {1, 2, 5},
 {1, 3, 4},
 {1, 3, 5},
 {2, 4, 6},
 {2, 5, 6},
 {3, 4, 6},
 {3, 5, 6},
 {2, 3, 4, 5}]
print zbar(G), zbar(H) 
       
3 4
3 4
############################################# # Data for Table 1 ############################################# 
       
nn=2 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
1 1
1 1
n(1/1) 
       
1.00000000000000
1.00000000000000
nn=3 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
2 2
2 2
n(2/2) 
       
1.00000000000000
1.00000000000000
nn=4 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
4 7
4 7
n(4/7) 
       
0.571428571428571
0.571428571428571
nn=5 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
7 23
7 23
n(7/23) 
       
0.304347826086957
0.304347826086957
nn=6 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
34 122
34 122
n(34/122) 
       
0.278688524590164
0.278688524590164
nn=7 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
303 888
303 888
n(303/888) 
       
0.341216216216216
0.341216216216216
nn=8 uq=uni(nn) numb=num_noisol(nn) print uq, numb 
       
5318 11302
5318 11302
n(5318/11302) 
       
0.470536188285259
0.470536188285259
################################### # Example H(2) in Figure 3.2 with Zbar + 1 < z_0. ################################### 
       
h1=graphs.CompleteGraph(4) h2=graphs.CompleteGraph(4) h2.relabel([5,6,7,8]) h1.relabel([1,2,3,4]) h=h1.union(h2) h.add_edges([(1,5),(2,6)]) show(h) 
       
print Z(h), zbar(h) ZF_min_sets(h) 
       
4 4
[{1, 2, 3, 7},
 {1, 2, 3, 8},
 {1, 2, 4, 7},
 {1, 2, 4, 8},
 {1, 3, 4, 7},
 {1, 3, 4, 8},
 {2, 3, 4, 7},
 {2, 3, 4, 8},
 {3, 5, 6, 7},
 {3, 5, 6, 8},
 {3, 5, 7, 8},
 {3, 6, 7, 8},
 {4, 5, 6, 7},
 {4, 5, 6, 8},
 {4, 5, 7, 8},
 {4, 6, 7, 8}]
4 4
[{1, 2, 3, 7},
 {1, 2, 3, 8},
 {1, 2, 4, 7},
 {1, 2, 4, 8},
 {1, 3, 4, 7},
 {1, 3, 4, 8},
 {2, 3, 4, 7},
 {2, 3, 4, 8},
 {3, 5, 6, 7},
 {3, 5, 6, 8},
 {3, 5, 7, 8},
 {3, 6, 7, 8},
 {4, 5, 6, 7},
 {4, 5, 6, 8},
 {4, 5, 7, 8},
 {4, 6, 7, 8}]
targ=TAR_reconfig(h,5) targ.plot() 
       
targ.is_connected() 
       
False
False
targ6=TAR_reconfig(h,6) targ6.is_connected() 
       
True
True
################################### # Example H_2 in Figure 3.3 with underline-z_0 < z_0. ################################### 
       
g=Graph("G~vlTO") show(g) 
       
ZofG=Z(g) ZbarG=zbar(g) print ZofG, ZbarG print TAR_reconfig(g,ZofG).is_connected() print TAR_reconfig(g,ZofG+1).is_connected() print TAR_reconfig(g,ZbarG).is_connected() print TAR_reconfig(g,ZbarG+1).is_connected() 
       
4 6
False
True
False
True
4 6
False
True
False
True
ZF_min_sets(g) 
       
[{0, 2, 3, 6},
 {0, 2, 3, 7},
 {0, 2, 5, 6},
 {0, 2, 5, 7},
 {0, 3, 4, 6},
 {0, 3, 4, 7},
 {0, 4, 5, 6},
 {0, 4, 5, 7},
 {2, 3, 4, 6},
 {2, 3, 4, 7},
 {2, 4, 5, 6},
 {2, 4, 5, 7},
 {1, 2, 3, 5, 6, 7},
 {1, 3, 4, 5, 6, 7}]
[{0, 2, 3, 6},
 {0, 2, 3, 7},
 {0, 2, 5, 6},
 {0, 2, 5, 7},
 {0, 3, 4, 6},
 {0, 3, 4, 7},
 {0, 4, 5, 6},
 {0, 4, 5, 7},
 {2, 3, 4, 6},
 {2, 3, 4, 7},
 {2, 4, 5, 6},
 {2, 4, 5, 7},
 {1, 2, 3, 5, 6, 7},
 {1, 3, 4, 5, 6, 7}]
targ5=TAR_reconfig(g,ZofG+1) targ5.plot() 
       
# Necessarily TAR_reconfig(g,6) is disconnected because new minimal sets are added. 
       
################################### # Example 3.7: Removing one of only two twins may not reduce zero forcing number. ################################### 
       
g=Graph({0:[1,2,3],1:[4,5]}) show(g) 
       
print Z(g) ZF_min_sets(g) 
       
2
[{2, 4}, {2, 5}, {3, 4}, {3, 5}]
2
[{2, 4}, {2, 5}, {3, 4}, {3, 5}]
h=Graph({0:[1,2,3],1:[4]}) show(h) 
       
print Z(h) ZF_min_sets(h) 
       
2
[{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}]
2
[{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}]
# 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/3/.sage/temp/sage.math.iastate.edu/12704/tmp_QfsC8X.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/12704/tmp_FcK93O.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/12704/tmp_R3X6iY.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading Zq_c.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/12704/tmp_QfsC8X.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/12704/tmp_FcK93O.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/12704/tmp_R3X6iY.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-R 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 power dominating set up to size k. def TAR_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 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 #input: A graph G and integer k #output: The TARE PD reconfiguration graph on PDS of size up to k def TARE_reconfig(G,k): # The first part of this code is the same as that given for TAR above. S=ZFS_up_to_size_k(G,k) H=Graph() H.add_vertices(S) 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]) # 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. 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 def TE_reconfig(G,k): S=ZFsets(G,k) #creates a list of all zf sets of size k. 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 
       
#F-Zpoly def ZFS_poly(G): # Bryan Curtis d = order(G) coeff = [len(ZFsets(G,k)) for k in range(1,d+1)] return coeff 
       
#F-unique # The following code finds the number of graphs (with no isol vtxs) with unique reconfiguration graphs # def uni(n): # Store all graphs without isolated vertices to a list: no_isol = [g for g in graphs(n) if min([g.degree(v) for v in g]) >=1] # Create a list of lists - each sublist contains all graphs with the same reconfiguration graph # The first element of each sublist is a copy of the reconfiguration graph (directly corresponding to the second element) unique = [] for g in no_isol: flag = False tar_g = TAR_reconfig(g,n) for h in unique: if tar_g.is_isomorphic(h[0]): h.append(g) flag = True break if not flag: unique.append([tar_g,g]) # Keep only graphs with unique reconfiguration graph: unique = [p for p in unique if len(p) == 2] return len(unique) # Display examples (may want to suppress output) # for g in unique: # g[1].show() # def num_noisol(n): # Store all graphs without isolated vertices to a list: no_isol = [g for g in graphs(n) if min([g.degree(v) for v in g]) >=1] return len(no_isol) 
       
#F-zbar def get_minimal_subsets(sets): sets = sorted(map(set, sets), key=len) minimal_subsets = [] for s in sets: if not any(minimal_subset.issubset(s) for minimal_subset in minimal_subsets): minimal_subsets.append(s) return minimal_subsets # Outputs all minimal zero forcing sets def ZF_min_sets(G): ord = G.order() ZFS = ZFS_up_to_size_k(G,ord) mZFS = get_minimal_subsets(ZFS) return mZFS # Outputs the upper minimal zero forcing number def zbar(G): min_list = ZF_min_sets(G) zb = max(len(x) for x in min_list) return zb