/* maxflow.cpp */
#include <stdio.h>
#include "graph.h"
/*
special constants for node->parent
*/
#define TERMINAL ( (arc *) 1 ) /* to terminal */
#define ORPHAN ( (arc *) 2 ) /* orphan */
#define INFINITE_D ((int)(((unsigned)-1)/2)) /* infinite distance to the terminal */
/***********************************************************************/
/*
Functions for processing active list.
i->next points to the next node in the list
(or to i, if i is the last node in the list).
If i->next is NULL iff i is not in the list.
There are two queues. Active nodes are added
to the end of the second queue and read from
the front of the first queue. If the first queue
is empty, it is replaced by the second queue
(and the second queue becomes empty).
*/
template <typename captype, typename tcaptype, typename flowtype>
inline void Graph<captype,tcaptype,flowtype>::set_active(node *i)
{
if (!i->next)
{
/* it's not in the list yet */
if (queue_last[1]) queue_last[1] -> next = i;
else queue_first[1] = i;
queue_last[1] = i;
i -> next = i;
}
}
/*
Returns the next active node.
If it is connected to the sink, it stays in the list,
otherwise it is removed from the list
*/
template <typename captype, typename tcaptype, typename flowtype>
inline typename Graph<captype,tcaptype,flowtype>::node* Graph<captype,tcaptype,flowtype>::next_active()
{
node *i;
while ( 1 )
{
if (!(i=queue_first[0]))
{
queue_first[0] = i = queue_first[1];
queue_last[0] = queue_last[1];
queue_first[1] = NULL;
queue_last[1] = NULL;
if (!i) return NULL;
}
/* remove it from the active list */
if (i->next == i) queue_first[0] = queue_last[0] = NULL;
else queue_first[0] = i -> next;
i -> next = NULL;
/* a node in the list is active iff it has a parent */
if (i->parent) return i;
}
}
/***********************************************************************/
template <typename captype, typename tcaptype, typename flowtype>
inline void Graph<captype,tcaptype,flowtype>::set_orphan_front(node *i)
{
nodeptr *np;
i -> parent = ORPHAN;
np = nodeptr_block -> New();
np -> ptr = i;
np -> next = orphan_first;
orphan_first = np;
}
template <typename captype, typename tcaptype, typename flowtype>
inline void Graph<captype,tcaptype,flowtype>::set_orphan_rear(node *i)
{
nodeptr *np;
i -> parent = ORPHAN;
np = nodeptr_block -> New();
np -> ptr = i;
if (orphan_last) orphan_last -> next = np;
else orphan_first = np;
orphan_last = np;
np -> next = NULL;
}
/***********************************************************************/
template <typename captype, typename tcaptype, typename flowtype>
inline void Graph<captype,tcaptype,flowtype>::add_to_changed_list(node *i)
{
if (changed_list && !i->is_in_changed_list)
{
node_id* ptr = changed_list->New();
*ptr = (node_id)(i - nodes);
i->is_in_changed_list = true;
}
}
/***********************************************************************/
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::maxflow_init()
{
node *i;
queue_first[0] = queue_last[0] = NULL;
queue_first[1] = queue_last[1] = NULL;
orphan_first = NULL;
TIME = 0;
for (i=nodes; i<node_last; i++)
{
i -> next = NULL;
i -> is_marked = 0;
i -> is_in_changed_list = 0;
i -> TS = TIME;
if (i->tr_cap > 0)
{
/* i is connected to the source */
i -> is_sink = 0;
i -> parent = TERMINAL;
set_active(i);
i -> DIST = 1;
}
else if (i->tr_cap < 0)
{
/* i is connected to the sink */
i -> is_sink = 1;
i -> parent = TERMINAL;
set_active(i);
i -> DIST = 1;
}
else
{
i -> parent = NULL;
}
}
}
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::maxflow_reuse_trees_init()
{
node* i;
node* j;
node* queue = queue_first[1];
arc* a;
nodeptr* np;
queue_first[0] = queue_last[0] = NULL;
queue_first[1] = queue_last[1] = NULL;
orphan_first = orphan_last = NULL;
TIME ++;
while ((i=queue))
{
queue = i->next;
if (queue == i) queue = NULL;
i->next = NULL;
i->is_marked = 0;
set_active(i);
if (i->tr_cap == 0)
{
if (i->parent) set_orphan_rear(i);
continue;
}
if (i->tr_cap > 0)
{
if (!i->parent || i->is_sink)
{
i->is_sink = 0;
for (a=i->first; a; a=a->next)
{
j = a->head;
if (!j->is_marked)
{
if (j->parent == a->sister) set_orphan_rear(j);
if (j->parent && j->is_sink && a->r_cap > 0) set_active(j);
}
}
add_to_changed_list(i);
}
}
else
{
if (!i->parent || !i->is_sink)
{
i->is_sink = 1;
for (a=i->first; a; a=a->next)
{
j = a->head;
if (!j->is_marked)
{
if (j->parent == a->sister) set_orphan_rear(j);
if (j->parent && !j->is_sink && a->sister->r_cap > 0) set_active(j);
}
}
add_to_changed_list(i);
}
}
i->parent = TERMINAL;
i -> TS = TIME;
i -> DIST = 1;
}
//test_consistency();
/* adoption */
while ((np=orphan_first))
{
orphan_first = np -> next;
i = np -> ptr;
nodeptr_block -> Delete(np);
if (!orphan_first) orphan_last = NULL;
if (i->is_sink) process_sink_orphan(i);
else process_source_orphan(i);
}
/* adoption end */
//test_consistency();
}
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::augment(arc *middle_arc)
{
node *i;
arc *a;
tcaptype bottleneck;
/* 1. Finding bottleneck capacity */
/* 1a - the source tree */
bottleneck = middle_arc -> r_cap;
for (i=middle_arc->sister->head; ; i=a->head)
{
a = i -> parent;
if (a == TERMINAL) break;
if (bottleneck > a->sister->r_cap) bottleneck = a -> sister -> r_cap;
}
if (bottleneck > i->tr_cap) bottleneck = i -> tr_cap;
/* 1b - the sink tree */
for (i=middle_arc->head; ; i=a->head)
{
a = i -> parent;
if (a == TERMINAL) break;
if (bottleneck > a->r_cap) bottleneck = a -> r_cap;
}
if (bottleneck > - i->tr_cap) bottleneck = - i -> tr_cap;
/* 2. Augmenting */
/* 2a - the source tree */
middle_arc -> sister -> r_cap += bottleneck;
middle_arc -> r_cap -= bottleneck;
for (i=middle_arc->sister->head; ; i=a->head)
{
a = i -> parent;
if (a == TERMINAL) break;
a -> r_cap += bottleneck;
a -> sister -> r_cap -= bottleneck;
if (!a->sister->r_cap)
{
set_orphan_front(i); // add i to the beginning of the adoption list
}
}
i -> tr_cap -= bottleneck;
if (!i->tr_cap)
{
set_orphan_front(i); // add i to the beginning of the adoption list
}
/* 2b - the sink tree */
for (i=middle_arc->head; ; i=a->head)
{
a = i -> parent;
if (a == TERMINAL) break;
a -> sister -> r_cap += bottleneck;
a -> r_cap -= bottleneck;
if (!a->r_cap)
{
set_orphan_front(i); // add i to the beginning of the adoption list
}
}
i -> tr_cap += bottleneck;
if (!i->tr_cap)
{
set_orphan_front(i); // add i to the beginning of the adoption list
}
flow += bottleneck;
}
/***********************************************************************/
template <typename captype, typename tcaptype, typename flowtype>
void Graph<captype,tcaptype,flowtype>::process_source_orphan(node *i)
{
node *j;
arc *a0, *a0_min = NULL, *a;
int d, d_min = INFINITE_D;
/* trying to find a new parent */
for (a0=i->first; a0; a0=a0->next)
if (a0->sister->r_cap)
{
j = a0 -> head;
if (!j->is_sink && (a=j->parent))
{
/* checking the origin of j */
d = 0;
while ( 1 )
{
if (j->TS == TIME)
{
d += j -> DIST;
break;
}
a = j -> parent;
d
没有合适的资源?快使用搜索试试~ 我知道了~
Yuri Boykov 基于图论的图像分割代码
共18个文件
m:12个
h:3个
cpp:3个
1星 需积分: 50 21 下载量 97 浏览量
2015-05-13
10:36:20
上传
评论 2
收藏 26KB ZIP 举报
温馨提示
Y. Y. Boykov, “Interactive Graph Cuts for Optimal Boundary
资源推荐
资源详情
资源评论
收起资源包目录
Bk_matlab.zip (18个子文件)
BK_SetPairwise.m 760B
BK_SetUnary.m 1022B
BK_SetNeighbors.m 1KB
graph.h 18KB
BK_ListHandles.m 360B
BK_Delete.m 206B
BK_Create.m 711B
BK_Minimize.m 278B
energy.h 11KB
BK_GetLabeling.m 235B
maxflow.cpp 17KB
block.h 7KB
BK_UnitTest.m 6KB
BK_AddVars.m 320B
BK_LoadLib.m 496B
bk_matlab.cpp 14KB
BK_BuildLib.m 2KB
graph.cpp 3KB
共 18 条
- 1
资源评论
- 鸟不拉2015-11-24没有用,不知道怎么运行
- sapphire2232016-12-30这不是网上找的代码吗,不是原创,辣鸡
Angeldream123
- 粉丝: 121
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功