# This worksheet is Appendix 1 of
# "Using Markov chains to determine expected propagation time for probabilistic zero forcing"
# by Yu Chan, Emelie Curl, Jesse Geneson, Leslie Hogben, and Kevin Liu
# This worksheet is written by Yu Chan
# It contains the code for computing the expected propagation time of
# all graphs of orders 4, 5, 6 and 7
|
|
Code
# to run, enter the next two cells
|
|
## PZFBaseGraph ##
class PZFBaseGraph(Graph):
def __init__(self, *args, **kwargs):
blue_set=[];
if kwargs.has_key('blue_set'):
blue_set=kwargs.pop('blue_set')
super(PZFBaseGraph,self).__init__(*args, **kwargs)
self.set_blue_vertices(blue_set)
def set_blue_vertices(self, blue_set):
self.set_vertices(dict([(b,'blue') for b in blue_set]))
self.set_vertices(dict([(w,'white') for w in self.vertices() if w not in blue_set]))
def get_blue_vertices(self):
return sorted([v for v, key in self.get_vertices().items() if key=='blue'])
def get_white_vertices(self):
return sorted([v for v, key in self.get_vertices().items() if key!='blue'])
def get_blue_neighbors(self):
return sorted([w for w in self.get_white_vertices() if \
w in flatten([self.neighbors(u) for u in self.get_blue_vertices()],max_level=1)
])
def Pr(self, u, w=None):
if w==None:
return 1-prod([1-self.Pr(v,u) for v in self.neighbors(u) if v in self.get_blue_vertices()])
if w in self.get_blue_vertices():
return 1
if u in self.get_white_vertices():
return 0
if w not in self.neighbors(u):
return 0
return len([v for v in self.get_blue_vertices() if v in self.neighbors(u) or v==u])/Rational(self.degree(u))
def get_next_state(self):
S=set(self.get_blue_neighbors())
return [[sorted(s), product(flatten([map(lambda x: self.Pr(x),s),map(lambda x: 1-self.Pr(x),S.difference(s))]))]\
for s in Subsets(S)]
def show(self):
return self.plot(vertex_colors={'blue':self.get_blue_vertices(),'white':self.get_white_vertices()})
## PZFStateGraph ##
class PZFStateGraph(DiGraph):
blue_set=None;base_graph=None
start_state=None;end_state=None
def __init__(self, *args, **kwargs):
super(PZFStateGraph,self).__init__({},weighted=True,loops=True)
blue_set=kwargs.pop('blue_set') if kwargs.has_key('blue_set') else []
base_graph=kwargs.pop('base_graph') if kwargs.has_key('base_graph') else graphs.EmptyGraph()
self.set_base_graph(base_graph,blue_set)
def plot(self, *args, **options): return DiGraph(self).plot(*args, **options)
def show(self, *args, **kwargs): return DiGraph(self).show(*args, **kwargs)
def get_base_graph(self): return self.base_graph
def set_base_graph(self, g, blue_set):
new_state=PZFBaseGraph(g, blue_set=blue_set)
new_state_name=str(new_state.get_blue_vertices())
self.base_graph=new_state
self.start_state=str(new_state.get_blue_vertices())
self.end_state=str(sorted(new_state.vertices()))
self.add_vertex(new_state_name)
self.set_vertex(new_state_name, new_state)
# sort states by the number of blue vertices in their base graph
def legal_sorted(self, v_list): return sorted(v_list, key=lambda x: len(eval(x)))
def get_states(self): return self.legal_sorted(self.vertices())
def get_child_states(self): return [v for v in self.vertices() if self.out_degree(v)==0]
def has_next_step(self): return self.get_child_states()!=[]
def step(self):
new_parent_states=self.get_child_states()
for parent in new_parent_states:
for child, pr in self.get_vertex(parent).get_next_state():
if pr!=0:
new_state=PZFBaseGraph(self.base_graph, blue_set=sorted(flatten([eval(parent),child],max_level=1)))
new_state_name=str(new_state.get_blue_vertices())
self.add_edge(parent,new_state_name,pr)
self.set_vertex(new_state_name,new_state)
self.merge_states()
def add_edge(self, u, v=None, label=None):
if self.has_edge(u,v): super(PZFStateGraph,self).add_edge(u, v,
self.edge_label(u,v)+(label if label!=None else 0))
else: super(PZFStateGraph,self).add_edge(u, v, label)
def merge_states(self):
AutG=self.base_graph.automorphism_group();
child_list=[v for v in self.vertices() if self.out_degree(v)==0]
while len(child_list)!=0:
blue_set=tuple(eval(child_list[0]))
orbit_list=[str(sorted(list(o))) for o in AutG.orbit(blue_set, action='OnSets')]
state_list=[o for o in orbit_list if o in self.vertices()]
# combine isomorphic states by adding their incoming probability
in_edges=self.incoming_edges(state_list)
self.delete_edges(in_edges)
for (u,v,e) in in_edges: self.add_edge(u, state_list[0], e)
self.delete_vertices(state_list[1:])
child_list=filter(lambda x: x not in state_list,child_list)
def get_markov_matrix(self):
while self.has_next_step(): self.step()
sorted_index=map(lambda x: self.vertices().index(x)+1,sorted(self.vertices(),key=lambda x: len(eval(x))))
P=Permutation(sorted_index).to_matrix()
return P^-1*self.weighted_adjacency_matrix()*P
def get_ept(self):
M=self.get_markov_matrix();
n=M.dimensions()[0];
one = matrix(QQ, n, n, lambda i, j: (0 if j!=(n-1) else 1));
return ((M-one-identity_matrix(n))^-1)[0,n-1]+1
## ept ##
def ept(G, blue_set=None):
if blue_set!=None: return PZFStateGraph(base_graph=G, blue_set=blue_set).get_ept()
ept_list=dict([[v, ept(G, {v})] for v in G.vertices()])
min_v=min(ept_list,key=ept_list.get)
return (min_v,ept_list.get(min_v))
|
|
Result
Graph Atlas Data
import networkx.generators.atlas
atlas_graphs = [Graph(i) for i in networkx.generators.atlas.graph_atlas_g()]
atlas_graphs_data=[{'index':i,
'order':atlas_graphs[i].order(),
'components':atlas_graphs[i].connected_components_number(),
'graph':atlas_graphs[i]
} for i in range(len(atlas_graphs))]
connected_data=[data for data in atlas_graphs_data if data['components']==1]
|
|
# example
|
|
G=atlas_graphs_data[52]['graph']
show(G)
S=PZFStateGraph(base_graph=G, blue_set=[0])
show(S.get_markov_matrix())
(v,e)=ept(G)
show("ept = ",e,", with vertex =",v)
|
Order 4
result=[(lambda data, (v, e):
data['graph'].plot(
figsize=[2,2], fontsize=10,
title='G'+str(data['index'])+': '+str(n(e,digits=5))+'\n',
title_pos=[0,1],
vertex_size=30,
vertex_color='white',vertex_colors={'blue': [v]},
vertex_labels=False)
)(data,ept(data['graph']))
for data in [data for data in connected_data if data['order']==4]]
for fig in result:
fig.show();
     
