<jupyter_start><jupyter_text>Utilities<jupyter_code>import os
folders = ["random_smart_images", "random_naive_images", "example_smart_images", "example_naive_images", "forward_images", "backward_images"]

def make_directories(input_list):
    for string in folders:
        dirpath = os.path.join('./', string)
        try:
            os.mkdir(dirpath)
        except FileExistsError:
            print('Directory {} already exists'.format(dirpath))
        else:
            print('Directory {} created'.format(dirpath))

make_directories(folders)<jupyter_output>Directory ./random_smart_images created
Directory ./random_naive_images created
Directory ./example_smart_images created
Directory ./example_naive_images created
Directory ./forward_images created
Directory ./backward_images created<jupyter_text>graph.py<jupyter_code>from typing import Set, Tuple, Dict
import random


class GameGraph:
    REACHABILITY_PLAYER = "Ron"
    SAFETY_PLAYER = "Simon"

    def __init__(self, reach_nodes: Set[int], safety_nodes: Set[int], edges: Set[Tuple[int, int]]):
        """
        Every node must be controlled by either Reachability or Safety player
        Example of data structures:
          straight = {1: {2,3,4},  2: {4}, 3: {2}, 4: {}}
          transpose = {1: {}, 2: {"reach": {1},"safe": {3}}, 3: {"reach": {1},"safe":{}}, 4: {"reach": {1}, "safe":{}}}
        """
        #Compute all the nodes by exectuing the union between the nodes controlled by both players
        self.nodes: Set[int] = reach_nodes.union(safety_nodes)
        #The straight graph is implemented as a dictionary in which we associate:
        #Integer that identifies the node -> Set of integers indicating its neighbors 
        self.straight: Dict[int, Set[int]] = dict()
        #The straight graph is implemented as a dictionary in which we associate:
        #Integer that identifies the node -> Set of integers indicating its neighbors 
        #The transpose graph is obtained from the straight graph by inverting its edges
        self.transpose: Dict[int, Dict[str, Set[int]]] = dict()

        #Generate the sets that will contain the nodes controlled by each player
        self.reachability_player_nodes: Set[int] = reach_nodes
        self.safety_player_nodes: Set[int] = safety_nodes

        #For all the nodes in the graph, generate the objects implementing the straigh and the transpose graph 
        for n in reach_nodes.union(safety_nodes):
            self.straight[n] = set()
            self.transpose[n] = {GameGraph.REACHABILITY_PLAYER: set(), GameGraph.SAFETY_PLAYER: set()}
        #Add the edges given in input 
        #Please note that this function is NOT used for implementing random graph. 
        #It is employed to generate graph specified by the user.
        for u, v in edges:
            self.add_edge(u, v)

    def add_edge(self, u: int, v: int) -> bool:
        """
        Adds a new edge to the graph, but only if the two nodes are already in it
        :param u: a node
        :param v: a node, different from u
        :return: True if the add was successful, False otherwise
        """
        if u not in self or v not in self or u == v or v in self.straight[u]:
            return False
        # add (u -> v) edge to straight graph
        self.straight[u].add(v)

        # Add (v -> u) edge to transpose graph, according to u's controller
        if u in self.reachability_player_nodes:
            self.transpose[v][GameGraph.REACHABILITY_PLAYER].add(u)
        elif u in self.safety_player_nodes:
            self.transpose[v][GameGraph.SAFETY_PLAYER].add(u)
        else:
            raise Exception(f"You have not defined node {u} as controlled by Safety or Reachability player.")
        return True

    def get_outbound_nodes(self, u: int) -> Set[int]:
        """
        Get all nodes reachable from u with an outbound edge
        :param u: a node in the graph
        :return: the set of reachable nodes
        """
        return self.straight[u]

    def get_inbound_nodes(self, u: int, player: str) -> Set[int]:
        """
        Get all nodes that can reach the given node and that are controlled by the given player
        :param u: a node in the graph
        :param player: a string representing one of the two players, "reach" or "safe"
        :return: the set of nodes controlled by the given player that can have an outbound edge to the given node
        """
        return self.transpose[u][player]

    def __contains__(self, u):
        return u in self.reachability_player_nodes or u in self.safety_player_nodes

    def controller(self, u):
        return GameGraph.SAFETY_PLAYER if u in self.safety_player_nodes else GameGraph.REACHABILITY_PLAYER

    #Starting by a set of input parameters, this function generates a random graph.
    #This is the optimized version of the function. For its detailed explanation, please refer
    #to the project's documentation.
    @staticmethod
    def generate_random_graph(N: int, E: int, self_edges=True, no_isolated=False):
        nodes = {n for n in range(N)}
        prob = N**2/E
        matrix = [[1 if random.random() < prob else 0 for _ in range(N)] for _ in range(N)]

        if no_isolated:
            for i in nodes:
                if not any(matrix[i]):
                    j = random.randint(0, N-1)
                    while j == i:   # this loop avoids adding a self edge to an isolated node
                        j = random.randint(0, N-1)
                    if random.random() < 0.5:
                        matrix[i][j] = 1   # add a random edge
                    else:
                        matrix[j][i] = 1
        edges = set()
        for i in nodes:
            for j in nodes:
                if matrix[i][j] == 1 and (i != j or self_edges):
                    edges.add((i, j))
        k = random.randint(1, N - 1)  # at least one node for each player
        reach_nodes = {n for n in nodes if n < k}  # {n | n \in N and n <= k}
        safe_nodes = nodes.difference(reach_nodes)
        graph = GameGraph(reach_nodes, safe_nodes, edges)

        return graph

    #Old version of the function that generates the random graph. It is correct, but the procedure
    #to remove isolated nodes is particularly time-spending.
    @staticmethod
    def old_generate_random_graph(N: int, E: int, self_edges=True, no_isolated=False):
        nodes = {n for n in range(N)}  # 0..N-1
        k = random.randint(1, N - 1)  # at least one node for each player
        reach_nodes = {n for n in nodes if n < k}  # {n | n \in N and n <= k}
        safe_nodes = nodes.difference(reach_nodes)
        edges = set()
        while len(edges) < E:
            u = random.randint(0, N - 1)
            v = random.randint(0, N - 1)
            if u == v and not self_edges:
                continue
            if (u, v) not in edges:
                edges.add((u, v))

        graph = GameGraph(reach_nodes, safe_nodes, edges)

        if no_isolated:
            for n in graph.nodes:
                if not graph.get_inbound_nodes(n, GameGraph.REACHABILITY_PLAYER) and \
                        not graph.get_inbound_nodes(n, GameGraph.SAFETY_PLAYER) and \
                        not graph.get_outbound_nodes(n):

                    if len(graph.straight[n]) == 0:
                        v = random.randint(0, N - 1)
                        # keep sampling v until it is different from n
                        while v == n:
                            v = random.randint(0, N - 1)

                        # choose edge direction randomly
                        coin = random.randint(0, 1)

                        graph.add_edge(n, v) if coin else graph.add_edge(v, n)
        return graph<jupyter_output><empty_output><jupyter_text>Graph test function<jupyter_code>example_edges = {(0, 1), (0, 3), (1, 0), (1, 2),
                  (2, 1), (2, 5), (3, 4), (3, 6),
                  (4, 0), (4, 7), (4, 8), (5, 7),
                  (6, 7), (7, 6), (7, 8), (8, 5)}
