Generated on Mon Jul 6 18:09:34 2009 for Gecode by doxygen 1.5.9
Gecode::Int::Extensional::LayeredGraph

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

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

#include <extensional.hh>

List of all members.

Classes

class  Edge
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

 LayeredGraph (Space &home, ViewArray< View > &x, DFA &d)
 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 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

static ExecStatus post (Space &home, ViewArray< View > &x, DFA &d)
 Post propagator on views x and DFA d.

Protected Member Functions

bool constructed (void) const
 Test whether layered graph has already been constructed.
void eliminate (void)
 Eliminate assigned prefix, return how many layers removed.
ExecStatus construct (Space &home)
 Construct layered graph.
ExecStatus prune (Space &home)
 Prune incrementally.
 LayeredGraph (Space &home, bool share, LayeredGraph< View, Degree, StateIdx > &p)
 Constructor for cloning p.

Protected Attributes

Council< Index > c
 The advisor council.
ViewArray< View > x
 The views.
DFA dfa
 The DFA describing the language.
StateIdx start
 The start state for graph construction.
Layer * layers
 The layers of the graph.
State * states
 The states used in the graph.
IndexRange i_ch
 Index range with in-degree modifications.
IndexRange o_ch
 Index range with out-degree modifications.

Detailed Description

template<class View, class Degree, class StateIdx>
class Gecode::Int::Extensional::LayeredGraph< View, 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.

Constructor & Destructor Documentation

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

Constructor for cloning p.

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

template<class View , class Degree , class StateIdx >
Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::LayeredGraph ( Space &  home,
ViewArray< View > &  x,
DFA &  d 
) [inline]

Constructor for posting.

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

Member Function Documentation

template<class View , class Degree , class StateIdx >
bool Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::constructed ( void   )  const [inline, protected]

Test whether layered graph has already been constructed.

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

template<class View , class Degree , class StateIdx >
void Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::eliminate ( void   )  [inline, protected]

Eliminate assigned prefix, return how many layers removed.

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

template<class View , class Degree , class StateIdx >
ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::construct ( Space &  home  )  [inline, protected]

Construct layered graph.

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

template<class View , class Degree , class StateIdx >
ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::prune ( Space &  home  )  [inline, protected]

Prune incrementally.

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

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

Copy propagator during cloning.

Implements Gecode::Actor.

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

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

Cost function (defined as high linear).

Implements Gecode::Propagator.

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

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

Give advice to propagator.

Reimplemented from Gecode::Propagator.

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

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

Perform propagation.

Implements Gecode::Propagator.

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

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

Delete propagator and return its size.

Reimplemented from Gecode::Actor.

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

template<class View , class Degree , class StateIdx >
ExecStatus Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::post ( Space &  home,
ViewArray< View > &  x,
DFA &  d 
) [inline, static]

Post propagator on views x and DFA d.

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

Member Data Documentation

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

The advisor council.

Definition at line 151 of file extensional.hh.

template<class View, class Degree, class StateIdx>
ViewArray<View> Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::x [protected]

The views.

Definition at line 153 of file extensional.hh.

template<class View, class Degree, class StateIdx>
DFA Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::dfa [protected]

The DFA describing the language.

Definition at line 155 of file extensional.hh.

template<class View, class Degree, class StateIdx>
StateIdx Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::start [protected]

The start state for graph construction.

Definition at line 157 of file extensional.hh.

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

The layers of the graph.

Definition at line 159 of file extensional.hh.

template<class View, class Degree, class StateIdx>
State* Gecode::Int::Extensional::LayeredGraph< View, Degree, StateIdx >::states [protected]

The states used in the graph.

Definition at line 161 of file extensional.hh.

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

Index range with in-degree modifications.

Definition at line 163 of file extensional.hh.

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

Index range with out-degree modifications.

Definition at line 165 of file extensional.hh.

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