javascript map all paths

Question

im not able to figure out the following problem. At point 1 I could either go to point 2 or point 5. From point to I could go to 3 or 4. From point 5 I could go to 6 or 7. From 7 there is only one path to 9. I would like to calculate all the full paths. Im not looking for the fastest route or anything. I need all the paths there are in a manner that I could follow them easily.

I have 2 questions:

Im not sure im using the correct way to 'store' the options (a[1]=[2,5]). Is this ok or is there a better way ?
Im not sure how to solve this. Can anyone give me a clue ? Im hoping im looking in the right direction :-)

The path:

  1 ->2 ->3
        ->4
    ->5 ->6
        ->7 ->8 ->9

And the desired result:

 1,2,3
 1,2,4
 1,5,6
 1,5,7,8,9

My attempt at solving this in javascript

// this doesn't do what I need 
var a = [];
a[1]=[2,5];    
a[2]=[3,4];
a[5]=[6,7];
a[7]=[8];
a[8]=[9];

trytoloop(a,1);

function trytoloop(a,key){
    if(a[key]){
         for (var y in a[key]){
                document.write(key);

                trytoloop(a,a[key][y]);
         }
    } else {
        document.write(key);
    }
}

Do you have cycles in your graph? (in this case you need to decide how to deal with them). Instead of writing semi-random valu to HTML collect all paths in array of arrays. Also consider renaming `trytoloop` to something more meaningful - it will help you understand what you are trying to do... — Alexei Levenkov, Dec 09 '12 at 19:44

Emily · Answer 1 · 2012-12-09T20:00:36.360

I put a solution below, but don't look if you don't want spoilers! It only deals with the case when there are no cycles in the graph.

Some hints without giving away the answer: I suggest that in your recursive function, you keep track of the whole path so far in the second argument, not just the current location, since otherwise you'll end up with a list of locations visited but how do you know the path that got you to each one? Second, in Javascript it's not considered good practice to iterate through an array with the for ... in construct, so you can use a regular for loop going from 0 to the length of the array. Thirdly, you're going to want to print the constructed path out at some point, but you don't want to do it at every step: instead, you want to print out the path when it's complete; that is, when there are no more places to go from the current location. Finally, I replaced document.write with console.log, since I believe document.write will overwrite the document contents each time you print something.

var a = [];
a[1]=[2,5];
a[2]=[3,4];
a[5]=[6,7];
a[7]=[8,9];

trytoloop(a,[1]);

function trytoloop(a,path){
  var last = path[path.length - 1];
  var next_hops = a[last];
  // if there could be cycles, you might want to check that next_hops doesn't
  // contain any already visited locations
  if (next_hops) {
    for (var i = 0; i < next_hops.length; i++) {
      var new_path = path.concat([next_hops[i]]);
      trytoloop(a, new_path);
    }
  } else {
    console.log(path);
  }
}

*in Javascript you can't iterate through an array with the `for ... in`* is a bit misleading. There are good reasons not to do it, yet, it is still possible. — Yoshi, Dec 09 '12 at 19:57
Good point, I'll edit it. OP see http://stackoverflow.com/questions/500504/javascript-for-in-with-arrays for explanation. — Emily, Dec 09 '12 at 20:00
Thank you ! Im still trying to wrap my head around this but with there examples im sure I will figure it out. Ill also look at the link ! — Arjen, Dec 09 '12 at 20:12

score 2 · Accepted Answer · answered Dec 09 '12 at 19:51

You do not keep track of the partial path you've built up so far. The array idea seems fine, though. Here's a working version with some more meaningful names: http://jsfiddle.net/YkH5b/.

// A cleaner way of defining the next keys
var nextKeysMap = {
    1: [2, 5],    
    2: [3, 4],
    5: [6, 7],
    7: [8],
    8: [9]
};

var fullPaths = [];
generateFullPaths([1], 1);  // start off with partial path [1] and thus at key 1

function generateFullPaths(partialPath, currentKey) {
    if(currentKey in nextKeysMap) {  // can we go further?
        var nextKeys = nextKeysMap[currentKey];  // all possible next keys
        for (var i = 0; i < nextKeys.length; i++) {  // loop over them
            var nextKey = nextKeys[i];
            // append the current key, and build the path further
            generateFullPaths(partialPath.concat(nextKey), nextKey);
         }
    } else {  // we cannot go further, so this is a full path
        fullPaths.push(partialPath);
    }
}

for(var i = 0; i < fullPaths.length; i++) {
    console.log(fullPaths[i].join(","));
}

score 1 · Answer 3 · answered Dec 09 '12 at 20:00

I haven't tried this, but off the top of my head, you could try something along these lines:

// use an object, and set the numbers as keys and the values as the child options
var a = {};
a[1] = {2:{3:{},4:{}},5:{6:{},7:{8:{9:{}}}}};

(function trytoloop(obj,num,str){
    if(str.length>0) str += ',';
    str += num
    if(Object.keys(obj).length==0) document.writeln(str+'<br />');
    else for(var key in obj) trytoloop(obj[key],key,str);
})(a[1],1,'');

score 1 · Answer 4 · answered Dec 09 '12 at 20:09

1

Here's my solution: Fiddle

The final output it's going to the console, and you can change the initial node in here console.log(getPaths(1)); (starting from the node 1 according to your requirements).

answered Dec 09 '12 at 20:09

rdiazv

1,153
7
7

javascript map all paths

4 Answers4