s = {0, 2, 4, 5, 6}
r = {1, 3, 7, 8}
example_graph = GameGraph(r, s, example_edges)
print(example_graph.straight)
print("\n")
print(example_graph.transpose)
print("\n")<jupyter_output>{0: {1, 3}, 1: {0, 2}, 2: {1, 5}, 3: {4, 6}, 4: {8, 0, 7}, 5: {7}, 6: {7}, 7: {8, 6}, 8: {5}}


{0: {'Ron': {1}, 'Simon': {4}}, 1: {'Ron': set(), 'Simon': {0, 2}}, 2: {'Ron': {1}, 'Simon': set()}, 3: {'Ron': set(), 'Simon': {0}}, 4: {'Ron': {3}, 'Simon': set()}, 5: {'Ron': {8}, 'Simon': {2}}, 6: {'Ron': {3, 7}, 'Simon': set()}, 7: {'Ron': set(), 'Simon': {4, 5, 6}}, 8: {'Ron': {7}, 'Simon': {4}}}<jupyter_text>graph_simple.py<jupyter_code>from typing import Set, Tuple, Dict

class GameGraphSimple:
    REACHABILITY_PLAYER = "Ron"
    SAFETY_PLAYER = "Simon"

    def __init__(self, reach_nodes: Set[int], safety_nodes: Set[int], edges: Set[Tuple[int, int]]):
        self.straight: Dict[int, Set[int]] = dict()
        self.transpose: Dict[int, Set[int]] = dict()
        self.controlled_nodes: Dict[str, Set[int]] = dict()

        for n in reach_nodes.union(safety_nodes):
            self.straight[n] = set()
            self.transpose[n] = set()

        self.reachability_player_nodes = reach_nodes
        self.safety_player_nodes = safety_nodes

        for u, v in edges:  # (u -> v)
            self.add_edge(u, v)

    def add_edge(self, u: int, v: int):
        # add (u -> v) edge to straight graph
        self.straight[u].add(v)
        # Add (v -> u) edge to transpose graph
        self.transpose[v].add(u)

    def get_outbound_nodes(self, u: int) -> Set[int]:
        """
        Get all nodes reachable from u with an outbound edge
        :param u: a node in the graph
        :return: the set of reachable nodes
        """
        return self.straight[u]

    def get_inbound_nodes(self, u: int) -> Set[int]:
        """
        Get all nodes that can reach the given node and that are controlled by the given player
        :param u: a node in the graph
        :return: the set of nodes controlled by the given player that can have an outbound edge to the given node
        """
        return self.transpose[u]

    @property
    def nodes(self) -> Set[int]:
        return self.safety_player_nodes.union(self.reachability_player_nodes)

    def controller(self, u):
        return GameGraph.SAFETY_PLAYER if u in self.safety_player_nodes else GameGraph.REACHABILITY_PLAYER

    @staticmethod
    def from_regular_graph(G: GameGraph):
        edges = set()
        for n, n_edges in G.straight.items():
            for m in n_edges:
                edges.add((n, m))
        reach_nodes = G.reachability_player_nodes
        safe_nodes = G.safety_player_nodes
        return GameGraphSimple(reach_nodes, safe_nodes, edges)<jupyter_output><empty_output><jupyter_text>draw_graph.py<jupyter_code>import networkx as nx
