knowrob  2.1.0
A Knowledge Base System for Cognition-enabled Robots
Classes | Public Member Functions | Protected Member Functions | Static Protected Member Functions | Protected Attributes | List of all members
knowrob::QueryTree Class Reference

#include <QueryTree.h>

Collaboration diagram for knowrob::QueryTree:
Collaboration graph
[legend]

Classes

class  Node
 
struct  NodeComparator
 
class  Path
 

Public Member Functions

 QueryTree (const FormulaPtr &query)
 
 ~QueryTree ()
 
 QueryTree (const QueryTree &)=delete
 
auto numPaths () const
 
const auto & paths () const
 
auto begin () const
 
auto end () const
 
 QueryTree (const FormulaPtr &query)
 
 ~QueryTree ()
 
 QueryTree (const QueryTree &)=delete
 
auto numPaths () const
 
const auto & paths () const
 
auto begin () const
 
auto end () const
 

Protected Member Functions

Node * createNode (Node *parent, const FormulaPtr &phi, bool isNegated)
 
void expandNextNode ()
 
Node * createNode (Node *parent, const FormulaPtr &phi, bool isNegated)
 
void expandNextNode ()
 

Static Protected Member Functions

static std::list< QueryTree::Node * > getLeafs (Node *n)
 
static bool hasCompletePath (Node *leaf)
 
static void constructPath (Node *leaf, Path &path)
 
static std::list< QueryTree::Node * > getLeafs (Node *n)
 
static bool hasCompletePath (Node *leaf)
 
static void constructPath (Node *leaf, Path &path)
 

Protected Attributes

const FormulaPtr query_
 
std::list< Path > paths_
 
Node * rootNode_
 
std::priority_queue< Node *, std::vector< Node * >, NodeComparator > openNodes_
 

Detailed Description

Constructs a tableau-like tree by decomposing an input formula.

Definition at line 24 of file QueryTree.h.

Constructor & Destructor Documentation

◆ QueryTree() [1/4]

QueryTree::QueryTree ( const FormulaPtr &  query)
explicit

Definition at line 15 of file QueryTree.cpp.

16  : rootNode_(new Node(nullptr, query, false)) {
17  openNodes_.push(rootNode_);
18  while (!openNodes_.empty()) {
19  expandNextNode();
20  }
21 }
knowrob::QueryTree::openNodes_
std::priority_queue< Node *, std::vector< Node * >, NodeComparator > openNodes_
Definition: QueryTree.h:113

◆ ~QueryTree() [1/2]

QueryTree::~QueryTree ( )

Definition at line 23 of file QueryTree.cpp.

23  {
24  std::list<Node *> fifo;
25  fifo.push_back(rootNode_);
26  while (!fifo.empty()) {
27  Node *next = fifo.front();
28  fifo.pop_front();
29  for (auto *x: next->successors) {
30  fifo.push_back(x);
31  }
32  delete next;
33  }
34  rootNode_ = nullptr;
35 }

◆ QueryTree() [2/4]

knowrob::QueryTree::QueryTree ( const QueryTree &  )
delete

◆ QueryTree() [3/4]

knowrob::QueryTree::QueryTree ( const FormulaPtr &  query)
explicit

◆ ~QueryTree() [2/2]

knowrob::QueryTree::~QueryTree ( )

◆ QueryTree() [4/4]

knowrob::QueryTree::QueryTree ( const QueryTree &  )
delete

Member Function Documentation

◆ begin() [1/2]

auto knowrob::QueryTree::begin ( ) const
inline
Returns
begin iterator over paths from root to leafs.

Definition at line 45 of file QueryTree.h.

45 { return paths_.begin(); }
knowrob::QueryTree::paths_
std::list< Path > paths_
Definition: QueryTree.h:105

◆ begin() [2/2]

auto knowrob::QueryTree::begin ( ) const
inline
Returns
begin iterator over paths from root to leafs.

Definition at line 45 of file QueryTree.h.

45 { return paths_.begin(); }

