[igraph] Rewiring connected graph and/or checking connectedness locally

[Rafael Calsaverini]

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