VariationsOfZsap

###A random algorithm is implemented for finding the value of Zsap's. import random #if this line is not included, then change random.choice to choice. 

###Codes for all variations of Zsap. def Z_game(g,B,ban=[]): """ Input: g: a simple graph B: a set of initial blue vertices ban: a set of banned vertices Output: return the derived set under the regular CCR-Z. Note: vertices in ban cannot make a force, but are still white neighbors if white. """ V=g.vertices(); white_neighbors={}; #a dictionary with the structure {v: list of white neighbors} white_numbers={}; #a dictionary with the structure {v: number of white neighbors} for v in V: nbh=g.neighbors(v); for b in B: try: nbh.remove(b); except ValueError: pass; white_neighbors[v]=nbh; white_numbers[v]=len(nbh); queue=copy(B); #queue stores list of vertices that can possibly make a force derived_set=copy(B); #derived_set stores the set of blue vertices whole_loop=True; while whole_loop: #keep searching if queue!=[] try: v=queue[0]; queue.remove(v); if v not in ban and white_numbers[v]==1: u=white_neighbors[v][0]; #the only white neighbor derived_set.append(u); #make the force #update white_numbers, white_neighbors, and queue if white_numbers[u]==1: queue.append(u); u_nbr=g.neighbors(u); for w in u_nbr: white_neighbors[w].remove(u); white_numbers[w]+=-1; if w in derived_set and white_numbers[w]==1: queue.append(w); except IndexError: whole_loop=False; return derived_set; def Zell_game(g,B,ban=[]): ##every non-isolated vertex can force itself if no other white neighbors. """ Input: g: a simple graph B: a set of initial blue vertices ban: a set of banned vertices Output: return the derived set under the CCR-Zell. That is, in addition to CCR-Z, every non-isolated vertex can force itself if no other white neighbors. Note: vertices in ban cannot make a force, but are still white neighbors if white. """ #Build h from g by deleting all isolated vertices, # since they are not going to change the outcome. h=g.copy(); for v in g.vertices(): if h.degree(v)==0: h.delete_vertex(v); V=h.vertices(); white_neighbors={}; #a dictionary with the structure {v: list of white closed neighbors} white_numbers={}; #a dictionary with the structure {v: number of white closed neighbors} for v in V: nbh=h.neighbors(v); nbh.append(v); for b in B: try: nbh.remove(b); except ValueError: pass; white_neighbors[v]=nbh; white_numbers[v]=len(nbh); queue=copy(V); #queue stores list of vertices that can possibly make a force derived_set=copy(B); #derived_set stores the set of blue vertices whole_loop=True; while whole_loop: #keep searching if queue!=[] try: v=queue[0]; queue.remove(v); if v not in ban and white_numbers[v]==1: u=white_neighbors[v][0]; #the only white neighbor derived_set.append(u); #make the force #update white_numbers, white_neighbors, and queue u_nbr=h.neighbors(u); u_nbr.append(u); for w in u_nbr: white_neighbors[w].remove(u); white_numbers[w]+=-1; if white_numbers[w]==1: queue.append(w); except IndexError: whole_loop=False; return derived_set; def Zplus_game(g,B): """ Input: g: a simple graph B: a set of initial blue vertices Output: return the derived set under the CCR-Zplus. That is, apply CCR-Z to each white branch. Note: the banned set is not implemented, since Zvcoc has no Zplus version. """ white_graph=g.copy(); #recording the induced subgraph on white derived_set=copy(B); #derived_set stores the set of blue vertices for b in derived_set: white_graph.delete_vertex(b); whole_loop=True; while whole_loop: whole_loop=False; #open again only when something found. whole_extra_B=[]; #extra blue vertices found in this round partition=white_graph.connected_components(); for com in partition: considered_set=copy(com); for v in derived_set: considered_set.append(v); considered_graph=g.subgraph(considered_set); #this is a white branch extra_B=Z_game(considered_graph,derived_set); #apply Z_game to this white branch for v in derived_set: extra_B.remove(v); for v in extra_B: whole_loop=True; #something found, open whole_loop whole_extra_B.append(v); #update new derived_set and new white_graph. for v in whole_extra_B: derived_set.append(v); white_graph.delete_vertex(v); return derived_set; def Zsap_game(g,B,rule="CCRZ",oc_rule=False,banned_dict={}): """ Input: g: a simple graph B: a set of initial blue non-edges rule: rule that appplies - "CCRZ", "CCRZell", or "CCRZplus" oc_rule: if the odd cycle rule applies - True or False banned_dict: a dictionary with structure {v: banned vertices in the local game l(g,v,rule)} **Usually called by find_Zsap when get_value="vertex". Output: return the derived set of the SAP zero forcing game through the CCRZsap^rule. """ active={}; #for each vertex i, assign a value of 1,0. #1 means l(g,i) can possibly make a force, while 0 means that is impossible. V=g.vertices(); for v in V: active[v]=1; #complete banned_dict by empty sets for v in V: if v not in banned_dict.keys(): banned_dict[v]=[]; queue=[v for v in V] #vertices i such that its local game is still active derived_set=copy(B); #derived_set stores the set of blue non-edges ####### #the whole_loop contains two sub-loops: regular_loop and oc_loop # regular_loop go make all possible forces without the odd cycle rule # oc_rule make all possible forces with only the odd cycle rule #whole_loop stops when nothing is found in both sub-loops #if oc_rule=False, then whole_loop will run only once. ####### whole_loop=True; while whole_loop: whole_loop=False; #open again only when something found, either in regular_loop or oc_loop. regular_loop=True; while regular_loop: try: u=queue[0]; #starting from the second whloe loop, queue is given by oc loop. queue.remove(u); if active[u]==1: #consider the local game l(g,u,rule) #local_B contains all the neighbors of u, u itself, and all blue non-neighbor of u #make all possible forces in this local game local_B=g.neighbors(u); local_B.append(u); for v in V: if (u,v) in derived_set or (v,u) in derived_set: local_B.append(v); if rule=="CCRZ": extra_B=list(Z_game(g,local_B,banned_dict[u])); if rule=="CCRZell": extra_B=list(Zell_game(g,local_B,banned_dict[u])); if rule=="CCRZplus": extra_B=list(Zplus_game(g,local_B)); for v in local_B: extra_B.remove(v); for v in extra_B: derived_set.append((u,v)); active[v]=1; queue.append(v); whole_loop=True; #something found, open whole_loop active[u]=0; except IndexError: regular_loop=False; if oc_rule: oc_loop=True; white_graph=g.complement().copy(); for e in derived_set: white_graph.delete_edge(e); for v in V: GNv=white_graph.subgraph(g.neighbors(v)); #The induced subgraph on N(v) of white_graph for C in GNv.connected_components_subgraphs(): deg=C.degree_sequence(); if min(deg)==2 and max(deg)==2 and C.order()%2==1: #That is, if C is an odd cycle whole_loop=True; #something found, open whole_loop for e in C.edges(labels=False): derived_set.append(e); white_graph.delete_edge(e); for v in C.vertices(): queue.append(v); active[v]=1; else: whole_loop=False; return derived_set; def find_Zsap(g,rule="CCRZ",oc_rule=False,get_value=False): """ Input: g: a simple graph rule: rule that appplies - "CCRZ", "CCRZell", or "CCRZplus" oc_rule: if the odd cycle rule applies - True or False get_value: False, "edge", or "vertex". Output: Return Zsap according the choice of get_value. Here oc_rule can be equipped or not, and the rule also varies. If get_value=False, then return True or False depending on Zsap=0 or not. (polynomial-time). If get_value="edge", then return Zsap. If get_value="vertex", then return Zoc. ** rule="CCRZplus" and get_value="vertex" is not compatable, since Zvc-oc^plus is not defined. """ mbar=g.complement().size(); #number of non-edges if get_value==False: #only check if [] a Zsap zero forcing set derived_set=Zsap_game(g,[],rule,oc_rule); if mbar==len(derived_set): return True; else: return False; if get_value=="edge": #number of non-edges grows up rapidly Ebar=g.complement().edges(labels=False); mbar=len(Ebar); lbd=-1; ubd=mbar; while ubd-lbd>=2: #apply random algorithm; guess=random.choice(range(lbd+1,ubd)); #take an interior point in [lbd,ubd]; found=False; for B in Combinations(Ebar,guess): if mbar==len(Zsap_game(g,B,rule,oc_rule)): found=True; break; if found: ubd=guess; else: lbd=guess; return ubd; if get_value=="vertex": gbar=g.complement(); Ebar=gbar.edges(labels=False); V=g.vertices(); mbar=len(Ebar); n=g.order(); lbd=-1; ubd=n; while ubd-lbd>=2: #apply random algorithm; guess=random.choice(range(lbd+1,ubd)); #take an interior point in [lbd,ubd]; found=False; for sub in Combinations(V,guess): #build initial blue nonedges B; B=[]; for ebar in Ebar: i,j=ebar; if i in sub or j in sub: B.append(ebar); #build banned_dict; banned_dict={v:[] for v in V}; for j in sub: ##(i:j -> k) is banned if j is in sub and {i,j} is nonedge. for i in gbar.neighbors(j): banned_dict[i].append(j); if mbar==len(Zsap_game(g,B,rule,oc_rule,banned_dict)): found=True; break; if found: ubd=guess; else: lbd=guess; return ubd; 

