PatternUtils.cc

Go to the documentation of this file.

/*
 * PatternUtils.cc
 *
 * Copyright (C) 2008,2009,2011,2014 Linas Vepstas
 *
 * Author: Linas Vepstas <linasvepstas@gmail.com>  February 2008
 *
 * 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/atomutils/FindUtils.h>
#include "PatternUtils.h"

using namespace opencog;

namespace opencog {

bool remove_constants(const std::set<Handle> &vars,
                      std::vector<Handle> &clauses)
{
    bool modified = false;

    // Caution: this loop modifies the clauses list!
    std::vector<Handle>::iterator i;
    for (i = clauses.begin(); i != clauses.end(); )
    {
        Handle clause(*i);
        if (any_unquoted_in_tree(clause, vars)
            or contains_atomtype(clause, GROUNDED_PREDICATE_NODE)
            or contains_atomtype(clause, GROUNDED_SCHEMA_NODE))
        {
            ++i;
        }
        else
        {
            i = clauses.erase(i);
            modified = true;
        }
    }

    return modified;
}

/* ======================================================== */
void get_connected_components(const std::set<Handle>& vars,
                              const HandleSeq& clauses,
                              std::vector<HandleSeq>& components,
                              std::vector<std::set<Handle>>& component_vars)
{
    std::vector<Handle> todo(clauses);

    while (0 < todo.size())
    {
        // no_con_yet == clauses that failed to connect to any existing
        // component.
        std::vector<Handle> no_con_yet;
        bool did_at_least_one = false;

        for (const Handle& cl: todo)
        {
            bool extended = false;

            // Which component might this possibly belong to??? Try them all.
            size_t nc = components.size();
            for (size_t i = 0; i<nc; i++)
            {
                std::set<Handle>& cur_vars(component_vars[i]);
                // If clause cl is connected to this component, then add it
                // to this component.
                if (any_unquoted_in_tree(cl, cur_vars))
                {
                    // Extend the component
                    components[i].push_back(cl);

                    // Add to the varset cache for that component.
                    FindAtoms fv(vars);
                    fv.search_set(cl);
                    for (const Handle& v : fv.varset) cur_vars.insert(v);

                    extended = true;
                    did_at_least_one = true;
                    break;
                }
            }

            if (not extended)
                no_con_yet.push_back(cl);
        }

        if (did_at_least_one)
        {
            todo = no_con_yet;
            continue;
        }

        // Grab the first clause that failed to attach to something,
        // and use it to start a new component.
        Handle ncl(no_con_yet.back());
        no_con_yet.pop_back();
        todo = no_con_yet;

        // If we are here, we found a disconnected clause.
        // Start a new component
        components.push_back({ncl});

        FindAtoms fv(vars);
        fv.search_set(ncl);
        component_vars.push_back(fv.varset);
    }
}

HandleSeq get_free_vars_in_tree(const Handle& tree)
{
    std::set<Handle> varset;

    std::function<void (const Handle&)> find_rec = [&](const Handle& h)
    {
        Type t = h->getType();
        if (t == VARIABLE_NODE)
        {
            varset.insert(h);
            return;
        }

        if (classserver().isA(t, LAMBDA_LINK))
            return;

        LinkPtr l(LinkCast(h));
        if (l)
        {
            for (const Handle& oh : l->getOutgoingSet())
                find_rec(oh);
        }

        return;
    };

    find_rec(tree);

    return HandleSeq(varset.begin(), varset.end());
}

} // namespace opencog

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