Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx > Class Template Reference
[Integer propagators]

Domain consistent layered graph (regular) propagator. More...

#include <extensional.hh>

Classes
class	Edge
	Edge defined by in-state and out-state More...
class	Index
	Advisors for views (by position in array) More...
class	IndexRange
	Range approximation of which positions have changed. More...
class	Layer
	Layer for a view in the layered graph More...
class	LayerValues
	Iterator for telling variable domains by scanning support. More...
class	State
	States are described by number of incoming and outgoing edges. More...
class	Support
	Support information for a value More...
Public Member Functions
template<class Var >
	LayeredGraph (Home home, const VarArgArray< Var > &x, const DFA &dfa)
	Constructor for posting.
virtual Actor *	copy (Space &home, bool share)
	Copy propagator during cloning.
virtual PropCost	cost (const Space &home, const ModEventDelta &med) const
	Cost function (defined as high linear).
virtual void	reschedule (Space &home)
	Schedule function.
virtual ExecStatus	advise (Space &home, Advisor &a, const Delta &d)
	Give advice to propagator.
virtual ExecStatus	propagate (Space &home, const ModEventDelta &med)
	Perform propagation.
virtual size_t	dispose (Space &home)
	Delete propagator and return its size.
Static Public Member Functions
template<class Var >
static ExecStatus	post (Home home, const VarArgArray< Var > &x, const DFA &dfa)
	Post propagator on views x and DFA dfa.
Protected Types
typedef Gecode::Support::IntTypeTraits < Val >::utype	ValSize
	Type for support size.
Protected Member Functions
State &	i_state (int i, StateIdx is)
	Return in state for layer i and state index is.
State &	i_state (int i, const Edge &e)
	Return in state for layer i and in state of edge e.
bool	i_dec (int i, const Edge &e)
	Decrement out degree for in state of edge e for layer i.
State &	o_state (int i, StateIdx os)
	Return out state for layer i and state index os.
State &	o_state (int i, const Edge &e)
	Return state for layer i and out state of edge e.
bool	o_dec (int i, const Edge &e)
	Decrement in degree for out state of edge e for layer i.
void	audit (void)
	Perform consistency check on data structures.
template<class Var >
ExecStatus	initialize (Space &home, const VarArgArray< Var > &x, const DFA &dfa)
	Initialize layered graph.
	LayeredGraph (Space &home, bool share, LayeredGraph< View, Val, Degree, StateIdx > &p)
	Constructor for cloning p.
Protected Attributes
Council< Index >	c
	The advisor council.
int	n
	Number of layers (and views).
Layer *	layers
	The layers of the graph.
StateIdx	max_states
	Maximal number of states per layer.
unsigned int	n_states
	Total number of states.
unsigned int	n_edges
	Total number of edges.
IndexRange	i_ch
	Index range with in-degree modifications.
IndexRange	o_ch
	Index range with out-degree modifications.
IndexRange	a_ch
	Index range for any change (for compression).

Detailed Description

template<class View, class Val, class Degree, class StateIdx>
class Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >

Domain consistent layered graph (regular) propagator.

The algorithm for the regular propagator is based on: Gilles Pesant, A Regular Language Membership Constraint for Finite Sequences of Variables, CP 2004. Pages 482-495, LNCS 3258, Springer-Verlag, 2004.

The propagator is not capable of dealing with multiple occurences of the same view.

Requires

 #include <gecode/int/extensional.hh>

Definition at line 69 of file extensional.hh.

Member Typedef Documentation

template<class View, class Val, class Degree, class StateIdx>

typedef Gecode::Support::IntTypeTraits<Val>::utype Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::ValSize [protected]

Type for support size.

Definition at line 93 of file extensional.hh.

Constructor & Destructor Documentation

template<class View , class Val , class Degree , class StateIdx >

Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::LayeredGraph	(	Space &	home,
		bool	share,
		LayeredGraph< View, Val, Degree, StateIdx > &	p
	)			`[inline, protected]`

Constructor for cloning p.

Definition at line 710 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

template<class Var >

Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::LayeredGraph	(	Home	home,
		const VarArgArray< Var > &	x,
		const DFA &	dfa
	)			`[inline]`

Constructor for posting.

Definition at line 237 of file layered-graph.hpp.

Member Function Documentation

template<class View , class Val , class Degree , class StateIdx >