#Code for the data in the Table of all parameters. #Computing the number of graphs with beta=0, where beta is one type of Zsap variations. print "n: number of vertices"; print "a0: number of connected graphs on n vertices"; print "a1: number of connected graphs on n vertices with Zsap=0"; print "a2: number of connected graphs on n vertices with Zsap^ell=0"; print "a3: number of connected graphs on n vertices with Zsap^plus=0"; print "---"; print "n","[a1/a0,a2/a0,a3/a0]"; print " [sap, ell, +]"; data={} proportion={}; for n in range(1,11): all_counter=0; Zsap_counter=0; Zsapell_counter=0; Zsapplus_counter=0; for g in graphs.nauty_geng("%s -c"%n): all_counter+=1; if find_Zsap(g,oc_rule=True): Zsap_counter+=1; if find_Zsap(g,"CCRZell",oc_rule=True): Zsapell_counter+=1; if find_Zsap(g,"CCRZplus",oc_rule=True): Zsapplus_counter+=1; data[n]=[all_counter,Zsap_counter,Zsapell_counter,Zsapplus_counter]; all=data[n][0] proportion[n]=[]; for i in range(1,4): proportion[n].append(N(data[n][i]/all,digits=2)) print n,proportion[n]; print "---" print "n","[a0,a1,a2,a3]"; for n in range(1,11): print n,data[n]; ### Expected outcome: ### #n: number of vertices #a0: number of connected graphs on n vertices #a1: number of connected graphs on n vertices with Zsap=0 #a2: number of connected graphs on n vertices with Zsap^ell=0 #a3: number of connected graphs on n vertices with Zsap^plus=0 #--- #n [a1/a0,a2/a0,a3/a0] # [sap, ell, +] #1 [1.0, 1.0, 1.0] #2 [1.0, 1.0, 1.0] #3 [1.0, 1.0, 1.0] #4 [1.0, 1.0, 1.0] #5 [0.86, 0.95, 0.95] #6 [0.79, 0.92, 0.92] #7 [0.74, 0.89, 0.89] #8 [0.73, 0.88, 0.88] #9 [0.76, 0.89, 0.89] #10 [0.79, 0.90, 0.91] #--- #n [a0,a1,a2,a3] #1 [1, 1, 1, 1] #2 [1, 1, 1, 1] #3 [2, 2, 2, 2] #4 [6, 6, 6, 6] #5 [21, 18, 20, 20] #6 [112, 88, 103, 103] #7 [853, 628, 756, 757] #8 [11117, 8164, 9753, 9784] #9 [261080, 197895, 231541, 232580] #10 [11716571, 9242060, 10576775, 10636311] 

