Algorithme d’abstraction de chemins de graphes requirejs

J’ai une structure de données contenant un graphique semblable à celui de l’image suivante: Structure de données arborescente

Dans cette arborescence, un nœud peut avoir un nombre quelconque d’enfants uniques parmi les niveaux inférieurs. Dans l’arborescence de l’image représente un ensemble de chemins. Où chaque chemin doit commencer par un nœud du niveau 1 et se terminer par un nœud de marque “*”. Les chemins de l’arbre dans l’image sont donc:

A then C then G A then C then G then J A then D then G A then D then G the J A then D then K, and so on... 

En fait, mon arbre d’origine est énorme (environ 2 millions de séquences) et le nombre maximal de nœuds par niveau est de 61 (sur 11 niveaux). Cela provoque donc de nombreux problèmes de consommation de mémoire dans mon application (une application de vision par ordinateur pour SAMSUNG).

Mon objective est d’avoir un algorithme itératif qui représente ces chemins dans un format de chaîne plus compact. Donc, je pense que nous le problème est divisé en trois étapes comme suit. J’ai construit la structure de données de l’arborescence (étape 2), mais je ne peux toujours pas dériver d’algorithme itératif qui obtient la chaîne / séquence de sortie à l’étape 3 à partir de l’arborescence .

1- Chaîne d’entrée:

(ACG) | (ACGJ) | (ADG) | (ADGJ ) | (ADK) | .... (ACG) | (ACGJ) | (ADG) | (ADGJ ) | (ADK) | ....

Où “|” représente des alternatives.

2- Structure de données d’arbre de construction de ces chemins

3- Chaîne de sortie requirejse:

(A (CG [J]) | (D (G [J]) | K)) | (B ....) (A (CG [J]) | (D (G [J]) | K)) | (B ....) .

Où où “|” représente des alternatives et “[]” englobe les options. La chaîne de sortie cible doit être optimisée, car il n’ya pas plus de facteurs communs pouvant être pris pour la simplifier davantage.

Vous pouvez utiliser une modification du DFS itératif, qui utilise une stack pour garder une trace des nœuds non traités. Cet algorithme ne stocke jamais plus de 6 caractères sur la stack * pour un seul nœud, et il y a toujours moins de N nœuds sur la stack (N étant le nombre de nœuds dans le graphique). Vous avez indiqué que N serait au plus 61 * 11 = 671, il y aurait donc un maximum d’environ 4000 éléments possibles sur la stack.

Dans le pseudocode ci-dessous, un nœud “de destination” est un nœud étoilé dans l’exemple ci-dessus, par exemple G * .

Initialisation:

Un nœud factice Φ est introduit avec une arête de Φ dans chacun des nœuds “racines”, par exemple les nœuds A et B ci-dessus. Le jeton pour Φ est supposé être un caractère non imprimable, ou vous pouvez le vérifier explicitement avant de l’append à la chaîne de sortie. Le nœud Φ est poussé sur la stack avant d’appeler la fonction.

 outSsortingng := "" while stack not empty pop token if token is node outSsortingng := outSsortingng + node(token) // Line 5 - explanation below if node(token) has children if node(token) is destination outSsortingng := outSsortingng + "[" push "]" end if node(token) has multiple children for each child of node(token), from right to left push ")" push child push "(" push "|" end pop // remove last "|" else push child end end else // token is ()[]| outSsortingng := outSsortingng + token end end 

La sortie de cet algorithme pour la première partie de votre graphique (A et ses enfants) est (avec des espaces supplémentaires ajoutés pour la clarté; les espaces peuvent être facilement ajoutés au code):

 A (CG [J]) | (D (G [J]) | (K)) 

Vous remarquerez un écart entre votre résultat et le mien: le dernier nœud K est entre parenthèses dans ma solution. Si cela n’est pas souhaitable (cela pourrait entraîner une laideur telle que A[(B)|(C)] ), vous pouvez l’éliminer en effectuant une vérification supplémentaire lorsque vous retirez un jeton de nœud de la stack au prix d’une surcharge supplémentaire. Remplacez simplement la ligne 5 ci-dessus par:

 if (node(token) has no children AND last character of outSsortingng is "(" AND next token on stack is ")") remove trailing "(" from outSsortingng concatenate token to outSsortingng pop ")" from stack and ignore else outSsortingng := outSsortingng + node(token) // as above end 

Faites-moi savoir si vous avez des questions ou si j’ai raté quelque chose.

* Cela se produira dans le cas (probablement hautement improbable) d’un nœud en cours d’écriture sous la forme |[(A)] . La plupart des nœuds occuperont 4 caractères ou moins dans la stack.

Notez que ce n’est pas tout à fait une réponse – je ne pouvais pas mettre l’image et tout dans un commentaire bien.

Étant donné ce graphique:

Graphique

Solution 1

 (A (B | C) E*) | (ABD*) | (ACF*) 

Solution 2

 (AB (D* | E*)) | (AC (E* | F*)) 

Solution 3

 (A (B (D* | E*) | C (E* | F*))) 

Question

Comment voulez-vous résoudre cette ambiguïté? Vous devez définir précisément ce que vous recherchez comme “la” réponse.