◆ constructPath() [1/2]

void QueryTree::constructPath ( Node *  leaf,
Path &  path 
)
staticprotected

Definition at line 103 of file QueryTree.cpp.

103  {
104  Node *parent = leaf;
105  do {
106  if (parent->formula->type() == FormulaType::PREDICATE ||
107  parent->formula->type() == FormulaType::MODAL) {
108  if (parent->isNegated) {
109  path.nodes_.push_back(std::make_shared<Negation>(parent->formula));
110  } else {
111  path.nodes_.push_back(parent->formula);
112  }
113  }
114  parent = parent->parent;
115  } while (parent);
116 }

◆ constructPath() [2/2]

static void knowrob::QueryTree::constructPath ( Node *  leaf,
Path &  path 
)
staticprotected

◆ createNode() [1/2]

QueryTree::Node * QueryTree::createNode ( Node *  parent,
const FormulaPtr &  phi,
bool  isNegated 
)
protected

Definition at line 87 of file QueryTree.cpp.

87  {
88  Node *newNode = new Node(parent, phi, isNegated);
89  parent->successors.push_back(newNode);
90  openNodes_.push(newNode);
91  return newNode;
92 }

◆ createNode() [2/2]

Node* knowrob::QueryTree::createNode ( Node *  parent,
const FormulaPtr &  phi,
bool  isNegated 
)
protected

◆ end() [1/2]

auto knowrob::QueryTree::end ( ) const
inline
Returns
end iterator over paths from root to leafs.

Definition at line 50 of file QueryTree.h.

50 { return paths_.end(); }

◆ end() [2/2]

auto knowrob::QueryTree::end ( ) const
inline
Returns
end iterator over paths from root to leafs.

Definition at line 50 of file QueryTree.h.

50 { return paths_.end(); }

◆ expandNextNode() [1/2]

void QueryTree::expandNextNode ( )
protected

Definition at line 118 of file QueryTree.cpp.

118  {
119  auto next = openNodes_.top();
120  next->isOpen = false;
121  openNodes_.pop();
122 
123  switch (next->formula->type()) {
124  case FormulaType::PREDICATE:
125  case FormulaType::MODAL:
126  for (Node *leaf: getLeafs(next)) {
127  if (hasCompletePath(leaf)) {
128  paths_.emplace_back();
129  auto &path = paths_.back();
130  constructPath(leaf, path);
131  }
132  }
133  break;
134 
135  case FormulaType::CONJUNCTION: {
136  auto *formula = (Conjunction *) next->formula.get();
137  if (next->isNegated) {
138  for (Node *leaf: getLeafs(next)) {
139  for (auto &phi: formula->formulae()) {
140  createNode(leaf, phi, true);
141  }
142  }
143  } else {
144  for (Node *leaf: getLeafs(next)) {
145  Node *parent = leaf;
146  for (auto &phi: formula->formulae()) {
147  parent = createNode(parent, phi, false);
148  }
149  }
150  }
151  break;
152  }
153 
154  case FormulaType::DISJUNCTION: {
155  auto *formula = (Disjunction *) next->formula.get();
156  if (next->isNegated) {
157  for (Node *leaf: getLeafs(next)) {
158  Node *parent = leaf;
159  for (auto &phi: formula->formulae()) {
160  parent = createNode(parent, phi, true);
161  }
162  }
163  } else {
164  for (Node *leaf: getLeafs(next)) {
165  for (auto &phi: formula->formulae()) {
166  createNode(leaf, phi, false);
167  }
168  }
169  }
170  break;
171  }
172 
173  case FormulaType::IMPLICATION: {
174  auto *formula = (Implication *) next->formula.get();
175  if (next->isNegated) {
176  for (Node *leaf: getLeafs(next)) {
177  Node *parent = leaf;
178  parent = createNode(parent, formula->antecedent(), false);
179  createNode(parent, formula->consequent(), true);
180  }
181  } else {
182  for (Node *leaf: getLeafs(next)) {
183  createNode(leaf, formula->antecedent(), true);
184  createNode(leaf, formula->consequent(), false);
185  }
186  }
187  break;
188  }
189 
190  case FormulaType::NEGATION: {
191  auto *formula = (Negation *) next->formula.get();
192  for (Node *leaf: getLeafs(next)) {
193  createNode(leaf, formula->negatedFormula(), !next->isNegated);
194  }
195  break;
196  }
197  }
198 }
knowrob::QueryTree::createNode
Node * createNode(Node *parent, const FormulaPtr &phi, bool isNegated)
Definition: QueryTree.cpp:87
knowrob::QueryTree::hasCompletePath
static bool hasCompletePath(Node *leaf)
Definition: QueryTree.cpp:94
knowrob::QueryTree::constructPath
static void constructPath(Node *leaf, Path &path)
Definition: QueryTree.cpp:103
knowrob::QueryTree::getLeafs
static std::list< QueryTree::Node * > getLeafs(Node *n)
Definition: QueryTree.cpp:69
knowrob::parsers::formula::formula
FormulaRule & formula()
Definition: formula.cpp:283