n: number of vertices
a0: number of connected graphs on n vertices
a1: number of connected graphs on n vertices with Zsap=0
a2: number of connected graphs on n vertices with Zsap^ell=0
a3: number of connected graphs on n vertices with Zsap^plus=0
---
n [a1/a0,a2/a0,a3/a0]
  [sap, ell,   +]
1 [1.0, 1.0, 1.0]
2 [1.0, 1.0, 1.0]
3 [1.0, 1.0, 1.0]
4 [1.0, 1.0, 1.0]
5 [0.86, 0.95, 0.95]
6 [0.79, 0.92, 0.92]
7 [0.74, 0.89, 0.89]
8 [0.73, 0.88, 0.88]
9 [0.76, 0.89, 0.89]
10 [0.79, 0.90, 0.91]
---
n [a0,a1,a2,a3]
1 [1, 1, 1, 1]
2 [1, 1, 1, 1]
3 [2, 2, 2, 2]
4 [6, 6, 6, 6]
5 [21, 18, 20, 20]
6 [112, 88, 103, 103]
7 [853, 628, 756, 757]
8 [11117, 8164, 9753, 9784]
9 [261080, 197895, 231541, 232580]
10 [11716571, 9242060, 10576775, 10636311]

n: number of vertices
a0: number of connected graphs on n vertices
a1: number of connected graphs on n vertices with Zsap=0
a2: number of connected graphs on n vertices with Zsap^ell=0
a3: number of connected graphs on n vertices with Zsap^plus=0
---
n [a1/a0,a2/a0,a3/a0]
  [sap, ell,   +]
