3

我有以下代码来绘制图形的最小生成树

## g is an igraph graph
mst = minimum.spanning.tree(g)
E(g)$color <- "SkyBlue2"

## how to I make mst a different color
E(g)[E(mst)]$color = "red"  ### <---- I WANT TO DO ESSENTIALLY THIS

plot(g,  edge.label=E(g)$weight)

也就是说，对于一个简单的图表，我找到了 mst。我想将 mst 更改为红色并将 mst 绘制为主图的一部分。为此，我想选择g也在mst. 我该怎么做呢？

更新：

更一般地说，我有一个图g0，它是 的 mst g，它有n顶点。它的构造如下

## implementing the Dijkstra-Prim algorithm
v0 = sample(1:n, 1)
g0 = graph.empty(n=n, directed=FALSE)
weight.g0 = 0
while(length(setdiff(1:n, v0) > 0)) {
  ## chose the shortest edge in the cut set of g

  ## to find the cut, figure out the set of edges where vertex is
  ## in v0 and the other is not
  cutset = E(g)[ v0 %->% setdiff(1:n, v0)]

  ## find the lightest weight edge
  cutweights = E(g)$weight[cutset]
  lightest_edge_idx = which(cutweights == min(cutweights))[1]
  weight.g0 = weight.g0 + min(cutweights)

  ## get the vertices of the lightest weight edge, add to path
  lightest_edge = cutset[as.numeric(cutset)[lightest_edge_idx]]
  vertices = get.edges(g, as.numeric(lightest_edge))

  g0 <- add.edges(g0, vertices, weight=min(cutweights))


  ## now that we have the vertices, add the one that is not in the
  ## graph already
  for(vtx in vertices) {
    if(!(vtx %in% v0)) {
      v0 = c(vtx, v0)
    }
  }

}

我知道我可能没有使用 igraph 的很多有用功能，但我确实g0在这个循环结束时成为了一个 mst。鉴于此，我有

E(g0)
Edge sequence:

[1]   8 --  1
[2]   2 --  1
[3]   9 --  8
[4]   9 --  5
[5]   3 --  2
[6]   4 --  3
[7]   7 --  3
[8]  11 --  4
[9]   7 --  6
[10] 11 -- 10
> E(g)
Edge sequence:

[1]   2 --  1
[2]   5 --  1
[3]   8 --  1
[4]   3 --  2
[5]   5 --  2
[6]   6 --  2
[7]   4 --  3
[8]   6 --  3
[9]   7 --  3
[10]  7 --  4
[11] 11 --  4
[12]  6 --  5
[13]  8 --  5
[14]  9 --  5
[15]  7 --  6
[16]  9 --  6
[17] 10 --  6
[18] 10 --  7
[19] 11 --  7
[20]  9 --  8
[21] 10 --  9
[22] 11 -- 10

我的问题是，如何将属性分配给 E(g) 中也在 E(g0) 中的边？

4

1 回答 1

5

这实际上很容易，因为minimum.spanning.tree()保留了边缘属性。所以你只需要分配一个边缘 id 属性，你就会看到哪些边缘是红色的。它是这样的：

# Some test data, no edge weights, quite boring
g <- erdos.renyi.game(20,2/20)
g
# IGRAPH U--- 20 24 -- Erdos renyi (gnp) graph
# + attr: name (g/c), type (g/c), loops (g/l), p (g/n)

E(g)$id <- seq_len(ecount(g))
mst <- minimum.spanning.tree(g)
mst
# IGRAPH U--- 20 18 -- Erdos renyi (gnp) graph
# + attr: name (g/c), type (g/c), loops (g/l), p (g/n), id (e/n)
E(mst)$id
# [1]  1  2  3  6  7  8  9 10 11 12 13 16 18 19 20 22 23 24

E(g)$color <- "black"
E(g)$color[E(mst)$id] <- "red"
plot(g)

在此处输入图像描述

于 2012-09-28T22:49:46.593 回答