Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx > Class Template Reference
Other available functionality » Integer propagators

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

`#include <extensional.hh>`

## Classes

class | State
| States are described by number of incoming and outgoing edges. More...
class | Edge
| Edge defined by in-state and out-state More...
class | Support
| Support information for a value More...
class | Layer
| Layer for a view in the layered graph More...
class | LayerValues
| Iterator for telling variable domains by scanning support. More...
class | Index
| Advisors for views (by position in array) More...
class | IndexRange
| Range approximation of which positions have changed. 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)
| 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.
ModEventDelta | modeventdelta (void) const
| Return the modification event delta.
virtual void | advise (Space &home, Advisor &a)
| Run advisor a to be run on failure in failed space.
double | afc (void) const
| Return the accumlated failure count.
unsigned int | id (void) const
| Return propagator id.
PropagatorGroup | group (void) const
| Return group propagator belongs to.
void | group (PropagatorGroup g)
| Add propagator to group g.
bool | disabled (void) const
| Whether propagator is currently disabled.
virtual | ~Actor (void)
| To avoid warnings.

## 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.
static void * | operator new (size_t s, Space &home)
| Allocate memory from space.
static void | operator delete (void *p, Space &home)
| No-op for exceptions.
static void * | operator new (size_t s)
| Not used.
static void | operator delete (void *p)
| Not used.

## 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, LayeredGraph< View, Val, Degree, StateIdx > &p)
| Constructor for cloning p.
Protected Member Functions inherited from Gecode::Propagator
| Propagator (Home home)
| Constructor for posting.
| Propagator (Space &home, Propagator &p)
| Constructor for cloning p.
Propagator * | fwd (void) const
| Return forwarding pointer during copying.
Kernel::GPI::Info & | gpi (void)
| Provide access to global propagator information.

## 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>
extensional.hh

Definition at line 67 of file extensional.hh.

## Member Typedef Documentation

## ValSize

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 91 of file extensional.hh.

## Constructor & Destructor Documentation

## LayeredGraph() [1/2]

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

Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::LayeredGraph | ( | Space & | home,
|  | LayeredGraph< View, Val, Degree, StateIdx > & | p )

inline protected

Constructor for cloning p.

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

## LayeredGraph() [2/2]

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 232 of file layered-graph.hpp.

## Member Function Documentation

## i_state() [1/2]

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 85 of file layered-graph.hpp.

## i_state() [2/2]

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.

## i_dec()

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 )

inline protected

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

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

## o_state() [1/2]

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 102 of file layered-graph.hpp.

## o_state() [2/2]

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.

## o_dec()

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 )

inline protected

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

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

## audit()

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 242 of file layered-graph.hpp.

## initialize()

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 265 of file layered-graph.hpp.

## copy()

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

Actor * Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::copy | ( | Space & | home | ) |

virtual

Copy propagator during cloning.

Implements Gecode::Actor.

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

## cost()

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

virtual

Cost function (defined as high linear).

Implements Gecode::Propagator.

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

## reschedule()

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

void Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::reschedule | ( | Space & | home | ) |

virtual

Schedule function.

Implements Gecode::Propagator.

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

## advise()

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 )

virtual

Give advice to propagator.

Reimplemented from Gecode::Propagator.

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

## propagate()

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

ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Val, Degree, StateIdx >::propagate | ( | Space & | home,
|  | const ModEventDelta & | med )

virtual

Perform propagation.

Implements Gecode::Propagator.

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

## dispose()

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 583 of file layered-graph.hpp.

## post()

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 )

static

Post propagator on views x and DFA dfa.

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

## Member Data Documentation

## c

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 154 of file extensional.hh.

## n

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 156 of file extensional.hh.

## layers

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 158 of file extensional.hh.

## max_states

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 160 of file extensional.hh.

## n_states

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 162 of file extensional.hh.

## n_edges

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 164 of file extensional.hh.

## i_ch

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 166 of file extensional.hh.

## o_ch

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 168 of file extensional.hh.

## a_ch

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 170 of file extensional.hh.

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

- gecode/int/extensional.hh
- gecode/int/extensional/layered-graph.hpp