Basic Idea
Multiple Paths
Sequence Tuple
- Generate multiple possible sequences
- (Droplet, Path, Current Bifurcation, minSteps, maxSteps)
Algorithm to generate all possible sequences
- Start with Payload Droplet at last Bifurcation in its path
if headerDroplet needed:
for all possible header droplet paths:
add header droplet to list of sequenceTuples
add list of sequenceTuples to list of possible Sequences
Algorithm to generate all possible sequences
- List of possible Sequences
- { { (Pld, Path, currBif, 0,0),(Hdr-A, H-A-Path, curBif, minOffset-A, maxOffset-A)}
{ (Pld, Path, currBif, 0,0),(Hdr-B, H-B-Path, curBif, minOffset-B, maxOffset-B) } }
Algorithm to generate all possible sequences
- Ascend the Path recursively for every Droplet and decide at every Bifurcation if another heder droplet is needed
- This generates a (possibly huge) list of possibleSequences
Derive Droplet Sequence from list of possible sequences
- Not every entry in the list of possible sequences represents a feasible sequence (e.g. same start time for 2 droplets)
sort list of possible sequences according to their length
take shortest sequence
if sequence is feasible and droplets don't coalesce:
return found sequence
else:
move on to next sequence
Possible Improvements
- Performance !
- Recursion for finding possible sequences not implemented with good performance
- Check paths for header droplets that are likely to produce a short (with a lower amount of header droplets) sequence
- After all possible sequences for these few paths are found check for feasability and colesceing
- Just in case no sequence was found check the more complicated possible sequences
- No verfication yet (that the sequence really realizes the correct payload path)