Question: Non-Redundant Edges in Connected Components
0
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 <- 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  "C"$B
 "D" "E"

$C  "B" "D"$D
 "E"

$E  "A" "B"$F
character(0)

$G  "H"$H
 "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  "C" "E"$B
 "D" "E" "C"

$C  "B" "D" "A"$D
 "E" "B" "C"

$E  "A" "B" "D"$F
character(0)

$G  "H"$H
 "G"


That's right.

Answer: Non-Redundant Edges in Connected Components
1
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.