Simple planar graph on 3 vertices demonstrting that "is_straight_line_drawing()" has a bug

is_straight_line_drawing.recreate.cpp

//=======================================================================
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
/*
f=is_straight_line_drawing.recreate
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f
cpplint --filter=-legal/copyright,-build/namespaces,-runtime/references $f.cpp
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config
*/
//=======================================================================
#include <cassert>
#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/ref.hpp>

#include <boost/graph/boyer_myrvold_planar_test.hpp>
#include <boost/graph/planar_canonical_ordering.hpp>
#include <boost/graph/is_straight_line_drawing.hpp>
#include <boost/graph/chrobak_payne_drawing.hpp>


using namespace boost;

// a class to hold the coordinates of the straight line embedding
struct coord_t {
    std::size_t x;
    std::size_t y;
};

int main(int, char**) {
    typedef adjacency_list< vecS, vecS, undirectedS,
        property< vertex_index_t, int >, property< edge_index_t, int > >
        graph;

    graph g(3);
    add_edge(0, 1, g);
    add_edge(2, 0, g);
    add_edge(1, 2, g);

    // Initialize the interior edge index
    property_map< graph, edge_index_t >::type e_index = get(edge_index, g);
    graph_traits< graph >::edges_size_type edge_count = 0;
    graph_traits< graph >::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
        put(e_index, *ei, edge_count++);

    typedef std::vector< std::vector< graph_traits< graph >::edge_descriptor > >
        embedding_storage_t;
    typedef boost::iterator_property_map< embedding_storage_t::iterator,
        property_map< graph, vertex_index_t >::type >
        embedding_t;

    embedding_storage_t embedding_storage(num_vertices(g));
    embedding_t embedding(embedding_storage.begin(), get(vertex_index, g));

    // Test for planarity one final time; compute the planar embedding as a
    // side-effect
    assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
            boyer_myrvold_params::embedding = &embedding[0]));


    // Create the planar embedding
    assert(boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
        boyer_myrvold_params::embedding = embedding));

    // Find a canonical ordering
    std::vector< graph_traits< graph >::vertex_descriptor > ordering;
    planar_canonical_ordering(g, embedding, std::back_inserter(ordering));

    // Set up a property map to hold the mapping from vertices to coord_t's
    typedef std::vector< coord_t > straight_line_drawing_storage_t;
    typedef boost::iterator_property_map<
        straight_line_drawing_storage_t::iterator,
        property_map< graph, vertex_index_t >::type >
        straight_line_drawing_t;

    straight_line_drawing_storage_t straight_line_drawing_storage(
        num_vertices(g));
    straight_line_drawing_t straight_line_drawing(
        straight_line_drawing_storage.begin(), get(vertex_index, g));

    // Compute the straight line drawing
    chrobak_payne_straight_line_drawing(
        g, embedding, ordering.begin(), ordering.end(), straight_line_drawing);

    straight_line_drawing[0].x = 4143438;
    straight_line_drawing[0].y = 86426;
    straight_line_drawing[1].x = 4064945;
    straight_line_drawing[1].y = 7932;
    straight_line_drawing[2].x = 4064944;
    straight_line_drawing[2].y = 7931;

    // Verify that the drawing is actually a plane drawing
    assert(is_straight_line_drawing(g, straight_line_drawing));

    return 0;
}

Recreate of issue with only three vertex planar graph:

hermann@7950x:~$ f=is_straight_line_drawing.recreate
g++ -O3 -Wall -pedantic -Wextra $f.cpp -o $f
cpplint --filter=-legal/copyright,-build/namespaces,-runtime/references $f.cpp
cppcheck --enable=all --suppress=missingIncludeSystem $f.cpp --check-config
Done processing is_straight_line_drawing.recreate.cpp
Checking is_straight_line_drawing.recreate.cpp ...
hermann@7950x:~$ ./is_straight_line_drawing.recreate 
is_straight_line_drawing.recreate: is_straight_line_drawing.recreate.cpp:101: int main(int, char**): Assertion `is_straight_line_drawing(g, straight_line_drawing)' failed.
Aborted (core dumped)
hermann@7950x:~$