0

Given a vertex v1, how can I get the vertex v2 whose edge (v1,v2) has the maximum weight?

My approach to the problem is this one:

library(igraph)
maxEdge = max(E(g)[from(id)]$weight
which(E(g)$weight==maxEdge))

But I don't know how to get the vertex ID. Any ideas?

Minimal example data

library(igraph)

g1 <- graph.full(5)
V(g1)$name <- 1:5    
g2 <- graph.full(5)
V(g2)$name <- 6:10
g3 <- graph.ring(5)
V(g3)$name <- 11:15
g <- g1 + g2 + g3 + edge('1', '6') + edge('1', '11')
V(g)$name <- letters[1:vcount(g)]
# Random data
set.seed(ecount(g))
E(g)$weight <- runif(ecount(g))

maxEdge = max(E(g)[from(1)]$weight)
idEdge = which(E(g)$weight==maxEdge)

My approach get the edge id (idEdge). However, want get the vertex ID!

For instance:

V(g)
[1] "a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m" "n" "o"

E(g)[from("a")] -> $weight
[1]  b -- a -> 0.97175023
[2]  c -- a -> 0.08375751
[3]  d -- a -> 0.87386992
[4]  e -- a -> 0.32923136
[26] f -- a -> 0.10740653
[27] k -- a -> 0.56277556

Considering the example above, what I need is a function that must return "b" or "2".

Alan Valejo
  • 1,305
  • 3
  • 24
  • 44
  • Can you provide some *minimal* example data that is reproducible? - [how to make a great reproducible example](http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example) – thelatemail Aug 01 '13 at 01:46
  • You should `set.seed` to make your example reproducible. Better to get the expected result. – agstudy Aug 01 '13 at 02:28
  • I edited the original post to make my example reproducible (using set.seed). – Alan Valejo Aug 01 '13 at 18:04

2 Answers2

1

Once you have the ID of the edge that has the maximal weight, you can use get.edge(graph, edge.id) to get the vertex IDs of the endpoints. So, the full solution is something like:

edge.seq <- E(g)[from(source)]
max.weight <- max(edge.seq$weight)
get.edges(graph, edge.seq[edge.seq$weight == max.weight])

I'm not an expert in R so maybe there's a simpler way.

Tamás
  • 47,239
  • 12
  • 105
  • 124
0

You can use get.adjedgelist to get adjacent edges for all the graph. Then looping through the resulted list to take the edge with maximum weight.

lapply(get.adjedgelist(g),
       function(x)
         E(g)[x[which.max(get.edge.attribute(g,'weight',x))]])

Checking this in a small example:

library(igraph)
set.seed(123)
g <- graph.full(4)
V(g)$name <- 1:5    
V(g)$name <- letters[1:vcount(g)]
E(g)$weight <- runif(ecount(g))
E(g)$label=round(E(g)$weight,2)
ll <- lapply(get.adjedgelist(g),
       function(x)
         E(g)[x[which.max(get.edge.attribute(g,'weight',x))]])
plot(g,layout=layout.fruchterman.reingold)

enter image description here

$a
Edge sequence:
    e       
e [2] c -- a

$b
Edge sequence:
    e       
e [5] d -- b

$c
Edge sequence:
    e       
e [4] c -- b

$d
Edge sequence:
    e       
e [5] d -- b
agstudy
  • 119,832
  • 17
  • 199
  • 261