Re: [igraph] nb of links of the bipartite graph of two given subgraphs

[Gábor Csárdi]

Hi,

here is what I would try first. Create a boolean vector and mark the
vertices in your first set. Then go through all adjacent vertices to
the vertices in your second set and check whether they are marked. The
time complexity for this is O(n+m), linear in the number of vertices
and edges.

Best,
Gabor

On Wed, Feb 2, 2011 at 6:58 PM, sergiu netotea <address@hidden> wrote:
> Hi,
>
> What is the fastest test in igraph to check if two vertices are
> linked? I ask because I have two vertex sets and I want to count
> something like the number of links between the two sets. Perhaps one
> could call such a monster the bipartite graph of two given subgraphs.
> Or is there already a way to compute such a graph directly, eg by a
> function call or a number of function calls, like graph
> unions/intersections? I understand there is no support for bipartite
> graphs yet, but in this setup the the so called bipartite graph would
> be a subgraph itself, of the big graph that contains the vertex sets
> in question. Even speedier wold be for me to at least say if there is
> AT LEAST one link between the two vertex sets, although the total
> number would be better to have. I have to do this fast and for many
> times (many pairs of subgraphs).
>
> Any help, ideas or simple encouragements would be kindly appreciated,
> Sergiu
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM