[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] how do you check for connectedness?
From: |
Figa Pelosa |
Subject: |
Re: [igraph] how do you check for connectedness? |
Date: |
Tue, 17 Nov 2009 10:31:30 +0000 (GMT) |
thanks!
--- Mar 17/11/09, Tamas Nepusz <address@hidden> ha scritto:
> Da: Tamas Nepusz <address@hidden>
> Oggetto: Re: [igraph] how do you check for connectedness?
> A: "Help for igraph users" <address@hidden>
> Data: Martedì 17 novembre 2009, 10:08
> > I'm writing a little program in
> matlab and I'd need to check if a graph is connected.
> > What I do now is basically an iteration on the
> exponentiation of the adjacency matrix: I do that until two
> subsequent steps produce equal results and then I check if
> every node is connected to other nodes.
> >
> > It's quite a slow tecnique, so I was wondering if in
> iGraph (which can do this check pretty fast) you use a
> different method.
> We use a breadth-first search starting from vertex zero and
> we keep track of the number of visited vertices (see
> http://en.wikipedia.org/wiki/Breadth-first_search). If
> the BFS queue becomes empty and the number of visited
> vertices is less than the number of vertices in the graph,
> then there exists at least a single vertex which is not
> reachable from vertex zero, hence the graph is not
> connected. Otherwise it is connected (weakly).
>
> --
> Tamas
>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>