Algorithm for survey flow

Question

I have to code a tool which will allow business users to create a survey. Some questions should only be asked if the person filling the survey answered the previous questions in a specific way. But some questions should be displayed, whatever the chosen answer is.

Thus far, I came up with a graph structure, here is a theoretical example of what it would look like:

(I only have a basic knowledge of graph theory so please excuse the choice of word which might not be as accurate as it could be)

The rounds like A,B,C represent questions and the value on the links represent the precondition to access the question.

NULL means that there are no precondition and a value like "0" or "1" means that the previous question must have an answer with the value "0" or "1" to display the question.

Concrete example: I'm at round A. I have two possible answer. The first one has a value of "0". The second, a value of "1". If I choose the answer with value "0" then I will go to question B.

I'm now at round B. Whatever the answer is, I will go to round E because there are no precondition.

E is a leaf node, so I go back to B. B has another child node F with no precondition so I move to question F. Let's end the flow there.

I can also have one question that has multiple precondition. This is represented by question N. It can only be accessed if the answer is "5" on question F and "DE" on question I. In this case, after answering question F, since only one precondition is valid at this state, we will go back up in the graph and it's only after answering "DE" on question I that we can then move to question N.

My question is about the algorithm to use for such a survey. Is there an existing algorithm covering this use case ? I thought this looks like a DFS graph traversal but the conditionals make me doubt.

Also, am I overcomplicating things and can this be expressed much more simply ? I'd really like some advice at this stage.

Thanks for your help !

Answer 1

According to your description, I would change slightly the concept of the graph you have proposed to the following:

• Make it into a directed graph (that is, a graph where each arc has a source and a target).
• Have one node per question and one node per answer (each answer of each question is a different node). Each question node would need to have one flag to determine whether it is "question type" or "answer type" and one flag to mark whether it has been visited.
• Each question node would be connected to each of its answers (direction [Question] -> [Answer]).
• Each answer precondition ("to reach question B you need to answer 0 in question A") would be represented by an arc from one answer (node [Answer 0 of question A]) to the question it "unlocks" (node [Question B]). If a question requires several answers, it would have several incoming arcs.
• Each question precondition ("to reach question D you need to answer to question A, no matter the choice") would be represented by an arc from one question (node [Question A]) to another question (node [Question D]).

Then the algorithm would go along the following lines:

1. Have a stack of pending nodes P which initially contains the node corresponding to the first question of the survey.
2. Pop the first element of P, Q, which should always be a question node, and mark it as visited.
3. Get the list of successors of Q (nodes that are connected to the current node through an outgoing arc) and split it into "answer successors", QtoA, and "question successors", QtoQ.
4. Add all the elements in QtoQ to P (if there is any way to have these ordered, such as by some "question id", make sure, they are added in a way that the first element ends on top of the stack).
5. Ask the question (you could even store the questions in the graph and retrieve all the information that you need from it).
6. Get the node of the chosen answer A from QtoA, mark it as visited and collect the list of all of its successors in turn, AtoQ.
7. For every node R in AtoQ (again, consider ordering here if there is any), if all of the predecessors of R (i.e. the nodes connected to R through an incoming arc) are marked as visited, then add R to P.
8. If there are any nodes in P go to step 2.

This should reproduce the order that you describe. If you want to have the ability to have several possible unlocking answers (e.g. "from A you would go to B if you answer 1 or 2") you would need to do some more tweaking (namely, in step 6 you would need to replace the "visited" check for "answer type" predecessors of R to something like "R is reachable through visited nodes from the predecessor of the predecessor of R"), but it should still be possible to get it to work.

Maybe you already know about it, but if you are interested in using a graph as your only data source (which may or may not be the case), you might find interesting graph-oriented databases like Neo4j.