planar_face_traversal fails miserably on a planar, 3-connected graph

[julian.pfeifle@…]

Input is the graph of a cube with a triangular prism attached. Output of the traversal is bizarre.

[julian.pfeifle@…]

minimal .cc program to reproduce the bug

[expaler]

Modified program that properly initializes the edge index map.

[expaler]

The algorithm requires an edge index map that already associates edges with distinct integers. Simply defining an internal edge index map in the adjacency list type is not enough. You must update the edge index map as you add edges to the graph. The planar_face_traversal_nab.cc file shows the fix to your program. The output is now:

New face: 1 0 8 9 visitor done. New face: 0 1 7 6 visitor done. New face: 3 2 4 visitor done. New face: 2 3 6 5 visitor done. New face: 4 2 5 7 visitor done. New face: 3 4 9 8 visitor done. New face: 0 6 3 8 visitor done. New face: 5 6 7 visitor done. New face: 7 1 9 4 visitor done.