On Tue, May 10, 2011 at 3:22 PM, Rafael Calsaverini
<
address@hidden> wrote:
> Hi,
> I am working on a monte carlo simulation of a system whose state is
> described as a graph. At every step of the simulation I must generate a new
> set of edges for the graph based on it's last state and accept or not the
> new configuration based on some criteria. The problem is that I
> must guarantee that the graph remain connected at each step.
> The way I'm doing this now is by brute force:
> - select a random pair of vertices;
> - if there's not an edge between them, create one.
> - if there is an edge between them, remove it and check if the graph
> remains connected.
> - if it does, then proceed, if it doesn't, put the edge back and try
> another pair.
> This works for my purposes, but the problem is that the last step is too
> expensive. There's a phase in the model where the graph is almost fully
> connected and it's very improbable that removing an edge will divide the
> graph in two components. There's another phase in which the graph resembles
> a star, and almost any edge I try to remove will make the graph not
> connected, so I keep removing edges and putting them back for a long time.
> My question are:
> is there a different way to do this?
> is there any function in igraph that will rewire the graph and keep it
> connected?
> is there any way to check locally if removing a given edge will separate the
> graph in two components?
> My graphs are not big (20 to 50 vertices, from a few edges to fully
> connected), but I have to repeat the monte carlo steps many, many, many
> times...
> Thanks in advance for the help
> ---
> Rafael Calsaverini
> Dep. de Física Geral, Sala 336
> Instituto de Física - Universidade de São Paulo
>
>
address@hidden
>
http://stoa.usp.br/calsaverini/weblog
> CEL: (11) 7525-6222
> USP: (11) 3091-6803
>
>