Implements the component graph. More...

#include <include/dlvhex2/ComponentGraph.h>

Collaboration diagram for ComponentGraph:

Data Structures
struct	ComponentInfo
	Implements meta information about components. More...
struct	DependencyInfo
	Meta information about rule dependencies in the component. More...
Public Types
typedef boost::adjacency_list < boost::setS, boost::listS, boost::bidirectionalS, ComponentInfo, DependencyInfo >	Graph
typedef boost::graph_traits < Graph >	Traits
typedef Graph::vertex_descriptor	Component
typedef Graph::edge_descriptor	Dependency
typedef Traits::vertex_iterator	ComponentIterator
typedef Traits::edge_iterator	DependencyIterator
typedef Traits::out_edge_iterator	PredecessorIterator
typedef Traits::in_edge_iterator	SuccessorIterator
typedef std::set< Component >	ComponentSet
typedef std::map< Component, DependencyInfo >	DepMap
Public Member Functions
	ComponentGraph (const DependencyGraph &dg, ProgramCtx &ctx, RegistryPtr reg)
	Constructor to construct a component graph out of a DependencyGraph.
virtual	~ComponentGraph ()
	Destructor.
ComponentGraph *	clone () const
	For explicit cloning of the graph.
Component	collapseComponents (const ComponentSet &originals, const ComponentSet &shared=ComponentSet())
void	computeCollapsedComponentInfos (const ComponentSet &comps, const ComponentSet &sharedcomps, DepMap &newIncomingDependencies, DepMap &newOutgoingDependencies, ComponentInfo &newComponentInfo) const
	Compute the dependency infos and component info before putting components `comps' and `sharedcomps' into a new component.
const Graph &	getInternalGraph () const
virtual void	writeGraphViz (std::ostream &o, bool verbose) const
	Output graph as graphviz source (dot file).
std::pair< ComponentIterator, ComponentIterator >	getComponents () const
	Get range over all components.
std::pair< DependencyIterator, DependencyIterator >	getDependencies () const
	Get range over all edges.
const ComponentInfo &	getComponentInfo (Component c) const
	Get node info given node.
const DependencyInfo &	getDependencyInfo (Dependency dep) const
	Get dependency info given dependency.
std::pair< PredecessorIterator, PredecessorIterator >	getDependencies (Component c) const
	Get dependencies (to predecessors) = arcs from this component to others.
std::pair< SuccessorIterator, SuccessorIterator >	getProvides (Component c) const
	Get provides (dependencies to successors) = arcs from other component to this one.
Component	sourceOf (Dependency d) const
	Get source of dependency = component that depends.
Component	targetOf (Dependency d) const
	Get target of dependency = component upon which the source depends.
const ComponentInfo &	propsOf (Component c) const
	Get node properties.
ComponentInfo &	propsOf (Component c)
	Get node properties.
const DependencyInfo &	propsOf (Dependency d) const
	Get dependency properties.
DependencyInfo &	propsOf (Dependency d)
	Get dependency properties.
unsigned	countComponents () const
	Retrieves the number of components.
unsigned	countDependencies () const
	Retrieves the number of depdencies.
Static Public Member Functions
static void	calculateStratificationInfo (RegistryPtr reg, ComponentInfo &ci)
	Computes stratification info for a component and stores it in the graph.
static void	calculatePredicatesOfComponent (RegistryPtr reg, ComponentInfo &ci)
	Computes the set of all predicates in this component.
Protected Member Functions
	ComponentGraph (const ComponentGraph &other)
	Copy-constructor.
virtual void	writeGraphVizComponentLabel (std::ostream &o, Component c, unsigned index, bool verbose) const
	Writes a single component in dot format.
virtual void	writeGraphVizDependencyLabel (std::ostream &o, Dependency dep, bool verbose) const
	Writes a single dependency in dot format.
void	calculateComponents (const DependencyGraph &dg)
	Computes the meta information about the dependencies in the graph.
bool	calculateFixedDomain (ComponentInfo &ci) const
	Checks if a given component uses value invention.
bool	computeRecursiveAggregatesInComponent (ComponentInfo &ci) const
	Checks if a given component uses recursive aggregates.
