include/dlvhex2/EvalGraphBuilder.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 EVAL_GRAPH_BUILDER_HPP_INCLUDED__03112010
#define EVAL_GRAPH_BUILDER_HPP_INCLUDED__03112010

#include "dlvhex2/FinalEvalGraph.h"
#include "dlvhex2/ComponentGraph.h"
#include "dlvhex2/ASPSolverManager.h"
#include "dlvhex2/Logger.h"

#include <boost/range/iterator_range.hpp>
#include <boost/concept/assert.hpp>
#include <boost/concept_check.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/unordered_set_of.hpp>
#include <boost/bimap/unordered_multiset_of.hpp>
#include <boost/scoped_ptr.hpp>

DLVHEX_NAMESPACE_BEGIN

class ProgramCtx;

//template<typename EvalGraphT>
// TODO make this a template for EvalGraphT and ComponentGraphT, for faster prototyping we use fixed types for these graphs
class DLVHEX_EXPORT EvalGraphBuilder
{
    // types
    public:
        typedef FinalEvalGraph EvalGraphT;
        typedef EvalGraphT::EvalUnit EvalUnit;
        typedef ComponentGraph::Component Component;
        typedef ComponentGraph::Dependency Dependency;

    protected:
        // we use identity as hash function as eval units are distinct unsigned ints

        BOOST_CONCEPT_ASSERT((boost::Convertible<Component, void*>));
        BOOST_CONCEPT_ASSERT((boost::Convertible<EvalUnit, unsigned>));

        struct identity
        {
            inline unsigned operator()(unsigned u) const { return u; }
        };

        // bidirectional mapping:
        // set of components -> one eval unit
        // set of components <- one eval unit
        // constraint components that have been pushed up are ignored here
        // (nothing can depend on them, and they are not "used" until all their
        // dependencies have been fulfilled)
        typedef boost::bimaps::bimap<
            boost::bimaps::unordered_set_of<Component>,
            boost::bimaps::unordered_set_of<EvalUnit>
            > ComponentEvalUnitMapping;

    protected:
        struct UnusedVertexFilter
        {
            // unfortunately, this predicate must be default constructible
            UnusedVertexFilter(): ceum(0) {}
            UnusedVertexFilter(const ComponentEvalUnitMapping* ceum): ceum(ceum) {}
            UnusedVertexFilter(const UnusedVertexFilter& other): ceum(other.ceum) {}
            UnusedVertexFilter& operator=(const UnusedVertexFilter& other)
                { ceum = other.ceum; return *this; }
            /* Execution.
             * @return True if vertex is still in graph -> return true if not mapped yet. */
            bool operator()(Component comp) const
                { assert(ceum); return ceum->left.find(comp) == ceum->left.end(); }
            const ComponentEvalUnitMapping* ceum;
        };
        struct UnusedEdgeFilter
        {
            // unfortunately, this predicate must be default constructible
            UnusedEdgeFilter(): cg(0), ceum(0) {}
            UnusedEdgeFilter(const ComponentGraph* const cg,
                const ComponentEvalUnitMapping* const ceum): cg(cg), ceum(ceum) {}
            UnusedEdgeFilter(const UnusedEdgeFilter& other): cg(other.cg), ceum(other.ceum) {}
            UnusedEdgeFilter& operator=(const UnusedEdgeFilter& other)
                { cg = other.cg; ceum = other.ceum; return *this; }
            /* Execution.
             * @return True if edge is still in graph -> return true if not mapped yet. */
            bool operator()(Dependency dep) const
            {
                assert(cg && ceum);
                return
                    (ceum->left.find(cg->targetOf(dep)) == ceum->left.end()) &&
                    (ceum->left.find(cg->sourceOf(dep)) == ceum->left.end());
            }
            const ComponentGraph* cg;
            const ComponentEvalUnitMapping* ceum;
        };

    public:
        typedef boost::filtered_graph<ComponentGraph::Graph,
            UnusedEdgeFilter, UnusedVertexFilter> ComponentGraphRest;

        // members
    protected:
        ProgramCtx& ctx;
        boost::scoped_ptr<ComponentGraph> clonedcgptr;
        ComponentGraph& cg;
        EvalGraphT& eg;
        ASPSolverManager::SoftwareConfigurationPtr externalEvalConfig;

        ComponentEvalUnitMapping mapping;

        UnusedEdgeFilter unusedEdgeFilter;
        UnusedVertexFilter unusedVertexFilter;
        ComponentGraphRest cgrest;

        // methods
    public:
        EvalGraphBuilder(
            ProgramCtx& ctx, ComponentGraph& cg, EvalGraphT& eg,
            ASPSolverManager::SoftwareConfigurationPtr externalEvalConfig);
        virtual ~EvalGraphBuilder();

        //
        // accessors
        //
        inline const EvalGraphT& getEvalGraph() const { return eg; }
        inline ComponentGraph& getComponentGraph() { return cg; }
        inline const ComponentGraphRest& getComponentGraphRest() const { return cgrest; }
        Component getComponentForUnit(EvalUnit u) const;

        RegistryPtr registry();

        inline ProgramCtx& getProgramCtx(){ return ctx; }

        //
        // modifiers
        //

        //  NodeRange nodes, UnitRange orderedDependencies);
        virtual EvalUnit createEvalUnit(
            const std::list<Component>& comps, const std::list<Component>& ccomps);
        //template<typename NodeRange, typename UnitRange>
        //virtual EvalUnit createEvalUnit(
};
typedef boost::shared_ptr<EvalGraphBuilder> EvalGraphBuilderPtr;

DLVHEX_NAMESPACE_END
#endif                           // EVAL_GRAPH_BUILDER_HPP_INCLUDED__03112010

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