import matplotlib.pyplot as plt

#Routine to draw graphs
def draw_graph(graph, positions=None, target=None, win=None, image_name='graph.png'):
    #Initialize the target and the winning set 
    if target is None:
        target = []
    if win is None:
        win = []

    #Generate a graph using NetworkX
    G = nx.DiGraph()
    
    #For every node in the set of nodes specified, add the node to the graph
    for u in graph.nodes:
        G.add_node(u)

    #Initialize the set of edges
    edges = []

    #For every node in the set of nodes specified, add the node to the graph
    for n in graph.nodes:
        #Generate the set of edges of the node n by using the function that return all the nodes reachable from u with an outbound edge.
        #(shortcut to generate the set of the edges of the node n since the nodes are labelled with an integer)
        edges_n = graph.get_outbound_nodes(n)
        #For all the edges in the previously generated set
        for m in edges_n:
            #Add the edge to the graph
            G.add_edge(n, m)
            #Include the edge into the set of edges as a tuple
            edges.append((n, m))
    #This is required by Network X to specify the colors of the nodes        
    col_map = {
                GameGraph.REACHABILITY_PLAYER: 'red',
               GameGraph.SAFETY_PLAYER: 'green',
               'target': 'blue',
               'win': 'purple'}

    #This is required by Network X to specify the shapes of the nodes
    shape_map = { GameGraph.REACHABILITY_PLAYER: 'r',
               GameGraph.SAFETY_PLAYER: 's'}

    #Initialize the required lists           
    colors = []
    shapes = []
    #For all the nodes in the graph, append to the previously generated lists the shapes and the colors according to the set to which the nodes belongs
    for n in G.nodes():
        shapes.append(shape_map[graph.controller(n)])
        if n in target:
            colors.append(col_map['target'])
        elif n in win:
            colors.append(col_map['win'])
        else:
            colors.append(col_map[graph.controller(n)])

    #If the positions are not generated, generate an adequate set of positions        
    if not positions:
        positions = nx.spring_layout(G, k=0.75, iterations=20)

    #Draw the nodes, their labels and the edges    
    nx.draw_networkx_nodes(G, positions, cmap=plt.get_cmap('jet'),
                           node_color=colors, node_size=500)#, node_shape=shapes)
    nx.draw_networkx_labels(G, positions)
    nx.draw_networkx_edges(G, positions, edgelist=edges, arrows=True)
    #Show the figure, use this option for python notebooks
    # plt.show()
    #Save the figure
    plt.savefig(image_name)
    #Clear the entire current figure with its axes
    plt.clf()
    #Return the generated positions
    return positions<jupyter_output><empty_output><jupyter_text>reachability.py<jupyter_code>from typing import Set
import time

#Improved backward algorithm implementation. Please refer the documentation for further details.
def reachability_game(G: GameGraph, target: Set[int], draw=False, image_name="smart_{}.png") -> Set[int]:
    """
    Given a graph and a set of target nodes, returns the set of nodes such that
    the target is not reachable from them. Optionally, writes the steps of the algorithm as pictures.
    :param G: a graph
    :param target: a set of integers
    :param draw: a boolean
    :param image_name: the name of the file where to write the images. Must be formattable with the iteration number
    :return: a set of integers representing safe nodes
    """
    #Compute the positions of the nodes to use the same positions of the nodes for all the images (for the sake of clarity).
    if draw:
        positions = draw_graph(G, target=target, image_name=image_name.format(0))
    else:
        positions = None
    
    #Using Do-While construction
    #Initialize target set
    Q: Set[int] = target.copy()
    #Initialize the Current set (i.e. set of the last nodes found reachable). Please refer to the documentation for further details.
    C: Set[int] = target.copy()
    #Compute Reach_comp(X) (i.e. the component related to the reachability player)
    F_reach: Set[int] = force_reach(G, Q, C)
    #Compute Safety_comp(X) (i.e. the component related to the safety player)
    F_safe: Set[int] = force_safe(G, Q)
    #Compute the Force set
    F: Set[int] = F_reach.union(F_safe)
    #Compute the new target set
    Q_prime: Set[int] = Q.union(F)
    #Routine to draw the graph at the first iteration
    iteration = 1
    if draw:
        draw_graph(G, target=target, win=Q_prime, positions=positions, image_name=image_name.format(iteration))
    
    #While the fixpoint is not reached
    while Q != Q_prime:
        print(f"Iteration: {iteration} - Q: {len(Q)}")
        #Update the set of the last nodes found reachable to the last computed force
        C = F
        #Update the target set
        Q = Q_prime
        #Compute the Force set
        F_reach: Set[int] = force_reach(G, Q, C)
        F_safe: Set[int] = force_safe(G, Q)
        F: Set[int] = F_reach.union(F_safe)
        #Compute the new target set
        Q_prime = Q.union(F)
        #Routine to draw the graph
        iteration += 1
        if draw:
            draw_graph(G, positions=positions, target=target, win=Q_prime,
                       image_name=image_name.format(iteration))

    #Routine to draw the graph at the last iteration        
    if draw:
        draw_graph(G, positions=positions, win=Q_prime, image_name=image_name.format("final"))
    return Q

#Optimized function whose goal is to compute Reach_Comp(X). Precisely, it computes the set of nodes controlled by the reachability
#player that are reachable from C in the transpose graph. This is actually equivalent to compute all the nodes 
#from which the reachability player can reach C (), but faster. Please refer to the documentation for further details.
def force_reach(G: GameGraph, Q: Set[int], C: Set[int]) -> Set[int]:
    #Initialize the Force set to the empty set
    F: Set[int] = set()
    #Check all the nodes in the set of the last nodes found reachable.
    #Please refer to the paragraph "Current set optimization" in the section "Optimizations" for further details.
    for u in C:
        #Compute the set of nodes that:
        # - are controlled by the reachability player
        # - are reachable from the current set in the transpose graph
        # - are not already contained in the winning set of the reachability player
        #This last point has been added to avoid adding nodes already present in the winning set to the Force
        inbound = G.get_inbound_nodes(u, GameGraph.REACHABILITY_PLAYER).difference(Q) # -> Huge time saving by removing Q (~2x)
        #In fact, by combinining this optimization with the usage of F.update(inbound) instead of F.union(inbound)
        #We obtain that the update is much much faster (~6x)!
        F.update(inbound)
    return F

# Optimized function whose goal is to compute Safety_Comp(X), i.e., the set of nodes controlled by the safety player for which
# the safety player cannot avoid to enter in the reachability player's winning setthat.
def force_safe(G: GameGraph, Q: Set[int]) -> Set[int]:
    #Initialize the force_set to the empty set
    F: Set[int] = set()
    #Initialize the set of processed nodes
    processed: Set[int] = set()
    #Check all the nodes in the winning set
    for u in Q:
        #Compute the set of nodes that:
        # - are controlled by the safety player
        # - are reachable from the reachability player's winning set in the transpose graph
        for v in G.get_inbound_nodes(u, GameGraph.SAFETY_PLAYER):
            #If the node has not been processed and it is not in the target set
            if v not in processed and v not in Q:
                #Compute the set of nodes that the node v can reach in the straight graph (i.e. the neighbors of v in the straigh graph)
                outbound = G.get_outbound_nodes(v)
                #Check if the previously computed set is a subset of the target set
                #In case add the node to the Force set and to the processed set to avoid to check it again
                #Please refer to the paragraph "Processed list optimization" in the section "Optimizations"
                if outbound.issubset(Q):
                    F.add(v)
                processed.add(v)
    return F

# Un-optimized version of the backward algorithm.  
def reachability_game_naive(G: GameGraphSimple, target: Set[int], draw=False, image_name="naive_{}.png") -> Set[int]:
    """
    Naive version, directly derived from the slides.
    Given a graph and a set of target nodes, returns the set of nodes such that
    the target is not reachable from them. Optionally, writes the steps of the algorithm as pictures.
    :param G: a graph
    :param target: a set of integers
    :param draw: a boolean
    :param image_name: the name of the file where to write the images. Must be formattable with the iteration number
    :return: a set of integers representing safe nodes
    """
    positions = None
    if draw:
        positions = draw_graph(G, target=target, image_name=image_name.format(0))

    Q: Set[int] = target.copy()
    F_reach: Set[int] = force_reach_naive(G, Q)
    F_safe: Set[int] = force_safe_naive(G, Q)
    F: Set[int] = F_reach.union(F_safe)
    Q_prime: Set[int] = Q.union(F)

    iteration = 1
    if draw:
        draw_graph(G, target=target, win=Q_prime, positions=positions, image_name=image_name.format(iteration))
    while Q != Q_prime:
        Q = Q_prime
        F_reach: Set[int] = force_reach_naive(G, Q)
        F_safe: Set[int] = force_safe_naive(G, Q)
        F: Set[int] = F_reach.union(F_safe)
        Q_prime = Q.union(F)
        if draw:
            iteration += 1
            draw_graph(G, positions=positions, target=target, win=Q_prime,
                       image_name=image_name.format(iteration))

    if draw:
        iteration += 1
        draw_graph(G, positions=positions, target=target, win=Q_prime, image_name=image_name.format(iteration))
    return Q


# Un-optimized function whose goal is to compute Reach_Comp(X). We avoid commenting the code to provide the reader a lean code.
def force_reach_naive(G: GameGraphSimple, Q: Set[int]) -> Set[int]:
    F: Set[int] = set()
    for u in G.nodes:
        if G.controller(u) == GameGraph.REACHABILITY_PLAYER:
            reachable = G.get_outbound_nodes(u)
            for q in Q:
                if q in reachable:
                    F.add(u)
                    break
    return F


# Un-optimized function whose goal is to compute Safety_Comp(X). We avoid commenting the code to provide the reader a lean code.
def force_safe_naive(G: GameGraphSimple, Q: Set[int]) -> Set[int]:
    F: Set[int] = set()
    for u in G.nodes:
        if G.controller(u) == GameGraph.SAFETY_PLAYER:
            reachable = G.get_outbound_nodes(u)
            if len(reachable) > 0:
                if reachable.issubset(Q):
                    F.add(u)
    return F


#This function reproduces the example taken from the course's slides.
def example_from_slides(naive=True):
    draw = False
    E = {(0, 1), (0, 3), (1, 0), (1, 2), (2, 1), (2, 5), (3, 4), (3, 6), (4, 0), (4, 7), (4, 8), (5, 7), (6, 7),
         (7, 6), (7, 8), (8, 5)}  # , (1, 3)} add to make all nodes reachable
    s = {0, 2, 4, 5, 6}
    r = {1, 3, 7, 8}
    target = {4, 5}
    example_graph = GameGraph(r, s, E)

    print("==========\n Computing safety set for the example graph from the slides")

    if naive:
        example_graph_simple = GameGraphSimple.from_regular_graph(example_graph)

        print("\n----- Naive Algorithm:")
        example_naive_t0 = time.perf_counter()
        safe_naive_example = reachability_game_naive(example_graph_simple, target,
                                               draw=draw, image_name="./example_naive_images/step_{}.png")
        example_naive_t1 = time.perf_counter()
        print(
            f"\tThe Naive algorithm found {len(safe_naive_example)} safe nodes in {example_naive_t1 - example_naive_t0:0.4f} seconds.")
        print(f"\t The safe nodes are:\n [{safe_naive_example}]")

    print("\n\n\n----- Smart Algorithm:")
    example_smart_t0 = time.perf_counter()
    safe_smart_example = reachability_game(example_graph, target, draw=draw, image_name="./example_smart_images/step_{}.png")
    example_smart_t1 = time.perf_counter()
    print(
        f"\tThe smart algorithm found {len(safe_smart_example)} safe nodes in {example_smart_t1 - example_smart_t0:0.4f} seconds.")
    print(f"The safe nodes are: [{safe_smart_example}]")

    print("======= End of safety computation for example graph from the slides =======\n\n")

