Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0

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 Actorcopy (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.
 
- Public Member Functions inherited from Gecode::Propagator
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.
 
- Public Member Functions inherited from Gecode::Actor
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 Public Member Functions inherited from Gecode::Actor
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

Statei_state (int i, StateIdx is)
 Return in state for layer i and state index is.
 
Statei_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.
 
Stateo_state (int i, StateIdx os)
 Return out state for layer i and state index os.
 
Stateo_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.
 
Propagatorfwd (void) const
 Return forwarding pointer during copying.
 
Kernel::GPI::Infogpi (void)
 Provide access to global propagator information.
 

Protected Attributes

Council< Indexc
 The advisor council.
 
int n
 Number of layers (and views)
 
Layerlayers
 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

Definition at line 67 of file extensional.hh.

Member Typedef Documentation

◆ ValSize

template<class View , class Val , class Degree , class StateIdx >
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 )
inlineprotected

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 )
inlineprotected

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 )
inlineprotected

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 )
inlineprotected

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 )
inlineprotected

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 )
inlineprotected

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 )
inlineprotected

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)
inlinevirtual

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: