# Algorithm for finding optimal branch points

I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd like to minimize the amount of duplicate processing required. For example, if variations occur at step B, I could run step A one for all results before "branching" at step B (see #2 below). Similarly, I could branch again at step D if additional variations on step D are indicated (see #3 below).

1) Base Process:

input --> A --> B --> C --> D --> E --> result


2) Modification of Step B:

input --> A --> B1 --> C --> D --> E --> result1
B2 --> C --> D --> E --> result2


3) Modification of Steps B and D:

input --> A --> B1 --> C --> D1 --> E --> result1
D2 --> E --> result2
B2 --> C --> D1 --> E --> result3
D2 --> E --> result4


Is there a simple algorithm to determine the the common process steps and the branch points as in #3 given a base flow as in #1 and a list of steps to change, e.g.

Variation  StepB  StepD
1         1      1
2         1      2
3         2      1
4         2      2


The above example is simple but there could be hundreds of variations modifying dozens of different steps in actual usage.

• If, as your question seems to imply, you can represent your process flows as strings, you are looking for common substrings, which would represent common steps in your flows. Maybe suffix trees could help. – didierc Feb 18 '13 at 21:41
• Interesting tack... in the code the process flows are represented as Xml structures, but that could easily be reduced down to strings. I need to do some research on suffix trees but it does looks like a promising approach. – jasonm76 Feb 19 '13 at 14:03
• stackoverflow has many good questions and answers on that topic. – didierc Feb 19 '13 at 23:11

If whatever happens after $B$ depends on that, you can't "reuse" any runs after a modified $B$. So the tree-like scheduling is really the best that can be done.
• Misunderstood then... If you get each schedule as a list like $A_1 B_5 C_1 D_3 \ldots$ it would be enough just to get the list of schedules and sort them lexicographically, and then go through the list and see where each differs from the next. Need to keep the intermediate results up to where we are now in left-to-right order, and start from the correct point. – vonbrand Feb 19 '13 at 14:56