Cyclomatic Complexity (complexity)

Question

I have a program for finding shortest distance/path and I got a correct answer but I am getting an issue i.e., "Function 'shortestPath' has a complexity of 9. Maximum allowed is 6." This is the algorithm:

const graph = {
  start: { A: 5, D: 8 },
  A: { B: 9, C: 3 },
  D: { C: 4, E: 6 },
  C: { B: 5, E: 2 },
  B: { end: 7 },
  E: { end: 4 },
  end: {}
};

function shortestCostNode(costs, processed) {
  return Object.keys(costs).reduce((lowest, node) => {
    if (lowest === null || costs[node] < costs[lowest]) {
      if (!processed.includes(node)) {
        lowest = node;
      }
    }
    
    return lowest;
  }, null);
}

// this function returns the minimum cost and path to reach end
function shortestPath(graph) {
  // track lowest cost to reach each node
  const costs = Object.assign({ end: Infinity }, graph.start);
  
  const parents = { end: null };
  
  for (let child in graph.start) {
    parents[child] = 'start';
  }
  
  const processed = [];
  let node = shortestCostNode(costs, processed);
  
  while (node) {
    let cost = costs[node];
    let children = graph[node];
    
    for (let n in children) {
      if (children.hasOwnProperty(n)) {
        let newCost = cost + children[n];
        
        if (!costs[n] || costs[n] > newCost) {
          costs[n] = newCost;
          parents[n] = node;
        }
      }
    }
    
    processed.push(node);
    node = shortestCostNode(costs, processed);
  }

  let optimalPath = ["end"];
  let parent = parents.end;
  
  while (parent) {
    optimalPath.push(parent);
    parent = parents[parent];
  }
  
  optimalPath.reverse();

  const result = {
    distance: costs.end,
    path: optimalPath
  };
  return result;
}

How to reduce complexity of Function shortestPath?

Answer 1

Cyclomatic complexity

is a measure of the number of possible paths thorough some code. For example an if statement with one clause eg if (foo) {} has two paths, One if foo is true and one if false. Any point where the code can branch, the branches are counted as part of the cyclomatic complexity.

Unfortunately how the complexity is summed differs so without knowing how the metric was calculated there is no easy way to give an answer. The best you can do is reduce the number of possible branches in the code.

Improving the code

Looking at your code and there is plenty of room to reduce the number of branches.

The function shortestCostNode is not needed as the shortest link in a node has no influence on the final result. The shortest link may well move you to the longest path. Searching for the shortest link is no improvement on picking nodes sequentially.

shortestCostNode is the major source of complexity in your solution, it effectively randomizes your search. Because of this you must track which path you have traveled so you don't end up repeating the same path, this adds a lot of baggage.

If you systematically search all possible paths in order (keeping track of where you have not been) you eliminate the need to track where you have been and can thus remove a lot of code.

Use a stack to search a tree

As the search for the shortest path involves traveling along paths and then backtracking to the nearest untraveled branch a stack is the best way to keep track of your progress.

You start at a node, push all paths and the cost so far to a stack, then pop one path and move along that path to the next node adding the cost as you do. Then do the same for the next node.

When you reach an end node you then check the distance and if it is the shortest so far you save that distance and the path traveled. Then pop the next path step from the stack until all paths have been checked.

A Recursive stack

The simplest (but not the quickest) way to implement a stack is via recursion.

Thus you end up with a function something like

function shortestPath(graph) {
    const result = {distance: Infinity}, endName = "end";
    function followPath(node, totalDist = 0, path = ["start"]) {
        for (const [name, length] of Object.entries(node)) {
            const distance = totalDist + length;
            if (distance < result.distance) {
                if (name === endName) {  
                    Object.assign(result, {distance, path: [...path, endName]}); 
                } else {
                    path.push(name);
                    followPath(graph[name], distance, path);
                    path.pop();
                }
            }
        }
    }
    followPath(graph.start);
    return result;
}

The function has a Cyclomatic complexity of about 5.

Note that the function only follows paths while the distance traveled is less than the shortest path found already found. This means that you may not need to check all paths to the end.

There is also plenty of room for improvement (in terms of complexity and performance), but as you have not defined much about the graphs possible structure there is no point going any further,.

Answer 2

const vs let

First I would like to applaud the use of const in some places. There are however places where const could be used instead of let - e.g. for optimalPath, since it never gets re-assigned. It is advised to default to using const and then switch to let when re-assignment is deemed necessary. This helps avoid accidental re-assignment and other bugs.

Adding to optimalPath

Instead of calling push() to add items to optimalPath and then calling reverse, the unshift() method can be used to add items to the beginning of the array, which eliminates the need to reverse the array.

Iterating in shortestCostnode()

Note the MDN documentation for Array.prototype.reduce() - for parameter initialValue

initialValue Optional
A value to use as the first argument to the first call of the callback. If no initialValue is supplied, the first element in the array will be used as the initial accumulator value and skipped as currentValue. Calling reduce() on an empty array without an initialValue will throw a TypeError.

This means that instead of passing null for the initial value, the value could be omitted in order to use the first value as the initial value of lowest and it would skip that first iteration. This would then eliminate the need to check lowest === null in that if condition.

Memoization

A possible optimization is to memoize results - e.g. if shortestCostNode() ever gets called with duplicate arguments then store the computed return value so it can be looked up on subsequent calls and returned without needing to re-compute the value.

Iterating over children items

For the loop within the while loop

for (let n in children) {

      if (children.hasOwnProperty(n)) {

consider using a for...of loop combined with Object.entries(children)

Then there is no need to check if the property exists in children (instead of higher up in the prototype chain)

for (const [n, child] of Object.entries(children)) {

That uses const instead of `let because the values don't need to be re-assigned within the loop.

A more appropriate name for n would be key:

for (const [key, child] of Object.entries(children)) {