In this WWW page we show some of of the solutions delivered by each heuristic discussed in the paper. These have been obtained by running the different algorithms on the airfoil1 graph, for which we have information on the coordinates of its nodes. By painting its edges in different colors according to their individual cost, the viewer can have a visual idea on the power and limitations of each heuristic method.
Edges are painted in the following way: red edges have a cost greter than 250; orange edges have cost between 100 and 250; green edges have a cost between 50 and 100; and blue edges have at most cost 50. The cost of an edge e=uv in a layout f corresponds to |f(u)-f(v)|.
Please click on the pictures to see them in full size!
- The original graph: airfoil1 is made up of 4253 nodes,
12289 edges and has diameter 64. This graph is a mesh used in FE methods.
The best layout found in this layout has cost 285231.
- A random layout.
Cost: 17174118
- The normal layout.
Cost: 407921
- The successive augmentation heuristic with a random initial ordering of nodes. (gre)
Cost: 11755558
- The successive augmentation heuristic with a random-breadth initial ordering of nodes. (rbs)
Cost: 2408682
- The successive augmentation heuristic with a breadth-first search initial ordering of nodes. (bfs)
Cost: 713039
- The successive augmentation heuristic with a depth-first search initial ordering of nodes. (dfs)
Cost: 741733
- Hillclimbing on the FlipE neighborhood. (hillcE)
Cost: 10781712
- Hillclimbing on the Flip2 neighborhood. (hillc2)
Cost: 1191184
- Hillclimbing on the Flip3 neighborhood. (hillc3)
Cost: 1933272
- Spectral sequencing. (spec)
Cost: 352682
- Three phases of simulated annealing (sa) [begining, middle, end].
Final cost: 292777
- A random layout.