Question: Non-Redundant Edges in Connected Components
0
gravatar for Dario Strbenac
11 months ago by
Dario Strbenac1.4k
Australia
Dario Strbenac1.4k 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 • 301 views
ADD COMMENTlink modified 11 months ago by Hervé Pagès ♦♦ 13k • written 11 months ago by Dario Strbenac1.4k

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 11 months ago • written 11 months ago by nitesh.turaga140

That's right.

ADD REPLYlink written 11 months ago by Dario Strbenac1.4k
Answer: Non-Redundant Edges in Connected Components
1
gravatar for Hervé Pagès
11 months ago by
Hervé Pagès ♦♦ 13k
United States
Hervé Pagès ♦♦ 13k 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.

ADD COMMENTlink written 11 months ago by Hervé Pagès ♦♦ 13k

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.

ADD REPLYlink written 11 months ago by Dario Strbenac1.4k
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 16.09
Traffic: 165 users visited in the last hour