<jupyter_start><jupyter_text>Study Loop Problem<jupyter_code>%load_ext autoreload
%autoreload 2

import clique_discovery 
from helpers import *<jupyter_output><empty_output><jupyter_text>AlgorithmsGiven a finite set of symbols $\Sigma$, a trace $T$ is defined as a finite sequence $T \in \Sigma^*, T = \sigma_1 \sigma_2 ... \sigma_M$. Let be $\overline{T} = \{ T_1, ... , T_N \}$, a set of N traces. The following algorithms are proposed.**Definition: Successor Pairs in $\overline{T}$**The idea is to retain the order of appearance of each symbol as edges in a directed graph, but discarding the repetitions. Given a trace $T$ of length $M$, we define $\phi^T_{\sigma_i}$ as the maximal sequence of ordered pairs starting at $\sigma_i$ not containing $(\sigma_i,\sigma_i)$:$\phi^T_{\sigma_i} = (\sigma_i,\sigma_{i+1}) ... (\sigma_i,\sigma_j), 1 \le i < j \le M $ such that $\sigma_i \ne \sigma_j$The *partial successor pairs $\phi^T$* is the concatenation in order:$\phi^T = \phi^T_{\sigma_1} \phi^T_{\sigma_2} ... \phi^T_{\sigma_M} $The *successor pairs sequence of $\overline{T}$* is defined as the concatenation of $\phi^{T_i}$ for all $T_i \in \overline{T}$: $\Phi^\overline{T} = \phi^{T_1} ... \phi^{T_N} = (\sigma_1^a,\sigma_1^b)(\sigma_2^a,\sigma_2^b) ... = p_1p_2 ...  $  **Definition: Weigthed Successor Pairs of $\overline{T}$**Let's define $p \cap^\ \Phi'$ as the number of appearances of the pair $p$ in a sequence of pairs $ \Phi'$ . Then the *weighted successors set of pairs in $\Phi^\overline{T}$* is defined as$\Phi^\overline{T}_{w} = \{ p_i \in \Phi^\overline{T} | p_i \cap^\ \Phi^\overline{T} = w \}$ (Me falta poner como ejemplo ABCDE y decir que corresponde a la traza de un simple path de un control flow graph)  Obtain serial control flow treeGiven a trace $\overline{T}$, obtain the inferred paths of $\overline{T}$, create a graph with its symbols and *untangle* it by removing extra edges.1. Obtain the set of succesor pairs $\Phi^\overline{T}$1. For each $\Phi^\overline{T}_{w} \ne \emptyset$   1. Construct a directed graph $G_w = (V_w, E_w) $ with $ E_w = \{ p_i \in \Phi^\overline{T}_{w} \}$  1. Obtain the clique set $Cliques(G_w^u) = \{ V1, ..., V_Q \}$ (vertex set of the maximal connected components) of the undirected equivalent $G_w^u$   1. For each $C_i \in Cliques(G')$ construct a sequence $P_i^w = v_0 ... v_{ | C_i |  }$ such that $ in\_degree( v_i , G_w ) = i $1. $P^\overline{T} = \cup{ P_i^w }$ is the set of inferred paths of $\overline{T}$1. Be $F' = (V_{F'}, E_{F'}) $ constructed from all the pairs $ E_F = \{ (\sigma_i^k, \sigma_i+1^k) \}$ such that $\sigma_i^k, \sigma_i+1^k$ appears consecutive in some $ P_k \subset P^\overline{T} $1. Be $F = ( V_F = V_{F'}, E_F \subset E_{F'} )$ Infer a serial control flow graph Infer a parallel control flow graph  Still Failing Examples<jupyter_code>combined_loops = [
    list("lklk1212ABCDEABCDEABCDE1212"),
    list("lk12ABCDEABCDE"),
    list("lk12ABCDE"),

]
inferred_paths = clique_discovery.infer_paths_from_traces( combined_loops )
# nice_graph( inferred_paths )
untangled_graph( clique_discovery.minimally_connected_graph( inferred_paths ) )

G = clique_discovery.created_auxiliary_graph( inferred_paths )
for a in list("12ABClk"):
    for b in list("12ABClk"):
        try:
            print (a, b, G.edges[a, b]["weight"], G.edges[b, a]["weight"])
        except:
            pass
loop_inside = [
    list("12ABCdefdefFG"),
    list("12ABCdefdefdefFG"),
    list("34ABCdefFG"),
    list("hjkhjkFG")
]
inferred_paths = clique_discovery.infer_paths_from_traces( loop_inside )
nice_graph( inferred_paths, with_weigths=False )
untangled_graph( clique_discovery.minimally_connected_graph( inferred_paths ), with_weigths=False )
# inferred_paths
head_with_loop = [
    list("12ABCDefABCDABCDef"),
]
inferred_paths = clique_discovery.infer_paths_from_traces( head_with_loop )
nice_graph( inferred_paths )
untangled_graph( clique_discovery.minimally_connected_graph( inferred_paths ) )<jupyter_output>{3.0: [['2', 'A', 'B', 'C', 'D'], ['1', 'A', 'B', 'C', 'D']], 2.0: [['2', 'e', 'f'], ['1', 'e', 'f']], 1.0: [['1', '2'], ['f', 'e']]}
{'fraction_non_alphanumeric': 0.1625484496124031, 'fraction_numerical': 0.015261627906976744, 'mean_word_length': 4.411533420707733, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 8, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '480693', 'license': 'Apache-2.0', 'n_tokens_mistral': 1543, 'n_tokens_neox': 1464, 'n_words': 441, 'path': 'notebooks/2-structures/2020-01-20-LoopProblem.ipynb', 'repo_name': 'jpgil/logdelay', 'size': '4128'}