gtsam  4.1.0
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 
23 namespace gtsam {
24 
25 /* ************************************************************************* */
26 template<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
gtsam::MetisIndex::augment
void augment(const FactorGraph< FACTOR > &factors)
Augment the variable index with new factors.
Definition: MetisIndex-inl.h:27
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:61
gtsam::FactorGraph::size
size_t size() const
return the number of factors (including any null factors set by remove() ).
Definition: FactorGraph.h:302
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::FactorGraph
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition: FactorGraph.h:94