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

[Gábor Csárdi]

Rafael,

igraph is not very good for dynamic graphs, removing or adding an edge
has the same cost, as recreating the graph from scratch.

You could try using adjacency lists instead of igraph graphs, if you
don't need to call any igraph functions to calculate properties of
your graphs while doing the MC. This also means that you'll need to
write your own function that checks for connectedness, but this is not
very hard, a DFS of BFS will do.

There is a measure that you could use for deciding whether the graph
will be connected, if you remove any single edge from it. It is called
edge connectivity. Unfortunately, it is expensive to calculate it, and
it is cheaper to actually remove the edge and check that the graph is
connected.

Or, theoretically you could also check the biconnected components in
your graphs, removing and edge from a biconnected component keeps that
component connected. But again, I think this will take more time to
maintain than just checking connectedness.

Best,
Gabor

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
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>
>



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI