include/dlvhex2/InternalGroundASPSolver.h

Go to the documentation of this file.

/* dlvhex -- Answer-Set Programming with external interfaces.
 * Copyright (C) 2005-2007 Roman Schindlauer
 * Copyright (C) 2006-2015 Thomas Krennwallner
 * Copyright (C) 2009-2016 Peter Schüller
 * Copyright (C) 2011-2016 Christoph Redl
 * Copyright (C) 2015-2016 Tobias Kaminski
 * Copyright (C) 2015-2016 Antonius Weinzierl
 *
 * This file is part of dlvhex.
 *
 * dlvhex is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation; either version 2.1 of
 * the License, or (at your option) any later version.
 *
 * dlvhex 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
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with dlvhex; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
 * 02110-1301 USA.
 */

#ifndef INTERNALGROUNDASPSOLVER_HPP_INCLUDED__09122011
#define INTERNALGROUNDASPSOLVER_HPP_INCLUDED__09122011

#include "dlvhex2/ID.h"
#include "dlvhex2/Interpretation.h"
#include "dlvhex2/ProgramCtx.h"
#include <vector>
#include <set>
#include <map>
#include <boost/foreach.hpp>
#include "dlvhex2/Printhelpers.h"
#include "CDNLSolver.h"
#include "dlvhex2/OrdinaryASPProgram.h"
#include "dlvhex2/AnnotatedGroundProgram.h"
#include "dlvhex2/GenuineSolver.h"
//#include <bm/bm.h>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/shared_ptr.hpp>

DLVHEX_NAMESPACE_BEGIN

#ifdef _MSC_VER
// suppresses warning C4250: 'dlvhex::InternalGroundASPSolver' : inherits 'dlvhex::CDNLSolver::dlvhex::CDNLSolver::addNogood' via dominance
// (there is a compiler bug in MSVC; the call of addNogood is actually _not_ ambigious because the method is pure virtual in GenuineGroundSolver)
#pragma warning (disable: 4250)
#endif

class InternalGroundASPSolver : public CDNLSolver, public GenuineGroundSolver
{
    private:
        std::string bodyAtomPrefix;
        int bodyAtomNumber;

    protected:
        bool firstmodel;
        int modelCount;

    protected:
        // structural program information
        AnnotatedGroundProgram program;
        RegistryPtr reg;

        Set<IDAddress> ordinaryFacts;
        InterpretationPtr ordinaryFactsInt;
        Set<IDAddress> nonSingularFacts;

        // dependency graph
        typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, IDAddress> Graph;
        typedef Graph::vertex_descriptor Node;
        boost::unordered_map<IDAddress, Node, SimpleHashIDAddress> depNodes;
        Graph depGraph;

        std::vector<Set<IDAddress> > depSCC;
        boost::unordered_map<IDAddress, int, SimpleHashIDAddress> componentOfAtom;
        boost::unordered_map<IDAddress, IDAddress, SimpleHashIDAddress> bodyAtomOfRule;

        // data structures for unfounded set computation
        Set<IDAddress> unfoundedAtoms;
        boost::unordered_map<IDAddress, Set<ID>, SimpleHashIDAddress > rulesWithPosBodyLiteral;
        boost::unordered_map<IDAddress, Set<ID>, SimpleHashIDAddress > rulesWithNegBodyLiteral;
        boost::unordered_map<IDAddress, Set<ID>, SimpleHashIDAddress > rulesWithPosHeadLiteral;
        boost::unordered_map<IDAddress, Set<IDAddress>, SimpleHashIDAddress > foundedAtomsOfBodyAtom;
        boost::unordered_map<IDAddress, ID, SimpleHashIDAddress> sourceRule;

        // statistics
        long cntDetectedUnfoundedSets;

        // initialization members
        void createNogoodsForRule(ID ruleBodyAtomID, ID ruleID);
        void createNogoodsForRuleBody(ID ruleBodyAtomID, const Tuple& ruleBody);
        Set<std::pair<ID, ID> > createShiftedProgram();
        void computeClarkCompletion();
        void createSingularLoopNogoods(InterpretationConstPtr frozen);
        virtual void resizeVectors();
        void setEDB();
        void computeDepGraph();
        void computeStronglyConnectedComponents();
        void initSourcePointers();
        void initializeLists(InterpretationConstPtr frozen);

        // unfounded set members
        virtual void setFact(ID fact, int dl, int cause);
        virtual void clearFact(IDAddress litadr);
        void removeSourceFromAtom(IDAddress litadr);
        void addSourceToAtom(IDAddress litadr, ID rule);
        Set<IDAddress> getDependingAtoms(IDAddress litadr);
        void getInitialNewlyUnfoundedAtomsAfterSetFact(ID fact, Set<IDAddress>& newlyUnfoundedAtoms);
        void updateUnfoundedSetStructuresAfterSetFact(ID fact);
        void updateUnfoundedSetStructuresAfterClearFact(IDAddress litadr);
        ID getPossibleSourceRule(const Set<ID>& ufs);
        bool useAsNewSourceForHeadAtom(IDAddress headAtom, ID sourceRule);
        Set<ID> getUnfoundedSet();

        // helper members
        bool doesRuleExternallySupportLiteral(ID ruleID, ID lit, const Set<ID>& s);
        Set<ID> getExternalSupport(const Set<ID>& s);
        Set<ID> satisfiesIndependently(ID ruleID, const Set<ID>& y);
        Nogood getLoopNogood(const Set<ID>& ufs);
        ID createNewAtom(ID predID);
        ID createNewBodyAtom();
        std::string toString(const Set<ID>& lits);
        std::string toString(const Set<IDAddress>& lits);
        std::string toString(const std::vector<IDAddress>& lits);

        template <typename T>
        inline std::vector<T> intersect(const Set<T>& a, const std::vector<T>& b) {
            std::vector<T> i;
            BOOST_FOREACH (T el, a) {
                if (contains(b, el)) i.push_back(el);
            }
            return i;
        }

        template <typename T>
        inline Set<T> intersect(const Set<T>& a, const Set<T>& b) {
            Set<T> out;
            std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), insert_set_iterator<T>(out));
            return out;
        }

        InterpretationPtr outputProjection(InterpretationConstPtr intr);
    public:
        InternalGroundASPSolver(ProgramCtx& ctx, const AnnotatedGroundProgram& p, InterpretationConstPtr frozen = InterpretationConstPtr());
        virtual void addProgram(const AnnotatedGroundProgram& p, InterpretationConstPtr frozen = InterpretationConstPtr());
        virtual Nogood getInconsistencyCause(InterpretationConstPtr explanationAtoms);
        virtual void addNogoodSet(const NogoodSet& ns, InterpretationConstPtr frozen = InterpretationConstPtr());

        virtual void restartWithAssumptions(const std::vector<ID>& assumptions);
        virtual void addPropagator(PropagatorCallback* pb);
        virtual void removePropagator(PropagatorCallback* pb);
        virtual void setOptimum(std::vector<int>& optimum);
        virtual InterpretationPtr getNextModel();
        virtual int getModelCount();
        virtual std::string getStatistics();

        std::string getImplicationGraphAsDotString();

        typedef boost::shared_ptr<InternalGroundASPSolver> Ptr;
        typedef boost::shared_ptr<const InternalGroundASPSolver> ConstPtr;
};
#ifdef _MSC_VER
#pragma warning (default: 4250)
#endif

typedef InternalGroundASPSolver::Ptr InternalGroundASPSolverPtr;
typedef InternalGroundASPSolver::ConstPtr InternalGroundASPSolverConstPtr;

DLVHEX_NAMESPACE_END
#endif

// vim:expandtab:ts=4:sw=4:
// mode: C++
// End: