InitiateSearchCB.cc

Go to the documentation of this file.

/*
 * InitiateSearchCB.cc
 *
 * Copyright (C) 2015 Linas Vepstas
 *
 * Author: Linas Vepstas <linasvepstas@gmail.com>  April 2015
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License v3 as
 * published by the Free Software Foundation and including the exceptions
 * at http://opencog.org/wiki/Licenses
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program; if not, write to:
 * Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */

#include <opencog/atoms/execution/EvaluationLink.h>
#include <opencog/atomutils/FindUtils.h>

#include "InitiateSearchCB.h"
#include "PatternMatchEngine.h"

using namespace opencog;

// Uncomment below to enable debug print
// #define DEBUG
#ifdef DEBUG
#define dbgprt(f, varargs...) printf(f, ##varargs)
#else
#define dbgprt(f, varargs...)
#endif

/* ======================================================== */

InitiateSearchCB::InitiateSearchCB(AtomSpace* as) :
    _classserver(classserver()),
    _variables(NULL),
    _pattern(NULL),
    _type_restrictions(NULL),
    _dynamic(NULL),
    _as(as)
{
}

void InitiateSearchCB::set_pattern(const Variables& vars,
                                   const Pattern& pat)
{
    _search_fail = false;
    _variables = &vars;
    _pattern = &pat;
    _type_restrictions = &vars.typemap;
    _dynamic = &pat.evaluatable_terms;
}


/* ======================================================== */

// Find a good place to start the search.
//
// The handle h points to a clause.  In principle, it is enough to
// simply find a constant in the clause, and just start there. In
// practice, this can be an awful way to do things. So, for example,
// most "typical" clauses will be of the form
//
//    EvaluationLink
//        PredicateNode "blah"
//        ListLink
//            VariableNode $var
//            ConceptNode  "item"
//
// Typically, the incoming set for "blah" will be huge, so starting the
// search there would be a poor choice. Typically, the incoming set to
// "item" will be much smaller, and so makes a better choice.  The code
// below tries to pass over "blah" and pick "item" instead.  It does so
// by comparing the size of the incoming sets of the two constants, and
// picking the one with the smaller ("thinner") incoming set. Note that
// this is a form of "greedy" search.
//
// Atoms that are inside of dynamically-evaluatable terms are not
// considered. That's because groundings for such terms might not exist
// in the atomspace, so a search that starts there is doomed to fail.
//
// Note that the algo explores the clause to its greatest depth. That's
// OK, because typical clauses are never very deep.
//
// A variant of this algo could incorporate the Attentional focus
// into the "thinnest" calculation, so that only high-AF atoms are
// considered.
//
// Note that the size of the incoming set really is a better measure,
// and not the depth.  So, for example, if "item" has a huge incoming
// set, but "blah" does not, then "blah" is a much better place to
// start.
//
// size_t& depth will be set to the depth of the thinnest constant found.
// Handle& start will be set to the link containing that constant.
// size_t& width will be set to the incoming-set size of the thinnest
//               constant found.
// The returned value will be the constant at which to start the search.
// If no constant is found, then the returned value is the undefnied
// handle.
//
Handle
InitiateSearchCB::find_starter(const Handle& h, size_t& depth,
                               Handle& start, size_t& width)
{
    // If its a node, then we are done. Don't modify either depth or
    // start.
    Type t = h->getType();
    if (_classserver.isNode(t)) {
        if (t != VARIABLE_NODE) {
            width = h->getIncomingSetSize();
            return h;
        }
        return Handle::UNDEFINED;
    }

    // Ignore all ChoiceLink's. Picking a starter inside one of these
    // will almost surely be disconnected from the rest of the graph.
    if (CHOICE_LINK == t)
        return Handle::UNDEFINED;

    // Ignore all dynamically-evaluatable links up front.
    if (_dynamic->find(h) != _dynamic->end())
        return Handle::UNDEFINED;

    // Iterate over all the handles in the outgoing set.
    // Find the deepest one that contains a constant, and start
    // the search there.  If there are two at the same depth,
    // then start with the skinnier one.
    size_t deepest = depth;
    start = Handle::UNDEFINED;
    Handle hdeepest(Handle::UNDEFINED);
    size_t thinnest = SIZE_MAX;

    LinkPtr ll(LinkCast(h));
    for (Handle hunt : ll->getOutgoingSet())
    {
        size_t brdepth = depth + 1;
        size_t brwid = SIZE_MAX;
        Handle sbr(h);

        // Blow past the QuoteLinks, since they just screw up the search start.
        if (QUOTE_LINK == hunt->getType())
            hunt = LinkCast(hunt)->getOutgoingAtom(0);

        Handle s(find_starter(hunt, brdepth, sbr, brwid));

        if (s != Handle::UNDEFINED
            and (brwid < thinnest
                 or (brwid == thinnest and deepest < brdepth)))
        {
            deepest = brdepth;
            hdeepest = s;
            start = sbr;
            thinnest = brwid;
        }

    }
    depth = deepest;
    width = thinnest;
    return hdeepest;
}

