Re: [Boost-users] graphlib changes in 1.40

Subject: Re: [Boost-users] graphlib changes in 1.40
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-10-08 13:41:04

On Thu, 8 Oct 2009, Ralph Gauges wrote:

> Jeremiah Willcock wrote:
>> On Thu, 8 Oct 2009, Ralph Gauges wrote:
>> 
>>> Hi,
>>> 
>>> I use the graph library in some of my programs and I recently moved to
>>> boost 1.40 because older version did not work on snow leopard.
>>> 
>>> I noticed that although the changelog does not mention any changes in
>>> the graph library, some of the layout algorithms have changes (e.g.
>>> random layout and fruchterman reingold)
>>> in the way they are called. They seem to use some new topology concept,
>>> unfortunately the documentation for those algorithms have not been 
>>> updated.
>>> 
>>> I was wondering if there is any updated documentation especially on the
>>> fruchterman reingold algorithm. I tried to guess what the new parameters
>>> mean, but so far I have not been able to
>>> get the same results as with the graph library from 1.39. No matter how
>>> I set the values so far, all my nodes end up essentially in the same
>>> place, although they are all disconnected and I would expect them to be
>>> spread out.
>> 
>> The new parameters should pretty much match up to the old ones except that 
>> the topology parameter allows a more general specification of your output 
>> region than a simple width/height pair (allowing more shapes, for example). 
>> There could be a bug if your are unable to reproduce the old behavior. 
>> What call were you using with the old version?  I will try to translate it 
>> over so you can test it out.
>> 
> Thanks for the fast response.
> In boost prior to 1.40 the called looked like this:
>
>           boost::fruchterman_reingold_force_directed_layout
>               (this->mGraph,
>                boost::get(vertex_position_t(),this->mGraph),
>                sidelength,
>                sidelength);
>
> For now I was restricting the call to a square and the nodes in the graph 
> were all disconnected, so there should only be repulsive forces.
>
> Now I tried to do the same thing using a topology;
>                     boost::rectangle_topology<> 
> topology(0.0,0.0,sidelength,sidelength);
>           boost::rectangle_topology<>::point_type origin;
>           origin[0]=0.0;
>           origin[1]=0.0;
>           boost::rectangle_topology<>::point_difference_type extent;
>           extent[0]=20.0;  // I also tries sidelength instead of 20.0
>           extent[1]=20.0;
>
>           boost::fruchterman_reingold_force_directed_layout
>               (this->mGraph,
>                boost::get(vertex_position_t(),this->mGraph),
>                topology,
>                origin,
>                extent
>               );
>
> I guess the topology has the same role as the width and height argument in 
> the older version, but I do not know what "origin" and "extent" since they do 
> not seem to have a correspondence in the old version.
> I tries to interpret extent as the extend of the area which would actually be 
> redundant information since this is already specified in the topology. Next I 
> thought it might be the width and the height of a node, but changing the 
> values did not seem to make a difference.
>
> I also tried to move the origin from 0.0,0.0 to the center of the box etc, 
> but the nodes were always all clustered around the origin with minimal 
> deviations in their position.
>
> I also tried to set the attractive and repulsive forces to some constants, 
> but that also did not seem to make a difference in the result.
>
> So essentially I just don't know what origin and extent are since the old 
> version did not seem to have corresponding parameters.

Origin and extent are redundant for the topology you have chosen, but are 
not in all topologies.  Try setting both origin and extent to 
topology.center() and see if that fixes your issue.

-- Jeremiah Willcock