<jupyter_start><jupyter_text>Case Study: Finding a Path We start by defining a relation $R$:<jupyter_code>R = { (1,2), (2,3), (1,3), (2,4), (4,5), (3,6) }<jupyter_output><empty_output><jupyter_text>In order to visualize this relation as a graph, we use some **graphviz** magic.  Don't worry about the details of displaying the graph, as you are not required to understand these details.<jupyter_code>import graphviz as gv

def dot_graph(R):
    """This function takes binary relation R as inputs and shows this relation as
       a graph using the module graphviz.
    """
    dot = gv.Digraph()
    Nodes = { p[0] for p in R }.union({ p[1] for p in R })
    for n in Nodes:
        dot.node(str(n))
    for (x, y) in R:
        dot.edge(str(x), str(y))
    return dot<jupyter_output><empty_output><jupyter_text>Using the function defined above, we can now visualize the relation $R$ as a graph:<jupyter_code>dot = dot_graph(R)
dot<jupyter_output><empty_output><jupyter_text>We can even output this graph as in *PDF*.  This will create a PDF file with the name "graph.pdf".<jupyter_code>dot.render('graph', view=True)<jupyter_output><empty_output><jupyter_text>The relational product of two relations $R_1$ and $R_2$ is defined as follows:$$ R_1 \circ R_2 := \Bigl\{ \langle x, z \rangle \mid \exists y: \bigl(\langle x, y\rangle \in R_1 \wedge \langle y, z \rangle \in R_2\bigr)\Bigr\}$$<jupyter_code>def product(R1, R2):
    "Compute the relational product of R1 and R2."
    return { (x, z) for (x, y1) in R1 for (y2, z) in R2 if y1 == y2 }<jupyter_output><empty_output><jupyter_text>Lets try this function using the relation $R$ defined above.<jupyter_code>R2 = product(R, R)
R2<jupyter_output><empty_output><jupyter_text>We can visualize the relation R2.  However, let us first show the original relation $R$ again as a reference.<jupyter_code>dot_graph(R)
dot_graph(R2)<jupyter_output><empty_output><jupyter_text>Itis also interesting to visualize the relation $R \cup R \circ R$:<jupyter_code>dot_graph(R.union(R2))<jupyter_output><empty_output><jupyter_text>The transitive closure of a binary relation $R \subseteq M \times M$ can be computed by the following fixpoint iteration:$$ R_{n+1} = R \cup R \circ R_n $$<jupyter_code>def transClosure(R):
    T = R
    while True:
        oldT = T
        T    = R.union(product(R,T))
        if T == oldT:
            return T<jupyter_output><empty_output><jupyter_text>Lets compute the transitive closure of the relation $R$ defined at the beginning of the notebook.<jupyter_code>T = transClosure(R)<jupyter_output><empty_output><jupyter_text>Let us view this relation as a graph:<jupyter_code>dot_graph(T)<jupyter_output><empty_output><jupyter_text>The following function joins to paths into a single path.<jupyter_code>def join(L1, L2):
    return L1 + L2[1:]<jupyter_output><empty_output><jupyter_text>Let us see how it works.<jupyter_code>join( (1, 2, 3), (3, 4, 5))<jupyter_output><empty_output><jupyter_text>The function pathProduct defined below is a generalization of the function product.  Instead of combining pairs, it combines tuples of arbitrary length.<jupyter_code>def pathProduct(P, R):
    return { join(T1, T2) for T1 in P for T2 in R if T1[-1] == T2[0] }<jupyter_output><empty_output><jupyter_text>Lets see what how this function performs on our relation $R$.<jupyter_code>pathProduct(R, R)
pathProduct(R, pathProduct(R, R))<jupyter_output><empty_output><jupyter_text>As a generalization of the function product we define the function pathClosure.  Instead of using relations, this function takes sets of tuples where the tuples are representing paths in a graph.<jupyter_code>def pathClosure(R):
    P = R
    while True:
        oldP = P
        P    = R.union(pathProduct(P, R))
        if P == oldP:
            return P<jupyter_output><empty_output><jupyter_text>Let us see this in action:<jupyter_code>P = pathClosure(R)
P<jupyter_output><empty_output><jupyter_text>Let us change the graph $R$ so that it becomes cyclic:<jupyter_code>R.add((6, 1))
R<jupyter_output><empty_output><jupyter_text>First, we compute all paths of length $2$:<jupyter_code>R2 = pathProduct(R, R)
R2<jupyter_output><empty_output><jupyter_text>Everything seems to be just fine so far.  Let's compute the paths of length 4:<jupyter_code>R4 = pathProduct(R2, R2)
R4<jupyter_output><empty_output><jupyter_text>The last path, i.e. the path (6, 1, 3, 6, 1) is cyclic!  If we would keep cyclic paths in our function pathClosure, then this function does not terminate, as it will find paths that become longer and longer.The following function checks whether a path $P$ is cyclic.  To check whether a path is cyclic, we just have to check if a node occurs more than once.  The easiest way to check this is to turn $P$ into a set.  If the number of elements of this set is less than the length of $P$, then $P$ must be cyclic.<jupyter_code>def cyclic(P):
    return len(set(P)) < len(P)<jupyter_output><empty_output><jupyter_text>Now we are ready to redefine the function pathClosure so that it also works for a cyclic relation.  The only thing we need to change is the definition of the function pathProduct so that it does not return cyclic paths.<jupyter_code>def pathProduct(P, R):
    return { join(T1, T2) for T1 in P for T2 in R if T1[-1] == T2[0] and not cyclic(join(T1, T2)) }<jupyter_output><empty_output><jupyter_text>Let us try to compute all paths in our cyclic relation $R$.  First, lets view $R$ again:<jupyter_code>dot_graph(R)
pathClosure(R)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10538684020245842, 'fraction_numerical': 0.014461315979754157, 'mean_word_length': 4.955866523143165, 'pattern_counts': {'":': 0, '<': 94, '<?xml version=': 0, '>': 93, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '23', 'dir': 'jupyter-structured-clean-dedup', 'id': '381414', 'license': 'MIT', 'n_tokens_mistral': 1969, 'n_tokens_neox': 1913, 'n_words': 652, 'path': 'Python/Path-Finding.ipynb', 'repo_name': 'AbdalrohmanGitHub/Logik', 'size': '5532'}