14 using namespace shogun;
42 m_num_nodes = num_nodes;
56 void CGraphCut::init()
62 for (int32_t i = 0; i < cards.
size(); i++)
66 SG_ERROR(
"This implementation of the graph cut optimizer supports only binary variables.");
71 m_num_factors_at_order.
zero();
83 SG_ERROR(
"This implementation of the graph cut optimizer supports only factors of order <= 3.");
86 ++m_num_factors_at_order[num_vars];
91 int32_t max_num_edges = m_num_factors_at_order[2] + 3 * m_num_factors_at_order[3];
92 m_num_nodes = m_num_variables + m_num_factors_at_order[3];
109 m_num_nodes = num_nodes;
112 m_nodes = SG_MALLOC(
Node, m_num_nodes);
113 m_edges = SG_MALLOC(
Edge, 2 * num_edges);
114 m_edges_last = m_edges;
116 for (int32_t i = 0; i < m_num_nodes; i++)
120 m_nodes[i].
first = NULL;
131 m_active_first[0] = NULL;
132 m_active_last[0] = NULL;
133 m_active_first[1] = NULL;
134 m_active_last[1] = NULL;
135 m_orphan_first = NULL;
136 m_orphan_last = NULL;
140 for (int32_t i = 0; i < m_num_nodes; i++)
142 node_i = m_nodes + i;
172 "%s::inference(): the output assignment should be prepared as"
173 "the same size as variables!\n",
get_name());
179 for (int32_t vi = 0; vi < assignment.
size(); vi++)
191 void CGraphCut::add_factor(
CFactor* factor)
195 for (int32_t i = 0; i < fcards.
size(); i++)
211 int32_t var = fvars[0];
229 int32_t var0 = fvars[0];
230 int32_t var1 = fvars[1];
239 SG_DEBUG(
"Truncation is applied to ensure regularity / submodularity.");
245 B = B + (delta - subtrA * 2) + 0.0001;
274 SG_ERROR(
"\nRegularity condition is not satisfied\n");
284 int32_t var0 = fvars[0];
285 int32_t var1 = fvars[1];
286 int32_t var2 = fvars[2];
296 int32_t
id = get_tripleId(fvars);
297 float64_t P = (A + D + F + G) - (B + C + E + H);
328 add_edge(var1, var2, B + C - A - D, 0);
329 add_edge(var2, var0, B + E - A - F, 0);
330 add_edge(var0, var1, C + E - A - G, 0);
366 add_edge(var2, var1, F + G - E - H, 0);
367 add_edge(var0, var2, D + G - C - H, 0);
368 add_edge(var1, var0, D + F - B - H, 0);
378 SG_ERROR(
"This implementation of the graph cut optimizer does not support factors of order > 3.");
386 int32_t counter = m_num_variables;
388 for (int32_t i = 0; i < m_triple_list.get_num_elements(); i++)
392 if (triple[0] == vec[0] && triple[1] == vec[1] && triple[2] == vec[2])
400 m_triple_list.push_back(triple);
402 ASSERT(counter - m_num_variables < m_num_factors_at_order[3]);
409 ASSERT(i >= 0 && i < m_num_nodes);
422 m_flow += (cap_source < cap_sink) ? cap_source : cap_sink;
424 m_nodes[i].
tree_cap = cap_source - cap_sink;
429 ASSERT(i >= 0 && i < m_num_nodes);
430 ASSERT(j >= 0 && j < m_num_nodes);
433 ASSERT(reverse_capacity >= 0);
435 Edge* e = m_edges_last++;
436 e->
id = m_num_edges++;
437 Edge* e_rev = m_edges_last++;
438 e_rev->
id = m_num_edges++;
440 Node* node_i = m_nodes + i;
441 Node* node_j = m_nodes + j;
448 node_j->
first = e_rev;
450 e_rev->
head = node_i;
455 void CGraphCut::set_active(
Node* node_i)
457 if (node_i->
next == NULL)
460 if (m_active_last[1])
462 m_active_last[1]->
next = node_i;
466 m_active_first[1] = node_i;
469 m_active_last[1] = node_i;
470 node_i->
next = node_i;
474 Node* CGraphCut::next_active()
482 if ((node_i = m_active_first[0]) == NULL)
484 m_active_first[0] = node_i = m_active_first[1];
485 m_active_last[0] = m_active_last[1];
486 m_active_first[1] = NULL;
487 m_active_last[1] = NULL;
496 if (node_i->
next == node_i)
498 m_active_first[0] = NULL;
499 m_active_last[0] = NULL;
503 m_active_first[0] = node_i->
next;
509 if (node_i->
parent != NULL)
518 Node* current_node = NULL;
519 bool active_set_found =
true;
525 test_consistency(current_node);
527 Edge* connecting_edge;
530 active_set_found = grow(connecting_edge, current_node);
532 if (!active_set_found)
537 if (connecting_edge == NULL)
545 augment_path(connecting_edge);
557 bool CGraphCut::grow(
Edge* &edge,
Node* ¤t_node)
559 Node* node_i, *node_j;
561 if ((node_i = current_node) != NULL)
565 if (node_i->
parent == NULL)
571 if (node_i == NULL && (node_i = next_active()) == NULL)
579 for (edge = node_i->
first; edge != NULL; edge = edge->
next)
585 if (node_j->
parent == NULL)
610 for (edge = node_i->
first; edge != NULL; edge = edge->
next)
616 if (node_j->
parent == NULL)
642 node_i->
next = node_i;
643 current_node = node_i;
653 void CGraphCut::augment_path(
Edge* connecting_edge)
684 for (node_i = connecting_edge->
head; ; node_i = edge->
head)
699 if (bottleneck > - node_i->
tree_cap)
724 set_orphan_front(node_i);
732 set_orphan_front(node_i);
736 for (node_i = connecting_edge->
head; ; node_i = edge->
head)
750 set_orphan_front(node_i);
758 set_orphan_front(node_i);
761 m_flow += bottleneck;
764 void CGraphCut::adopt()
769 while ((np = m_orphan_first) != NULL)
774 while ((np = m_orphan_first) != NULL)
776 m_orphan_first = np->
next;
780 if (m_orphan_first == NULL)
782 m_orphan_last = NULL;
785 process_orphan(node_i, node_i->
type_tree);
788 m_orphan_first = np_next;
792 void CGraphCut::set_orphan_front(
Node* node_i)
798 np->
next = m_orphan_first;
802 void CGraphCut::set_orphan_rear(
Node* node_i)
809 if (m_orphan_last != NULL)
811 m_orphan_last->
next = np;
826 Edge* edge0_min = NULL;
832 for (edge0 = node_i->
first; edge0 != NULL; edge0 = edge0->
next)
837 node_j = edge0->
head;
839 if (node_j->
type_tree == terminalType_tree && (edge = node_j->
parent) != NULL)
889 if ((node_i->
parent = edge0_min) != NULL)
897 for (edge0 = node_i->
first; edge0 != NULL; edge0 = edge0->
next)
899 node_j = edge0->
head;
901 if (node_j->
type_tree == terminalType_tree && (edge = node_j->
parent) != NULL)
906 if (is_active_source || is_active_sink)
913 set_orphan_rear(node_j);
922 if (m_nodes[i].parent != NULL)
928 return default_terminal;
935 for (int32_t i = 0; i < m_num_nodes; i++)
937 Node* node_i = m_nodes + i;
952 for (int32_t i = 0; i < m_num_edges; i++)
954 Edge* edge = m_edges + i;
962 for (int32_t i = 0; i < m_num_nodes; i++)
964 Node* node_i = m_nodes + i;
977 void CGraphCut::test_consistency(
Node* current_node)
985 for (int32_t i = 0; i < m_num_nodes; i++)
987 node_i = m_nodes + i;
988 if (node_i->
next || node_i == current_node)
994 for (int32_t r = 0; r < 3; r++)
996 node_i = (r == 2) ? current_node : m_active_first[r];
1000 for (; ; node_i = node_i->
next)
1004 if (node_i->
next == node_i)
1007 ASSERT(node_i == m_active_last[r])
1009 ASSERT(node_i == current_node)
1019 for (int32_t i = 0; i < m_num_nodes; i++)
1021 node_i = m_nodes + i;
1024 if (node_i->
parent == NULL) {}
1031 ASSERT(node_i->tree_cap < 0)
1038 ASSERT(node_i->parent->residual_capacity > 0)
1043 if (node_i->parent && !node_i->next)
1049 for (edge = node_i->
first; edge; edge = edge->
next)
1061 for (edge = node_i->
first; edge; edge = edge->
next)
virtual const char * get_name() const
float64_t residual_capacity
float64_t evaluate_energy(const SGVector< int32_t > state) const
const SGVector< int32_t > get_variables() const
int32_t get_num_factors() const
CDynamicObjectArray * get_factors() const
void add_edge(int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity)
int32_t get_num_elements() const
Class CMAPInferImpl abstract class of MAP inference implementation.
void build_st_graph(int32_t num_nodes, int32_t num_edges)
SGVector< float64_t > get_energies() const
float64_t compute_maxflow()
void add_tweights(int32_t i, float64_t cap_source, float64_t cap_sink)
int32_t get_num_vars() const
ETerminalType get_assignment(int32_t i, ETerminalType default_termainl=SOURCE)
Dynamic array class for CSGObject pointers that creates an array that can be used like a list or an a...
EMessageType get_loglevel() const
const int32_t get_num_vars() const
Class CFactorGraph a factor graph is a structured input in general.
CSGObject * get_element(int32_t index) const
SGVector< int32_t > get_cardinalities() const
#define SG_UNSTABLE(func,...)
Class CFactor A factor is defined on a clique in the factor graph. Each factor can have its own data...
const SGVector< int32_t > get_cardinalities() const
virtual float64_t inference(SGVector< int32_t > assignment)