SHOGUN  3.2.1
 全部  命名空间 文件 函数 变量 类型定义 枚举 枚举值 友元 宏定义  
GraphCut.h
浏览该文件的文档.
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 ( (Edge *) 1 ) // to terminal
25 #define ORPHAN_EDGE ( (Edge *) 2 ) // orphan
26 
27 #define INFINITE_D 1000000000 // infinite distance to the terminal
28 
29 namespace shogun
30 {
32 {
33  SOURCE = 0, // source terminal
34  SINK = 1 // sink terminal
35 };
36 
37 struct Node;
38 struct Edge
39 {
40  int32_t id; // edge id
41  Node* head; // node the edge point to
42  Edge* next; // next edge with the same originated node
43  Edge* reverse; // reverse edge
44  float64_t residual_capacity; // residual capacity
45 };
46 
47 struct Node
48 {
49  int32_t id; // node id
50  Edge* first; // first outcoming edge
51  Edge* parent; // node's parent
52  Node* next; // pointer to the next active node (or itself if it is the last node in the list)
53  int32_t timestamp; // timestamp showing when dist_to_terminal was computed
54  int32_t dist_terminal; // distance to the terminal
55  ETerminalType type_tree; // the type of the tree that the node belongs to
56  float64_t tree_cap; // if tree_cap > 0 then tree_cap is residual capacity of the edge SOURCE->node
57  // otherwise -tree_cap is residual capacity of the edge node->SINK
58 };
59 
60 struct NodePtr
61 {
62  Node* ptr; // pointer of the node
63  NodePtr* next; // point to the next
64 };
65 
76 class CGraphCut : public CMAPInferImpl
77 {
78 public:
80  CGraphCut();
81 
87 
97  CGraphCut(int32_t num_nodes, int32_t num_edges);
98 
100  virtual ~CGraphCut();
101 
103  virtual const char* get_name() const
104  {
105  return "GraphCut";
106  }
107 
113  virtual float64_t inference(SGVector<int32_t> assignment);
114 
117  {
118  return m_flow;
119  }
120 
126  void build_st_graph(int32_t num_nodes, int32_t num_edges);
127 
135  void add_edge(int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity);
136 
146  void add_tweights(int32_t i, float64_t cap_source, float64_t cap_sink);
147 
149  void init_maxflow();
150 
178 
190  ETerminalType get_assignment(int32_t i, ETerminalType default_termainl = SOURCE);
191 
193  void print_graph();
194 
196  void print_assignment();
197 
198 private:
200  void init();
201 
209  void add_factor(CFactor* factor);
210 
216  int32_t get_tripleId(SGVector<int32_t> triple);
217 
231  void set_active(Node* node_i);
232 
234  Node* next_active();
235 
240  void set_orphan_front(Node* node_i);
241 
246  void set_orphan_rear(Node* node_i);
247 
253  void process_orphan(Node* node_i, ETerminalType terminalType_tree);
254 
262  bool grow(Edge* &edge, Node* &current_node);
263 
268  void augment_path(Edge* connecting_edge);
269 
271  void adopt();
272 
274  void test_consistency(Node* current_node = NULL);
275 protected:
276  float64_t m_map_energy; // the total energy of the factor graph
277 
278 private:
279  int32_t m_num_variables; // number of variables in the factor graph
280  SGVector<int32_t> m_num_factors_at_order; // statistic of the number of the factors at order [1, 2, 3]
281  DynArray< SGVector<int32_t> > m_triple_list; // list of triple nodes, for order-3 factors
282 
283  Node* m_nodes; // nodes in the st graph
284  int32_t m_num_nodes; // number of nodes
285  Edge* m_edges; // edges in the st graph
286  Edge* m_edges_last; // point to the end of the added edges
287  int32_t m_num_edges; // number of edges
288 
289  float64_t m_flow; // total flow
290  int32_t m_timestamp; // timestamp
291 
292  Node* m_active_first[2]; // list of active nodes
293  Node* m_active_last[2]; // list of active nodes
294 
295  NodePtr* m_orphan_first; // list of pointers to orphans
296  NodePtr* m_orphan_last; // list of pointers to orphans
297 };
298 
299 }
300 #endif
virtual const char * get_name() const
Definition: GraphCut.h:103
float64_t residual_capacity
Definition: GraphCut.h:44
int32_t id
Definition: GraphCut.h:49
void print_assignment()
Definition: GraphCut.cpp:960
ETerminalType
Definition: GraphCut.h:31
Node * next
Definition: GraphCut.h:52
float64_t m_map_energy
Definition: GraphCut.h:276
void add_edge(int32_t i, int32_t j, float64_t capacity, float64_t reverse_capacity)
Definition: GraphCut.cpp:427
Class CMAPInferImpl abstract class of MAP inference implementation.
Definition: MAPInference.h:97
void build_st_graph(int32_t num_nodes, int32_t num_edges)
Definition: GraphCut.cpp:107
float64_t compute_maxflow()
Definition: GraphCut.cpp:516
void add_tweights(int32_t i, float64_t cap_source, float64_t cap_sink)
Definition: GraphCut.cpp:407
int32_t timestamp
Definition: GraphCut.h:53
Edge * parent
Definition: GraphCut.h:51
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
ETerminalType type_tree
Definition: GraphCut.h:55
ETerminalType get_assignment(int32_t i, ETerminalType default_termainl=SOURCE)
Definition: GraphCut.cpp:920
float64_t get_flow()
Definition: GraphCut.h:116
Edge * first
Definition: GraphCut.h:50
Class CFactorGraph a factor graph is a structured input in general.
Definition: FactorGraph.h:27
float64_t tree_cap
Definition: GraphCut.h:56
Node * head
Definition: GraphCut.h:41
virtual ~CGraphCut()
Definition: GraphCut.cpp:47
Node * ptr
Definition: GraphCut.h:62
Edge * reverse
Definition: GraphCut.h:43
Edge * next
Definition: GraphCut.h:42
NodePtr * next
Definition: GraphCut.h:63
int32_t dist_terminal
Definition: GraphCut.h:54
int32_t id
Definition: GraphCut.h:40
Class CFactor A factor is defined on a clique in the factor graph. Each factor can have its own data...
Definition: Factor.h:89
virtual float64_t inference(SGVector< int32_t > assignment)
Definition: GraphCut.cpp:169

SHOGUN 机器学习工具包 - 项目文档