Trouver tous les chemins uniques dans la structure de l'arbre

Question

Disons que j'ai une structure de répertoire aménagé dans un fichier texte

root1 
    child1 
    child2 
     grandchild1 
     grandchild2 
    child3 
root2 
    child1 
    child2 
     grandchild1 
      greatgrandchild1 

Comment puis-je transformer la structure de l'arbre ci-dessus dans un tableau imbriqué qui ressemble à ceci:

[ 
    [ "root1", "child1" ], 
    [ "root1", "child2", "grandchild1" ], 
    [ "root1", "child2", "grandchild2" ], 
    [ "root1", "child3" ], 
    [ "root2", "child1" ], 
    [ "root2", "child2", "grandchild1", "greatgrandchild1" ] 
] 

modifier

Obtenir plus loin, mais encore avoir des problèmes à pied à travers l'arbre récursive

var $text = '' 
+ 'root1\n' 
+ ' r1 child1\n' 
+ ' r1 child2\n' 
+ ' r1 grandchild1\n' 
+ ' r1 grandchild2\n' 
+ ' r1 child3\n' 
+ 'root2\n' 
+ ' r2 child1\n' 
+ ' r2 c1\n' 
+ '  r2 c1 g1\n' 
+ ' r2 child2\n' 
+ ' r2 grandchild1\n' 
+ '  r2 greatgrandchild1\n' 
+ 'test!\n' 
+ 'root3\n' 
+ ' r3 child1\n' 
+ ' r3 c1\n' 
+ '  r3 c1 g1\n' 
+ ' r3 child3\n' 
+ ' r3 grandchild1\n' 
+ '  r3 greatgrandchild1'; 

var dirGen = (function(trees) { 
    "use strict"; 

    var indent = /[\s\t]/g; 
    var lTrim = /[\s\t]*/; 
    var $trees = decompose(trees); 
    var $root = []; 

    function init() { 
    var paths = $trees.map(treeMap) 
    $test(paths); 
    } 

    function treeMap(tree, n, arr) { 
    var base = new LinkedList(); 
    return bfs(-1, tree, base); 
    } 

    function bfs(n, tree, base) { 
    var l, t; 
    n++; 
    //base case 
    if (n === tree.length) return trails(base); 
    l = tree.length; 
    t = tree[n]; 
    var cur = { label: t.replace(lTrim, ""), depth: depth(t), children: [] }; 
    //set root 
    if (n === 0) { 
     base.tree = cur; 
     return bfs(n, tree, base); 
    } 

    base.push(cur); 

    return bfs(n, tree, base); 

    } 

    function depth(str) { 
    var d = str.match(indent); 
    if (d === null) return 0; 
    return d.length; 
    } 

    function trails(arr) { 
    return arr; 
    } 

    function LinkedList() {} 

    LinkedList.prototype.push = function(node) { 
    var l = this.tree.children.length; 
    var j = l - 1; 
    if (l === 0) { 
     this.tree.children.push(node); 
     return; 
    } 
    //walk through children array in reverse to get parent 
    while (j > -1) { 
     var d = this.tree.children[j].depth; 
     //child 
     if (node.depth > d) { 
     console.log(this.tree.children[j], node) 
     return this.tree.children[j].children.push(node); 
     } 
     //sibling 
     if (node.depth === d) { 

     } 

     j--; 
    } 

    } 

    function decompose(arr) { 
    var treeBreak = /[\r\n](?=\w)/gm; 
    var lines = /[\r\n]+(?!\s)*/g; 
    return arr.split(treeBreak).map(function(str) { 
     return str.split(lines) 
    }); 
    } 

    function $test(str) { 
    var json = JSON.stringify(str, null, 2); 
    var wtf = "<pre>" + json + "</pre>"; 
    document.write(wtf); 
    } 

    return init; 

})($text); 

dirGen(); 

Le code jusqu'à présent me fait ce tableau JSON:

Answer 1

(répondre à ma propre question) Ok, donc l'implémentation comporte trois parties: (1) convertir le fichier texte en une arborescence, puis (2) utiliser dfs sur l'arbre pour trouver les chemins uniques, et enfin (3) fusionner tous les chemins en un seul tableau.

D'abord, le convertisseur de texte en arbre. Vous avez encore besoin de trouver la profondeur (niveau d'indentation) de chaque élément parce que ce qui détermine si elle est un enfant ou un frère:

