igraph 中尚未实现计算最小 s-t 切割

Question

我一直在尝试使用 R 中的 igraph 包简单地获取图形的最小切割。我从 "seeds" 数据集中读取了大约 60 行，该数据集在 UCI 数据集中用于机器学习，属于聚类类别，分类。我只是想实现一种对未标记点进行分类的半监督方法（我故意对数据集进行了一些更改以满足我的需要）。

我使用一些启发式方法构建了一个图表，我觉得启发式方法工作正常。但是当我使用 graph.mincut 函数计算最小割时，问题就出现了。

当我运行这一行

# g is the graph I am using graph.mincut(g, value.only = FALSE)

完美returns

$value
[1] 1

$cut
[1] 144

$partition1
[1] 24

$partition2
 [1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

但是当我给出源变量和目标变量时，即

graph.mincut(g, source = 1, target = 30, value.only = FALSE)

我收到一条错误消息说

Error in graph.mincut(g, source = 1, target = 30, value.only = FALSE) : 
Calculating minimum s-t cuts is not implemented yet

如果我给出以下行

graph.mincut(g, source = 1, target = 30, value.only = TRUE)

我得到的答案是

[1] 11

如果有人能告诉我哪里出错了，我将不胜感激。

Answer 1

您应该可以使用 igraph 包中的 stMincuts 函数获得最小切割：

library(igraph)
set.seed(144)
g <- erdos.renyi.game(10, .5, directed=TRUE)
cut <- stMincuts(g, source=1, target=4)

现在您可以访问值：

cut$value
# [1] 4

被切割的边缘：

E(g)[cut$cuts[[1]]]
# Edge sequence:
#            
# [8]  1 -> 3
# [15] 1 -> 4
# [24] 1 -> 6
# [30] 1 -> 7

和一个分区中的顶点：

V(g)[cut$partition1s[[1]]]
# Vertex sequence:
# [1] 1

如果有多个剪切（我在此处提供的示例中有两个），您可以获得 edges/vertices，例如 cut$cuts[[2]] 和 cut$partition1s[[2]]， ...

igraph 中尚未实现计算最小 s-t 切割

Calculating minimum s-t cuts is not implemented yet in igraph

r

igraph