Protected Attributes
ProgramCtx &	ctx
	ProgramCtx.
RegistryPtr	reg
	Registry used for debugging and printing.
const DependencyGraph &	dg
	In non-debug mode this graph's lifetime can end after the constructor finished.
Graph	cg
	Internal component graph.
Private Member Functions
	BOOST_CONCEPT_ASSERT ((boost::Convertible< DependencyGraph::Node, unsigned int >))

Detailed Description

Implements the component graph.

A component graph is created from a dependency graph by collecting SCCs into single nodes components.

A component graph is a dag (acyclic by the above construction).

Vertices (= components) store a set of rules and information about the dependencies within the collapsed part of the dependency graph.

Edges (= collapsed dependencies) store information about the collapsed dependencies.

A component contains

external atoms depending only on other components (=outer eatoms),
rules within the component (=inner rules),
constraints within the component (=inner constraints), and
external atoms depending on rules in the component (=inner eatoms).

For each component, only one of these storages must hold an object, except for inner eatoms which can only exist if there are inner rules.

Definition at line 71 of file ComponentGraph.h.

Member Typedef Documentation

typedef Graph::vertex_descriptor ComponentGraph::Component

Definition at line 165 of file ComponentGraph.h.

typedef Traits::vertex_iterator ComponentGraph::ComponentIterator

Definition at line 167 of file ComponentGraph.h.

typedef std::set<Component> ComponentGraph::ComponentSet

Definition at line 172 of file ComponentGraph.h.

typedef Graph::edge_descriptor ComponentGraph::Dependency

Definition at line 166 of file ComponentGraph.h.

typedef Traits::edge_iterator ComponentGraph::DependencyIterator

Definition at line 168 of file ComponentGraph.h.

typedef std::map<Component, DependencyInfo> ComponentGraph::DepMap

Definition at line 173 of file ComponentGraph.h.

typedef boost::adjacency_list< boost::setS, boost::listS, boost::bidirectionalS, ComponentInfo, DependencyInfo> ComponentGraph::Graph

Definition at line 162 of file ComponentGraph.h.

typedef Traits::out_edge_iterator ComponentGraph::PredecessorIterator

Definition at line 169 of file ComponentGraph.h.

typedef Traits::in_edge_iterator ComponentGraph::SuccessorIterator

Definition at line 170 of file ComponentGraph.h.

typedef boost::graph_traits<Graph> ComponentGraph::Traits

Definition at line 163 of file ComponentGraph.h.

Constructor & Destructor Documentation

ComponentGraph::ComponentGraph ( const ComponentGraph & other ) [protected]

Copy-constructor.

Only to be used by explicit clone method.

Parameters:

other Component to copy.

Definition at line 1259 of file ComponentGraph.cpp.

References DBGLOG.

Referenced by clone().

ComponentGraph::ComponentGraph	(	const DependencyGraph &	dg,
		ProgramCtx &	ctx,
		RegistryPtr	reg
	)

Constructor to construct a component graph out of a DependencyGraph.

Parameters:

dp	DependencyGraph used as basis for the ComponentGraph.
ctx	ProgramCtx.
reg	See ComponentGraph::reg.

Definition at line 106 of file ComponentGraph.cpp.

References calculateComponents(), and DBGLOG.

ComponentGraph::~ComponentGraph ( ) [virtual]

Destructor.

Definition at line 119 of file ComponentGraph.cpp.

References DBGLOG.

Member Function Documentation

ComponentGraph::BOOST_CONCEPT_ASSERT ( (boost::Convertible< DependencyGraph::Node, unsigned int >) ) [private]

void ComponentGraph::calculateComponents ( const DependencyGraph & dg ) [protected]

Computes the meta information about the dependencies in the graph.

Parameters:

dp	DependencyGraph to compute the information for.

Definition at line 332 of file ComponentGraph.cpp.

Referenced by ComponentGraph().

bool ComponentGraph::calculateFixedDomain ( ComponentInfo & ci ) const [protected]

Checks if a given component uses value invention.

Parameters:

ci	ComponentInfo of the component to check.

