SHOGUN  4.1.0
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
GraphCut.h
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2014 Jiaolong Xu
8  * Copyright (C) 2014 Jiaolong Xu
9  */
10 
11 #ifndef __GRAPH_CUT_H__
12 #define __GRAPH_CUT_H__
13 
14 #include <shogun/lib/config.h>
15 
16 #include <shogun/lib/SGVector.h>
17 #include <shogun/lib/List.h>
18 #include <shogun/base/DynArray.h>
22 
23 /* special constants for node->parent. */
24 #define TERMINAL_EDGE ( (GCEdge *) 1 ) // to terminal
25 #define ORPHAN_EDGE ( (GCEdge *) 2 ) // orphan
26 
27 #define INFINITE_D 1000000000 // infinite distance to the terminal
28 
29 namespace shogun
30 {
33 {
35  SOURCE = 0,
37  SINK = 1
38 };
39 
40 struct GCNode;
44 struct GCEdge
45 {
47  int32_t id;
56 };
57 
61 struct GCNode
62 {
64  int32_t id;
74  int32_t timestamp;
76  int32_t dist_terminal;
83 };
84 
88 struct GCNodePtr
89 {
94 };
95 
106 class CGraphCut : public CMAPInferImpl
107 {
108 public:
110  CGraphCut();
111 
116  CGraphCut(CFactorGraph* fg);
117 
127  CGraphCut(int32_t num_nodes, int32_t num_edges);
128 
130  virtual ~CGraphCut();
131 
133  virtual const char* get_name() const
134  {
135  return "GraphCut";
136  }
137 
143  virtual float64_t inference(SGVector<int32_t> assignment);
144 
147  {
148  return m_flow;
149  }
150 
156  void build_st_graph(int32_t num_nodes, int32_t num_edges);
157 
165  void add_edge(int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity);
166 
176  void add_tweights(int32_t i, float64_t cap_source, float64_t cap_sink);
177 
179  void init_maxflow();
180 
208 
220  ETerminalType get_assignment(int32_t i, ETerminalType default_terminal = SOURCE);
221 
223  void print_graph();
224 
226  void print_assignment();
227 
228 private:
230  void init();
231 
239  void add_factor(CFactor* factor);
240 
246  int32_t get_tripleId(SGVector<int32_t> triple);
247 
261  void set_active(GCNode* node_i);
262 
264  GCNode* next_active();
265 
270  void set_orphan_front(GCNode* node_i);
271 
276  void set_orphan_rear(GCNode* node_i);
277 
283  void process_orphan(GCNode* node_i, ETerminalType terminalType_tree);
284 
292  bool grow(GCEdge* &edge, GCNode* &current_node);
293 
298  void augment_path(GCEdge* connecting_edge);
299 
301  void adopt();
302 
304  void test_consistency(GCNode* current_node = NULL);
305 protected:
308 
309 private:
311  int32_t m_num_variables;
313  SGVector<int32_t> m_num_factors_at_order;
315  DynArray< SGVector<int32_t> > m_triple_list;
316 
318  GCNode* m_nodes;
320  int32_t m_num_nodes;
322  GCEdge* m_edges;
324  GCEdge* m_edges_last;
326  int32_t m_num_edges;
327 
329  float64_t m_flow;
331  int32_t m_timestamp;
332 
334  GCNode* m_active_first[2];
336  GCNode* m_active_last[2];
337 
339  GCNodePtr* m_orphan_first;
341  GCNodePtr* m_orphan_last;
342 };
343 
344 }
345 #endif
float64_t tree_cap
Definition: GraphCut.h:82
virtual const char * get_name() const
Definition: GraphCut.h:133
float64_t residual_capacity
Definition: GraphCut.h:55
GCEdge * parent
Definition: GraphCut.h:68
Graph cuts node.
Definition: GraphCut.h:61
void print_assignment()
Definition: GraphCut.cpp:984
ETerminalType
Definition: GraphCut.h:32
float64_t m_map_energy
Definition: GraphCut.h:307
void add_edge(int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity)
Definition: GraphCut.cpp:451
GCEdge * next
Definition: GraphCut.h:51
Graph guts node pointer.
Definition: GraphCut.h:88
Class CMAPInferImpl abstract class of MAP inference implementation.
Definition: MAPInference.h:98
ETerminalType type_tree
Definition: GraphCut.h:78
void build_st_graph(int32_t num_nodes, int32_t num_edges)
Definition: GraphCut.cpp:122
GCEdge * reverse
Definition: GraphCut.h:53
GCNode * ptr
Definition: GraphCut.h:91
GCNodePtr * next
Definition: GraphCut.h:93
float64_t compute_maxflow()
Definition: GraphCut.cpp:540
void add_tweights(int32_t i, float64_t cap_source, float64_t cap_sink)
Definition: GraphCut.cpp:431
GCNode * next
Definition: GraphCut.h:72
Template Dynamic array class that creates an array that can be used like a list or an array...
Definition: DynArray.h:32
double float64_t
Definition: common.h:50
int32_t dist_terminal
Definition: GraphCut.h:76
int32_t id
Definition: GraphCut.h:64
float64_t get_flow()
Definition: GraphCut.h:146
GCEdge * first
Definition: GraphCut.h:66
Graph cuts edge.
Definition: GraphCut.h:44
all of classes and functions are contained in the shogun namespace
Definition: class_list.h:18
Class CFactorGraph a factor graph is a structured input in general.
Definition: FactorGraph.h:27
virtual ~CGraphCut()
Definition: GraphCut.cpp:42
int32_t id
Definition: GraphCut.h:47
int32_t timestamp
Definition: GraphCut.h:74
Class CFactor A factor is defined on a clique in the factor graph. Each factor can have its own data...
Definition: Factor.h:89
GCNode * head
Definition: GraphCut.h:49
virtual float64_t inference(SGVector< int32_t > assignment)
Definition: GraphCut.cpp:193
ETerminalType get_assignment(int32_t i, ETerminalType default_terminal=SOURCE)
Definition: GraphCut.cpp:944

SHOGUN Machine Learning Toolbox - Documentation