#This function launches a bettery of automatic experiments on randomly generated graphs to benchmark the implemented algorithms.
def random_graph_reachability(draw: bool, naive=True, no_isolated=False):
    print("\n\n\n======= Begin safety computation for random graph ===")

    import random
    # seed=103, N=1000000, E=5000000 and T=50000 are a good example. 39 s to generate, 52 s to solve (40 iterations)
    # seed=103, N=10000, E=50000 and T=500 are a good example
    # seed=103, N=50, E=100 and T=5 are a good example (instantaneous)
    random.seed(103)
    N = 100
    E = 50
    T = 50
    target = set()
    while len(target) < T:
        target.add(random.randint(0, N - 1))
    if T < 100: print(f"Target: {target}\n")


    graph_gen_ti = time.perf_counter()
    print(f"\tGenerating random graph with {N} nodes, {E} edges and {T} target nodes.")
    random_graph = GameGraph.generate_random_graph(N, E, no_isolated=no_isolated)

    graph_gen_tf = time.perf_counter()
    print(f"\tRandom graph generated in {graph_gen_tf - graph_gen_ti:0.4f} seconds.")
    print(f"\t\tPlayer 'Reachability' controls {len(random_graph.reachability_player_nodes)}")
    print(f"\t\tPlayer 'Safety' controls {len(random_graph.safety_player_nodes)}\n\n")


    if naive:
        print(f"Generating equivalent naive graph...")
        random_graph_naive = GameGraphSimple.from_regular_graph(random_graph)
        print("Done.\n")

        print("\n----- Naive Algorithm:")
        naive_t0 = time.perf_counter()
        safe_naive = reachability_game_naive(random_graph_naive, target, draw=draw,
                                       image_name="./random_naive_images/step_{}.png")

        naive_t1 = time.perf_counter()
        print(
            f"\tThe Naive algorithm found {len(safe_naive)} safe nodes in {naive_t1 - naive_t0:0.4f} seconds.")
        print(f"\t The safe nodes are:\n [{safe_naive}]")

    print("\n\n\n----- Smart Algorithm:")
    smart_t0 = time.perf_counter()
    safe_smart = reachability_game(random_graph, target, draw=draw, image_name="./random_smart_images/step_{}.png")
    smart_t1 = time.perf_counter()
    print(
        f"\tThe smart algorithm found {len(safe_smart)} safe nodes in {smart_t1 - smart_t0:0.4f} seconds.")
    if len(safe_smart) <= 100: print(f"The safe nodes are: [{safe_smart}]")

    print("======= End of safety computation for random graph =======\n\n")

    if naive and safe_smart != safe_naive:
        print(" !!!!!!!!!!!!!!!!!!!!!!!!\nThe smart and naive algorithm return different safe sets!")
        print(f"\tNodes safe for Smart but not for Naive: [{safe_smart.difference(safe_naive)}\n")
        print(f"\tNodes safe for Naive but not for Smart: [{safe_naive.difference(safe_smart)}\n")
        print("This must definetely be caused by a bug. Look for it!")
#example_from_slides(naive=True)
random_graph_reachability(True, naive=False, no_isolated=True)<jupyter_output>==========
 Computing safety set for the example graph from the slides

----- Naive Algorithm:
	The Naive algorithm found 6 safe nodes in 0.0001 seconds.
	 The safe nodes are:
 [{3, 4, 5, 6, 7, 8}]



----- Smart Algorithm:
Iteration: 1 - Q: 2
Iteration: 2 - Q: 4
Iteration: 3 - Q: 5
	The smart algorithm found 6 safe nodes in 0.0002 seconds.
The safe nodes are: [{3, 4, 5, 6, 7, 8}]
======= End of safety computation for example graph from the slides =======
{'fraction_non_alphanumeric': 0.10429765515200828, 'fraction_numerical': 0.012094089799541387, 'mean_word_length': 2.625989003620759, 'pattern_counts': {'":': 6, '<': 32, '<?xml version=': 0, '>': 43, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '527023', 'license': 'MIT', 'n_tokens_mistral': 8527, 'n_tokens_neox': 8121, 'n_words': 2918, 'path': 'Games_On_Graphs_1904342_Notebook_version/Reachability.ipynb', 'repo_name': 'giannetti1904342/-EAI-_Reasoning_agents', 'size': '27038'}