javascriptjsonrecursionshortest-pathlongest-path

How can I calculate the shortest and longest paths of this Q&A flow?


I have a Q&A flow like the following:

enter image description here

The basic idea is that depending on the answer chosen for a question, a different question will be asked next.

I am currently representing this Q&A flow with the following JavaScript object:

var QAndAObj = {
  1: {
    question: 'Question 1',
    answers: [
      {
        answerText: 'Answer 1-1',
        nextQuestion: 2
      },
      {
        answerText: 'Answer 1-2',
        nextQuestion: 3
      }
    ]
  },
  2: {
    question: 'Question 2',
    answers: [
      {
        answerText: 'Answer 2-1',
        nextQuestion: 3
      },
      {
        answerText: 'Answer 2-2',
        nextQuestion: null
      }
    ]
  },
  3: {
    question: 'Question 3',
    answers: [
      {
        answerText: 'Answer 3-1',
        nextQuestion: 4
      },
      {
        answerText: 'Answer 3-2',
        nextQuestion: null
      },
      {
        answerText: 'Answer 3-3',
        nextQuestion: null
      }
    ]
  },
  4: {
    question: 'Question 4',
    answers: [
      {
        answerText: 'Answer 4-1',
        nextQuestion: null
      },
      {
        answerText: 'Answer 4-2',
        nextQuestion: null
      }
    ]
  }
};

To show the user a progress bar, I'd like to be able to calculate the longest and shortest paths through the question flow.

My initial thought was to write a recursive function like the following to go down each possible path in the flow:

function recurse(node) {
  for (var i = 0; i < node.answers.length; i++) {
    if (node.answers[i].nextQuestion) {
      recurse(QAndAObj[node.answers[i].nextQuestion]);
    }
  }
}

The above function does allow me to hit each node in the flow, but I'm not sure how to calculate the longest and shortest paths through the flow.

Any help/advice/code would be greatly appreciated.
Thank you very much.


Solution

  • Take a look at this jsFiddle for a working example.

    function shortAndLong(QATree, startNode) {
        var paths = [];
        function findAllPaths(startNode, currentCost) {
            for (var i = 0; i < startNode.answers.length; i++) {
                var child = startNode.answers[i];
                if (child.nextQuestion == null) {
                    paths.push(currentCost);
                }else {
                    findAllPaths(QATree[child.nextQuestion], currentCost+1);
                }
            }
        }
        findAllPaths(startNode, 1);
        return [Math.min.apply(Math, paths), Math.max.apply(Math, paths)]
    }
    console.debug('ans',shortAndLong(QAndAObj, QAndAObj[1]));//returns [2, 4]
    console.debug('ans',shortAndLong(QAndAObj, QAndAObj[2]));//returns [1, 3]
    console.debug('ans',shortAndLong(QAndAObj, QAndAObj[3]));//returns [1, 2]
    console.debug('ans',shortAndLong(QAndAObj, QAndAObj[4]));//returns [1, 1]
    

    The basics are

    1. Create a list of all paths through the graph, keeping the number of answers needed
    2. Find max and min