[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Rewiring connected graph and/or checking connectedness loca
From: |
Tamás Nepusz |
Subject: |
Re: [igraph] Rewiring connected graph and/or checking connectedness locally |
Date: |
Wed, 11 May 2011 21:13:13 +0200 |
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
>