减少度数为 1 的序列中的边的算法？

Question

我正在使用 GTFS 标准中的 public 交通数据，并且一直在构建整个路线中起点站到目标站的边缘列表。我在下面放了一些示例 R 代码来显示数据和图表的示例。

library(igraph)

# edgelist with two nodes with outdegree > 1. 
edgelist <- data.frame(source = c("Z","A", "B", "C", "D", "E", "F", "F", "A"),
                       target = c("A","B", "C", "D", "E", "F", "G", "H", "I"),
                       edge_sequence = c(0,1, 2, 3, 4, 5, 6, NA , NA),
                       source_node_out_degree = c(1,1, 1, 1, 1, 1, 2, 2, 2),
                       group = factor(c(1,1,1,1,1,1,1,2,2)))

# i would like to remove edges within my sequence that have an outdegree of 
# one and merge the original source with the 
plot(graph.data.frame(edgelist), edge.arrow.size = 0.3)

下面是我想要生成的边缘列表。在这个例子中，我减少了 A->F 的连接，因为它是一个。沿着序列和b。只有出度为 1 的节点在 A 和 F 之间。

# the expected edgelist after simplifying the network. Connecting nodes that 
# have outdegree > 1 on the sequence of edges. 
new_expected_edgelist <- data.frame(source = c("Z","A", "F", "F", "A"),
                                    target = c("A","F", "G", "H", "I"))

# edges with outdegree == 1 have been reduced. 
plot(graph.data.frame(new_expected_edgelist), edge.arrow.size = 0.3)

这一应用将使我能够简化我的网络，以便仅可视化多个 public 运输路线之间共享的边缘。一些路线延伸到连接之外的许多站点到任何其他站点，并且使可视化网络的复杂性更加困难。

Answer 1

您可以使用contract.vertices命令：

g<-graph.data.frame(edgelist)
h<-contract.vertices(g,c(1,2,3,3,3,3,3,8,9,10))

减少度数为 1 的序列中的边的算法？

Algorithm for reducing edges in a sequence with out degree of 1?

r

igraph