![]() |
Connect++ 0.5.0
A fast, readable connection prover for first-order logic.
|
Representation of the Matrix within a proof. More...
#include <Matrix.hpp>
Public Member Functions | |
Matrix () | |
Use this constructor if you really want an empty Matrix. | |
Matrix (size_t) | |
Use this constructor when you know how many predicates there are. | |
Matrix (const Matrix &)=delete | |
You're never going to need to copy a Matrix. | |
Matrix (const Matrix &&)=delete | |
Matrix & | operator= (const Matrix &)=delete |
Matrix & | operator= (const Matrix &&)=delete |
ClauseNum | get_num_clauses () const |
Straightforward get method. | |
const Clause & | operator[] (size_t i) const |
Straightforward get method. | |
bool | is_positive (size_t i) const |
Is a particular Clause positive?. | |
bool | is_negative (size_t i) const |
Is a particular Clause negative?. | |
bool | is_conjecture (size_t i) const |
Is a particular Clause a conjecture? | |
void | set_num_equals (uint32_t n) |
Straightforward set method. | |
pair< bool, size_t > | find_start () const |
Use a simple heuristic to find a good start clause. | |
void | set_num_preds (size_t) |
Make an empty index. | |
void | add_clause (Clause &, string="") |
Add a Clause to the Matrix and update the index accordingly. | |
void | find_limited_extensions (Unifier &, vector< InferenceItem > &, Clause &, VariableIndex &, TermIndex &) |
Find all possible extensions given a Clause, but only consider the first Literal in the Clause. | |
void | find_all_extensions (Unifier &, vector< InferenceItem > &, Clause &, VariableIndex &, TermIndex &) |
Find all possible extensions given a Clause, considering all Literals in the Clause. | |
void | deterministic_reorder (size_t) |
Deterministic reorder of the clauses. | |
void | random_reorder () |
Randomly reorder the matrix. | |
void | random_reorder_literals () |
Randomly reorder the literals in each clause in the matrix. | |
void | move_equals_to_start () |
Self-explanatory. | |
vector< Clause >::const_iterator | cbegin () const |
vector< Clause >::const_iterator | cend () const |
vector< Clause >::iterator | begin () |
vector< Clause >::iterator | end () |
string | to_string () const |
Make a string representation. | |
string | make_LaTeX (bool=false) const |
Make a usable LaTeX representation. | |
void | write_to_prolog_file (const path &) const |
Write to a file that can be read by Prolog. | |
void | show_tptp () const |
Output in TPTP compatible format. | |
void | sort_clauses_by_increasing_size () |
Self-explanatory. | |
Private Member Functions | |
void | find_extensions (Unifier &, vector< InferenceItem > &, const Literal &, LitNum, VariableIndex &, TermIndex &) |
Find all possible extensions, given a Literal. | |
void | make_clauses_copy () |
Store a copy of the clauses. | |
template<class Comparison > | |
void | sort_clauses (Comparison comparison) |
Template method for general sorting of clauses, which sorts roles at the same time. | |
Private Attributes | |
vector< Clause > | clauses |
The Matrix itself is just a set of Clauses. | |
vector< bool > | positive_clauses |
Keep track of which clauses are positive. | |
vector< bool > | negative_clauses |
Keep track of which clauses are negative. | |
vector< string > | clause_roles |
Keep track of which clauses are conjectures etc. | |
uint32_t | num_equals |
You need to know how many equality axioms there are in case you want to move them around. | |
vector< Clause > | clauses_copy |
It makes sense to keep a copy of the clauses if your schedule reorders multiple times. | |
vector< string > | roles_copy |
It makes sense to keep a copy of the roles if your schedule reorders multiple times. | |
bool | copy_saved |
Remember whether you've saved a copy. | |
vector< vector< MatrixPairType > > | index |
We want to be able to quickly identify where in each clause a particular literal lives. | |
Static Private Attributes | |
static std::mt19937 | d |
Randomness for random reordering. | |
Friends | |
ostream & | operator<< (ostream &, const Matrix &) |
Representation of the Matrix within a proof.
The Matrix itself never actually changes. However we do want to be able to look things up quickly when finding possible extension steps, so we build an index to help with that.
This class is also the natural place to implement the finding of all extensions, and the start clause heuristics.
Definition at line 73 of file Matrix.hpp.
|
inline |
Use this constructor if you really want an empty Matrix.
Definition at line 198 of file Matrix.hpp.
Matrix::Matrix | ( | size_t | num_predicates | ) |
Use this constructor when you know how many predicates there are.
num_predicates | Number of predicates. |
Definition at line 30 of file Matrix.cpp.
|
delete |
You're never going to need to copy a Matrix.
Let the compiler be your friend.
void Matrix::add_clause | ( | Clause & | clause, |
string | role = "" ) |
Add a Clause to the Matrix and update the index accordingly.
Optionally add a clause role.
clause | Reference to the Clause. |
role | A string denoting the role of the clause. |
Definition at line 91 of file Matrix.cpp.
|
inline |
Definition at line 345 of file Matrix.hpp.
|
inline |
Definition at line 343 of file Matrix.hpp.
|
inline |
Definition at line 344 of file Matrix.hpp.
void Matrix::deterministic_reorder | ( | size_t | n | ) |
Deterministic reorder of the clauses.
Call the reorder algorithm the specified number of times. This assumes you have stored a copy of the original clauses.
n | Number of times to call the reorder algorithm |
Only store a copy of the clauses the first time you do this.
Definition at line 105 of file Matrix.cpp.
|
inline |
Definition at line 346 of file Matrix.hpp.
void Matrix::find_all_extensions | ( | Unifier & | u, |
vector< InferenceItem > & | result, | ||
Clause & | c, | ||
VariableIndex & | var_index, | ||
TermIndex & | term_index ) |
Find all possible extensions given a Clause, considering all Literals in the Clause.
See the documentation for find_extensions, which does all the heavy lifting.
u | A reference to a Unifier function object. |
result | A reference to a vector of InferenceItems. Start with this empty. |
c | The Clause of interest. |
var_index | A reference to the VariableIndex. |
term_index | A reference to the TermIndex. |
Definition at line 235 of file Matrix.cpp.
|
private |
Find all possible extensions, given a Literal.
Essentially this involves finding all the Clauses in the Matrix containing a Literal complementary to the one of interest, and selecting each of those Literals that unifies with the one of interest. You can do this by traversing a single row of the index.
It's up to the caller to decide whether to clear the result.
u | Reference to a Unifier function object. |
result | Reference to a vector of InferenceItems. |
lit | Reference to the Literal of interest. |
ind | the index (position) of the Literal in its Clause. |
var_index | Reference to the VariableIndex. |
term_index | Reference to the TermIndex. |
Definition at line 207 of file Matrix.cpp.
void Matrix::find_limited_extensions | ( | Unifier & | u, |
vector< InferenceItem > & | result, | ||
Clause & | c, | ||
VariableIndex & | var_index, | ||
TermIndex & | term_index ) |
Find all possible extensions given a Clause, but only consider the first Literal in the Clause.
See the documentation for find_extensions, which does all the heavy lifting.
u | A reference to a Unifier function object. |
result | A reference to a vector of InferenceItems. Start with this empty. |
c | The Clause of interest. |
var_index | A reference to the VariableIndex. |
term_index | A reference to the TermIndex. |
Definition at line 225 of file Matrix.cpp.
pair< bool, size_t > Matrix::find_start | ( | ) | const |
Use a simple heuristic to find a good start clause.
Find a start clause that is positive/negative according to the –negative flag, and if possible also a conjecture clause. Also, indicate if there is no positive/negative clause, which means the problem is trivial.
Definition at line 51 of file Matrix.cpp.
|
inline |
bool Matrix::is_conjecture | ( | size_t | i | ) | const |
Is a particular Clause a conjecture?
i | Index of Clause to check. |
Definition at line 46 of file Matrix.cpp.
|
inline |
Is a particular Clause negative?.
i | Index of Clause to check. |
Definition at line 247 of file Matrix.hpp.
|
inline |
Is a particular Clause positive?.
i | Index of Clause to check. |
Definition at line 241 of file Matrix.hpp.
|
inlineprivate |
Store a copy of the clauses.
Definition at line 152 of file Matrix.hpp.
string Matrix::make_LaTeX | ( | bool | subbed = false | ) | const |
Make a usable LaTeX representation.
subbed | Implement substitutions if true. |
Definition at line 270 of file Matrix.cpp.
void Matrix::move_equals_to_start | ( | ) |
Self-explanatory.
BUT only do this to the matrix built at the start of the process, as it assumes the equality axioms are at the end of the matrix.
Definition at line 183 of file Matrix.cpp.
|
inline |
Straightforward get method.
Beware - the parameter is not checked, so behave!
i | Index of item to get. |
Definition at line 235 of file Matrix.hpp.
void Matrix::random_reorder | ( | ) |
Randomly reorder the matrix.
Definition at line 136 of file Matrix.cpp.
void Matrix::random_reorder_literals | ( | ) |
Randomly reorder the literals in each clause in the matrix.
Definition at line 162 of file Matrix.cpp.
|
inline |
Straightforward set method.
n | Number of equality axioms. |
Definition at line 259 of file Matrix.hpp.
void Matrix::set_num_preds | ( | size_t | num_predicates | ) |
Make an empty index.
Definition at line 42 of file Matrix.cpp.
void Matrix::show_tptp | ( | ) | const |
Output in TPTP compatible format.
Definition at line 300 of file Matrix.cpp.
|
inlineprivate |
Template method for general sorting of clauses, which sorts roles at the same time.
ClauseComparisons.hpp contains function objects that can be used with this to implement different orderings.
Definition at line 166 of file Matrix.hpp.
|
inline |
Self-explanatory.
Inspired by "Machine Learning Guidance for Connection Tableaux," Farber et al. 2020 although with a different measure of size and happening at a different place.
Makes use of the sort_clauses template.
Definition at line 379 of file Matrix.hpp.
string Matrix::to_string | ( | ) | const |
Make a string representation.
Definition at line 247 of file Matrix.cpp.
void Matrix::write_to_prolog_file | ( | const path & | path_to_file | ) | const |
Write to a file that can be read by Prolog.
This is for proof checking.
path_to_file | Reference to path object. |
Definition at line 283 of file Matrix.cpp.
|
friend |
Definition at line 312 of file Matrix.cpp.
|
private |
Keep track of which clauses are conjectures etc.
This allows start clause heuristics to be applied.
Definition at line 96 of file Matrix.hpp.
|
private |
The Matrix itself is just a set of Clauses.
Definition at line 78 of file Matrix.hpp.
|
private |
It makes sense to keep a copy of the clauses if your schedule reorders multiple times.
Definition at line 106 of file Matrix.hpp.
|
private |
Remember whether you've saved a copy.
Definition at line 115 of file Matrix.hpp.
|
staticprivate |
Randomness for random reordering.
Definition at line 127 of file Matrix.hpp.
|
private |
We want to be able to quickly identify where in each clause a particular literal lives.
Store clause and position as pairs in a row corresponding to the literal.
Definition at line 123 of file Matrix.hpp.
|
private |
Keep track of which clauses are negative.
This allows start clause heuristics to be applied.
Definition at line 90 of file Matrix.hpp.
|
private |
You need to know how many equality axioms there are in case you want to move them around.
Definition at line 101 of file Matrix.hpp.
|
private |
Keep track of which clauses are positive.
This allows start clause heuristics to be applied.
Definition at line 84 of file Matrix.hpp.
|
private |
It makes sense to keep a copy of the roles if your schedule reorders multiple times.
Definition at line 111 of file Matrix.hpp.