# code taken from https://sage.math.iastate.edu/home/pub/54/
import random
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 statistic(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;