1/*
2 * FindSeparator.h
3 *
4 * Created on: Nov 23, 2010
5 * Author: nikai
6 * Description: find the separator of bisectioning for a given graph
7 */
8
9#pragma once
10
11#include <map>
12#include <vector>
13#include <gtsam/inference/Key.h>
14#include <gtsam/inference/Symbol.h>
15
16#include "PartitionWorkSpace.h"
17
18namespace gtsam { namespace partition {
19
20// typedef std::map<size_t, size_t> PartitionTable; // from the key to the partition: 0 - separator, > 1: submap id
21
22 /** the metis Nest dissection result */
23 struct MetisResult {
24 std::vector<size_t> A, B; // frontals
25 std::vector<size_t> C; // separator
26 };
27
28 /**
29 * use Metis library to partition, return the size of separator and the optional partition table
30 * the size of dictionary mush be equal to the number of variables in the original graph (the largest one)
31 */
32 template<class GenericGraph>
33 std::optional<MetisResult> separatorPartitionByMetis(const GenericGraph& graph, const std::vector<size_t>& keys,
34 WorkSpace& workspace, bool verbose);
35
36 /**
37 * return the number of submaps and the parition table of the partitioned graph (**stored in workspace.partitionTable**).
38 * return 0 if failed Note that the original output of Metis is 0,1 for submap, and 2 for the separator.
39 */
40 template<class GenericGraph>
41 int findSeparator(const GenericGraph& graph, const std::vector<size_t>& keys,
42 const int minNodesPerMap, WorkSpace& workspace, bool verbose, const std::optional<std::vector<Symbol> >& int2symbol,
43 const bool reduceGraph, const int minNrConstraintsPerCamera, const int minNrConstraintsPerLandmark);
44
45}} //namespace
46