NestedDissection.h
Go to the documentation of this file.
1 /*
2  * NestedDissection.h
3  *
4  * Created on: Nov 27, 2010
5  * Author: nikai
6  * Description: apply nested dissection algorithm to the factor graph
7  */
8 
9 #pragma once
10 
11 #include <vector>
12 #include <memory>
13 #include <gtsam/nonlinear/Ordering.h>
14 
15 namespace gtsam { namespace partition {
16 
20  template <class NLG, class SubNLG, class GenericGraph>
22  public:
23  typedef std::shared_ptr<SubNLG> sharedSubNLG;
24 
25  private:
26  NLG fg_; // the original nonlinear factor graph
27  Ordering ordering_; // the variable ordering in the nonlinear factor graph
28  std::vector<Symbol> int2symbol_; // the mapping from integer key to symbol
29  sharedSubNLG root_; // the root of generated cluster tree
30 
31  public:
32  sharedSubNLG root() const { return root_; }
33 
34  public:
35  /* constructor with post-determined partitoning*/
36  NestedDissection(const NLG& fg, const Ordering& ordering, const int numNodeStopPartition, const int minNodesPerMap, const bool verbose = false);
37 
38  /* constructor with pre-determined cuts*/
39  NestedDissection(const NLG& fg, const Ordering& ordering, const std::shared_ptr<Cuts>& cuts, const bool verbose = false);
40 
41  private:
42  /* convert generic subgraph to nonlinear subgraph */
43  sharedSubNLG makeSubNLG(const NLG& fg, const std::vector<size_t>& frontals, const std::vector<size_t>& sep, const std::shared_ptr<SubNLG>& parent) const;
44 
45  void processFactor(const typename GenericGraph::value_type& factor, const std::vector<int>& partitionTable, // input
46  std::vector<GenericGraph>& frontalFactors, NLG& sepFactors, std::vector<std::set<size_t> >& childSeps, // output factor graphs
47  typename SubNLG::Weeklinks& weeklinks) const;
48 
49  /* recursively partition the generic graph */
51  const GenericGraph& fg, const GenericUnaryGraph& unaryFactors,
52  const std::vector<size_t>& keys, const std::vector<int>& partitionTable, const int numSubmaps, // input
53  std::vector<GenericGraph>& frontalFactors, vector<GenericUnaryGraph>& frontalUnaryFactors, NLG& sepFactors, // output factor graphs
54  std::vector<std::vector<size_t> >& childFrontals, std::vector<std::vector<size_t> >& childSeps, std::vector<size_t>& localFrontals, // output sub-orderings
55  typename SubNLG::Weeklinks& weeklinks) const;
56 
57  NLG collectOriginalFactors(const GenericGraph& gfg, const GenericUnaryGraph& unaryFactors) const;
58 
59  /* recursively partition the generic graph */
60  sharedSubNLG recursivePartition(const GenericGraph& gfg, const GenericUnaryGraph& unaryFactors, const std::vector<size_t>& frontals, const std::vector<size_t>& sep,
61  const int numNodeStopPartition, const int minNodesPerMap, const std::shared_ptr<SubNLG>& parent, WorkSpace& workspace, const bool verbose) const;
62 
63  /* recursively partition the generic graph */
64  sharedSubNLG recursivePartition(const GenericGraph& gfg, const GenericUnaryGraph& unaryFactors, const std::vector<size_t>& frontals, const std::vector<size_t>& sep,
65  const std::shared_ptr<Cuts>& cuts, const std::shared_ptr<SubNLG>& parent, WorkSpace& workspace, const bool verbose) const;
66 
67  };
68 
69 }} //namespace
gtsam::partition::NestedDissection::ordering_
Ordering ordering_
Definition: NestedDissection.h:27
gtsam::partition::WorkSpace
Definition: PartitionWorkSpace.h:19
gtsam::partition::NestedDissection::processFactor
void processFactor(const typename GenericGraph::value_type &factor, const std::vector< int > &partitionTable, std::vector< GenericGraph > &frontalFactors, NLG &sepFactors, std::vector< std::set< size_t > > &childSeps, typename SubNLG::Weeklinks &weeklinks) const
Definition: NestedDissection-inl.h:80
keys
const KeyVector keys
Definition: testRegularImplicitSchurFactor.cpp:40
gtsam::partition::NestedDissection::makeSubNLG
sharedSubNLG makeSubNLG(const NLG &fg, const std::vector< size_t > &frontals, const std::vector< size_t > &sep, const std::shared_ptr< SubNLG > &parent) const
Definition: NestedDissection-inl.h:65
gtsam::partition::NestedDissection::fg_
NLG fg_
Definition: NestedDissection.h:26
gtsam::partition::NestedDissection::partitionFactorsAndVariables
void partitionFactorsAndVariables(const GenericGraph &fg, const GenericUnaryGraph &unaryFactors, const std::vector< size_t > &keys, const std::vector< int > &partitionTable, const int numSubmaps, std::vector< GenericGraph > &frontalFactors, vector< GenericUnaryGraph > &frontalUnaryFactors, NLG &sepFactors, std::vector< std::vector< size_t > > &childFrontals, std::vector< std::vector< size_t > > &childSeps, std::vector< size_t > &localFrontals, typename SubNLG::Weeklinks &weeklinks) const
Definition: NestedDissection-inl.h:117
gtsam::partition::NestedDissection::root
sharedSubNLG root() const
Definition: NestedDissection.h:32
gtsam::partition::NestedDissection::int2symbol_
std::vector< Symbol > int2symbol_
Definition: NestedDissection.h:28
gtsam::partition::NestedDissection::NestedDissection
NestedDissection(const NLG &fg, const Ordering &ordering, const int numNodeStopPartition, const int minNodesPerMap, const bool verbose=false)
Definition: NestedDissection-inl.h:20
ordering
static enum @1096 ordering
gtsam::partition::NestedDissection
Definition: NestedDissection.h:21
gtsam::partition::GenericUnaryGraph
std::vector< sharedGenericUnaryFactor > GenericUnaryGraph
Definition: GenericGraph.h:131
gtsam::partition::NestedDissection::collectOriginalFactors
NLG collectOriginalFactors(const GenericGraph &gfg, const GenericUnaryGraph &unaryFactors) const
Definition: NestedDissection-inl.h:157
gtsam
traits
Definition: SFMdata.h:40
gtsam::partition::NestedDissection::root_
sharedSubNLG root_
Definition: NestedDissection.h:29
gtsam::partition::NestedDissection::sharedSubNLG
std::shared_ptr< SubNLG > sharedSubNLG
Definition: NestedDissection.h:23
sep
std::string sep
Definition: IOFormat.cpp:1
gtsam::Ordering
Definition: inference/Ordering.h:33
gtsam::partition::NestedDissection::recursivePartition
sharedSubNLG recursivePartition(const GenericGraph &gfg, const GenericUnaryGraph &unaryFactors, const std::vector< size_t > &frontals, const std::vector< size_t > &sep, const int numNodeStopPartition, const int minNodesPerMap, const std::shared_ptr< SubNLG > &parent, WorkSpace &workspace, const bool verbose) const
Definition: NestedDissection-inl.h:169


gtsam
Author(s):
autogenerated on Fri Nov 1 2024 03:33:49