Returns:: False if ci uses value invention and true otherwise.

Definition at line 561 of file ComponentGraph.cpp.

References Rule::body, DBGLOG, ID::doesRuleContainExtatoms(), Rule::head, ComponentGraph::ComponentInfo::innerConstraints, ComponentGraph::ComponentInfo::innerRules, ID::isAggregateAtom(), ID::isBuiltinAtom(), ID::isExternalAtom(), ID::isNaf(), ID::isOrdinaryAtom(), ID::isVariableTerm(), ComponentGraph::ComponentInfo::outerEatoms, ComponentGraph::ComponentInfo::stratifiedLiterals, ComponentGraph::ComponentInfo::stronglySafeVariables, Atom::tuple, OrdinaryAtom::unifiesWith(), and WARNING().

Referenced by calculateComponents().

void ComponentGraph::calculatePredicatesOfComponent	(	RegistryPtr	reg,
		ComponentInfo &	ci
	)		`[static]`

Computes the set of all predicates in this component.

Parameters:

reg	Registry used for resolving IDs.
ci	ComponentInfo of the component to check.

Definition at line 830 of file ComponentGraph.cpp.

References Rule::body, DBGLOG, PluginAtom::getInputType(), Rule::head, ComponentGraph::ComponentInfo::innerConstraints, ComponentGraph::ComponentInfo::innerRules, ExternalAtom::inputs, ID::isAggregateAtom(), ID::isExternalAtom(), ID::isOrdinaryAtom(), AggregateAtom::literals, ExternalAtom::pluginAtom, PluginAtom::PREDICATE, and ComponentGraph::ComponentInfo::predicatesOccurringInComponent.

Referenced by calculateComponents().

void ComponentGraph::calculateStratificationInfo	(	RegistryPtr	reg,
		ComponentInfo &	ci
	)		`[static]`

Computes stratification info for a component and stores it in the graph.

Parameters:

reg	Registry used for resolving IDs.
ci	ComponentInfo of the component to check.

Definition at line 769 of file ComponentGraph.cpp.

References Rule::body, DBGLOG, ExternalAtom::getExtSourceProperties(), PluginAtom::getInputType(), Rule::head, ComponentGraph::ComponentInfo::innerRules, ExternalAtom::inputs, ID::isExternalAtom(), ID::isNaf(), ExtSourceProperties::isNonmonotonic(), ID::isOrdinaryAtom(), ExternalAtom::pluginAtom, PluginAtom::PREDICATE, ComponentGraph::ComponentInfo::predicatesDefinedInComponent, ComponentGraph::ComponentInfo::stratifiedLiterals, Atom::tuple, and OrdinaryAtom::unifiesWith().

Referenced by calculateComponents(), and computeCollapsedComponentInfos().

ComponentGraph * ComponentGraph::clone ( ) const

For explicit cloning of the graph.

Returns:: Pointer to a copy of this ComponentGraph.

Definition at line 1272 of file ComponentGraph.cpp.

References ComponentGraph().

ComponentGraph::Component ComponentGraph::collapseComponents	(	const ComponentSet &	originals,
		const ComponentSet &	shared = `ComponentSet()`
	)

Definition at line 1071 of file ComponentGraph.cpp.

References cg, computeCollapsedComponentInfos(), DBGLOG, DBGLOG_SCOPE, LOG, printrange(), and propsOf().

Referenced by EvalHeuristicEasy::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), calculateComponents(), EvalGraphBuilder::createEvalUnit(), and DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::preprocessComponents().

void ComponentGraph::computeCollapsedComponentInfos	(	const ComponentSet &	comps,
		const ComponentSet &	sharedcomps,
		DepMap &	newIncomingDependencies,
		DepMap &	newOutgoingDependencies,
		ComponentInfo &	newComponentInfo
	)		const

Compute the dependency infos and component info before putting components `comps' and `sharedcomps' into a new component.

