FindSeparator-inl.h
Go to the documentation of this file.
1 /*
2  * FindSeparator-inl.h
3  *
4  * Created on: Nov 23, 2010
5  * Updated: Feb 20. 2014
6  * Author: nikai
7  * Author: Andrew Melim
8  * Description: find the separator of bisectioning for a given graph
9  */
10 
11 #pragma once
12 
13 #include <stdexcept>
14 #include <iostream>
15 #include <vector>
16 #include <boost/tuple/tuple.hpp>
17 #include <boost/shared_array.hpp>
18 
19 #include <gtsam/base/timing.h>
20 
21 #include "FindSeparator.h"
22 
23 extern "C" {
24 #include <metis.h>
25 #include "metislib.h"
26 }
27 
28 
29 
30 namespace gtsam { namespace partition {
31 
32  typedef boost::shared_array<idx_t> sharedInts;
33 
34  /* ************************************************************************* */
41  std::pair<int, sharedInts> separatorMetis(idx_t n, const sharedInts& xadj,
42  const sharedInts& adjncy, const sharedInts& adjwgt, bool verbose) {
43 
44  // control parameters
45  std::vector<idx_t> vwgt; // the weights of the vertices
46  idx_t options[METIS_NOPTIONS];
47  METIS_SetDefaultOptions(options); // use defaults
48  idx_t sepsize; // the size of the separator, output
49  sharedInts part_(new idx_t[n]); // the partition of each vertex, output
50 
51  // set uniform weights on the vertices
52  vwgt.assign(n, 1);
53 
54  // TODO: Fix at later time
55  //boost::timer::cpu_timer TOTALTmr;
56  if (verbose) {
57  printf("**********************************************************************\n");
58  printf("Graph Information ---------------------------------------------------\n");
59  printf(" #Vertices: %d, #Edges: %u\n", n, *(xadj.get()+n) / 2);
60  printf("\nND Partitioning... -------------------------------------------\n");
61  //TOTALTmr.start()
62  }
63 
64  // call metis parition routine
65  METIS_ComputeVertexSeparator(&n, xadj.get(), adjncy.get(),
66  &vwgt[0], options, &sepsize, part_.get());
67 
68  if (verbose) {
69  //boost::cpu_times const elapsed_times(timer.elapsed());
70  //printf("\nTiming Information --------------------------------------------------\n");
71  //printf(" Total: \t\t %7.3f\n", elapsed_times);
72  printf(" Sep size: \t\t %d\n", sepsize);
73  printf("**********************************************************************\n");
74  }
75 
76  return std::make_pair(sepsize, part_);
77  }
78 
79  /* ************************************************************************* */
80  void modefied_EdgeComputeSeparator(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt,
81  idx_t *adjwgt, idx_t *options, idx_t *edgecut, idx_t *part)
82  {
83  idx_t i, ncon;
84  graph_t *graph;
85  real_t *tpwgts2;
86  ctrl_t *ctrl;
87  ctrl = SetupCtrl(METIS_OP_OMETIS, options, 1, 3, nullptr, nullptr);
88  ctrl->iptype = METIS_IPTYPE_GROW;
89  //if () == nullptr)
90  // return METIS_ERROR_INPUT;
91 
92  InitRandom(ctrl->seed);
93 
94  graph = SetupGraph(ctrl, *nvtxs, 1, xadj, adjncy, vwgt, nullptr, nullptr);
95 
96  AllocateWorkSpace(ctrl, graph);
97 
98  ncon = graph->ncon;
99  ctrl->ncuts = 1;
100 
101  /* determine the weights of the two partitions as a function of the weight of the
102  target partition weights */
103 
104  tpwgts2 = rwspacemalloc(ctrl, 2*ncon);
105  for (i=0; i<ncon; i++) {
106  tpwgts2[i] = rsum((2>>1), ctrl->tpwgts+i, ncon);
107  tpwgts2[ncon+i] = 1.0 - tpwgts2[i];
108  }
109  /* perform the bisection */
110  *edgecut = MultilevelBisect(ctrl, graph, tpwgts2);
111 
112  // ConstructMinCoverSeparator(&ctrl, &graph, 1.05);
113  // *edgecut = graph->mincut;
114  // *sepsize = graph.pwgts[2];
115  icopy(*nvtxs, graph->where, part);
116  std::cout << "Finished bisection:" << *edgecut << std::endl;
117  FreeGraph(&graph);
118 
119  FreeCtrl(&ctrl);
120  }
121 
122  /* ************************************************************************* */
128  std::pair<int, sharedInts> edgeMetis(idx_t n, const sharedInts& xadj, const sharedInts& adjncy,
129  const sharedInts& adjwgt, bool verbose) {
130 
131  // control parameters
132  std::vector<idx_t> vwgt; // the weights of the vertices
133  idx_t options[METIS_NOPTIONS];
134  METIS_SetDefaultOptions(options); // use defaults
135  idx_t edgecut; // the number of edge cuts, output
136  sharedInts part_(new idx_t[n]); // the partition of each vertex, output
137 
138  // set uniform weights on the vertices
139  vwgt.assign(n, 1);
140 
141  //TODO: Fix later
142  //boost::timer TOTALTmr;
143  if (verbose) {
144  printf("**********************************************************************\n");
145  printf("Graph Information ---------------------------------------------------\n");
146  printf(" #Vertices: %d, #Edges: %u\n", n, *(xadj.get()+n) / 2);
147  printf("\nND Partitioning... -------------------------------------------\n");
148  //cleartimer(TOTALTmr);
149  //starttimer(TOTALTmr);
150  }
151 
152  //int wgtflag = 1; // only edge weights
153  //int numflag = 0; // c style numbering starting from 0
154  //int nparts = 2; // partition the graph to 2 submaps
155  modefied_EdgeComputeSeparator(&n, xadj.get(), adjncy.get(), &vwgt[0], adjwgt.get(),
156  options, &edgecut, part_.get());
157 
158 
159  if (verbose) {
160  //stoptimer(TOTALTmr);
161  printf("\nTiming Information --------------------------------------------------\n");
162  //printf(" Total: \t\t %7.3f\n", gettimer(TOTALTmr));
163  printf(" Edge cuts: \t\t %d\n", edgecut);
164  printf("**********************************************************************\n");
165  }
166 
167  return std::make_pair(edgecut, part_);
168  }
169 
170  /* ************************************************************************* */
176  template <class GenericGraph>
177  void prepareMetisGraph(const GenericGraph& graph, const std::vector<size_t>& keys, WorkSpace& workspace,
178  sharedInts* ptr_xadj, sharedInts* ptr_adjncy, sharedInts* ptr_adjwgt) {
179 
180  typedef std::vector<int> Weights;
181  typedef std::vector<int> Neighbors;
182  typedef std::pair<Neighbors, Weights> NeighborsInfo;
183 
184  // set up dictionary
185  std::vector<int>& dictionary = workspace.dictionary;
186  workspace.prepareDictionary(keys);
187 
188  // prepare for {adjacencyMap}, a pair of neighbor indices and the correponding edge weights
189  int numNodes = keys.size();
190  int numEdges = 0;
191  std::vector<NeighborsInfo> adjacencyMap;
192  adjacencyMap.resize(numNodes);
193  std::cout << "Number of nodes: " << adjacencyMap.size() << std::endl;
194  int index1, index2;
195 
196  for(const typename GenericGraph::value_type& factor: graph){
197  index1 = dictionary[factor->key1.index];
198  index2 = dictionary[factor->key2.index];
199  std::cout << "index1: " << index1 << std::endl;
200  std::cout << "index2: " << index2 << std::endl;
201  // if both nodes are in the current graph, i.e. not a joint factor between frontal and separator
202  if (index1 >= 0 && index2 >= 0) {
203  std::pair<Neighbors, Weights>& adjacencyMap1 = adjacencyMap[index1];
204  std::pair<Neighbors, Weights>& adjacencyMap2 = adjacencyMap[index2];
205  try{
206  adjacencyMap1.first.push_back(index2);
207  adjacencyMap1.second.push_back(factor->weight);
208  adjacencyMap2.first.push_back(index1);
209  adjacencyMap2.second.push_back(factor->weight);
210  }catch(std::exception& e){
211  std::cout << e.what() << std::endl;
212  }
213  numEdges++;
214  }
215  }
216 
217  // prepare for {xadj}, {adjncy}, and {adjwgt}
218  *ptr_xadj = sharedInts(new idx_t[numNodes+1]);
219  *ptr_adjncy = sharedInts(new idx_t[numEdges*2]);
220  *ptr_adjwgt = sharedInts(new idx_t[numEdges*2]);
221  sharedInts& xadj = *ptr_xadj;
222  sharedInts& adjncy = *ptr_adjncy;
223  sharedInts& adjwgt = *ptr_adjwgt;
224  int ind_xadj = 0, ind_adjncy = 0;
225  for(const NeighborsInfo& info: adjacencyMap) {
226  *(xadj.get() + ind_xadj) = ind_adjncy;
227  std::copy(info.first .begin(), info.first .end(), adjncy.get() + ind_adjncy);
228  std::copy(info.second.begin(), info.second.end(), adjwgt.get() + ind_adjncy);
229  assert(info.first.size() == info.second.size());
230  ind_adjncy += info.first.size();
231  ind_xadj ++;
232  }
233  if (ind_xadj != numNodes) throw std::runtime_error("prepareMetisGraph_: ind_xadj != numNodes");
234  *(xadj.get() + ind_xadj) = ind_adjncy;
235  }
236 
237  /* ************************************************************************* */
238  template<class GenericGraph>
239  boost::optional<MetisResult> separatorPartitionByMetis(const GenericGraph& graph,
240  const std::vector<size_t>& keys, WorkSpace& workspace, bool verbose) {
241  // create a metis graph
242  size_t numKeys = keys.size();
243  if (verbose)
244  std::cout << graph.size() << " factors,\t" << numKeys << " nodes;\t" << std::endl;
245 
246  sharedInts xadj, adjncy, adjwgt;
247 
248  prepareMetisGraph<GenericGraph>(graph, keys, workspace, &xadj, &adjncy, &adjwgt);
249 
250  // run ND on the graph
251  size_t sepsize;
252  sharedInts part;
253  boost::tie(sepsize, part) = separatorMetis(numKeys, xadj, adjncy, adjwgt, verbose);
254  if (!sepsize) return boost::optional<MetisResult>();
255 
256  // convert the 0-1-2 from Metis to 1-2-0, so that the separator is 0, as later
257  // we will have more submaps
258  MetisResult result;
259  result.C.reserve(sepsize);
260  result.A.reserve(numKeys - sepsize);
261  result.B.reserve(numKeys - sepsize);
262  int* ptr_part = part.get();
263  std::vector<size_t>::const_iterator itKey = keys.begin();
264  std::vector<size_t>::const_iterator itKeyLast = keys.end();
265  while(itKey != itKeyLast) {
266  switch(*(ptr_part++)) {
267  case 0: result.A.push_back(*(itKey++)); break;
268  case 1: result.B.push_back(*(itKey++)); break;
269  case 2: result.C.push_back(*(itKey++)); break;
270  default: throw std::runtime_error("separatorPartitionByMetis: invalid results from Metis ND!");
271  }
272  }
273 
274  if (verbose) {
275  std::cout << "total key: " << keys.size()
276  << " result(A,B,C) = " << result.A.size() << ", " << result.B.size() << ", "
277  << result.C.size() << "; sepsize from Metis = " << sepsize << std::endl;
278  //throw runtime_error("separatorPartitionByMetis:stop for debug");
279  }
280 
281  if(result.C.size() != sepsize) {
282  std::cout << "total key: " << keys.size()
283  << " result(A,B,C) = " << result.A.size() << ", " << result.B.size() << ", " << result.C.size()
284  << "; sepsize from Metis = " << sepsize << std::endl;
285  throw std::runtime_error("separatorPartitionByMetis: invalid sepsize from Metis ND!");
286  }
287 
288  return result;
289  }
290 
291  /* *************************************************************************/
292  template<class GenericGraph>
293  boost::optional<MetisResult> edgePartitionByMetis(const GenericGraph& graph,
294  const std::vector<size_t>& keys, WorkSpace& workspace, bool verbose) {
295 
296  // a small hack for handling the camera1-camera2 case used in the unit tests
297  if (graph.size() == 1 && keys.size() == 2) {
298  MetisResult result;
299  result.A.push_back(keys.front());
300  result.B.push_back(keys.back());
301  return result;
302  }
303 
304  // create a metis graph
305  size_t numKeys = keys.size();
306  if (verbose) std::cout << graph.size() << " factors,\t" << numKeys << " nodes;\t" << std::endl;
307  sharedInts xadj, adjncy, adjwgt;
308  prepareMetisGraph<GenericGraph>(graph, keys, workspace, &xadj, &adjncy, &adjwgt);
309 
310  // run metis on the graph
311  int edgecut;
312  sharedInts part;
313  boost::tie(edgecut, part) = edgeMetis(numKeys, xadj, adjncy, adjwgt, verbose);
314 
315  // convert the 0-1-2 from Metis to 1-2-0, so that the separator is 0, as later we will have more submaps
316  MetisResult result;
317  result.A.reserve(numKeys);
318  result.B.reserve(numKeys);
319  int* ptr_part = part.get();
320  std::vector<size_t>::const_iterator itKey = keys.begin();
321  std::vector<size_t>::const_iterator itKeyLast = keys.end();
322  while(itKey != itKeyLast) {
323  if (*ptr_part != 0 && *ptr_part != 1)
324  std::cout << *ptr_part << "!!!" << std::endl;
325  switch(*(ptr_part++)) {
326  case 0: result.A.push_back(*(itKey++)); break;
327  case 1: result.B.push_back(*(itKey++)); break;
328  default: throw std::runtime_error("edgePartitionByMetis: invalid results from Metis ND!");
329  }
330  }
331 
332  if (verbose) {
333  std::cout << "the size of two submaps in the reduced graph: " << result.A.size()
334  << " " << result.B.size() << std::endl;
335  int edgeCut = 0;
336 
337  for(const typename GenericGraph::value_type& factor: graph){
338  int key1 = factor->key1.index;
339  int key2 = factor->key2.index;
340  // print keys and their subgraph assignment
341  std::cout << key1;
342  if (std::find(result.A.begin(), result.A.end(), key1) != result.A.end()) std::cout <<"A ";
343  if (std::find(result.B.begin(), result.B.end(), key1) != result.B.end()) std::cout <<"B ";
344 
345  std::cout << key2;
346  if (std::find(result.A.begin(), result.A.end(), key2) != result.A.end()) std::cout <<"A ";
347  if (std::find(result.B.begin(), result.B.end(), key2) != result.B.end()) std::cout <<"B ";
348  std::cout << "weight " << factor->weight;;
349 
350  // find vertices that were assigned to sets A & B. Their edge will be cut
351  if ((std::find(result.A.begin(), result.A.end(), key1) != result.A.end() &&
352  std::find(result.B.begin(), result.B.end(), key2) != result.B.end()) ||
353  (std::find(result.B.begin(), result.B.end(), key1) != result.B.end() &&
354  std::find(result.A.begin(), result.A.end(), key2) != result.A.end())){
355  edgeCut ++;
356  std::cout << " CUT ";
357  }
358  std::cout << std::endl;
359  }
360  std::cout << "edgeCut: " << edgeCut << std::endl;
361  }
362 
363  return result;
364  }
365 
366  /* ************************************************************************* */
367  bool isLargerIsland(const std::vector<size_t>& island1, const std::vector<size_t>& island2) {
368  return island1.size() > island2.size();
369  }
370 
371  /* ************************************************************************* */
372  // debug functions
373  void printIsland(const std::vector<size_t>& island) {
374  std::cout << "island: ";
375  for(const size_t key: island)
376  std::cout << key << " ";
377  std::cout << std::endl;
378  }
379 
380  void printIslands(const std::list<std::vector<size_t> >& islands) {
381  for(const std::vector<std::size_t>& island: islands)
382  printIsland(island);
383  }
384 
385  void printNumCamerasLandmarks(const std::vector<size_t>& keys, const std::vector<Symbol>& int2symbol) {
386  int numCamera = 0, numLandmark = 0;
387  for(const size_t key: keys)
388  if (int2symbol[key].chr() == 'x')
389  numCamera++;
390  else
391  numLandmark++;
392  std::cout << "numCamera: " << numCamera << " numLandmark: " << numLandmark << std::endl;
393  }
394 
395  /* ************************************************************************* */
396  template<class GenericGraph>
397  void addLandmarkToPartitionResult(const GenericGraph& graph, const std::vector<size_t>& landmarkKeys,
398  MetisResult& partitionResult, WorkSpace& workspace) {
399 
400  // set up cameras in the dictionary
401  std::vector<size_t>& A = partitionResult.A;
402  std::vector<size_t>& B = partitionResult.B;
403  std::vector<size_t>& C = partitionResult.C;
404  std::vector<int>& dictionary = workspace.dictionary;
405  std::fill(dictionary.begin(), dictionary.end(), -1);
406  for(const size_t a: A)
407  dictionary[a] = 1;
408  for(const size_t b: B)
409  dictionary[b] = 2;
410  if (!C.empty())
411  throw std::runtime_error("addLandmarkToPartitionResult: C is not empty");
412 
413  // set up landmarks
414  size_t i,j;
415  for(const typename GenericGraph::value_type& factor: graph) {
416  i = factor->key1.index;
417  j = factor->key2.index;
418  if (dictionary[j] == 0) // if the landmark is already in the separator, continue
419  continue;
420  else if (dictionary[j] == -1)
421  dictionary[j] = dictionary[i];
422  else {
423  if (dictionary[j] != dictionary[i])
424  dictionary[j] = 0;
425  }
426 // if (j == 67980)
427 // std::cout << "dictionary[67980]" << dictionary[j] << std::endl;
428  }
429 
430  for(const size_t j: landmarkKeys) {
431  switch(dictionary[j]) {
432  case 0: C.push_back(j); break;
433  case 1: A.push_back(j); break;
434  case 2: B.push_back(j); break;
435  default: std::cout << j << ": " << dictionary[j] << std::endl;
436  throw std::runtime_error("addLandmarkToPartitionResult: wrong status for landmark");
437  }
438  }
439  }
440 
441 #define REDUCE_CAMERA_GRAPH
442 
443  /* ************************************************************************* */
444  template<class GenericGraph>
445  boost::optional<MetisResult> findPartitoning(const GenericGraph& graph, const std::vector<size_t>& keys,
446  WorkSpace& workspace, bool verbose,
447  const boost::optional<std::vector<Symbol> >& int2symbol, const bool reduceGraph) {
448  boost::optional<MetisResult> result;
449  GenericGraph reducedGraph;
450  std::vector<size_t> keyToPartition;
451  std::vector<size_t> cameraKeys, landmarkKeys;
452  if (reduceGraph) {
453  if (!int2symbol.is_initialized())
454  throw std::invalid_argument("findSeparator: int2symbol must be valid!");
455 
456  // find out all the landmark keys, which are to be eliminated
457  cameraKeys.reserve(keys.size());
458  landmarkKeys.reserve(keys.size());
459  for(const size_t key: keys) {
460  if((*int2symbol)[key].chr() == 'x')
461  cameraKeys.push_back(key);
462  else
463  landmarkKeys.push_back(key);
464  }
465 
466  keyToPartition = cameraKeys;
467  workspace.prepareDictionary(keyToPartition);
468  const std::vector<int>& dictionary = workspace.dictionary;
469  reduceGenericGraph(graph, cameraKeys, landmarkKeys, dictionary, reducedGraph);
470  std::cout << "original graph: V" << keys.size() << ", E" << graph.size()
471  << " --> reduced graph: V" << cameraKeys.size() << ", E" << reducedGraph.size() << std::endl;
472  result = edgePartitionByMetis(reducedGraph, keyToPartition, workspace, verbose);
473  } else // call Metis to partition the graph to A, B, C
474  result = separatorPartitionByMetis(graph, keys, workspace, verbose);
475 
476  if (!result.is_initialized()) {
477  std::cout << "metis failed!" << std::endl;
478  return boost::none;
479  }
480 
481  if (reduceGraph) {
482  addLandmarkToPartitionResult(graph, landmarkKeys, *result, workspace);
483  std::cout << "the separator size: " << result->C.size() << " landmarks" << std::endl;
484  }
485 
486  return result;
487  }
488 
489  /* ************************************************************************* */
490  template<class GenericGraph>
491  int findSeparator(const GenericGraph& graph, const std::vector<size_t>& keys,
492  const int minNodesPerMap, WorkSpace& workspace, bool verbose,
493  const boost::optional<std::vector<Symbol> >& int2symbol, const bool reduceGraph,
494  const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark) {
495 
496  boost::optional<MetisResult> result = findPartitoning(graph, keys, workspace,
497  verbose, int2symbol, reduceGraph);
498 
499  // find the island in A and B, and make them separated submaps
500  typedef std::vector<size_t> Island;
501  std::list<Island> islands;
502 
503  std::list<Island> islands_in_A = findIslands(graph, result->A, workspace,
504  minNrConstraintsPerCamera, minNrConstraintsPerLandmark);
505 
506  std::list<Island> islands_in_B = findIslands(graph, result->B, workspace,
507  minNrConstraintsPerCamera, minNrConstraintsPerLandmark);
508 
509  islands.insert(islands.end(), islands_in_A.begin(), islands_in_A.end());
510  islands.insert(islands.end(), islands_in_B.begin(), islands_in_B.end());
511  islands.sort(isLargerIsland);
512  size_t numIsland0 = islands.size();
513 
514 #ifdef NDEBUG
515 // verbose = true;
516 // if (!int2symbol) throw std::invalid_argument("findSeparator: int2symbol is not set!");
517 // std::cout << "sep size: " << result->C.size() << "; ";
518 // printNumCamerasLandmarks(result->C, *int2symbol);
519 // std::cout << "no. of island: " << islands.size() << "; ";
520 // std::cout << "island size: ";
521 // for(const Island& island: islands)
522 // std::cout << island.size() << " ";
523 // std::cout << std::endl;
524 
525 // for(const Island& island: islands) {
526 // printNumCamerasLandmarks(island, int2symbol);
527 // }
528 #endif
529 
530  // absorb small components into the separator
531  size_t oldSize = islands.size();
532  while(true) {
533  if (islands.size() < 2) {
534  std::cout << "numIsland: " << numIsland0 << std::endl;
535  throw std::runtime_error("findSeparator: found fewer than 2 submaps!");
536  }
537 
538  std::list<Island>::reference island = islands.back();
539  if ((int)island.size() >= minNodesPerMap) break;
540  result->C.insert(result->C.end(), island.begin(), island.end());
541  islands.pop_back();
542  }
543  if (islands.size() != oldSize){
544  if (verbose) std::cout << oldSize << "-" << oldSize - islands.size() << " submap(s);\t" << std::endl;
545  }
546  else{
547  if (verbose) std::cout << oldSize << " submap(s);\t" << std::endl;
548  }
549 
550  // generate the node map
551  std::vector<int>& partitionTable = workspace.partitionTable;
552  std::fill(partitionTable.begin(), partitionTable.end(), -1);
553  for(const size_t key: result->C)
554  partitionTable[key] = 0;
555  int idx = 0;
556  for(const Island& island: islands) {
557  idx++;
558  for(const size_t key: island) {
559  partitionTable[key] = idx;
560  }
561  }
562 
563  return islands.size();
564  }
565 
566 }} //namespace
gtsam::partition::findIslands
list< vector< size_t > > findIslands(const GenericGraph2D &graph, const vector< size_t > &keys, WorkSpace &workspace, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)
Definition: GenericGraph.cpp:23
ctrl_t
Definition: libmetis/struct.h:139
vwgt
idx_t idx_t idx_t idx_t * vwgt
Definition: include/metis.h:197
ctrl_t::tpwgts
real_t * tpwgts
Definition: libmetis/struct.h:169
sepsize
idx_t idx_t idx_t idx_t idx_t * sepsize
Definition: include/metis.h:236
part
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t idx_t idx_t idx_t * part
Definition: include/metis.h:197
SetupGraph
#define SetupGraph
Definition: rename.h:90
ctrl_t::seed
idx_t seed
Definition: libmetis/struct.h:156
FreeGraph
#define FreeGraph
Definition: rename.h:98
gtsam::partition::MetisResult::B
std::vector< size_t > B
Definition: FindSeparator.h:23
xadj
idx_t idx_t * xadj
Definition: include/metis.h:197
gtsam::partition::sharedInts
boost::shared_array< idx_t > sharedInts
Definition: FindSeparator-inl.h:32
rwspacemalloc
#define rwspacemalloc
Definition: rename.h:257
n
int n
Definition: BiCGSTAB_simple.cpp:1
graph_t::where
idx_t * where
Definition: libmetis/struct.h:105
gtsam::partition::findPartitoning
boost::optional< MetisResult > findPartitoning(const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose, const boost::optional< std::vector< Symbol > > &int2symbol, const bool reduceGraph)
Definition: FindSeparator-inl.h:445
gtsam::partition::edgeMetis
std::pair< int, sharedInts > edgeMetis(idx_t n, const sharedInts &xadj, const sharedInts &adjncy, const sharedInts &adjwgt, bool verbose)
Definition: FindSeparator-inl.h:128
gtsam::partition::printIsland
void printIsland(const std::vector< size_t > &island)
Definition: FindSeparator-inl.h:373
METIS_ComputeVertexSeparator
int METIS_ComputeVertexSeparator(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *options, idx_t *r_sepsize, idx_t *part)
Definition: parmetis.c:161
ctrl_t::ncuts
idx_t ncuts
Definition: libmetis/struct.h:157
graph
NonlinearFactorGraph graph
Definition: doc/Code/OdometryExample.cpp:2
METIS_SetDefaultOptions
int METIS_SetDefaultOptions(idx_t *options)
Definition: auxapi.c:36
MultilevelBisect
#define MultilevelBisect
Definition: rename.h:208
a
Array33i a
Definition: Cwise_product.cpp:1
verbose
const bool verbose
Definition: serializationTestHelpers.h:33
key1
const Symbol key1('v', 1)
info
else if n * info
Definition: 3rdparty/Eigen/lapack/cholesky.cpp:18
METIS_NOPTIONS
#define METIS_NOPTIONS
Definition: include/metis.h:175
InitRandom
#define InitRandom
Definition: rename.h:246
AllocateWorkSpace
#define AllocateWorkSpace
Definition: rename.h:250
edgecut
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t idx_t idx_t * edgecut
Definition: include/metis.h:197
gtsam::partition::isLargerIsland
bool isLargerIsland(const std::vector< size_t > &island1, const std::vector< size_t > &island2)
Definition: FindSeparator-inl.h:367
rsum
#define rsum
Definition: gklib_rename.h:117
gtsam::partition::addLandmarkToPartitionResult
void addLandmarkToPartitionResult(const GenericGraph &graph, const std::vector< size_t > &landmarkKeys, MetisResult &partitionResult, WorkSpace &workspace)
Definition: FindSeparator-inl.h:397
result
Values result
Definition: OdometryOptimize.cpp:8
idx_t
int32_t idx_t
Definition: include/metis.h:101
options
idx_t idx_t idx_t idx_t idx_t idx_t idx_t real_t real_t idx_t * options
Definition: include/metis.h:197
graph_t::ncon
idx_t ncon
Definition: libmetis/struct.h:84
gtsam::partition::reduceGenericGraph
void reduceGenericGraph(const GenericGraph3D &graph, const std::vector< size_t > &cameraKeys, const std::vector< size_t > &landmarkKeys, const std::vector< int > &dictionary, GenericGraph3D &reducedGraph)
Definition: GenericGraph.cpp:353
e
Array< double, 1, 3 > e(1./3., 0.5, 2.)
gtsam::partition::MetisResult::A
std::vector< size_t > A
Definition: FindSeparator.h:23
real_t
float real_t
Definition: include/metis.h:132
ncon
idx_t * ncon
Definition: include/metis.h:197
gtsam::b
const G & b
Definition: Group.h:83
SetupCtrl
#define SetupCtrl
Definition: rename.h:194
gtsam::partition::separatorPartitionByMetis
boost::optional< MetisResult > separatorPartitionByMetis(const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose)
Definition: FindSeparator-inl.h:239
C
Matrix< Scalar, Dynamic, Dynamic > C
Definition: bench_gemm.cpp:37
gtsam
traits
Definition: chartTesting.h:28
adjwgt
idx_t idx_t idx_t idx_t idx_t idx_t * adjwgt
Definition: include/metis.h:197
FreeCtrl
#define FreeCtrl
Definition: rename.h:198
icopy
#define icopy
Definition: gklib_rename.h:28
gtsam::partition::prepareMetisGraph
void prepareMetisGraph(const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, sharedInts *ptr_xadj, sharedInts *ptr_adjncy, sharedInts *ptr_adjwgt)
Definition: FindSeparator-inl.h:177
gtsam::partition::modefied_EdgeComputeSeparator
void modefied_EdgeComputeSeparator(idx_t *nvtxs, idx_t *xadj, idx_t *adjncy, idx_t *vwgt, idx_t *adjwgt, idx_t *options, idx_t *edgecut, idx_t *part)
Definition: FindSeparator-inl.h:80
gtsam::partition::separatorMetis
std::pair< int, sharedInts > separatorMetis(idx_t n, const sharedInts &xadj, const sharedInts &adjncy, const sharedInts &adjwgt, bool verbose)
Definition: FindSeparator-inl.h:41
key2
const Symbol key2('v', 2)
adjncy
idx_t idx_t idx_t * adjncy
Definition: include/metis.h:197
gtsam::partition::printNumCamerasLandmarks
void printNumCamerasLandmarks(const std::vector< size_t > &keys, const std::vector< Symbol > &int2symbol)
Definition: FindSeparator-inl.h:385
gtsam::partition::WorkSpace::prepareDictionary
void prepareDictionary(const std::vector< size_t > &keys)
Definition: PartitionWorkSpace.h:29
gtsam::partition::findSeparator
int findSeparator(const GenericGraph &graph, const std::vector< size_t > &keys, const int minNodesPerMap, WorkSpace &workspace, bool verbose, const boost::optional< std::vector< Symbol > > &int2symbol, const bool reduceGraph, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark)
Definition: FindSeparator-inl.h:491
graph_t
Definition: libmetis/struct.h:82
keys
const KeyVector keys
Definition: testRegularImplicitSchurFactor.cpp:45
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
j
std::ptrdiff_t j
Definition: tut_arithmetic_redux_minmax.cpp:2
gtsam::partition::printIslands
void printIslands(const std::list< std::vector< size_t > > &islands)
Definition: FindSeparator-inl.h:380
timing.h
Timing utilities.
gtsam::partition::MetisResult::C
std::vector< size_t > C
Definition: FindSeparator.h:24
gtsam::partition::edgePartitionByMetis
boost::optional< MetisResult > edgePartitionByMetis(const GenericGraph &graph, const std::vector< size_t > &keys, WorkSpace &workspace, bool verbose)
Definition: FindSeparator-inl.h:293
ctrl_t::iptype
miptype_et iptype
Definition: libmetis/struct.h:144

gtsam
Author(s):
autogenerated on Sat May 8 2021 02:42:04