Algorithms in Gene

Although the bulk of Gene consists of uninteresting manipulation of data, various odd corners of the program (particularly its the user interface code) involve nontrivial algorithmic techniques. If interesting algorithms turn up here, they could turn up anywhere. So I am creating these pages as a showcase for the applications theoretical algorithms have as parts of a real-world application.

• Problem: center text accurately using space and option-space characters.
  Solution: an integer linear program closely related to Euclid's algorithm for GCD.
  
  
• Problem: quickly find the shortest connections between a given pair of people, for "Relations" tree drawing.
  Solution: backtracking search (implemented) or translation to a k-shortest-paths problem on a much larger graph (theoretical).

• Problem: look up and alphabetize a dynamically changing set of names.
  Solution: splay trees.
• Problem: search for substrings of names.
  Solution: Knuth-Morris-Pratt string matching.
• Problem: wrap text to fit into narrow columns in tree drawings.
  Solution: a linear time dynamic program.
• Problem: adjust widths of columns in tree drawings and recompute the total tree width.
  Solution: rake-compress trees.
• Problems: speed up scrolling and redisplay of tree drawings;
  quickly translate mouse clicks to active regions of drawings.
  Solution: interval trees.