我需要在图表上找到最小切割.我一直在阅读关于流网络的内容,但我能找到的是最大流算法,如Ford-Fulkerson,push-relabel等.鉴于最大流量最小切割定理,是否可以使用其中一种算法来查找使用最大流算法在图表上的最小割数？怎么样？
到目前为止我发现的最好的信息是,如果我发现"饱和"边缘,即流量等于容量的边缘,那些边缘对应于最小切割.真的吗？这对我来说听起来不是100%.确实,最小切口上的所有边缘都将饱和,但我相信也可能存在饱和边缘,这些边缘超出最小切割"路径".
是否有一个可靠且记录良好的Python库,可快速实现一种算法,可以在有向图中找到最大流量和最小切割量？
来自python-graph的pygraph.algorithms.minmax.maximum_flow解决了这个问题,但速度很慢:在一个有4000个节点和11000个边缘的有向图中查找最大流量和最小切割需要> 1分钟.我正在寻找至少快一个数量级的东西.
赏金:我在这个问题上提供了一笔赏金,看看自从提出这个问题以来情况是否发生了变化.如果您对自己推荐的图书馆有个人经验,可以获得奖励积分!
python graph-theory graph mathematical-optimization max-flow
我正在阅读http://www.geeksforgeeks.org/maximum-bipartite-matching/和http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm,我很难理解.似乎这个例子假设每个工作只能接受1个人,每个人想要1个工作.我想知道算法/代码将如何改变,例如,如果v set的容量> 1(可以为该工作雇佣多人)并且u set> 1(每个人想要超过1个工作)？
我正在寻找快速算法来计算动态图形中的最大流量(添加/删除具有相关边缘的节点到图形).即我们在G中有最大流量,现在添加/删除了相关边缘的新节点,我不想重新计算新图形的最大流量,事实上,我想使用此图形的先前可用结果.
任何非时间/内存消费者的预处理都是适当的.
最简单的想法是重新计算流量.
另一个简单的想法就是这样,保存以前maxflow计算中使用的所有扩充路径,现在用于添加顶点v,我们可以找到从源开始的简单路径(在前一步骤的更新容量图中),v然后转到目的地,但是问题是这条路应该简单,我找不到比O(n*E)更好的情况.(如果它只是一条路径或路径是不相交的,这可以在O(n + E)中完成,但事实并非如此).
另外对于删除节点以上的想法不起作用.
此外,我的问题与另一个关于动态边缘添加/删除的问题无关.
我正在进行医学图像分割,我想将模糊连通性算法与图形切割相结合,其思路是将图像与模糊连通性分割为背景,前景将用作图形切割算法的接收器和源,是我的代码获取图形切割分割的种子坐标
FC=afc(S,K); %// Absolute FC
u=FC>thresh;
v=FC<thresh;
s=regionprops(u, 'PixelIdxList'); %// listes de pixels de l´objet
t=regionprops(v, 'PixelIdxList'); %// listes de pixels de l´arrière plan
[a,b]=size(s);
[w,c,z]= size(t)
for i=1:a
for j=1:b
[y,x] = ind2sub(size(u), s(i,j).PixelIdxList);
end
end
for k=1:w
for d=1:c
[y1,x1] = ind2sub(size(v), t(k,d).PixelIdxList);
end
end
对于图形切割,我使用了文件交换中的算法
例如,我可以定义
Cs=-log([y x])
Ct=-log([y1 x1])
但问题是如何组合成本函数的信息,如代码源的这一部分
u = double((Cs-Ct) >= 0);
ps = min(Cs, Ct);
pt = ps
它将超过矩阵大小
matlab graph-theory image-processing image-segmentation max-flow
给定有向加权图,如何在所有顶点对之间找到最大流量(或最小边缘切割).
天真的方法就是调用像Dinic这样的Max Flow算法,其复杂度O((V^2)*E)为每对.
因此对于所有对都是如此O((V^4)*E).
是否有可能降低复杂性,O((V^3)*E)或O(V^3)通过一些优化？
opencv有一个max-flow算法的实现(GCGRAPH文件gcgraph.hpp中的类).它可以在这里找到.
有谁知道这个类实现了哪种特定的max-flow算法？
我试图从研究论文中描述的给定图像中提取头发,使用能量最小化的概念,能量函数依赖于先验概率和YCrCb颜色似然直方图.能量函数定义为:
(x)= data(x)+smooth(x).
data(x)= - Σ(log(I(x)| x)+ logsel(x)) [先验概率模型]
smooth(x)=Σ(x≠x)exp( - ||(x) - (x)|| ^ 2 /) [先前的YcrCb颜色模型]
我很困惑如何标记给定的图形(图像的像素被视为图形的节点).我尝试使用以下方法标记图形,但结果不符合预期:
def get_Edata(prob_dist, ycrcb_dist, img_y, img_x, pix):
e_data = 0
Y, Cr, Cb = pix
if ycrcb_dist[int(Y/4)][int(Cr/4)][int(Cb/4)] > 0 and prob_dist[img_y][img_x]>0:
e_data = -1*(math.log(ycrcb_dist[int(Y/4)][int(Cr/4)][int(Cb/4)], 10) + math.log(prob_dist[img_y][img_x], 10))
return e_data
def get_ESmooth(normalization_constant, pix_1, pix_2):
return math.exp(-(math.ceil(pix_1[0] - pix_2[0])**2)/normalization_constant)
虽然在图表中的节点之间添加权重,但我使用:
#adding the edges between neighbouring pixels.
img_graph.add_edge(central_node, neighbour_nodes, eSmooth, 0)
#adding the edges from source to node and from node to …假设我在图G =(V,E)上运行Ford-Fulkerson算法,结果是最大流量f max,它与最小切割Xmin相关联.我有兴趣通过增加图中任何一个边的容量来尽可能地增加流量.我如何识别这个边缘？
一种策略可能是:给定初始顶点s和最终顶点t,考虑从s到t的所有路径并验证具有较低容量的边缘.例如,如果我有1/1的边,这是我必须增加容量的顶点.
是否有解决此问题的通用算法？
我无法理解如何在具有下限（不是需求）的网络中找到循环流。我找到了下一个包含问题描述和解决策略的文档：
让我们考虑一个具有以下边的网络（l - 下限，c - 容量）：
1 -> 2 : l = 1 c = 3
2 -> 3 : l = 2 c = 4
3 -> 1 : l = 1 c = 2
据我了解，要解决这个问题，我们应该采取以下步骤：