/* ======================================================== */
Handle InitiateSearchCB::find_thinnest(const HandleSeq& clauses,
                                       const std::set<Handle>& evl,
                                       Handle& starter_term,
                                       size_t& bestclause)
{
    size_t thinnest = SIZE_MAX;
    size_t deepest = 0;
    bestclause = 0;
    Handle best_start(Handle::UNDEFINED);
    starter_term = Handle::UNDEFINED;

    size_t nc = clauses.size();
    for (size_t i=0; i < nc; i++)
    {
        // Cannot start with an evaluatable clause!
        if (0 < evl.count(clauses[i])) continue;
        Handle h(clauses[i]);
        size_t depth = 0;
        size_t width = SIZE_MAX;
        Handle term(Handle::UNDEFINED);
        Handle start(find_starter(h, depth, term, width));
        if (start != Handle::UNDEFINED
            and (width < thinnest
                 or (width == thinnest and depth > deepest)))
        {
            thinnest = width;
            deepest = depth;
            bestclause = i;
            best_start = start;
            starter_term = term;
        }
    }

    return best_start;
}

/* ======================================================== */
bool InitiateSearchCB::neighbor_search(PatternMatchEngine *pme)
{
    // Sometimes, the number of mandatory clauses can be zero...
    // We still want to search, though.
    const HandleSeq& clauses =
        (0 < _pattern->mandatory.size()) ?
             _pattern->mandatory : _pattern->cnf_clauses;

    // In principle, we could start our search at some node, any node,
    // that is not a variable. In practice, the search begins by
    // iterating over the incoming set of the node, and so, if it is
    // large, a huge amount of effort might be wasted exploring
    // dead-ends.  Thus, it pays off to start the search on the
    // node with the smallest ("narrowest" or "thinnest") incoming set
    // possible.  Thus, we look at all the clauses, to find the
    // "thinnest" one.
    //
    // Note also: the user is allowed to specify patterns that have
    // no constants in them at all.  In this case, the search is
    // performed by looping over all links of the given types.
    size_t bestclause;
    Handle best_start = find_thinnest(clauses, _pattern->evaluatable_holders,
                                      _starter_term, bestclause);

    // Cannot find a starting point! This can happen if all of the
    // clauses contain nothing but variables, or if all of the
    // clauses are evaluatable(!) Somewhat unusual, but it can
    // happen.  In this case, we need some other, alternative search
    // strategy.
    if (Handle::UNDEFINED == best_start)
    {
        _search_fail = true;
        return false;
    }

    _root = clauses[bestclause];
    dbgprt("Search start node: %s\n", best_start->toShortString().c_str());
    dbgprt("Start term is: %s\n", _starter_term == Handle::UNDEFINED ?
           "UNDEFINED" : _starter_term->toShortString().c_str());
    dbgprt("Root clause is: %s\n", _root->toShortString().c_str());

    // This should be calling the over-loaded virtual method
    // get_incoming_set(), so that, e.g. it gets sorted by attentional
    // focus in the AttentionalFocusCB class...
    IncomingSet iset = get_incoming_set(best_start);
    size_t sz = iset.size();
    for (size_t i = 0; i < sz; i++)
    {
        Handle h(iset[i]);
        dbgprt("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx\n");
        dbgprt("Loop candidate (%lu/%lu):\n%s\n", i+1, sz,
               h->toShortString().c_str());
        bool found = pme->explore_neighborhood(_root, _starter_term, h);

        // Terminate search if satisfied.
        if (found) return true;
    }

    // If we are here, we have searched the entire neighborhood, and
    // no satisfiable groundings were found.
    return false;
}

/* ======================================================== */
bool InitiateSearchCB::initiate_search(PatternMatchEngine *pme)
{
    dbgprt("Attempt to use node-neighbor search\n");
    _search_fail = false;
    bool found = neighbor_search(pme);
    if (found) return true;
    if (not _search_fail) return false;

    // If we are here, then we could not find a clause at which to
    // start, which can happen if the clauses hold no variables, and
    // they are all evaluatable. This can happen for sequence links;
    // we want to quickly rule out this case before moving to more
    // complex searches, below.
    dbgprt("Cannot use node-neighbor search, use no-var search\n");
    _search_fail = false;
    found = no_search(pme);
    if (found) return true;
    if (not _search_fail) return false;

    // If we are here, then we could not find a clause at which to
    // start, which can happen if the clauses consist entirely of
    // variables! Which can happen (there is a unit test for this,
    // the LoopUTest), and so instead, we search based on the link
    // types that occur in the atomspace.
    dbgprt("Cannot use no-var search, use link-type search\n");
    _search_fail = false;
    found = link_type_search(pme);
    if (found) return true;
    if (not _search_fail) return false;

    // The URE Reasoning case: if we found nothing, then there are no
    // links!  Ergo, every clause must be a lone variable, all by
    // itself. This is how some URE rules may start: the specify a single
    // variable, all by itself, and set some type restrictions on it,
    // and that's all. We deal with this in the variable_search()
    // method.
    dbgprt("Cannot use link-type search, use variable-type search\n");
    _search_fail = false;
    found = variable_search(pme);
    return found;
}

/* ======================================================== */
void InitiateSearchCB::find_rarest(const Handle& clause,
                                   Handle& rarest,
                                   size_t& count)
{
    Type t = clause->getType();
    if (QUOTE_LINK == t) return;
    if (CHOICE_LINK == t) return;

    LinkPtr lll(LinkCast(clause));
    if (NULL == lll) return;

    size_t num = (size_t) _as->get_num_atoms_of_type(t);
    if (num < count)
    {
        count = num;
        rarest = clause;
    }

    const HandleSeq& oset = lll->getOutgoingSet();
    for (const Handle& h : oset)
        find_rarest(h, rarest, count);
}

/* ======================================================== */
bool InitiateSearchCB::link_type_search(PatternMatchEngine *pme)
{
    const HandleSeq& clauses = _pattern->mandatory;

    _search_fail = false;
    _root = Handle::UNDEFINED;
    _starter_term = Handle::UNDEFINED;
    size_t count = SIZE_MAX;

    for (const Handle& cl: clauses)
    {
        // Evaluatables don't exist in the atomspace, in general.
        // Cannot start a search with them.
        if (0 < _pattern->evaluatable_holders.count(cl)) continue;
        size_t prev = count;
        find_rarest(cl, _starter_term, count);
        if (count < prev)
        {
            prev = count;
            _root = cl;
        }
    }

    // The URE Reasoning case: if we found nothing, then there are no
    // links!  Ergo, every clause must be a lone variable, all by
    // itself. This is how some URE rules may start: the specify a single
    // variable, all by itself, and set some type restrictions on it,
    // and that's all. We deal with this in the variable_search()
    // method.
    if (Handle::UNDEFINED == _root)
    {
        _search_fail = true;
        return false;
    }

    dbgprt("Start clause is: %s\n", _root->toShortString().c_str());
    dbgprt("Start term is: %s\n", _starter_term->toShortString().c_str());

    // Get type of the rarest link
    Type ptype = _starter_term->getType();

    HandleSeq handle_set;
    _as->get_handles_by_type(handle_set, ptype);

#ifdef DEBUG
    size_t i = 0;
#endif
    for (const Handle& h : handle_set)
    {
        dbgprt("yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy\n");
        dbgprt("Loop candidate (%lu/%lu):\n%s\n", ++i, handle_set.size(),
               h->toShortString().c_str());
        bool found = pme->explore_neighborhood(_root, _starter_term, h);
        if (found) return true;
    }
    return false;
}

