Software

Eulerian Circuit with Minimum Turning Cost - Given a connected graph and the cost/weight of each possible edge-turn, find an Eulerian circuit with a minimal weighting.

This problem is equivalent to the famed Traveling Salesman Problem (TSP) [HN-W65]. By converting the inputted graph G to a line graph L(G) (edges of G represented by vertices in L(G) and possible edge turns in G represented by edges in L(G)) our ECTC calculator program uses a modified version of the Bellman [Bel62] & Held-Karp [HeKa62] dynamic programming approach for the TSP to solve the ECTC problem.

The ECTC Project can be downloaded here (.zip folder, python implementation).

Building a structure using self-assembly of DNA molecules by origami folding typically requires finding a route corresponding to an Eulerian tour for a scaffolding strand through the desired structure. For the structure to be Eulerian, each vertex in the structure must be of even degree. The minimum weight matching problem may be used to find suitable augmenting edges.

A matching is a subset of edges in the graph such that any vertex is incident to at most one edge in the matching. A perfect matching is a matching such that every vertex is incident to exactly one edge in the matching. A perfect matching on the odd degree vertices of a target structure provides a set of augmenting edges to allow for an Eulerian route for the scaffolding strand.

The attached spreadsheet assigns weights to edges in the complement graph of the target structure based on their distance to the nearest integer and then finds a minimum weight perfect matching on the odd degree vertices. The user may override the edge costs if additional restrictions make the selection of particular augmenting edges more or less favorable.

The Matching spreadsheet can be downloaded here (.zip folder).

The Crystal Turtlebug program enumerates crystal nets (up to isomorphism). The program operates on a fragment of a Euclidean graph, with a symmetry group assigned to each vertex. The program expands the graph using the given symmetry operations, and then determines if the resulting structure is a crystal lattice (and returning the corresponding lattice basis if this is the case). For background on the algorithm see [MC11].

The program was written by Thomas Dickerson (Saint Michael's College) and Greg McColm (University of South Florida). It is designed to produce output data which is interoperable with standard crystallographic software packages such as Systre and TOPOS.

Crystal Turtlebug is available for download on SourceForge.

The Octet Truss Tile Finder enumerates the distinct branched junctions (tiles) existing as subsets of the octet truss. Uses orbits and stabilizers to verify the output, and can reduce any tile to its lexicographically minimal form.

Octet Truss Tile Finder is available for download on Google Code.