gtsam 4.1.1
gtsam
MetisIndex-inl.h
Go to the documentation of this file.
1/* ----------------------------------------------------------------------------
2
3 * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4 * Atlanta, Georgia 30332-0415
5 * All Rights Reserved
6 * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7
8 * See LICENSE for the license information
9
10 * -------------------------------------------------------------------------- */
11
18#pragma once
19
20#include <map>
21#include <vector>
22
23namespace gtsam {
24
25/* ************************************************************************* */
26template<class FACTOR>
28 std::map<int32_t, std::set<int32_t> > iAdjMap; // Stores a set of keys that are adjacent to key x, with adjMap.first
29 std::map<int32_t, std::set<int32_t> >::iterator iAdjMapIt;
30 std::set<Key> keySet;
31
32 /* ********** Convert to CSR format ********** */
33 // Assuming that vertex numbering starts from 0 (C style),
34 // then the adjacency list of vertex i is stored in array adjncy
35 // starting at index xadj[i] and ending at(but not including)
36 // index xadj[i + 1](i.e., adjncy[xadj[i]] through
37 // and including adjncy[xadj[i + 1] - 1]).
38 int32_t keyCounter = 0;
39
40 // First: Record a copy of each key inside the factorgraph and create a
41 // key to integer mapping. This is referenced during the adjaceny step
42 for (size_t i = 0; i < factors.size(); i++) {
43 if (factors[i]) {
44 for(const Key& key: *factors[i]) {
45 keySet.insert(keySet.end(), key); // Keep a track of all unique keys
46 if (intKeyBMap_.left.find(key) == intKeyBMap_.left.end()) {
47 intKeyBMap_.insert(bm_type::value_type(key, keyCounter));
48 keyCounter++;
49 }
50 }
51 }
52 }
53
54 // Create an adjacency mapping that stores the set of all adjacent keys for every key
55 for (size_t i = 0; i < factors.size(); i++) {
56 if (factors[i]) {
57 for(const Key& k1: *factors[i])
58 for(const Key& k2: *factors[i])
59 if (k1 != k2) {
60 // Store both in Key and int32_t format
61 int i = intKeyBMap_.left.at(k1);
62 int j = intKeyBMap_.left.at(k2);
63 iAdjMap[i].insert(iAdjMap[i].end(), j);
64 }
65 }
66 }
67
68 // Number of keys referenced in this factor graph
69 nKeys_ = keySet.size();
70
71 xadj_.push_back(0); // Always set the first index to zero
72 for (iAdjMapIt = iAdjMap.begin(); iAdjMapIt != iAdjMap.end(); ++iAdjMapIt) {
73 std::vector<int32_t> temp;
74 // Copy from the FastSet into a temporary vector
75 std::copy(iAdjMapIt->second.begin(), iAdjMapIt->second.end(),
76 std::back_inserter(temp));
77 // Insert each index's set in order by appending them to the end of adj_
78 adj_.insert(adj_.end(), temp.begin(), temp.end());
79 //adj_.push_back(temp);
80 xadj_.push_back((int32_t) adj_.size());
81 }
82}
83
84} // \ gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:69
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition: FactorGraph.h:93
size_t size() const
return the number of factors (including any null factors set by remove() ).
Definition: FactorGraph.h:305
void augment(const FactorGraph< FACTOR > &factors)
Augment the variable index with new factors.
Definition: MetisIndex-inl.h:27