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

[Tamás Nepusz]

One thing that would probably help with connectedness checking is knowing that 
by deleting an edge (A, B), the graph becomes disconnected if and only if A is 
not reachable from B any more. So, after deleting an edge (A, B), it is enough 
to check whether there is a path from A to B, it is not necessary to check the 
connectedness of the entire graph. Not sure whether it helps a lot, though, 
especially because igraph_shortest_paths only has a "from" argument in 0.5.4, 
"to" was added in 0.6 only (and it is not released yet).

-- 
T.


On 11 May 2011, at 21:10, Gábor Csárdi wrote:

> Well, yes. On a second thought, if you check for connectedness anyway,
> not to mention betweenness, after each deletion and addition, then
> igraph is good enough. The connectedness check has the same time
> complexity as edge addition/deletion, and betweenness is much worse.
> 
> I would suggest that you try profiling your code to see what takes long.
> 
> Gabor
> 
> On Wed, May 11, 2011 at 3:06 PM, Tamás Nepusz <address@hidden> wrote:
>>> I didn't know that igraph wasn't ideal for dynamical graphs. I used it 
>>> mainly cause I didn't had time to create my own library.
>> I just want to add that if your graph has only a couple of nodes as you 
>> mentioned (~20-50 vertices), then you're probably OK with igraph.
>> 
>> --
>> T.
>> 
>> 
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>> 
> 
> 
> 
> -- 
> Gabor Csardi <address@hidden>     MTA KFKI RMKI
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help
>