[Boost-users] BGL newbie kamada_kawai_spring_layout never returns

From: Eric B (eric.britz_at_[hidden])
Date: 2008-07-30 05:56:25

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)
       );
   }