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

Question

我一直在尝试使用 R 中的 igraph 包来简单地获得图形的一个 mincut。我从 UCI 数据集中可用的“种子”数据集中读取了大约 60 行，用于机器学习的聚类、分类类别下。我只是想实现一种对未标记点进行分类的半监督方法(我特意对数据集进行了一些更改以满足我的需要)。

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

当我运行这条线时
# g is the graph I am using
graph.mincut(g, value.only = FALSE)
它完美地返回

$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

您应该能够使用 stMincuts 获得最小切割。来自 igraph 的函数包裹:

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

如果有多个切割(我在此处提供的示例中有两个切割)，则可以使用例如 cut$cuts[[2]] 获取边/顶点。和 cut$partition1s[[2]] , ...