[Boost-users] [Graph] Defining coordinates for vertices

Subject: [Boost-users] [Graph] Defining coordinates for vertices
From: Maxime van Noppen (maxime_at_[hidden])
Date: 2009-07-15 04:56:05

Hi,

I can't figure out if it is possible (and if it is, how) to assign
coordinates to graph vertices on planar graphs. I've tried setting the
property vertex_index_t to std::pair<int, int> but it doesn't seem to
work (make_maximal_planar doesn't use them for example).

I'm trying to represent a 2D terrain via a triangular mesh. So far it is
easy : I add all the points of the mesh as vertices and create the
appropriated edges. But now I'm trying to make this graph evolve,  which
means adding new vertices (at some precise coordinates) and having them
automagically linked to all other vertices possible while keeping the
graph planar.

This is what I do for now but that doesn't work (full source code is
attached) :

------------------
typedef adjacency_list< vecS, vecS, undirectedS, property<
vertex_index_t, std::pair<int, int> >, property<edge_index_t, int> >
graph_t;
typedef graph_traits<graph_t>::edge_descriptor edge_t;
typedef graph_traits<graph_t>::vertex_descriptor vertex_t;

// Create the graph
graph_t g;

// Add the three vertices of a triangle
add_vertex(std::make_pair(0, 0), g);
add_vertex(std::make_pair(10, 0), g);
add_vertex(std::make_pair(5, 10), g);

// Create the three edges
add_edge(0, 1, g);
add_edge(0, 2, g);
add_edge(1, 2, g);

// Add some random points
add_vertex(std::make_pair(5, 5), g);
add_vertex(std::make_pair(0, 5), g);

// The goal is now to make g planar w.r.t. the coordinates

// 1- Either make_connected or add at least one edge to make the graph
//    connected

// 2- make_biconnected_planar

// 3- make_maximal_planar
------------------

The input graph is (using boost::print_graph) :

0 <--> 1 2
1 <--> 0 2
2 <--> 0 1
3 <-->
4 <-->

The output graph is :

0 <--> 1 2 3 4
1 <--> 0 2 3
2 <--> 0 1 3 4
3 <--> 2 4 0 1
4 <--> 3 2 0

It isn't palanar w.r.t. the given coordinates because 3 can't be
connected with 4 without crossing one of the edges of the triangle (3 is
supposed to be inside the triangle whereas 4 is outside).

I suppose that either I'm doing something wrong or that it might not be
possible to use the library this way.

Any help appreciated,

Thanks !

-- 
Maxime