Re: [boost] Boost.Graph GSoC 2010

Subject: Re: [boost] Boost.Graph GSoC 2010
From: Cezary Bartosiak (cezary.bartosiak_at_[hidden])
Date: 2010-03-30 14:15:53

>
> 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
> interfaces.
>

I think they should have got non-iterator versions. It's worth pointing out
that we would like to have got a possibility of inducing generators on an
existing set of vertices. I think it could be less comfortable with
iterators than with functions like the existing *generate_random_graph*. So,
there are two options we could call generators - the first in which we have
got an empty graph on input and we have to indicate a count of vertices to
generate (or probability, it depends on algorithms), the second we have got
a graph with some set of vertices and we would like to add some edges. There
is also the third option, when we have got a graph with some set of vertices
and some set of edges. Unfortunately I think there is no good solution of
how the generators should behave in such situation. Let's assume that
someone wants to induce a path topology on a star graph. It's impossible
when we don't admit rewiring and/or removing any edges. I know this example
is nonsensical, but illustrates the problem. Users may expect the algorithm
to not modify their graph beyond the addition of edges. Taking this into
consideration I'm coming to a conclusion that we should let users induce
topologies only on graphs without edges. Or, to be more precise, if some
graph has got edges we shouldn't be concerned about them and return a new
graph with a set of vertices from the input graph and only generated edges.

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.

Well, that's true ;) By the way - I think this is a good idea to provide a
few algorithms for sparse and dense graphs apart from the existing
generators. They differ in complexity.

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?

For empty graphs it could be randomly chosen. For graphs on which we induce
topologies we could let a potential user choose it at random or to point the
concrete one out. The same concerns wheel graphs etc...

As for functions like *is_star*, *is_path*, *is_wheel* etc. I think we can
treat them as particular cases of *graphs' similarity* problem. At the
moment I am not able to point "ready-made" algorithms out. But I'll look for
them. As to functions like *is_smallworld*, *is_scalefree*, *is_erdosrenyi *I
think this is sufficient to count measures like *clustering coefficient* for
instance.

I'm curious to see your comments, suggestions. I look forward to hearing
from you.

On 24 March 2010 14:35, Andrew Sutton <andrew.n.sutton_at_[hidden]> wrote:

> 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
> interfaces.
>
> 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
> andrew.n.sutton_at_[hidden]
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>