Eulerian Circuits with Turning Costs

A turning cost is the cost associated with traversing from one edge of a graph to another. This program is designed to find an optimal Eulerian tour through a graph where a tour is considered optimal if the total turning cost is minimized.

These Eulerian tours could be used to find threading sequences that would be used to create 2-dimensional and 3-dimensional nanostructures out of DNA.

This problem is unfortunately NP-Hard [Ell2+] but small instances, like those that are encountered in some threading problems, may be tractable in practice.

We adapted the Held-Karp dynmaic programming algorithm for solving the traveling salesman problem [HeKa62] to this problem. Dynamic programming is a method of problem solving that breaks a larger problem into smaller ones and then uses the smaller problems' solutions to recursively solve incrementally larger problems.

This program was written by Samuel Blakely and Mary Falcigno. It uses Python (2.6 and 2.7 both work) and requires the Networkx packacge (version 1.7).

The inputs for the program are an edge list and a turning cost matrix A, where each entry A_i,j represents the cost for traveling from edge i to edge j. If a turn does not exist, its cost entry in the matrix is given a value of -1. We also provide a utility program called createCostMatrix that generates a basic cost matrix where all impossible turns are given a cost of -1 and all other turns are given a cost of 0. From there, the user can weight the turns whose costs are 0 with any other positive turn cost value.

The Algorithm

Let n be the number of edges, the starting edge being 0, and the set of edges S={1...n}. We then name the weight of the turn between two edges i and j as w(i,j). Lastly, let C(S,ℓ) equal the total cost of traversing all edges in set S, starting at edge l and ending at edge 0.

These give our base and recursive cases for C(S,ℓ):

If |S| = 1, then

C({ℓ}, ℓ) = w(ℓ,0)

If |S| > 1, then

C(S,ℓ) = min_m∈S-ℓ [C(S-{ℓ},m) + w(m,ℓ)]

Once we have all C(S,ℓ) such that |S|=n, then the program concludes that the S which yields the minimum total turning cost is the optimal tour.

Our program starts off with a set S of size 1 and incrementally increases until the size of S equals the number of edges. For each size of S, the program generates the various possible sets S. The program builds the possible sets S from the edges given, taking edge 0 to be the starting edge and starting with S of size 1. In the first iteration, every S created contains one of the edges incident to the starting edge. Then, the program concatenates edges to each S to make each S contain a possible minimum Eulerian path of length 2. This is continued until the length is equal to the number of edges, n.

As these sets S are built, the turning costs for traversing each path is totaled. The turning costs for going from the starting edge to the first edge in S and for going from the last edge in S to the starting edge, completing the circuit, is added to the total turning cost for traversing the edges in S. Finally, whichever set yields the smallest total turning cost is returned as the optimal tour along with what the value of the minimum cost is.