Re: [Boost-users] [Graph] kamada_kawai_spring_layout runs forever

From: Mortoc (Mortoc_at_[hidden])
Date: 2006-08-16 13:47:51

Hi Sebi,

I think your problem is that all your verticies are at the same location.
>From the documentation:

" Prior to invoking this algorithm, it is recommended that the vertices be
placed along the vertices of a regular n-sided polygon via
circle_layout<http://www.boost.org/libs/graph/doc/circle_layout.html>.
"

-Chris

On 8/16/06, Sebi <sebi_at_[hidden]> wrote:
>
> 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";
>    }
> }
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>