[Boost-users] [Graph] kamada_kawai_spring_layout runs forever

From: Sebi (sebi_at_[hidden])
Date: 2006-08-16 08:54:15

hello,

i'm trying to use the boost graph libarary to layout a small (< 10  
nodes), fully connected, undirected graph.
the problem is, that the kamada_kawai_spring_layout() function never  
returns. when i comment out the code to set the weights for my graph  
it works, but then it is of course not of much use for me.

below is the sourcecode i came up with. as i said, when i comment out  
the line
        put(weightMap, e, 1.0);
it works (i.e. the program finishes after a short time) and all nodes  
are at the same location
i think the problem could be the way i connect the nodes, which is  
quite clumsy here. maybe someone has a better idea how to accomplish  
this.

regards and thanks in advance,
sebastian mecklenburg

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/graph_traits.hpp"
#include "boost/graph/kamada_kawai_spring_layout.hpp"
#include <iostream>

using namespace boost;

enum vertex_position_t { vertex_position };
namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }

struct pos
{
   double x;
   double y;
};

typedef adjacency_list<listS, listS, undirectedS,
                          // Vertex properties
                          boost::property<boost::vertex_index_t, int,
                          boost::property<vertex_position_t, pos> >,
                          // Edge properties
                          property<edge_weight_t, double> > WUGraph;
typedef graph_traits<WUGraph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<WUGraph>::edge_descriptor edge_descriptor;

int main(int argc, char *argv[]) {
        int numNodes = 5;				
        
        WUGraph ug;
        for(int i = 0; i < numNodes; ++i) {
                vertex_descriptor u = boost::add_vertex(ug);
                boost::put(vertex_index, ug, u, i);
        }
        graph_traits<WUGraph>::vertex_iterator vi, vi_end;
        graph_traits<WUGraph>::vertex_iterator vj, vj_end;
        
        boost::property_map<WUGraph, vertex_index_t>::type indexMap = get 
(vertex_index, ug);
        boost::property_map<WUGraph, edge_weight_t>::type weightMap = get 
(edge_weight, ug);
        for (tie(vi, vi_end) = vertices(ug); vi != vi_end; ++vi) {
                for (tie(vj, vj_end) = vertices(ug); vj != vj_end; ++vj) {
                        int i1 = get(indexMap, *vi);
                        int i2 = get(indexMap, *vj);
                        if(i1 < i2) {
                                edge_descriptor e = add_edge(*vi, *vj, ug).first;
                                put(weightMap, e, 1.0);
                        }
                }
        }
        boost::kamada_kawai_spring_layout(ug,
                                        get(vertex_position, ug),
                                        get(edge_weight, ug),
                                        side_length(50.0));
        
        boost::property_map<WUGraph, vertex_position_t>::type positionMap =  
get(vertex_position, ug);
        for (tie(vi, vi_end) = vertices(ug); vi != vi_end; ++vi) {
     std::cout << "  n" << get(vertex_index, ug, *vi) << "[ pos=\""
         << (int)positionMap[*vi].x + 25 << ", " << (int)positionMap 
[*vi].y + 25
         << "\" ];\n";
   }
}