python - 使用 R/igraph，有没有办法在考虑唯一节点属性的计数的情况下找到节点之间的最短路径？

Question

我正在尝试找出如何找到图上两个节点之间的最短路径，同时使用边的权重和基于所用节点的唯一属性计数的任意惩罚。

我尽量让问题保持一般性。

例如，考虑下图(简化演示):

在 R 中，我可能会像这样构建 igraph 对象:

编辑 - 修复了边缘权重中的拼写错误!

library(igraph)

nodes = data.frame(id=c("A","B","C","D","E","F","G","H","I"),
                   colour = c("blue","blue","blue","blue","blue",
                              "red","green","yellow", "red"))

edges = data.frame(from = c("A","B","C","D","E","F","G","H","I","I","I"),
                   to = c("B","C","D","E","F","G","H","A","A","E","F"),
                   #weight = c(5,6,7,5,1,5,3,2,8,8,4)) <<- TYPO - SORRY
                   weight = c(5,6,9,5,1,5,3,2,8,8,4))

g = graph_from_data_frame(edges, directed = F, vertices = nodes)

要从 A 到 E，我可以使用 igraph 函数计算最短路径。

shortest_paths(g, from="A",to="E", output="vpath")[[1]] 返回路径 A-H-G-F-E with distances(g, "A","E") 共 11 个。

但是 - 如果我想根据节点的独特颜色的数量添加惩罚怎么办？即对于它经过的每个新的彩色节点，权重为 +10。

A-H-G-F-E = 边权重为 11，使用 4 种颜色，所以总权重为 11+(4*10)=51

A-B-C-D-E = 25 的边权重使用 1 种颜色，总权重为 25+(1*10)=35

A-I-E = 16 的边权重，使用 2 种颜色，总权重为 16+(2*10)=36

A-I-F-E = 边的权重为 13，使用 2 种颜色，总权重为 13+(2*10)=33

A-I-F-E 现在是“最短路线”。

我(天真地)认为权重需要是先前访问过的节点历史记录的函数。

我目前正在使用 igraph bfs 和 dfs 尝试了解它的工作原理但没有取得多大成功，但我认为我找错了树。

在我尝试重新发明轮子之前，我是否缺少现有的 igraph“开箱即用”功能来解决这个问题？

我使用的是 R 3.6.0 和 igraph 1.2.4.1，但也能理解 Python。

TIA

Answer 1

一个有趣的问题。我会定义一个自定义距离/权重函数，从你的图中提取所有连接两个顶点的路径；对于每条路径，我们然后 (1) 计算边缘权重的总和(这本质上就是 distances 所做的)，(2) 确定唯一颜色的数量并将该值乘以 10，以及 (3 ) 将分数计算为边缘权重和独特颜色的缩放数量的总和。然后，“最佳”路径由总分最低的路径给出。

这里是:

min_wghtd_dist <- function(g, from, to) {
    pth <- all_simple_paths(g, from, to)
    score <- sapply(pth, function(x) {
        edge_ids <- get.edge.ids(g, head(rep(x, each = 2), -1)[-1])
        edge_sum <- sum(E(g)[edge_ids]$weight)
        col_wght <- 10 * length(unique(V(g)[x]$colour))
        edge_sum + col_wght
    })
    list(path = pth[[which.min(score)]], score = min(score))
}

min_wghtd_dist(g, "A", "E")
#$path
#+ 4/9 vertices, named, from 09c0a2a:
#[1] A I F E
#
#$score
#[1] 33

路径A->I->F->E根据您的要求被正确识别为最优路径。

---

示例数据

library(igraph)

nodes = data.frame(id=c("A","B","C","D","E","F","G","H","I"),
                   colour = c("blue","blue","blue","blue","blue",
                              "red","green","yellow", "red"))

edges = data.frame(from = c("A","B","C","D","E","F","G","H","I","I","I"),
                   to = c("B","C","D","E","F","G","H","A","A","E","F"),
                   weight = c(5,6,9,5,1,5,3,2,8,8,4))

g = graph_from_data_frame(edges, directed = F, vertices = nodes)