`sharedcomps' may only contain components with constraints that can be shared.

This method does not change the graph, it only changes the output arguments, hence it is const (and should stay const).

This method throws an exception if this operation makes the DAG cyclic.

Parameters:

comps	Set of overall components.
sharedcomps	Set of components which are shared among multiple evaluation units.
newIncomingDependencies	Collapsed incoming dependencies of the collapsed component.
newOutgoingDependencies	Collapsed outgoing dependencies of the collapsed component.
newComponentInfo	New ComponentInfo of the collapsed component.

Definition at line 877 of file ComponentGraph.cpp.

Referenced by collapseComponents().

bool ComponentGraph::computeRecursiveAggregatesInComponent ( ComponentInfo & ci ) const [protected]

Checks if a given component uses recursive aggregates.

Parameters:

ci	ComponentInfo of the component to check.

Returns:: True if ci uses recursive aggregates and false otherwise.

Definition at line 719 of file ComponentGraph.cpp.

References Rule::body, PluginAtom::getInputType(), Rule::head, ComponentGraph::ComponentInfo::innerRules, ExternalAtom::inputs, ID::isAggregateAtom(), ID::isExternalAtom(), ID::isOrdinaryAtom(), AggregateAtom::literals, ExternalAtom::pluginAtom, PluginAtom::PREDICATE, and Atom::tuple.

Referenced by calculateComponents(), and computeCollapsedComponentInfos().

unsigned ComponentGraph::countComponents ( ) const [inline]

Retrieves the number of components.

Returns:: Number of components.

Definition at line 332 of file ComponentGraph.h.

unsigned ComponentGraph::countDependencies ( ) const [inline]

Retrieves the number of depdencies.

Returns:: Number of depdencies.

Definition at line 336 of file ComponentGraph.h.

const ComponentInfo& ComponentGraph::getComponentInfo ( Component c ) const [inline]

Get node info given node.

Parameters:

c	Some component of the graph.

Returns:: ComponentInfo of c.

Definition at line 273 of file ComponentGraph.h.

Referenced by DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), calculateComponents(), and writeGraphVizComponentLabel().

std::pair<ComponentIterator, ComponentIterator> ComponentGraph::getComponents ( ) const [inline]

Get range over all components.

Returns:: Pair of begin and end iterator.

Definition at line 262 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicMonolithic::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), calculateComponents(), DumpingEvalGraphBuilder::createEvalUnit(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::preprocessComponents(), internal::transitivePredecessorComponents(), and internalgreedy::transitivePredecessorComponents().

std::pair<DependencyIterator, DependencyIterator> ComponentGraph::getDependencies ( ) const [inline]

Get range over all edges.

Returns:: Pair of begin and end iterator.

Definition at line 266 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicOldDlvhex::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), calculateComponents(), computeCollapsedComponentInfos(), and EvalGraphBuilder::createEvalUnit().

std::pair<PredecessorIterator, PredecessorIterator> ComponentGraph::getDependencies ( Component c ) const [inline]

Get dependencies (to predecessors) = arcs from this component to others.

Parameters:

c	Some component of the graph.

Returns:: Pair of begin and end iterator.

Definition at line 286 of file ComponentGraph.h.

const DependencyInfo& ComponentGraph::getDependencyInfo ( Dependency dep ) const [inline]

Get dependency info given dependency.

Parameters:

dep	Some dependency of the graph.

Returns:: DependencyInfo of dep.

Definition at line 279 of file ComponentGraph.h.

Referenced by EvalHeuristicGreedy::build(), and writeGraphVizDependencyLabel().

const Graph& ComponentGraph::getInternalGraph ( ) const [inline]

Definition at line 252 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicOldDlvhex::build(), EvalHeuristicTrivial::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), internal::transitivePredecessorComponents(), and internalgreedy::transitivePredecessorComponents().

std::pair<SuccessorIterator, SuccessorIterator> ComponentGraph::getProvides ( Component c ) const [inline]

Get provides (dependencies to successors) = arcs from other component to this one.

Parameters:

c	Some component of the graph.

Returns:: PAir of begin and end iterator.

Definition at line 293 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), computeCollapsedComponentInfos(), and DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::preprocessComponents().

const ComponentInfo& ComponentGraph::propsOf ( Component c ) const [inline]

Get node properties.

Parameters:

c	Some component of the graph.

Returns:: ComponentInfo of c.

Definition at line 311 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicOldDlvhex::build(), EvalHeuristicGreedy::build(), calculateComponents(), collapseComponents(), computeCollapsedComponentInfos(), EvalGraphBuilder::createEvalUnit(), and DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::preprocessComponents().

ComponentInfo& ComponentGraph::propsOf ( Component c ) [inline]

Get node properties.

Parameters:

c	Some component of the graph.

Returns:: ComponentInfo of c.

Definition at line 316 of file ComponentGraph.h.

const DependencyInfo& ComponentGraph::propsOf ( Dependency d ) const [inline]

Get dependency properties.

Parameters:

d	Some dependency of the graph.

Returns:: ComponentInfo of d.

Definition at line 321 of file ComponentGraph.h.

DependencyInfo& ComponentGraph::propsOf ( Dependency d ) [inline]

Get dependency properties.

Parameters:

d	Some dependency of the graph.

Returns:: ComponentInfo of d.

Definition at line 326 of file ComponentGraph.h.

Component ComponentGraph::sourceOf ( Dependency d ) const [inline]

Get source of dependency = component that depends.

Parameters:

d	Some dependency of the graph.

Returns:: Component where d origins.

Definition at line 299 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), computeCollapsedComponentInfos(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::preprocessComponents(), and writeGraphViz().

Component ComponentGraph::targetOf ( Dependency d ) const [inline]

Get target of dependency = component upon which the source depends.

Parameters:

d	Some dependency of the graph.

Returns:: Component where d ends.

Definition at line 305 of file ComponentGraph.h.

Referenced by EvalHeuristicEasy::build(), EvalHeuristicOldDlvhex::build(), EvalHeuristicGreedy::build(), DLVHEX_NAMESPACE_BEGIN::EvalHeuristicFromHEXSourcecode::build(), calculateComponents(), computeCollapsedComponentInfos(), EvalGraphBuilder::createEvalUnit(), and writeGraphViz().

void ComponentGraph::writeGraphViz	(	std::ostream &	o,
		bool	verbose
	)		const `[virtual]`

Output graph as graphviz source (dot file).

Parameters:

o	Stream to print the graph to.
verbose	True to include more information.

Definition at line 1221 of file ComponentGraph.cpp.

References cg, sourceOf(), targetOf(), writeGraphVizComponentLabel(), and writeGraphVizDependencyLabel().

Referenced by EvalHeuristicGreedy::build().

void ComponentGraph::writeGraphVizComponentLabel	(	std::ostream &	o,
		Component	c,
		unsigned	index,
		bool	verbose
	)		const `[protected, virtual]`

Writes a single component in dot format.

Parameters:

o	Stream to write to.
c	Component to output.
index	Index to use for identifying the component.
verbose	True to include more detailed information.

Definition at line 1149 of file ComponentGraph.cpp.

Referenced by writeGraphViz().

void ComponentGraph::writeGraphVizDependencyLabel	(	std::ostream &	o,
		Dependency	dep,
		bool	verbose
	)		const `[protected, virtual]`

Writes a single dependency in dot format.

Parameters:

o	Stream to write to.
dep	Dependency to output.
verbose	True to include more detailed information.

Definition at line 1199 of file ComponentGraph.cpp.

Referenced by writeGraphViz().

Field Documentation

Graph ComponentGraph::cg [protected]

Internal component graph.

Definition at line 189 of file ComponentGraph.h.

Referenced by calculateComponents(), collapseComponents(), and writeGraphViz().

ProgramCtx& ComponentGraph::ctx [protected]

ProgramCtx.

Definition at line 180 of file ComponentGraph.h.

Referenced by calculateComponents().

const DependencyGraph& ComponentGraph::dg [protected]

In non-debug mode this graph's lifetime can end after the constructor finished.

Definition at line 186 of file ComponentGraph.h.

RegistryPtr ComponentGraph::reg [protected]

Registry used for debugging and printing.

Definition at line 182 of file ComponentGraph.h.

The documentation for this class was generated from the following files:

include/dlvhex2/ComponentGraph.h
src/ComponentGraph.cpp

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation