|
OpenCog Framework
Branch: master, revision 6f0b7fc776b08468cf1b74aa9db028f387b4f0c0
|
|
OpenCog Framework
Branch: master, revision 6f0b7fc776b08468cf1b74aa9db028f387b4f0c0
|
#include <InitiateSearchCB.h>
Inheritance diagram for opencog::InitiateSearchCB: Collaboration diagram for opencog::InitiateSearchCB:Public Member Functions | |
| InitiateSearchCB (AtomSpace *) | |
| virtual void | set_pattern (const Variables &, const Pattern &) |
| virtual bool | initiate_search (PatternMatchEngine *) |
| Public Member Functions inherited from opencog::PatternMatchCallback | |
| virtual | ~PatternMatchCallback () |
| virtual bool | node_match (const Handle &patt_node, const Handle &grnd_node)=0 |
| virtual bool | variable_match (const Handle &patt_node, const Handle &grnd_node)=0 |
| virtual bool | link_match (const LinkPtr &patt_link, const LinkPtr &grnd_link)=0 |
| virtual bool | post_link_match (const LinkPtr &patt_link, const LinkPtr &grnd_link) |
| virtual bool | fuzzy_match (const Handle &ph, const Handle &gh) |
| virtual bool | evaluate_sentence (const Handle &eval, const std::map< Handle, Handle > &gnds)=0 |
| virtual bool | clause_match (const Handle &pattrn_link_h, const Handle &grnd_link_h) |
| virtual bool | optional_clause_match (const Handle &pattrn, const Handle &grnd)=0 |
| virtual bool | grounding (const std::map< Handle, Handle > &var_soln, const std::map< Handle, Handle > &term_soln)=0 |
| virtual IncomingSet | get_incoming_set (const Handle &h) |
| virtual void | push (void) |
| virtual void | pop (void) |
| virtual const std::set< Type > & | get_connectives (void) |
Protected Member Functions | |
| virtual Handle | find_starter (const Handle &, size_t &, Handle &, size_t &) |
| virtual Handle | find_thinnest (const HandleSeq &, const std::set< Handle > &, Handle &, size_t &) |
| virtual void | find_rarest (const Handle &, Handle &, size_t &) |
| virtual bool | neighbor_search (PatternMatchEngine *) |
| virtual bool | link_type_search (PatternMatchEngine *) |
| virtual bool | variable_search (PatternMatchEngine *) |
| virtual bool | no_search (PatternMatchEngine *) |
Protected Attributes | |
| ClassServer & | _classserver |
| const Variables * | _variables |
| const Pattern * | _pattern |
| const VariableTypeMap * | _type_restrictions |
| const std::set< Handle > * | _dynamic |
| Handle | _root |
| Handle | _starter_term |
| bool | _search_fail |
| AtomSpace * | _as |
Callback mixin class, used to provide a default atomspace search. This class is a pure virtual class, it does not implement any of the matching callbacks.
The only thing it provides is search initiation.
Definition at line 42 of file InitiateSearchCB.h.
| InitiateSearchCB::InitiateSearchCB | ( | AtomSpace * | as | ) |
Definition at line 42 of file InitiateSearchCB.cc.
|
protectedvirtual |
Find the rarest link type contained in the clause, or one of its subclauses. Of course, QuoteLinks, and anything under a Quotelink, must be ignored.
Definition at line 434 of file InitiateSearchCB.cc.
References _as, opencog::AtomSpace::get_num_atoms_of_type(), opencog::Atom::getType(), opencog::LinkCast(), and python.undocumented.blocksworld::t.
Here is the caller graph for this function:
|
protectedvirtual |
Definition at line 111 of file InitiateSearchCB.cc.
References _classserver, _dynamic, opencog::Atom::getIncomingSetSize(), opencog::Atom::getType(), opencog::ClassServer::isNode(), opencog::LinkCast(), python.undocumented.blocksworld::t, and opencog::Handle::UNDEFINED.
Here is the caller graph for this function:
|
protectedvirtual |
Iterate over all the clauses, to find the "thinnest" one. Skip any/all evaluatable clauses, as thes typically do not exist in the atomspace, anyway.
Definition at line 178 of file InitiateSearchCB.cc.
References find_starter(), and opencog::Handle::UNDEFINED.
Here is the caller graph for this function:
|
virtual |
Search for solutions/groundings over all of the AtomSpace, using the standard, canonical assumptions about the structure of the search pattern. Here, the "standard, canonical" assumptions are that the pattern consists of clauses that contain VariableNodes in them, with the VariableNodes interpreted in the "standard, canonical" way: namely, that these are the atoms that are to be grounded, as normally described elsewhere in the documentation. In such a case, a full and complete search for any/all possible groundings is performed; if there are groundings, they are guaranteed to be found; if there are none, then it is guaranteed that this will also be correctly reported. For certain, highly unusual (but still canonical) search patterns, the same grounding may be reported more than once; grep for notes pertaining to the ChoiceLink, and the ArcanaUTest for details. Otherwise, all possible groundings are guaranteed to be returned exactly once.
We emphasize "standard, canonical" here, for a reason: the pattern engine is capable of doing many strange, weird things, depending on how the callbacks are designed to work. For those other applications, it is possible or likely that this method will fail to traverse the "interesting" parts of the atomspace: non-standard callbacks may also need a non-standard search strategy.
Now, some notes on the strategy employed here, and how non-canonical callbacks might affect it:
1) Search will begin at the first non-variable node in the "thinnest" clause. The thinnest clause is chosen, so as to improve performance; but this has no effect on the thoroughness of the search. The search will proceed by exploring the entire incoming-set for this node.
This is ideal, when the node_match() callback accepts a match only when the pattern and suggested nodes are identical (i.e. are exactly the same atom). If the node_match() callback is willing to accept a broader range of node matches, then other possible solutions might be missed. Just how to fix this depends sharpely on what node_match() is willing to accept as a match.
Anyway, this seems like a very reasonable limitation: if you really want a lenient node_match(), then use variables instead. Don't overload node-match with something weird, and you should be OK. Otherwise, you'll have to implement your own initiate_search() callback.
2) If the clauses consist entirely of variables, i.e. if there is not even one single non-variable node in the pattern, then a search is driven by looking for all links that are of the same type as one of the links in one of the clauses.
If the link_match() callback is willing to accept a broader range of types, then this search method may fail to find some possible patterns.
Lets start by noting that this situation is very rare: most patterns will not consist entirely if Links and VariableNodes. Almost surely, most reasonable people will have at least one non-variable node in the pattern. So the disucssion below almost surely does not apply.
But if yhou really want this, there are several possible remedies. One is to modify the link_type_search() callback to try each possible link type that is considered bo be equivalent by link_match(). Another alternative is to just leave the link_match() callback alone, and use variables for links, instead. This is probably the best strategy, because then the fairly standard reasoning can be used when thinking about the problem. Of course, you can always write your own initiate_search() callback.
If the constraint 1) can be met, (which is always the case for "standard, canonical" searches, then the pattern match should be quite rapid. Incoming sets tend to be small; in addition, the implemnentation here picks the smallest, "tinnest" incoming set to explore.
The default implementation of node_match() and link_match() in this class does satisfy both 1) and 2), so this algo will work correctly, if these two methods are not overloaded with more callbacks that are lenient about matching.
If you overload node_match(), and do so in a way that breaks assumption 1), then you will scratch your head, thinking "why did my search fail to find this obvious solution?" The answer will be for you to create a new search algo, in a new class, that overloads this one, and does what you want it to. This class should probably not be modified, since it is quite efficient for the "standard, canonical" case.
Implements opencog::PatternMatchCallback.
Definition at line 386 of file InitiateSearchCB.cc.
References _search_fail, dbgprt, link_type_search(), neighbor_search(), no_search(), and variable_search().
|
protectedvirtual |
Initiate a search by looping over all Links of the same type as one of the links in the set of clauses. This attempts to pick the link type which has the smallest number of atoms of that type in the AtomSpace.
Definition at line 464 of file InitiateSearchCB.cc.
References _as, _pattern, _root, _search_fail, _starter_term, dbgprt, opencog::Pattern::evaluatable_holders, opencog::PatternMatchEngine::explore_neighborhood(), find_rarest(), opencog::AtomSpace::get_handles_by_type(), opencog::Atom::getType(), opencog::Pattern::mandatory, opencog::Atom::toShortString(), and opencog::Handle::UNDEFINED.
Here is the caller graph for this function:
|
protectedvirtual |
Given a set of clauses, find a neighborhood to search, and perform the search. A neighborhood is defined as all of the atoms that can be reached from a given (non-variable) atom, by following either it's incoming or its outgoing set.
A neighborhood search is guaranteed to find all possible groundings for the set of clauses. The reason for this is that, given a non-variable atom in the pattern, any possible grounding of that pattern must contain that atom, out of necessity. Thus, any possible grounding must be contained in that neighborhood. It is sufficient to walk that graph until a suitable grounding is encountered.
The return value is true if a grounding was found, else it returns false. That is, this return value works just like all the other satisfiability callbacks. The flag '_search_fail' is set to true if the search was not performed, due to a failure to find a sutiable starting point.
Definition at line 234 of file InitiateSearchCB.cc.
References _pattern, _root, _search_fail, _starter_term, opencog::Pattern::cnf_clauses, dbgprt, opencog::Pattern::evaluatable_holders, opencog::PatternMatchEngine::explore_neighborhood(), find_thinnest(), opencog::PatternMatchCallback::get_incoming_set(), opencog::Pattern::mandatory, opencog::Atom::toShortString(), and opencog::Handle::UNDEFINED.
Here is the caller graph for this function:
|
protectedvirtual |
No search – no variables, one evaluatable clause. The stop-go sequence demo falls in this category: no actual matching needs to be done; merely, the sequence needs to be evaluated. Arguably, it is a user error to use the pattern matcher for this, as there is nothing that needs to be matched. But, for just right now, we gloss over this, and allow it, because it is "closely related" to sequences with variables. It is a bit inefficient to use the pattern matcher for this, so if you want it to run fast, re-work the below to not use the PME.
Definition at line 639 of file InitiateSearchCB.cc.
References _pattern, _root, _search_fail, _starter_term, _variables, dbgprt, opencog::Pattern::evaluatable_holders, opencog::PatternMatchEngine::explore_neighborhood(), opencog::Pattern::mandatory, and opencog::Variables::varset.
Here is the caller graph for this function:Called to perform the actual search. This makes some default assumptions about the kind of things that might be matched, in order to drive a reasonably-fast search.
Implements opencog::PatternMatchCallback.
Reimplemented in opencog::SatisfyingSet, opencog::AFImplicator, opencog::Satisfier, opencog::BackwardChainerPMCB, opencog::DefaultImplicator, and opencog::ForwardChainerPMCB.
Definition at line 52 of file InitiateSearchCB.cc.
References _dynamic, _pattern, _search_fail, _type_restrictions, _variables, opencog::Pattern::evaluatable_terms, and opencog::Variables::typemap.
Here is the caller graph for this function:
|
protectedvirtual |
Initiate a search by looping over all atoms of the allowed variable types (as set with the set_type_testrictions() method). This assumes that the varset contains the variables to be searched over, and that the type restrictins are set up approrpriately.
If the varset is empty, or if there are no variables, then the entire atomspace will be searched. Depending on the pattern, many, many duplicates might be reported. If you are not using variables, then you probably don't want to use this method, either; you should create somethnig more clever.
Definition at line 535 of file InitiateSearchCB.cc.
References _as, _classserver, _pattern, _root, _search_fail, _starter_term, _type_restrictions, _variables, dbgprt, opencog::Pattern::evaluatable_holders, opencog::PatternMatchEngine::explore_neighborhood(), opencog::AtomSpace::get_handles_by_type(), opencog::AtomSpace::get_num_atoms_of_type(), opencog::ClassServer::getTypeName(), opencog::FindAtoms::least_holders, opencog::Pattern::mandatory, opencog::FindAtoms::search_set(), python.undocumented.blocksworld::t, opencog::Atom::toShortString(), opencog::Handle::UNDEFINED, and opencog::Variables::varset.
Here is the caller graph for this function:
|
protected |
Definition at line 79 of file InitiateSearchCB.h.
|
protected |
Definition at line 57 of file InitiateSearchCB.h.
|
protected |
Definition at line 62 of file InitiateSearchCB.h.
|
protected |
Definition at line 60 of file InitiateSearchCB.h.
|
protected |
Definition at line 64 of file InitiateSearchCB.h.
|
protected |
Definition at line 73 of file InitiateSearchCB.h.
|
protected |
Definition at line 65 of file InitiateSearchCB.h.
|
protected |
Definition at line 61 of file InitiateSearchCB.h.
|
protected |
Definition at line 59 of file InitiateSearchCB.h.
1.8.6 