1 [1.0, 1.0, 1.0]
2 [1.0, 1.0, 1.0]
3 [1.0, 1.0, 1.0]
4 [1.0, 1.0, 1.0]
5 [0.86, 0.95, 0.95]
6 [0.79, 0.92, 0.92]
7 [0.74, 0.89, 0.89]
8 [0.73, 0.88, 0.88]
9 [0.76, 0.89, 0.89]
10 [0.79, 0.90, 0.91]
---
n [a0,a1,a2,a3]
1 [1, 1, 1, 1]
2 [1, 1, 1, 1]
3 [2, 2, 2, 2]
4 [6, 6, 6, 6]
5 [21, 18, 20, 20]
6 [112, 88, 103, 103]
7 [853, 628, 756, 757]
8 [11117, 8164, 9753, 9784]
9 [261080, 197895, 231541, 232580]
10 [11716571, 9242060, 10576775, 10636311]

###Back up for data and proportion databk={1: [1, 1, 1, 1], 2: [1, 1, 1, 1], 3: [2, 2, 2, 2], 4: [6, 6, 6, 6], 5: [21, 18, 20, 20], 6: [112, 88, 103, 103], 7: [853, 628, 756, 757], 8: [11117, 8164, 9753, 9784], 9: [261080, 197895, 231541, 232580], 10: [11716571, 9242060, 10576775, 10636311]}; proportionbk={1: [1.0, 1.0, 1.0], 2: [1.0, 1.0, 1.0], 3: [1.0, 1.0, 1.0], 4: [1.0, 1.0, 1.0], 5: [0.86, 0.95, 0.95], 6: [0.79, 0.92, 0.92], 7: [0.74, 0.89, 0.89], 8: [0.73, 0.88, 0.88], 9: [0.76, 0.89, 0.89], 10: [0.79, 0.90, 0.91]} 

###Build function to confirm xi(G)=ZFloor(G) for |G|<=7. ###Miscellaneous functions: get_Z, find_ZFloor, has_minor, NoT3. def get_Z(g): """ Input: g: a simple graph Output: return the value of the conventional zero forcing number Z(g). """ V=g.vertices(); n=g.order(); lbd=-1; ubd=n; while ubd-lbd>=2: #apply random algorithm; guess=random.choice(range(lbd+1,ubd)); #take an interior point in [lbd,ubd]; found=False; for sub in Combinations(V,guess): if n==len(Z_game(g,sub)): found=True; break; if found: ubd=guess; else: lbd=guess; return ubd; def ZFloor_game(g,done,act,token): """ Input: g: a simple graph done: list of blue vertices that made their force (they shouldn't have white neighbors) act: list of blue vertices that make no force yet token: number of "free" blue vertices that can make a hop Output: if "act" together with "token" number of free blue vertices is a zero forcing set, then return True. Otherwise, return False. **ZFloor_game(g,[],[],k) is returning if ZFloor(g)<=k or not. """ #recursive algorithm is implemented, so each graph and each list should be copied h=g.copy() this_done=[]; this_act=[]; for v in done: h.delete_vertex(v); this_done.append(v); for v in act: this_act.append(v); #delete every edges between this_act. for u,w in Combinations(this_act,2): h.delete_edge(u,w); #Do one round of propagation according to CCR-Z again=True; while again: again=False; for v in this_act: if h.degree(v)==1: #this vertex can make CCR-Z. After that it is done, and cannot make a hope. u=h.neighbors(v)[0]; this_act.append(u); this_act.remove(v); this_done.append(v); h.delete_vertex(v); for w in this_act: h.delete_edge(u,w); again=True; break; if h.degree(v)==0: #this vertex can make a hop. token+1, delete it from h, and add it to done. token+=1; this_act.remove(v); this_done.append(v); h.delete_vertex(v); again=True; #When the while loop is done, all token are collected, and all vertices in act cannot make a force. if h.order()==0: return True; if h.order()!=0 and token==0: return False; #Find white set. And do recursion. white=h.vertices(); for v in this_act: white.remove(v); if token>=len(white): return True; else: for new_act in Combinations(white,token): #try all possible way to put the tokens if ZFloor_game(g,this_done,this_act+new_act,0)==True: return True; return False; def find_ZFloor(g): """ Input: g: a simple graph Output: return the value of ZFloor(g). """ ZF=g.order()-1; if ZF<0: #define ZFloor(null graph)=0 return ZF+1; try_lower=True; while try_lower: try_lower=False; if ZFloor_game(g,[],[],ZF)==True: try_lower=True; ZF+=-1; return ZF+1; ###T3Family, the forbidden graphs for xi(G)<=2. T3FamilyString=['C~', 'DFw','EBnW','F@QZo','G?Gisg','H??@qiK'] T3Family=[Graph(stg) for stg in T3FamilyString]; ## The code for has_minor comes from http://ask.sagemath.org/question/ ## 8112/graph-minor-code-too-slow-in-certain-situations-sage-46/ def has_minor(G, H): #return if G has a H minor or not. try: m = G.minor(H) return True except ValueError: return False def NoT3(g): #return True if g has a T3 minor. This means xi(G)>=3. #otherwise, return False. This means xi(G)<=2. ###usually SUPER slow... for t in T3Family: if has_minor(g,t): return True; return False; 

