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) |
|
|