LayeredGraph< View, Val, Degree, StateIdx >::State & Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::i_state	(	int	i,
		StateIdx	is
	)			`[inline, protected]`

Return in state for layer i and state index is.

Definition at line 89 of file layered-graph.hpp.

template<class View, class Val, class Degree, class StateIdx>

State& Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::i_state	(	int	i,
		const Edge &	e
	)			`[protected]`

Return in state for layer i and in state of edge e.

template<class View, class Val, class Degree, class StateIdx>

bool Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::i_dec	(	int	i,
		const Edge &	e
	)			`[protected]`

Decrement out degree for in state of edge e for layer i.

template<class View , class Val , class Degree , class StateIdx >

LayeredGraph< View, Val, Degree, StateIdx >::State & Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::o_state	(	int	i,
		StateIdx	os
	)			`[inline, protected]`

Return out state for layer i and state index os.

Definition at line 106 of file layered-graph.hpp.

template<class View, class Val, class Degree, class StateIdx>

State& Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::o_state	(	int	i,
		const Edge &	e
	)			`[protected]`

Return state for layer i and out state of edge e.

template<class View, class Val, class Degree, class StateIdx>

bool Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::o_dec	(	int	i,
		const Edge &	e
	)			`[protected]`

Decrement in degree for out state of edge e for layer i.

template<class View , class Val , class Degree , class StateIdx >

void Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::audit ( void ) [inline, protected]

Perform consistency check on data structures.

Definition at line 247 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

template<class Var >

ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::initialize	(	Space &	home,
		const VarArgArray< Var > &	x,
		const DFA &	dfa
	)			`[inline, protected]`

Initialize layered graph.

Definition at line 270 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

Actor * Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::copy	(	Space &	home,
		bool	share
	)			`[inline, virtual]`

Copy propagator during cloning.

Implements Gecode::Actor.

Definition at line 751 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

PropCost Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::cost	(	const Space &	home,
		const ModEventDelta &	med
	)			const `[inline, virtual]`

Cost function (defined as high linear).

Implements Gecode::Propagator.

Definition at line 744 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

void Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::reschedule ( Space & home ) [inline, virtual]

Schedule function.

Implements Gecode::Propagator.

Definition at line 596 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::advise	(	Space &	home,
		Advisor &	a,
		const Delta &	d
	)			`[inline, virtual]`

Give advice to propagator.

Reimplemented from Gecode::Propagator.

Definition at line 442 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::propagate	(	Space &	home,
		const ModEventDelta &	med
	)			`[inline, virtual]`

Perform propagation.

Implements Gecode::Propagator.

Definition at line 602 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

size_t Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::dispose ( Space & home ) [inline, virtual]

Delete propagator and return its size.

Reimplemented from Gecode::Actor.

Definition at line 588 of file layered-graph.hpp.

template<class View , class Val , class Degree , class StateIdx >

template<class Var >

ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::post	(	Home	home,
		const VarArgArray< Var > &	x,
		const DFA &	dfa
	)			`[inline, static]`

Post propagator on views x and DFA dfa.

Definition at line 687 of file layered-graph.hpp.

Member Data Documentation

template<class View, class Val, class Degree, class StateIdx>

Council<Index> Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::c [protected]

The advisor council.

Definition at line 156 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

int Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::n [protected]

Number of layers (and views).

Definition at line 158 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

Layer* Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::layers [protected]

The layers of the graph.

Definition at line 160 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

StateIdx Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::max_states [protected]

Maximal number of states per layer.

Definition at line 162 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

unsigned int Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::n_states [protected]

Total number of states.

Definition at line 164 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

unsigned int Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::n_edges [protected]

Total number of edges.

Definition at line 166 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

IndexRange Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::i_ch [protected]

Index range with in-degree modifications.

Definition at line 168 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

IndexRange Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::o_ch [protected]

Index range with out-degree modifications.

Definition at line 170 of file extensional.hh.

template<class View, class Val, class Degree, class StateIdx>

IndexRange Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::a_ch [protected]

Index range for any change (for compression).

Definition at line 172 of file extensional.hh.

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

gecode/int/extensional.hh (Revision: 15137)
gecode/int/extensional/layered-graph.hpp (Revision: 15137)

Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx > Class Template Reference [Integer propagators]

Classes

Public Member Functions

Static Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

template<class View, class Val, class Degree, class StateIdx> class Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx > Class Template Reference
[Integer propagators]

template<class View, class Val, class Degree, class StateIdx>
class Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >