Boost logo

Boost :

Subject: Re: [boost] Boost.Graph GSoC 2010
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-03-24 08:35:03

Hi Cezary,

I've got an idea related to the Topology Generators. I have participated in
> a project concerning epidemics spreading and, as a part of the project, we
> have implemented several social networks generators (Barabási–Albert model
> for instance). I hit upon an idea to implement these algorithms apart from
> proposed topology generators.

I think that this is a nice complement to work I did a couple of years ago.
I would certainly like to see the BGL usable for social network analysis.

> I know that Boost.Graph contains some algorithms for generating networks, I
> would like to add some extensions:

In fact, some of the generators that you mentioned. Erdos-Renyi, PLOD.
However, I'm not a huge fan of their interfaces. I'm not sure why there was
a need to build them as iterators. How do you think you could improve their

For the record, the two Erdos-Renyi generators are actually equivalent.
There's a relatively simple mathematical correspondence, but I forget what
it is :) They should generate graphs with the same basic measures.

> Coming back to Topology Generators I would implement them for some "basic"
> topologies, let's say: path, star, cycle, wheel, ladder, grid, hypercube,
> barbell, complete, frucht and many others if time remains...

> I would be glad to know your opinion.

The "easy" ones :) I did some very preliminary work on these also. Did you
have any thoughts on how you might implement these? How might you specify,
for example, which vertex represented the center of a star graph?

Andrew Sutton

Boost list run by bdawes at, gregod at, cpdaniel at, john at