###According to the order (time complexity), check if one of the following cases applies: ### - Zsapoc(G)=0; ### - G is a tree; ### - ZFloor(G)=M(G)-Zvcoc(G); ### - ZFloor(G)=Hadwiger number-1; ### - ZFloor(G)=3 and G has no T3 family; print "n: number of vertices"; print "all: number of connected graphs on n vertices"; print "categorized: number of graphs that fall into at least one of the categories"; print "ai=number of graphs that fall into the i-th category but not any of the previous categories" print "---"; print "n","[all, categorized]","categorized/all","[a1,a2,a3,a4,a5]"; remainder=[] for n in range(1,8): counter=0; Zsap_counter=0; extra_trees=0; extra_Zvcoc=0; extra_Knminor=0; extra_T3=0; for g in graphs.nauty_geng("%s -c"%n): counter+=1; if find_Zsap(g,oc_rule=True): Zsap_counter+=1; elif g.is_tree(): extra_trees+=1; else: zfloor=find_ZFloor(g); M=get_Z(g); #Up to seven vertices, M(G)=Z(G) zvcoc=find_Zsap(g,oc_rule=True,get_value="vertex"); if zfloor==M-zvcoc: extra_Zvcoc+=1; elif has_minor(g,graphs.CompleteGraph(zfloor+1)): extra_Knminor+=1; elif zfloor==3 and NoT3(g)==True: extra_T3+=1; else: remainder.append(g.canonical_label().graph6_string()); sshow(g); sum=Zsap_counter+extra_trees+extra_Zvcoc+extra_Knminor+extra_T3; print n,[counter,sum],N(sum/counter,digits=2),[Zsap_counter,extra_trees,extra_Zvcoc,extra_Knminor,extra_T3]; print "Graphs that doesn't fall into any of the five categories",remainder; ### Expected outcome: ### #n: number of vertices #all: number of connected graphs on n vertices #categorized: number of graphs that fall into at least one of the #categories #ai=number of graphs that fall into the i-th category but not any of the #previous categories #--- #n [all, categorized] categorized/all [a1,a2,a3,a4,a5] #1 [1, 1] 1.0 [1, 0, 0, 0, 0] #2 [1, 1] 1.0 [1, 0, 0, 0, 0] #3 [2, 2] 1.0 [2, 0, 0, 0, 0] #4 [6, 6] 1.0 [6, 0, 0, 0, 0] #5 [21, 21] 1.0 [18, 1, 1, 1, 0] #6 [112, 112] 1.0 [88, 3, 12, 9, 0] #7 [853, 853] 1.0 [628, 7, 125, 78, 15] #Graphs that doesn't fall into any of the five categories [] 

n: number of vertices
all: number of connected graphs on n vertices
categorized: number of graphs that fall into at least one of the
categories
ai=number of graphs that fall into the i-th category but not any of the
previous categories
---
n [all, categorized] categorized/all [a1,a2,a3,a4,a5]
1 [1, 1] 1.0 [1, 0, 0, 0, 0]
2 [1, 1] 1.0 [1, 0, 0, 0, 0]
3 [2, 2] 1.0 [2, 0, 0, 0, 0]
4 [6, 6] 1.0 [6, 0, 0, 0, 0]
5 [21, 21] 1.0 [18, 1, 1, 1, 0]
6 [112, 112] 1.0 [88, 3, 12, 9, 0]
7 [853, 853] 1.0 [628, 7, 125, 78, 15]
Graphs that doesn't fall into any of the five categories []

n: number of vertices
all: number of connected graphs on n vertices
categorized: number of graphs that fall into at least one of the categories
ai=number of graphs that fall into the i-th category but not any of the previous categories
---
n [all, categorized] categorized/all [a1,a2,a3,a4,a5]
1 [1, 1] 1.0 [1, 0, 0, 0, 0]
2 [1, 1] 1.0 [1, 0, 0, 0, 0]
3 [2, 2] 1.0 [2, 0, 0, 0, 0]
4 [6, 6] 1.0 [6, 0, 0, 0, 0]
5 [21, 21] 1.0 [18, 1, 1, 1, 0]
6 [112, 112] 1.0 [88, 3, 12, 9, 0]
7 [853, 853] 1.0 [628, 7, 125, 78, 15]
Graphs that doesn't fall into any of the five categories []