Boost C++ Libraries: Ticket #5121: planar_face_traversal fails miserably on a planar, 3-connected graph

attachment set

julian.pfeifle@… — Tue, 25 Jan 2011 14:47:33 GMT

attachment → planar_face_traversal_bug.cc

minimal .cc program to reproduce the bug

attachment set

expaler — Sun, 06 Mar 2011 16:49:00 GMT

attachment → planar_face_traversal_nab.cc

Modified program that properly initializes the edge index map.

expaler — Sun, 06 Mar 2011 16:54:22 GMT

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.

status changed; resolution set

expaler — Sun, 06 Mar 2011 16:55:40 GMT

status new → closed
resolution → invalid