|
Order 5
result=[(lambda data, (v, e):
data['graph'].plot(
figsize=[2,2], fontsize=10,
title='G'+str(data['index'])+': '+str(n(e,digits=5))+'\n',
title_pos=[0,1],
vertex_size=30,
vertex_color='white',vertex_colors={'blue': [v]},
vertex_labels=False)
)(data,ept(data['graph']))
for data in [data for data in connected_data if data['order']==5]]
for fig in result:
fig.show();
                    
|
Order 6
result=[(lambda data, (v, e):
data['graph'].plot(
figsize=[2,2], fontsize=10,
title='G'+str(data['index'])+': '+str(n(e,digits=5))+'\n',
title_pos=[0,1],
vertex_size=30,
vertex_color='white',vertex_colors={'blue': [v]},
vertex_labels=False)
)(data,ept(data['graph']))
for data in [data for data in connected_data if data['order']==6]]
for fig in result:
fig.show();
                                                                                                               
|
Order 7
result=[(lambda data, (v, e):
data['graph'].plot(
figsize=[2,2], fontsize=10,
title='G'+str(data['index'])+': '+str(n(e,digits=5))+'\n',
title_pos=[0,1],
vertex_size=30,
vertex_color='white',vertex_colors={'blue': [v]},
vertex_labels=False)
)(data,ept(data['graph']))
for data in [data for data in connected_data if data['order']==7]]
for fig in result:
fig.show();
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
|