testFindSeparator.cpp
Go to the documentation of this file.
1 /*
2  * testFindSeparator.cpp
3  *
4  * Created on: Nov 23, 2010
5  * Author: nikai
6  * Description: unit tests for FindSeparator
7  */
8 
10 
13 
14 using namespace std;
15 using namespace gtsam;
16 using namespace gtsam::partition;
17 
18 /* ************************************************************************* */
19 // x0 - x1 - x2
20 // l3 l4
22 {
24  graph.push_back(std::make_shared<GenericFactor2D>(0, NODE_POSE_2D, 3, NODE_LANDMARK_2D));
25  graph.push_back(std::make_shared<GenericFactor2D>(2, NODE_POSE_2D, 4, NODE_LANDMARK_2D));
26  graph.push_back(std::make_shared<GenericFactor2D>(0, NODE_POSE_2D, 1, NODE_POSE_2D));
27  graph.push_back(std::make_shared<GenericFactor2D>(1, NODE_POSE_2D, 2, NODE_POSE_2D));
28  std::vector<size_t> keys{0, 1, 2, 3, 4};
29 
30  WorkSpace workspace(5);
31  std::optional<MetisResult> actual = separatorPartitionByMetis<GenericGraph2D>(graph, keys,
32  workspace, true);
33 
34  CHECK(actual.has_value());
35  vector<size_t> A_expected{0, 3}; // frontal
36  vector<size_t> B_expected{2, 4}; // frontal
37  vector<size_t> C_expected{1}; // separator
38  CHECK(A_expected == actual->A);
39  CHECK(B_expected == actual->B);
40  CHECK(C_expected == actual->C);
41 }
42 
43 /* ************************************************************************* */
44 // x1 - x2 - x3, variable not used x0, x4, l7
45 // l5 l6
46 TEST ( Partition, separatorPartitionByMetis2 )
47 {
49  graph.push_back(std::make_shared<GenericFactor2D>(1, NODE_POSE_2D, 5, NODE_LANDMARK_2D));
50  graph.push_back(std::make_shared<GenericFactor2D>(3, NODE_POSE_2D, 6, NODE_LANDMARK_2D));
51  graph.push_back(std::make_shared<GenericFactor2D>(1, NODE_POSE_2D, 2, NODE_POSE_2D));
52  graph.push_back(std::make_shared<GenericFactor2D>(2, NODE_POSE_2D, 3, NODE_POSE_2D));
53  std::vector<size_t> keys{1, 2, 3, 5, 6};
54 
55  WorkSpace workspace(8);
56  std::optional<MetisResult> actual = separatorPartitionByMetis<GenericGraph2D>(graph, keys,
57  workspace, true);
58 
59  CHECK(actual.has_value());
60  vector<size_t> A_expected{1, 5}; // frontal
61  vector<size_t> B_expected{3, 6}; // frontal
62  vector<size_t> C_expected{2}; // separator
63  CHECK(A_expected == actual->A);
64  CHECK(B_expected == actual->B);
65  CHECK(C_expected == actual->C);
66 }
67 
68 /* *************************************************************************/
69 // x0 - x1 - x2 - x3
70 TEST ( Partition, edgePartitionByMetis )
71 {
73  graph.push_back(std::make_shared<GenericFactor3D>(0, 1, 0, NODE_POSE_3D, NODE_POSE_3D));
74  graph.push_back(std::make_shared<GenericFactor3D>(1, 2, 1, NODE_POSE_3D, NODE_POSE_3D));
75  graph.push_back(std::make_shared<GenericFactor3D>(2, 3, 2, NODE_POSE_3D, NODE_POSE_3D));
76  std::vector<size_t> keys{0, 1, 2, 3};
77 
78  WorkSpace workspace(6);
79  std::optional<MetisResult> actual = edgePartitionByMetis<GenericGraph3D>(graph, keys,
80  workspace, true);
81 
82  CHECK(actual.has_value());
83  vector<size_t> A_expected{0, 1}; // frontal
84  vector<size_t> B_expected{2, 3}; // frontal
85  vector<size_t> C_expected; // separator
86 // for(const size_t a: actual->A)
87 // cout << a << " ";
88 // cout << endl;
89 // for(const size_t b: actual->B)
90 // cout << b << " ";
91 // cout << endl;
92 
93  CHECK(A_expected == actual->A || A_expected == actual->B);
94  CHECK(B_expected == actual->B || B_expected == actual->A);
95  CHECK(C_expected == actual->C);
96 }
97 
98 /* *************************************************************************/
99 // x0 - x1 - x2 - x3 - x4
100 TEST ( Partition, edgePartitionByMetis2 )
101 {
103  graph.push_back(std::make_shared<GenericFactor3D>(0, 1, 0, NODE_POSE_3D, NODE_POSE_3D, 1));
104  graph.push_back(std::make_shared<GenericFactor3D>(1, 2, 1, NODE_POSE_3D, NODE_POSE_3D, 1));
105  graph.push_back(std::make_shared<GenericFactor3D>(2, 3, 2, NODE_POSE_3D, NODE_POSE_3D, 20));
106  graph.push_back(std::make_shared<GenericFactor3D>(3, 4, 3, NODE_POSE_3D, NODE_POSE_3D, 1));
107  std::vector<size_t> keys{0, 1, 2, 3, 4};
108 
109  WorkSpace workspace(6);
110  std::optional<MetisResult> actual = edgePartitionByMetis<GenericGraph3D>(graph, keys,
111  workspace, true);
112  CHECK(actual.has_value());
113  vector<size_t> A_expected{0, 1}; // frontal
114  vector<size_t> B_expected{2, 3, 4}; // frontal
115  vector<size_t> C_expected; // separator
116  CHECK(A_expected == actual->A);
117  CHECK(B_expected == actual->B);
118  CHECK(C_expected == actual->C);
119 }
120 
121 /* ************************************************************************* */
122 // x0 - x1 - x2
123 // l3 l4
124 TEST ( Partition, findSeparator )
125 {
127  graph.push_back(std::make_shared<GenericFactor2D>(0, NODE_POSE_2D, 3, NODE_LANDMARK_2D));
128  graph.push_back(std::make_shared<GenericFactor2D>(2, NODE_POSE_2D, 4, NODE_LANDMARK_2D));
129  graph.push_back(std::make_shared<GenericFactor2D>(0, NODE_POSE_2D, 1, NODE_POSE_2D));
130  graph.push_back(std::make_shared<GenericFactor2D>(1, NODE_POSE_2D, 2, NODE_POSE_2D));
131  std::vector<size_t> keys{0, 1, 2, 3, 4};
132 
133  WorkSpace workspace(5);
134  int minNodesPerMap = -1;
135  bool reduceGraph = false;
136  int numSubmaps = findSeparator<GenericGraph2D>(graph, keys, minNodesPerMap, workspace,
137  false, {}, reduceGraph, 0, 0);
138  LONGS_EQUAL(2, numSubmaps);
139  LONGS_EQUAL(5, workspace.partitionTable.size());
140  LONGS_EQUAL(1, workspace.partitionTable[0]);
141  LONGS_EQUAL(0, workspace.partitionTable[1]);
142  LONGS_EQUAL(2, workspace.partitionTable[2]);
143  LONGS_EQUAL(1, workspace.partitionTable[3]);
144  LONGS_EQUAL(2, workspace.partitionTable[4]);
145 }
146 
147 /* ************************************************************************* */
148 // x1 - x2 - x3, variable not used x0, x4, l7
149 // l5 l6
150 TEST ( Partition, findSeparator2 )
151 {
153  graph.push_back(std::make_shared<GenericFactor2D>(1, NODE_POSE_2D, 5, NODE_LANDMARK_2D));
154  graph.push_back(std::make_shared<GenericFactor2D>(3, NODE_POSE_2D, 6, NODE_LANDMARK_2D));
155  graph.push_back(std::make_shared<GenericFactor2D>(1, NODE_POSE_2D, 2, NODE_POSE_2D));
156  graph.push_back(std::make_shared<GenericFactor2D>(2, NODE_POSE_2D, 3, NODE_POSE_2D));
157  std::vector<size_t> keys{1, 2, 3, 5, 6};
158 
159  WorkSpace workspace(8);
160  int minNodesPerMap = -1;
161  bool reduceGraph = false;
162  int numSubmaps = findSeparator<GenericGraph2D>(graph, keys, minNodesPerMap, workspace,
163  false, {}, reduceGraph, 0, 0);
164  LONGS_EQUAL(2, numSubmaps);
165  LONGS_EQUAL(8, workspace.partitionTable.size());
166  LONGS_EQUAL(-1,workspace.partitionTable[0]);
167  LONGS_EQUAL(1, workspace.partitionTable[1]);
168  LONGS_EQUAL(0, workspace.partitionTable[2]);
169  LONGS_EQUAL(2, workspace.partitionTable[3]);
170  LONGS_EQUAL(-1,workspace.partitionTable[4]);
171  LONGS_EQUAL(1, workspace.partitionTable[5]);
172  LONGS_EQUAL(2, workspace.partitionTable[6]);
173  LONGS_EQUAL(-1,workspace.partitionTable[7]);
174 }
175 
176 /* *************************************************************************/
182 TEST ( Partition, findSeparator3_with_reduced_camera )
183 {
185  for (int j=1; j<=8; j++)
186  graph.push_back(std::make_shared<GenericFactor3D>(25, j));
187  for (int j=1; j<=16; j++)
188  graph.push_back(std::make_shared<GenericFactor3D>(26, j));
189  for (int j=9; j<=24; j++)
190  graph.push_back(std::make_shared<GenericFactor3D>(27, j));
191  for (int j=17; j<=24; j++)
192  graph.push_back(std::make_shared<GenericFactor3D>(28, j));
193 
194  std::vector<size_t> keys;
195  for(int i=1; i<=28; i++)
196  keys.push_back(i);
197 
198  vector<Symbol> int2symbol;
199  int2symbol.push_back(Symbol('x',0)); // dummy
200  for(int i=1; i<=24; i++)
201  int2symbol.push_back(Symbol('l',i));
202  int2symbol.push_back(Symbol('x',25));
203  int2symbol.push_back(Symbol('x',26));
204  int2symbol.push_back(Symbol('x',27));
205  int2symbol.push_back(Symbol('x',28));
206 
207  WorkSpace workspace(29);
208  bool reduceGraph = true;
209  int numIsland = findSeparator(graph, keys, 3, workspace, false, int2symbol, reduceGraph, 0, 0);
210  LONGS_EQUAL(2, numIsland);
211 
212  partition::PartitionTable& partitionTable = workspace.partitionTable;
213  for (int j=1; j<=8; j++)
214  LONGS_EQUAL(1, partitionTable[j]);
215  for (int j=9; j<=16; j++)
216  LONGS_EQUAL(0, partitionTable[j]);
217  for (int j=17; j<=24; j++)
218  LONGS_EQUAL(2, partitionTable[j]);
219  LONGS_EQUAL(1, partitionTable[25]);
220  LONGS_EQUAL(1, partitionTable[26]);
221  LONGS_EQUAL(2, partitionTable[27]);
222  LONGS_EQUAL(2, partitionTable[28]);
223 }
224 
225 /* ************************************************************************* */
226 int main() { TestResult tr; return TestRegistry::runAllTests(tr);}
227 /* ************************************************************************* */
std::optional< MetisResult > separatorPartitionByMetis(const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose)
#define CHECK(condition)
Definition: Test.h:108
int main()
static int runAllTests(TestResult &result)
TEST(Partition, separatorPartitionByMetis)
IsDerived< DERIVEDFACTOR > push_back(std::shared_ptr< DERIVEDFACTOR > factor)
Add a factor directly using a shared_ptr.
Definition: FactorGraph.h:190
Definition: BFloat16.h:88
NonlinearFactorGraph graph
std::optional< MetisResult > edgePartitionByMetis(const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose)
std::vector< sharedGenericFactor2D > GenericGraph2D
Definition: GenericGraph.h:49
int findSeparator(const GenericGraph &graph, const std::vector< size_t > &keys, const int minNodesPerMap, WorkSpace &workspace, bool verbose, const std::optional< std::vector< Symbol > > &int2symbol, const bool reduceGraph, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)
std::vector< sharedGenericFactor3D > GenericGraph3D
Definition: GenericGraph.h:97
#define LONGS_EQUAL(expected, actual)
Definition: Test.h:134
traits
Definition: chartTesting.h:28
std::vector< int > PartitionTable
const KeyVector keys
std::ptrdiff_t j


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:38:08