Partial validation of a complex series of conditions.

Question

I am currently in the process of working on an scheduling application and have run into a small snag. Because the field is heavily regulated for safety reasons the software is required to check a number of interdependent conditions to ensure a trip is possible. Instead of a nice tree of conditions - which would be simple to implement - I have this hideous directed graph. Now for the most part this wouldn't be difficult at all except for the fact I may not know all the information required in advance but still need to perform as much of the validation as possible.

I could implement this as a rat's nest of if/else statements but that would be a maintainability nightmare since the regulations change on a fairly regular basis. Since there are no cycles in the graph I'm thinking that some form of breadth-first approach is probably optimal. Am I on the right track? Are there any other alternative techniques for performing this kind of task?

Answer 1

The solution depends completely on what the directed acyclic graph (DAG) you speak of actually represents. Are the nodes AND and OR nodes, or are they conditional braches?

If they are conditional branches you don't need any breadth-first search because there is nothing to search for; you just take the branches according to the evaluated conditions. Yes, it could be easily implemented as a GOTO spaghetti. Another option is to create a database of the nodes (or a datastructure) and have a "virtual machine" which executes through the nodes one by one. This makes it more maintainable but also slower.

If it is an AND/OR/NOT graph then you need to evaluate the truth values for the nodes starting from the leaves. This is not breadth-first search, but kind-of reverse breadth first approach. You calculate the values for the leaves and then calculate the values of the internal nodes backwards; eventually you get an evaluation of the root node (true / false).

Answer 2

Sounds like you are trying to solve a common compilation problem called '[constant folding][1]'. (http://en.wikipedia.org/wiki/Constant%5Ffolding).

The good new is that it applies to DAGs (direct acyclic graph) and not just to trees. Basically the idea is to compute what you can from partial expressions. Things as simple as True AND X = X, or True OR X = True help pruning large parts of the tree. (The trivial implementation I know of is a matter of depth-first and backtracking more than breadth-first, but anyway it's not much code).

I still wonder why you got a graph an not an expression tree. If you can compute A from B or B from A you usually do not have both A and B as input at the same time. Then it should be possible to express the problem like a set of expression trees depending on available inputs. But it's raw guess. Can you give more details (exemple) on why you have this graph ?