var treeGrapher = (function() { 
    "use strict"; 

    var find = require("lodash.find"); 

    var indent = /[\s\t]/g; 
    var lTrim = /[\s\t]*/; 
    var treeBreak = /[\r\n](?=\w)/gm; 
    var lines = /[^\r\n]+/g 

    function init(text) { 
    return decompose(text).map(function(tree) { 
     return populate(-1, tree, {}) 
    }); 
    } 

    function depth(str) { 
    var d = str.match(indent); 
    if (d === null) return 0; 
    return d.length; 
    } 

    function decompose(txt) { 
    return txt.split(treeBreak).map(function(str) { 
     return str.match(lines); 
    }); 
    } 

    function populate(n, tree, root, cache, breadCrumbs) { 
    var branch, leaf, crumb; 
    //set index 
    n++; 
    //root case 
    if (n === tree.length) return root.tree; 

    branch = tree[n]; 
    leaf = { label: branch.replace(lTrim, ""), index: n, depth: depth(branch), children: [] }; 
    breadCrumbs = breadCrumbs || []; 
    crumb = cache ? { label: cache.label, index: cache.index, depth: cache.depth, node: cache } : undefined; 

    //set root 
    if (n === 0) { 
     root.tree = leaf; 
     return populate(n, tree, root, leaf, breadCrumbs); 
    } 

    //push child to cached parent from previous iteration 
    if (leaf.depth > cache.depth) { 
     cache.children.push(leaf); 
     root.parent = cache; 
     breadCrumbs.push(crumb) 
     return populate(n, tree, root, leaf, breadCrumbs); 
    } 

    //push child to distant parent via breadcrumb search 
    if (leaf.depth <= cache.depth) { 
     var rev = breadCrumbs.slice(0).reverse(); 
     var parentNode = find(rev, function(obj){ return obj.depth < leaf.depth }).node; 
     parentNode.children.push(leaf); 
     return populate(n, tree, root, leaf, breadCrumbs); 
    } 

    } 

    return init; 

})(); 

module.exports = treeGrapher; 

Ensuite, les DSF. Cet algorithme ne recherche qu'une arborescence à la fois, donc si votre structure de répertoires a plusieurs racines, vous devez la placer dans une boucle.

var uniquePaths = (function() { 
    "use strict"; 

    function init(tree) { 
    return walk(tree, [], []); 
    } 

    function walk(branch, path, basket) { 
    var fork = path.slice(0); 
    var i = 0; 
    var chld = branch.children; 
    var len = chld.length; 
    fork.push(branch.label); 
    if (len === 0) { 
     basket.push(fork); 
     return basket; 
    } 
    for (i; i < len; i++) walk(chld[i], fork, basket); 
    return basket; 
    } 

    return init; 

})(); 

module.exports = uniquePaths; 

Les mettre, ensemble, ressembler à ceci:

directory.tmpl.txt

root1 
    child1 
    child2 
     gc1 
root2 
root3 
    root3-child1  

main.js

var fs = require("fs"); 
var treeGrapher = require("./lib/treeGrapher.js"); 
var uniquePaths = require("./lib/uniquePaths.js"); 

var tmpl = fs.readFileSync("./director.tmpl.txt", "utf8"); 
var graphs = treeGrapher(tmpl); //returns an array of trees 
var paths = arrange(graphs); 

/**  
[ 
    [ "root1", "rootchild1" ], 
    [ "root1", "child2", "gc1" ], 
    [ "root2" ], 
    [ "root3", "root3-child1" ] 
] 
*/ 

function arrange(trees) { 
    var bucket = []; 
    trees.forEach(function(list) { 
     uniquePaths(list).forEach(function(arr) { 
      bucket.push(arr); 
     }); 
    }); 
    return bucket; 
} 

Answer 2

Je suis trop paresseux pour lire votre algorithme: - |

function populateTree (tree, text) { 
    var rTab, rChunks, rChunk; 
    var chunks, chunk; 
    var i, l, node; 
    if (!text) return; 
    rTab = /^\s{4}/gm; 
    rChunks = /[\r\n]+(?!\s{4})/g; 
    rChunk = /^(.+)(?:[\r\n]+((?:\r|\n|.)+))?$/; 
    chunks = text.split(rChunks); 
    l  = chunks.length; 
    for (i = 0; i < l; i++) { 
     chunk = chunks[i].match(rChunk); 
     node = { label: chunk[1], children: [] }; 
     tree.children.push(node); 
     populateTree(node, chunk[2] && chunk[2].replace(rTab, '')); 
    } 
} 

function printTree(tree, prefix) { 
    var i, l = tree.children.length; 
    for (i = 0; i < l; i++) { 
     console.log(prefix + tree.children[i].label); 
     printTree(tree.children[i], prefix + ' '); 
    } 
} 

Utilisation:

var tree = { children: [] }; 
populateTree(tree, text); 
printTree(tree, ''); 

Je ne suis pas familier avec NodeJS, je ne peux dire que cela fonctionne dans Chrome avec cette chaîne:

var text = '' 
+ 'root1\n' 
+ ' child1\n' 
+ ' child2\n' 
+ '  grandchild1\n' 
+ '  grandchild2\n' 
+ ' child3\n' 
+ 'root2\n' 
+ ' child1\n' 
+ ' child2\n' 
+ '  grandchild1\n' 
+ '   greatgrandchild1';