◆ expandNextNode() [2/2]

void knowrob::QueryTree::expandNextNode ( )
protected

◆ getLeafs() [1/2]

std::list< QueryTree::Node * > QueryTree::getLeafs ( Node *  n)
staticprotected

Definition at line 69 of file QueryTree.cpp.

69  {
70  std::list<Node *> out;
71  std::list<Node *> fifo;
72  fifo.push_back(n);
73  while (!fifo.empty()) {
74  Node *next = fifo.front();
75  fifo.pop_front();
76  if (next->successors.empty()) {
77  out.push_back(next);
78  } else {
79  for (auto *x: next->successors) {
80  fifo.push_back(x);
81  }
82  }
83  }
84  return out;
85 }

◆ getLeafs() [2/2]

static std::list<QueryTree::Node *> knowrob::QueryTree::getLeafs ( Node *  n)
staticprotected

◆ hasCompletePath() [1/2]

bool QueryTree::hasCompletePath ( Node *  leaf)
staticprotected

Definition at line 94 of file QueryTree.cpp.

94  {
95  Node *parent = leaf;
96  do {
97  if (parent->isOpen) return false;
98  parent = parent->parent;
99  } while (parent);
100  return true;
101 }

◆ hasCompletePath() [2/2]

static bool knowrob::QueryTree::hasCompletePath ( Node *  leaf)
staticprotected

◆ numPaths() [1/2]

auto knowrob::QueryTree::numPaths ( ) const
inline
Returns
number of paths from root of the tree to leafs.

Definition at line 35 of file QueryTree.h.

35 { return paths_.size(); }

◆ numPaths() [2/2]

auto knowrob::QueryTree::numPaths ( ) const
inline
Returns
number of paths from root of the tree to leafs.

Definition at line 35 of file QueryTree.h.

35 { return paths_.size(); }

◆ paths() [1/2]

const auto& knowrob::QueryTree::paths ( ) const
inline
Returns
list of paths from root of the tree to leafs.

Definition at line 40 of file QueryTree.h.

40 { return paths_; }

◆ paths() [2/2]

const auto& knowrob::QueryTree::paths ( ) const
inline
Returns
list of paths from root of the tree to leafs.

Definition at line 40 of file QueryTree.h.

40 { return paths_; }

Member Data Documentation

◆ openNodes_

std::priority_queue< Node *, std::vector< Node * >, NodeComparator > knowrob::QueryTree::openNodes_
protected

Definition at line 113 of file QueryTree.h.

◆ paths_

std::list< Path > knowrob::QueryTree::paths_
protected

Definition at line 105 of file QueryTree.h.

◆ query_

const FormulaPtr knowrob::QueryTree::query_
protected

Definition at line 104 of file QueryTree.h.

◆ rootNode_

Node * knowrob::QueryTree::rootNode_
protected

Definition at line 107 of file QueryTree.h.

The documentation for this class was generated from the following files: