6
\$\begingroup\$

I have an object like this:

[
   {
     origin: 'a',
     destination: 'b'
   },
   {
     origin: 'a',
     destination: 'c',
   },
   {
     origin: 'b',
     destination: 'c'
   },
   {
     origin: 'b',
     destination: 'd'
   },
   {
     origin: 'd',
     destination: 'c'
   },
   {
     origin: 'd',
     destination: 'e'
   }
];

given an origin and a destination I should find all the paths to get there.

So this is my code:

function getDestinations(origin, destinationEnd) {
  let destinations = payloads.filter(payload => payload.origin === origin);
  destinations = destinations.map(destination => {
    const destinationsRecursive = getDestinations(destination.destination, destinationEnd);
    if (destinationsRecursive.length) {
      return Object.assign({}, destination, {
        next: destinationsRecursive
      });
    } else if (destination.destination === destinationEnd){
      return Object.assign({}, destination, {
        end: true
      });
    }
  })
  destinations = destinations.filter(destination => destination !== undefined)
  return destinations;
}

Calling for example getDestinations('a', 'c'); would return this:

[
  {
    "origin": "a",
    "destination": "b",
    "next": [
      {
        "origin": "b",
        "destination": "c",
        "end": true
      },
      {
        "origin": "b",
        "destination": "d",
        "next": [
          {
            "origin": "d",
            "destination": "c",
            "end": true
          }
        ]
      }
    ]
  },
  {
    "origin": "a",
    "destination": "c",
    "end": true
  }
]

What whould you improve in my code to make the same better?

\$\endgroup\$
6
\$\begingroup\$

So first a quick refactor of the input object.

const Links = links => links.split(",").map(link => ({origin: link[0], dest : link[1]}));

So now links as created using Links("ab,bc,ac"); which is easier to deal with.


Cycles never end.

This problem is not as simple as it first appears.

All path finding algorithms need to be aware of the paths that lead in circles.

Your problem "ab,ac,bc,bd,dc,de" and the solutions for this are "abc", "abdc", and "ac". but if we change the last link to "da" we create a circular link. Your code will follow "abdabdabdab...." and so on until the call stack overflows.

In most recursive problems where you encounter a cyclic reference you can easily avoid the endless recursion by simply tracking the objects you have already referenced. Ending the recursion when you find a link that has already been traveled.

But your problem requires ALL paths which complicates the problem (Actualy impossible as cyclic links create infinite paths).

Consider the links "ab,ac,bc,bd,dc,da"

It has the following solutions

  1. ab, bc
  2. ab, bd, dc
  3. ab, bd, da, ac
  4. ac

If we marked all traveled then 3 would mark link ac as traveled and thus block solution 4.

Note: that the solutions include as many links as possible without repeating.

The following is not a valid solution as "ad" is repeated

  1. ab, bd, da, ab, bc

Currently your function crashed when presented with cyclic links.

Back to your code.

Now lets inprove your code. The code is too complex and very hard to read.

function getDestinations(origin, destinationEnd) {
  let destinations = payloads.filter(payload => payload.origin === origin);
  destinations = destinations.map(destination => {
    const destinationsRecursive = getDestinations(destination.destination, destinationEnd);
    if (destinationsRecursive.length) {
      return Object.assign({}, destination, {
        next: destinationsRecursive
      });
    } else if (destination.destination === destinationEnd){
      return Object.assign({}, destination, {
        end: true
      });
    }
  })
  destinations = destinations.filter(destination => destination !== undefined)
  return destinations;
}

Refactoring.

  1. Some bad naming needs fixing

payload becomes links and you use destination to mean a link, we can abbreviate destinationEnd as dest and getDestinations makes more sense as getPaths with destinationsRecursive better called paths

  1. Some redundancies to remove

Links filter, map, filter can be chained.

Also Object.assign is a bit noisy you can use {...obj} to do the same.

So now the function looks like

function getPaths(origin, dest) {
    return links
       .filter(link => link.origin === origin)
       .map(link => {
           const paths = getPaths(link.dest, dest);
           if (paths.length) {
               return {...link, more: paths};
           } else if (link.dest === dest){
               return {...link, end: true};
           }
      })
      .filter(link => link !== undefined);
}

Which is a lot more readable.

Performance

Now the problem of performance. map, and filter are both slow and use more memory than is needed. Each recursive call does not release memory until you exit, which happens at the end of the searches. Plus all the paths that are not part of the solution that you filter out each iteration

A quicker solution using a simple loop and changing when you create the new path so you don't need to hold paths that go no where.

function solvePaths(start, end, paths = []) {
    for (const link of links) {
        if (link.origin === start) {
            if (link.dest === end) {
                paths.push({...link, end : true});
            } else {
                const tryPath = solvePath(link.dest, end);
                if (tryPath.length) { paths.push({...link, more: tryPath}) }
            }
        }
    }
    return paths;
}

This avoids creating endless copies of the of the links array, via the filter and map methods. It also solves the problem of paths that fail.

Now to fix the cyclic reference problem

To do this you need to track the traveled path to each destination.

I have created a stack that tracks the current path links "traveled". When end points are found the current links are popped of the traveled stack so that the links are free to be use for another path to the destination.

The code is in the example below.

Well I think it works, it stops the crash, whether it finds all solutions may need some very in depth research which is beyond the scope of this answer.

UPDATED code snippet

I wanted to be sure that the function worked so did some more testing, and while I was doing it I realized that a further improvement could be made.

The problem is that each step requires the entire array of links to be iterated, checking if each link has the correct origin.

That can be offloaded to the creation of the links array. Using a Map indexed by origin allows the main loop to only loop over the links with the correct origin (links.origins(start) returns a pre-existing array of links with origin start). This is a significant performance increase.

function createLinks(links) {
    const byOrigin = new Map();
    links = links.split(",").map(link => {
        const origin  = link[0];
        const linkObj = {dest : link[1], origin};
        const origins = byOrigin.get(origin);
        if (!origins) { byOrigin.set(origin, [linkObj]) }
        else          { origins.push(linkObj) }
        return linkObj;
    })
    links.origins = origin => (origin = byOrigin.get(origin)) ? origin : [];
    return links;
}

function solvePath(start, end, links) {
    const traveled = [];
    return (function solvePath(start, end, paths = []) {
        for (const link of links.origins(start)) {
            if (!traveled.includes(link)) {
                if (link.dest === end) { paths.push({...link}) }
                else {
                    traveled.push(link);
                    const more = solvePath(link.dest, end);
                    if (more.length) {  paths.push({...link, more}) }
                    traveled.pop();
                }
            }
        }
        return paths;
    }) (start, end);
}

function show(paths, trek, treks = []){
    for (const path of paths) {
        if (path.more) { show(path.more, (trek === null ? path.origin : trek) + "> "+ path.dest,treks) }
        else {  treks.push((trek ? trek : path.origin) + "> "  + path.dest) }
    }
    return treks;
}





const _$ = (type,props)=>document.body.appendChild(Object.assign(document.createElement(type),props));

const theMap = "AB,AC,BC,BD,DC,DE,EC,DA,ED,EG,GD";
_$("div",{textContent : "Links : " + theMap});
show(
    solvePath("A","C",createLinks(theMap))
    ,null
).forEach(path=>_$("div",{textContent : path}))

\$\endgroup\$
1
\$\begingroup\$

Are you stuck with that data structure as input? It is leading to a lot of unnecessary array iteration..

Is the resulting data structure programmatically useful? It seems like you would still need to do some transformation on it to present in a view in any meaningful way.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.