Question: Non-Redundant Edges in Connected Components
0
14 months ago by
Dario Strbenac1.5k
Australia
Dario Strbenac1.5k wrote:

The connectedComp function determines a list of vertices that belong to a connected component. Is there a quick way to determine the non-redundant edges (i.e. not both A ⇔ B and B ⇔ A but one of these) in each connected component so that correlations (e.g. between pairs of protein measurements) may efficiently be calculated?

rbgl • 341 views
modified 13 months ago by Hervé Pagès ♦♦ 14k • written 14 months ago by Dario Strbenac1.5k

Hi Dario,

Maybe you can explain the problem to me a little more.

I'm trying to follow the example in the connectedComp help page. This is the graph the example mentions 

     con <- file(system.file("GXL/kmstEx.gxl",package="graph"), open="r")
km <- fromGXL(con)
close(con)
km <- graph::addNode(c("F","G","H"), km)
km <- addEdge("G", "H", km, 1)
km <- addEdge("H", "G", km, 1)


When I take a look at the edges() in the graph km, I only see the non redundant connections.

> edges(km)
$A [1] "C"$B
[1] "D" "E"

$C [1] "B" "D"$D
[1] "E"

$E [1] "A" "B"$F
character(0)

$G [1] "H"$H
[1] "G"


Only the list produced by the edges(ugraph(km)) function gives me redudant information. Am i understanding you question correctly?

> edges(ugraph(km))
$A [1] "C" "E"$B
[1] "D" "E" "C"

$C [1] "B" "D" "A"$D
[1] "E" "B" "C"

$E [1] "A" "B" "D"$F
character(0)

$G [1] "H"$H
[1] "G"

ADD REPLYlink modified 13 months ago • written 13 months ago by nitesh.turaga140

That's right.

Answer: Non-Redundant Edges in Connected Components
1
13 months ago by
Hervé Pagès ♦♦ 14k
United States
Hervé Pagès ♦♦ 14k wrote:

Hi Dario,

Here is a fast solution based on an unexported utility defined in the S4Vectors package:

connectedCompEdges <- function(concomp)
{
hits <- S4Vectors:::makeAllGroupInnerHits(lengths(concomp), hit.type=1L)
nodes <- unlist(concomp, use.names=FALSE)
from <- nodes[queryHits(hits)]
to <- nodes[subjectHits(hits)]
data.frame(from, to)
}


Call this on the list of components returned by RBGL::connectedComp().

H.

A simpler solution is to use the igraph package and use the induced_subgraph function with a vector of vertices belonging to a connected component to create a graph of the connected component. Then, the as_edgelist` function converts the graph into a 2-column matrix of edges defining the connected component.