Question

Non-Redundant Edges in Connected Components

0

Entering edit mode

Dario Strbenac ★ 1.5k

@dario-strbenac-5916

Last seen 4 days ago

Australia

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 • 1.4k views

ADD COMMENT • link updated 6.6 years ago by Hervé Pagès 16k • written 6.6 years ago by Dario Strbenac ★ 1.5k

0

Entering edit mode

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 REPLY • link 6.6 years ago nitesh.turaga ▴ 140

0

Entering edit mode

That's right.

ADD REPLY • link 6.6 years ago Dario Strbenac ★ 1.5k

score 1 · Answer 1 · 2018-06-01

1

Entering edit mode

Hervé Pagès 16k

@herve-pages-1542

Last seen 6 days ago

Seattle, WA, United States

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 COMMENT • link 6.6 years ago Hervé Pagès 16k

0

Entering edit mode

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 REPLY • link 6.6 years ago Dario Strbenac ★ 1.5k