Hi I'm trying to use BGL to build a layout for a graph. I have my own graph representation which is used to feed a boost graph which I intend to use to compute vertices positions. The positions will then be used to update my own graph representation. It works for some graph but for some others kamada_kawai_spring_layout never returns. So I think the code is ok But I Might have missed something when using kamada_kawai_spring_layout. Is it limited to some specific graph topologies ?!!! Some hints or help would be greatly appreciated. Thank you. Here after the relevant part of the code and the execution logs The log produced: NB DE VERTICES 10 NB DE EDGES 14 UNDIRECTEED NB DE VERTICES 10 UNDIRECTEED NB DE EDGES 13 vertex 32426192 is L1T1 boost id 0 nb edges 5 vertex 32429496 is L1T2 boost id 1 nb edges 4 vertex 32432404 is L1T3 boost id 2 nb edges 1 vertex 32434028 is L1T4 boost id 3 nb edges 1 vertex 32435652 is L1T5 boost id 4 nb edges 1 vertex 32438816 is L2T1 boost id 5 nb edges 2 vertex 32440868 is L2T2 boost id 6 nb edges 6 vertex 32445060 is L2T3 boost id 7 nb edges 2 vertex 32446684 is L2T4 boost id 8 nb edges 2 vertex 32448308 is L2T5 boost id 9 nb edges 2 edge from L1T1 to L2T1 edge from L1T1 to L2T2 edge from L1T1 to L2T3 edge from L1T1 to L2T4 edge from L1T1 to L2T5 edge from L1T2 to L1T3 edge from L1T2 to L1T4 edge from L1T2 to L1T5 edge from L1T2 to L2T2 edge from L2T1 to L2T2 edge from L2T2 to L2T3 edge from L2T2 to L2T4 edge from L2T2 to L2T5 BOOST GRAPH DESSCRIPTION using internal ids 0 <--> 5 6 7 8 9 1 <--> 2 3 4 6 2 <--> 1 3 <--> 1 4 <--> 1 5 <--> 0 6 6 <--> 0 1 5 7 8 9 7 <--> 0 6 8 <--> 0 6 9 <--> 0 6 BOOST GRAPH DESSCRIPTION using my ids 32426192 <--> 32438816 32440868 32445060 32446684 32448308 32429496 <--> 32432404 32434028 32435652 32440868 32432404 <--> 32429496 32434028 <--> 32429496 32435652 <--> 32429496 32438816 <--> 32426192 32440868 32440868 <--> 32426192 32429496 32438816 32445060 32446684 32448308 32445060 <--> 32426192 32440868 32446684 <--> 32426192 32440868 32448308 <--> 32426192 32440868 Computing circle_graph_layout Computing kamada_kawai_spring_layout <<<<< NEVER RETURNS The code: // TYPES DECLARATIONS AND INCLUDES #include <boost/utility.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/graph/random.hpp> #include <boost/pending/indirect_cmp.hpp> enum vertex_id_t { vertex_id = 500 }; enum edge_id_t { edge_id = 501 }; enum vertex_position_t { vertex_position = 502 }; namespace boost { BOOST_INSTALL_PROPERTY(vertex, id); BOOST_INSTALL_PROPERTY(edge, id); BOOST_INSTALL_PROPERTY(vertex, position); } struct point { double x; double y; }; #include <boost/graph/adjacency_list.hpp> typedef boost::adjacency_list< boost::vecS , boost::vecS , boost::undirectedS , boost::property<vertex_id_t, int , boost::property<vertex_position_t, point> > , boost::property<edge_id_t, int>

Graph; typedef boost::property<vertex_id_t, int> VertexId; typedef boost::property<edge_id_t, int> EdgeID;

#include <boost/graph/fruchterman_reingold.hpp> #include <boost/graph/random_layout.hpp> #include <boost/graph/kamada_kawai_spring_layout.hpp> #include <boost/graph/circle_layout.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/random/linear_congruential.hpp> // #include <boost/test/minimal.hpp> #include <iostream> #include <boost/limits.hpp> // CODE TO COMPUTE THE LAYOUT Extract::Graph gr; // this is my own graph representation // feeds gr .... std::cout << " NB DE VERTICES " << gr.Vertices.size() << std::endl; std::cout << " NB DE EDGES " << gr.Edges.size() << std::endl; if ( gr.Edges.size() ) { Graph g; // boost graph Extract::Graph::Undirected undirected_graph(gr); std::cout << " UNDIRECTEED NB DE VERTICES " << undirected_graph.Vertices.size() << std::endl; std::cout << " UNDIRECTEED NB DE EDGES " << undirected_graph.Edges.size() << std::endl; boost::property_map<Graph, vertex_id_t>::type vertex_id_map = get(vertex_id, g); // Add vertices to boost graph int vertex_internal_id = 0; for (Extract::Graph::Undirected::tVertices::iterator elt = undirected_graph.Vertices.begin() , stop = undirected_graph.Vertices.end() ; elt != stop ; ++elt) { // boost vertex are the same as index in set add_vertex( (int)elt->first // this the memory location of my own vertice data , g ); std::cout << " vertex " << (int)elt->first << " is " << elt->first->Name->get().c_str() << " boost id " << vertex_internal_id << " nb edges " << elt->second << std::endl; elt->second = vertex_internal_id; // use map for later edge addition => we associate internal data and boost vertices ids ++vertex_internal_id; } // Add edges to boost graph int current_edge_id = 0; for (Extract::Graph::Undirected::tEdges::iterator elt = undirected_graph.Edges.begin() , stop = undirected_graph.Edges.end() ; elt != stop ; ++elt) { add_edge( undirected_graph.Vertices[*elt->begin()] // use map to get the boost vertex_internal_id for first , undirected_graph.Vertices[*elt->rbegin()] // use map to get the boost vertex_internal_id for second , 1 , g ); std::cout << " edge from " << (*elt->begin())->Name->get().c_str() << " to " << (*elt->rbegin())->Name->get().c_str() << std::endl; } std::cout << "BOOST GRAPH DESSCRIPTION using internal ids" << std::endl; print_graph(g); std::cout << "BOOST GRAPH DESSCRIPTION using my ids" << std::endl; print_graph(g,vertex_id_map); std::cout << "Computing circle_graph_layout" << std::endl; boost::circle_graph_layout( g , get(vertex_position, g) , 10.0 ); std::cout << "Computing kamada_kawai_spring_layout" << std::endl; boost::kamada_kawai_spring_layout( g , get(vertex_position, g) , get(edge_id, g) , boost::side_length(50.0) ); // THE PROGRAM NEVER RETURNS HERE <<<<<<<<<<<<<<<<<<<<<<<<<< print_graph_layout( g , get(vertex_position, g) ); }