Zero forcing on directed graphs

2951 days ago by butler

This SAGE worksheet gives a rudimentary method used to compute the zero forcing number of a directed graph as well as its propagation time.

The code (with too many comments) needed to compute these is given below.

def zero_forcing(G,prop_time = False): """ INPUT: G a directed/oriented graph with vertices labeled 0,...,(n-1) OUTPUT: a minimal zero forcing set If prop_time = True then also finds set with min prop time """ n = G.order() nbrs = [] # Find lists of out neighbors (for push_zeros) for v in range(n): out_nbrs = [] for e in G.outgoing_edges(v): if e[0]==v: out_nbrs.append(e[1]) else: out_nbrs.append(e[0]) nbrs.append(out_nbrs) found_Z = False # a flag used for knowing when to stop outer loop best = (0,n) # used for prop time for t in range(1,n+1): # here t represents size of zero forcing sets for S in Combinations(range(n),t): Q = push_zeros(nbrs,S,n) # what can be achieved coloring S blue if len(Q[0]) == n: # all blue? if not prop_time: return S # if not tracking prop time, return zero forcing set found_Z = True # flag to stop outer loop after the current size if Q[1] < best[1]: # test to see if a better prop time is found best = (S,Q[1]) if found_Z: return best # return prop time def push_zeros(nbrs,S,n): """ INPUT: nbrs = a list of all out-neighbors of each vertex S = an initial set of "blue" vertices OUTPUT: the set of all vertices forced under repeated iteration of the color change rule """ active = set(S) # blue vertices that might be able to force filled = set(S) # blue vertices unfilled = set(range(n)).difference(filled) # white vertices force = True count = -1 # count keeps track of zero forcing rounds while force: # keep going until no more forces happen count += 1 # increase count force = False new_active = copy(active) # copy to be careful with prop time for v in active: # check each blue vertex which might force white_nbrs = set(nbrs[v]).intersection(unfilled) # find white neighbors if len(white_nbrs) == 0: # if no white neighbors, will never force new_active.remove(v) # remove from active elif len(white_nbrs) == 1: #one white neighbor so can force force = True w = white_nbrs.pop() # the white neighbor that we force filled.add(w) # w is now blue unfilled.remove(w) # so it's not white new_active.add(w) # w might now be able to force new_active.remove(v) # but v will never force again active = copy(new_active) # update what can be forcing return filled, count # return what was changed blue, and how many rounds 
       

To use this first form a directed graph (digraph) in SAGE and then pass it into the zero_forcing function.  There are several ways to form a digraph.

  • DiGraph(n):  Specifiy number of vertices (n) and then list edges
  • DiGraph(M):  M is a 0-1 matrix, edge from i->j if M(i,j)=1
  • digraphs:  Useful for a few families and random digraphs.

We illustrate each of these below and give examples of using the zero forcing process.

G=DiGraph(5) G.add_edges([(0,1),(1,3),(3,4),(3,2),(2,0),(2,5),(5,1),(0,5),(5,3)]) G.show() 
       
zero_forcing(G) 
       
[0, 2]
[0, 2]
zero_forcing(G, prop_time = True) 
       
([0, 2], 3)
([0, 2], 3)
M = matrix([[0,1,0,0,1,0], [1,0,0,1,0,1], [1,1,0,0,0,1], [0,1,1,0,0,0], [0,1,0,1,0,1], [0,0,0,1,1,0]]) H = DiGraph(M) H.show() 
       
zero_forcing(H) 
       
[3, 5]
[3, 5]
zero_forcing(H, prop_time = True) 
       
([3, 5], 3)
([3, 5], 3)
K = digraphs.RandomDirectedGNP(20,0.1) K.show() 
       
zero_forcing(K) 
       
[0, 3, 7, 8, 9, 19]
[0, 3, 7, 8, 9, 19]
zero_forcing(K,prop_time = True) 
       
([8, 9, 10, 12, 17, 19], 4)
([8, 9, 10, 12, 17, 19], 4)