1

我有这个生成随机图的代码，我如何识别图中的桥梁和切口

library(igraph)
G <- graph( c(1,2,1,3,1,4,3,4,3,5,5,6,6,7,7,8,8,9,3,8,5,8,10,1,10,2,11,2,12,1,13,4,13,7,14,2,15,6,16,7,17,8,19,13,18,4,19,7), directed = FALSE )
# Assign attributes to the graph
G$name    <- "A colorful example graph"
# Assign attributes to the graph's vertices
V(G)$name  <- toupper(letters[1:20])
V(G)$color <- sample(rainbow(20),20,replace=FALSE)
# Assign attributes to the edges
E(G)$weight <- runif(length(E(G)),.3,2)
# Plot the graph -- details in the "Drawing graphs" section of the igraph manual
plot(G, layout = layout.fruchterman.reingold, 
     main = G$name,
     vertex.label = V(G)$name,
     vertex.size = 15,
     vertex.color= V(G)$color,
     vertex.frame.color= "white",
     vertex.label.color = "white",
     vertex.label.family = "sans",
     edge.width=E(G)$weight, 
     edge.color="black")
4

2 回答 2

4

好的，鉴于我已经能够使用您定义的术语来辨别，这可能是一种让您实现目标的方法。希望它在一些小的方面有所帮助，尽管它肯定不是最有效的桥梁查找算法（迭代删除边和图分解的计数），但它对小图的工作相对较好。如果您需要更高效的东西，您可能需要手动编写 Trajan 或其他高效算法：

library(igraph)

G <- graph( c(1,2,1,3,1,4,3,4,3,5,5,6,6,7,7,8,8,9,3,8,5,8,10,1,10,2,11,2,12,1,13,4,13,7,14,2,15,6,16,7,17,8,19,13,18,4,19,7), directed = FALSE )

# Assign attributes to the graph
G$name    <- "A graph with articulated.nodes and bridges highlighted"

# Assign attributes to the graph's vertices
V(G)$name  <- toupper(letters[1:20])
V(G)$color <- sample(rainbow(20),20,replace=FALSE)

# Assign attributes to the edges
E(G)$weight <- runif(length(E(G)),.3,2)

##  Set normal vertices to black:
V(G)$color <- "black"

##  Set articulation points to red:
V(G)$color[ articulation.points(G) ] <- "red"

##  Set normal edges to black:
E(G)$color <- "black"

##  Set bridge edges to red:
num_comp <- length( decompose.graph(G) )
for (i in 1:length(E(G))) {
  G_sub <- delete.edges(G, i)
  if ( length( decompose.graph(G_sub) ) > num_comp ) E(G)$color[i] <- "red"
}

plot(G, layout = layout.fruchterman.reingold, 
     main = G$name,
     vertex.label = V(G)$name,
     vertex.size = 15,
     vertex.color= V(G)$color,
     vertex.frame.color= "white",
     vertex.label.color = "white",
     vertex.label.family = "sans",
     edge.width=E(G)$weight, 
     edge.color=E(G)$color)

在此处输入图像描述

于 2015-05-10T15:55:29.963 回答
1

它似乎没有实施。如此处所述，您可以从函数开始实现Trajan 算法以查找生成树：

minimum.spanning.tree

至于削减，相同的来源指向与您不同的定义，但您可能想检查一下。

于 2015-05-10T06:10:48.523 回答