ept - Order 4,5,6,7

1714 days ago by ychan2

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