GraphCuts算法解析，Graphcuts算法求最大流，最小割实例-阿里云开发者社区

GraphCuts算法解析，Graphcuts算法求最大流，最小割实例

2014-11-02 1189

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

全局流量管理 GTM，标准版 1个月

公共DNS（含HTTPDNS解析），每月1000万次HTTP解析

云解析 DNS，旗舰版 1个月

简介： 图割论文大合集下载： http://download.csdn.net/detail/wangyaninglm/8292305 代码： /* graph.h *//* Vladimir Kolmogorov (vnk@cs.

图割论文大合集下载：

http://download.csdn.net/detail/wangyaninglm/8292305

代码：

/* graph.h */
/* Vladimir Kolmogorov (vnk@cs.cornell.edu), 2001. */

/*
	This software library is a modification of the maxflow algorithm
	described in

	An Experimental Comparison of Min-Cut/Max-Flow Algorithms
	for Energy Minimization in Computer Vision.
	Yuri Boykov and Vladimir Kolmogorov.
	In Third International Workshop on Energy Minimization
	Methods in Computer Vision and Pattern Recognition, September 2001

	This algorithm was originally developed at Siemens.
	The main modification is that two trees are used for finding
	augmenting paths - one grows from the source and the other
	from the sink. (The original algorithm used only the former one).
	Details will be described in my PhD thesis.

	This implementation uses an adjacency list graph representation.邻接链表
	Memory allocation:
		Nodes: 22 bytes + one field to hold a residual capacity
		       of t-links (by default it is 'short' - 2 bytes)
		Arcs: 12 bytes + one field to hold a residual capacity 剩余容量
		      (by default it is 'short' - 2 bytes)
	(Note that arcs are always added in pairs （弧都是成对的添加）- in forward and reverse directions)

	Example usage (computes a maxflow on the following graph):

		        SOURCE
		       /       \
		     1/         \2
		     /      3    \
		   node0 -----> node1
		     |   <-----   |
		     |      4     |
		     \            /
		     5\          /6
		       \        /
		          SINK

	///////////////////////////////////////////////////

	#include <stdio.h>
	#include "graph.h"

	void test_maxflow()
	{
		Graph::node_id nodes[2];
		Graph *g = new Graph();

		nodes[0] = g -> add_node();
		nodes[1] = g -> add_node();
		g -> set_tweights(nodes[0], 1, 5);
		g -> set_tweights(nodes[1], 2, 6);
		g -> add_edge(nodes[0], nodes[1], 3, 4);

		Graph::flowtype flow = g -> maxflow();

		printf("Flow = %d\n", flow);
		printf("Minimum cut:\n");
		if (g->what_segment(nodes[0]) == Graph::SOURCE)
			printf("node0 is in the SOURCE set\n");
		else
			printf("node0 is in the SINK set\n");
		if (g->what_segment(nodes[1]) == Graph::SOURCE)
			printf("node1 is in the SOURCE set\n");
		else
			printf("node1 is in the SINK set\n");

		delete g;
	}

	///////////////////////////////////////////////////
*/

void test_maxflow()
{
	Graph::node_id nodes[2];
	Graph *g = new Graph();

	nodes[0] = g -> add_node();
	nodes[1] = g -> add_node();
	g -> set_tweights(nodes[0], 3, 3);
	g -> set_tweights(nodes[1], 3, 1);
	g -> add_edge(nodes[0], nodes[1], 1, 0);

	Graph::flowtype flow = g -> maxflow();

	printf("Flow = %d\n", flow);
	printf("Minimum cut:\n");
	if (g->what_segment(nodes[0]) == Graph::SOURCE)
		printf("node0 is in the SOURCE set\n");
	else
		printf("node0 is in the SINK set\n");
	if (g->what_segment(nodes[1]) == Graph::SOURCE)
		printf("node1 is in the SOURCE set\n");
	else
		printf("node1 is in the SINK set\n");

	delete g;
}