Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

If the later steps are independent of (some) of the previous steps, things get more interesting... but that presumes you have a completely reliable way of determining that. The simplest way to get the most efficient runs without too much extra work in this case would be just to store away the results of all runs, and instead of running any of them first check if the result is already stored (memoisation). Might need to supplement with some logic to clean up (delete results that won't be used ever again, or use some heuristic to delete them).

share|improve this answer
    
Thanks... The steps are dependent on one another, each taking the output of the preceding step and doing additional work. I'm trying to determine how to actually create the tree-like schedule based on the inputs. –  jasonm76 Feb 19 '13 at 13:58
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.