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
    1. Check paths for header droplets that are likely to produce a short (with a lower amount of header droplets) sequence
    2. After all possible sequences for these few paths are found check for feasability and colesceing
    3. 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)