37 m_num_nodes = num_nodes;
51 void CGraphCut::init()
59 m_active_first[0] = NULL;
60 m_active_last[0] = NULL;
61 m_active_first[1] = NULL;
62 m_active_last[1] = NULL;
63 m_orphan_first = NULL;
77 for (int32_t i = 0; i < cards.
size(); i++)
81 SG_ERROR(
"This implementation of the graph cut optimizer supports only binary variables.");
86 m_num_factors_at_order.
zero();
98 SG_ERROR(
"This implementation of the graph cut optimizer supports only factors of order <= 3.");
101 ++m_num_factors_at_order[num_vars];
106 int32_t max_num_edges = m_num_factors_at_order[2] + 3 * m_num_factors_at_order[3];
107 m_num_nodes = m_num_variables + m_num_factors_at_order[3];
124 m_num_nodes = num_nodes;
127 m_nodes = SG_MALLOC(
GCNode, m_num_nodes);
128 m_edges = SG_MALLOC(
GCEdge, 2 * num_edges);
129 m_edges_last = m_edges;
131 for (int32_t i = 0; i < m_num_nodes; i++)
135 m_nodes[i].
first = NULL;
141 m_active_first[0] = NULL;
142 m_active_last[0] = NULL;
143 m_active_first[1] = NULL;
144 m_active_last[1] = NULL;
145 m_orphan_first = NULL;
146 m_orphan_last = NULL;
155 m_active_first[0] = NULL;
156 m_active_last[0] = NULL;
157 m_active_first[1] = NULL;
158 m_active_last[1] = NULL;
159 m_orphan_first = NULL;
160 m_orphan_last = NULL;
164 for (int32_t i = 0; i < m_num_nodes; i++)
166 node_i = m_nodes + i;
196 "%s::inference(): the output assignment should be prepared as"
197 "the same size as variables!\n",
get_name());
203 for (int32_t vi = 0; vi < assignment.
size(); vi++)
215 void CGraphCut::add_factor(
CFactor* factor)
219 for (int32_t i = 0; i < fcards.
size(); i++)
235 int32_t var = fvars[0];
253 int32_t var0 = fvars[0];
254 int32_t var1 = fvars[1];
263 SG_DEBUG(
"Truncation is applied to ensure regularity / submodularity.");
269 B = B + (delta - subtrA * 2) + 0.0001;
298 SG_ERROR(
"\nRegularity condition is not satisfied\n");
308 int32_t var0 = fvars[0];
309 int32_t var1 = fvars[1];
310 int32_t var2 = fvars[2];
320 int32_t
id = get_tripleId(fvars);
321 float64_t P = (A + D + F + G) - (B + C + E + H);
352 add_edge(var1, var2, B + C - A - D, 0);
353 add_edge(var2, var0, B + E - A - F, 0);
354 add_edge(var0, var1, C + E - A - G, 0);
390 add_edge(var2, var1, F + G - E - H, 0);
391 add_edge(var0, var2, D + G - C - H, 0);
392 add_edge(var1, var0, D + F - B - H, 0);
402 SG_ERROR(
"This implementation of the graph cut optimizer does not support factors of order > 3.");
410 int32_t counter = m_num_variables;
412 for (int32_t i = 0; i < m_triple_list.get_num_elements(); i++)
416 if (triple[0] == vec[0] && triple[1] == vec[1] && triple[2] == vec[2])
424 m_triple_list.push_back(triple);
426 ASSERT(counter - m_num_variables < m_num_factors_at_order[3]);
433 ASSERT(i >= 0 && i < m_num_nodes);
446 m_flow += (cap_source < cap_sink) ? cap_source : cap_sink;
448 m_nodes[i].
tree_cap = cap_source - cap_sink;
453 ASSERT(i >= 0 && i < m_num_nodes);
454 ASSERT(j >= 0 && j < m_num_nodes);
457 ASSERT(reverse_capacity >= 0);
459 GCEdge* e = m_edges_last++;
460 e->
id = m_num_edges++;
461 GCEdge* e_rev = m_edges_last++;
462 e_rev->
id = m_num_edges++;
464 GCNode* node_i = m_nodes + i;
465 GCNode* node_j = m_nodes + j;
472 node_j->
first = e_rev;
474 e_rev->
head = node_i;
479 void CGraphCut::set_active(
GCNode* node_i)
481 if (node_i->
next == NULL)
484 if (m_active_last[1])
486 m_active_last[1]->
next = node_i;
490 m_active_first[1] = node_i;
493 m_active_last[1] = node_i;
494 node_i->
next = node_i;
498 GCNode* CGraphCut::next_active()
506 if ((node_i = m_active_first[0]) == NULL)
508 m_active_first[0] = node_i = m_active_first[1];
509 m_active_last[0] = m_active_last[1];
510 m_active_first[1] = NULL;
511 m_active_last[1] = NULL;
520 if (node_i->
next == node_i)
522 m_active_first[0] = NULL;
523 m_active_last[0] = NULL;
527 m_active_first[0] = node_i->
next;
533 if (node_i->
parent != NULL)
542 GCNode* current_node = NULL;
543 bool active_set_found =
true;
549 test_consistency(current_node);
554 active_set_found = grow(connecting_edge, current_node);
556 if (!active_set_found)
561 if (connecting_edge == NULL)
569 augment_path(connecting_edge);
581 bool CGraphCut::grow(
GCEdge* &edge,
GCNode* ¤t_node)
585 if ((node_i = current_node) != NULL)
589 if (node_i->
parent == NULL)
595 if (node_i == NULL && (node_i = next_active()) == NULL)
603 for (edge = node_i->
first; edge != NULL; edge = edge->
next)
609 if (node_j->
parent == NULL)
634 for (edge = node_i->
first; edge != NULL; edge = edge->
next)
640 if (node_j->
parent == NULL)
666 node_i->
next = node_i;
667 current_node = node_i;
677 void CGraphCut::augment_path(
GCEdge* connecting_edge)
708 for (node_i = connecting_edge->
head; ; node_i = edge->
head)
723 if (bottleneck > - node_i->
tree_cap)
748 set_orphan_front(node_i);
756 set_orphan_front(node_i);
760 for (node_i = connecting_edge->
head; ; node_i = edge->
head)
774 set_orphan_front(node_i);
782 set_orphan_front(node_i);
785 m_flow += bottleneck;
788 void CGraphCut::adopt()
793 while ((np = m_orphan_first) != NULL)
798 while ((np = m_orphan_first) != NULL)
800 m_orphan_first = np->
next;
804 if (m_orphan_first == NULL)
806 m_orphan_last = NULL;
809 process_orphan(node_i, node_i->
type_tree);
812 m_orphan_first = np_next;
816 void CGraphCut::set_orphan_front(
GCNode* node_i)
822 np->
next = m_orphan_first;
826 void CGraphCut::set_orphan_rear(
GCNode* node_i)
833 if (m_orphan_last != NULL)
835 m_orphan_last->
next = np;
856 for (edge0 = node_i->
first; edge0 != NULL; edge0 = edge0->
next)
861 node_j = edge0->
head;
863 if (node_j->
type_tree == terminalType_tree && (edge = node_j->
parent) != NULL)
913 if ((node_i->
parent = edge0_min) != NULL)
921 for (edge0 = node_i->
first; edge0 != NULL; edge0 = edge0->
next)
923 node_j = edge0->
head;
925 if (node_j->
type_tree == terminalType_tree && (edge = node_j->
parent) != NULL)
930 if (is_active_source || is_active_sink)
937 set_orphan_rear(node_j);
946 if (m_nodes[i].parent != NULL)
952 return default_terminal;
959 for (int32_t i = 0; i < m_num_nodes; i++)
961 GCNode* node_i = m_nodes + i;
976 for (int32_t i = 0; i < m_num_edges; i++)
978 GCEdge* edge = m_edges + i;
986 for (int32_t i = 0; i < m_num_nodes; i++)
988 GCNode* node_i = m_nodes + i;
1001 void CGraphCut::test_consistency(
GCNode* current_node)
1009 for (int32_t i = 0; i < m_num_nodes; i++)
1011 node_i = m_nodes + i;
1012 if (node_i->
next || node_i == current_node)
1018 for (int32_t r = 0; r < 3; r++)
1020 node_i = (r == 2) ? current_node : m_active_first[r];
1024 for (; ; node_i = node_i->
next)
1028 if (node_i->
next == node_i)
1031 ASSERT(node_i == m_active_last[r])
1033 ASSERT(node_i == current_node)
1043 for (int32_t i = 0; i < m_num_nodes; i++)
1045 node_i = m_nodes + i;
1048 if (node_i->
parent == NULL) {}
1055 ASSERT(node_i->tree_cap < 0)
1062 ASSERT(node_i->parent->residual_capacity > 0)
1067 if (node_i->parent && !node_i->next)
1073 for (edge = node_i->
first; edge; edge = edge->
next)
1085 for (edge = node_i->
first; edge; edge = edge->
next)
virtual const char * get_name() const
float64_t evaluate_energy(const SGVector< int32_t > state) const
float64_t residual_capacity
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
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
all of classes and functions are contained in the shogun namespace
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)
ETerminalType get_assignment(int32_t i, ETerminalType default_terminal=SOURCE)