/* ======================================================== */
bool InitiateSearchCB::variable_search(PatternMatchEngine *pme)
{
    const HandleSeq& clauses = _pattern->mandatory;

    // Find the rarest variable type;
    size_t count = SIZE_MAX;
    Type ptype = ATOM;

    dbgprt("varset size = %lu\n", _variables->varset.size());
    _root = Handle::UNDEFINED;
    _starter_term = Handle::UNDEFINED;
    for (const Handle& var: _variables->varset)
    {
        dbgprt("Examine variable %s\n", var->toShortString().c_str());
        auto tit = _type_restrictions->find(var);
        if (_type_restrictions->end() == tit) continue;
        const std::set<Type>& typeset = tit->second;
        dbgprt("Type-restictions set size = %lu\n", typeset.size());
        for (Type t : typeset)
        {
            size_t num = (size_t) _as->get_num_atoms_of_type(t);
            dbgprt("Type = %s has %lu atoms in the atomspace\n",
                   _classserver.getTypeName(t).c_str(), num);
            if (0 < num and num < count)
            {
                for (const Handle& cl : clauses)
                {
                    // Evaluatables dont' exist in the atomspace, in general.
                    // Cannot start a search with them.
                    if (0 < _pattern->evaluatable_holders.count(cl)) continue;
                    FindAtoms fa(var);
                    fa.search_set(cl);
                    if (cl == var)
                    {
                        _root = cl;
                        _starter_term = cl;
                        count = num;
                        ptype = t;
                        dbgprt("New minimum count of %lu\n", count);
                        break;
                    }
                    if (0 < fa.least_holders.size())
                    {
                        _root = cl;
                        _starter_term = *fa.least_holders.begin();
                        count = num;
                        ptype = t;
                        dbgprt("New minimum count of %lu (nonroot)\n", count);
                        break;
                    }
                }
            }
        }
    }

    // There were no type restrictions!
    if (Handle::UNDEFINED == _root)
    {
        dbgprt("There were no type restrictions! That must be wrong!\n");
        if (0 == clauses.size())
        {
            // This is kind-of weird, it can happen if all clauses
            // are optional.
            _search_fail = true;
            return false;
        }
        _root = _starter_term = clauses[0];
    }

    HandleSeq handle_set;
    if (ptype == ATOM)
        _as->get_handles_by_type(handle_set, ptype, true);
    else
        _as->get_handles_by_type(handle_set, ptype);

    dbgprt("Atomspace reported %lu atoms\n", handle_set.size());

#ifdef DEBUG
    size_t i = 0;
#endif
    for (const Handle& h : handle_set)
    {
        dbgprt("zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz\n");
        dbgprt("Loop candidate (%lu/%lu):\n%s\n", ++i, handle_set.size(),
               h->toShortString().c_str());
        bool found = pme->explore_neighborhood(_root, _starter_term, h);
        if (found) return true;
    }

    return false;
}

/* ======================================================== */
bool InitiateSearchCB::no_search(PatternMatchEngine *pme)
{
    if (0 < _variables->varset.size() or
        1 != _pattern->mandatory.size())
    {
        _search_fail = true;
        return false;
    }

    // The one-and-only clause must be evaluatable!
    const HandleSeq& clauses = _pattern->mandatory;
    const std::set<Handle>& evl = _pattern->evaluatable_holders;
    if (0 == evl.count(clauses[0]))
    {
        _search_fail = true;
        return false;
    }

    dbgprt("wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww\n");
    dbgprt("Non-search: no variables, no non-evaluatable clauses\n");
    _root = _starter_term = clauses[0];
    bool found = pme->explore_neighborhood(_root, _starter_term, _root);
    return found;
}

/* ===================== END OF FILE ===================== */