Generated on Wed Jan 4 17:49:22 2006 for Gecode by doxygen 1.4.6

Gecode::Int::Sortedness Namespace Reference


Detailed Description

Sortedness propagators


Classes

class  SccComponent
 Representation of a strongly connected component. More...
class  OfflineMinItem
 Item used to construct the OfflineMin sequence. More...
class  OfflineMin
 Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the sorted views y. More...
class  TupleMaxInc
 Index comparison for ViewArray<Tuple>. More...
class  TupleMinInc
 View comparison on ViewTuples. More...
class  TupleMinIncPerm
 View comparison on ViewTuples. More...
class  Sortedness
 Bounds consistent sortedness propagator. More...

Functions

template<class View, class Tuple, bool Perm>
bool glover (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
 Glover's maximum matching in a bipartite graph.
template<class View, class Tuple, bool Perm>
bool revglover (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
 Symmetric glover function for the upper domain bounds.
template<class View, class Tuple>
void computesccs (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
 Compute the sccs of the oriented intersection-graph.
template<class View, class Tuple, bool Perm, bool shared>
bool narrow_domx (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, int tau[], int phi[], int scclist[], SccComponent sinfo[], bool &nofix)
 Narrowing the domains of the x variables.
template<class View, class Tuple, bool Perm, bool shared>
bool narrow_domy (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
 Narrowing the domains of the y views.
template<class View, class Tuple, bool Perm>
void sort_sigma (ViewArray< Tuple > &xz, bool fixed)
 Build $\sigma$.
template<class View, class Tuple, bool Perm>
void sort_tau (ViewArray< Tuple > &xz, int tau[])
 Build $\tau$.
template<class View, class Tuple, bool shared>
bool normalize (Space *home, ViewArray< View > &y, ViewArray< Tuple > &xz, bool &nofix)
 Performing normalization on the views in y.
template<class View, class Tuple, bool Perm, bool shared>
bool perm_bc (Space *home, int tau[], ViewArray< Tuple > &xz, bool &crossingedge, bool &nofix)
 Bounds consistency on the permutation views.
template<class View, class Tuple, bool Perm, bool shared>
ExecStatus bounds_propagation (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, bool &repairpass, bool &nofix, bool &match_fixed)
 Perform bounds consistent sortedness propagation.
template<class View, class Tuple, bool Perm>
bool check_subsumption (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, bool &subsumed, int &dropfst)
 Subsumption test.
std::ostream & operator<< (std::ostream &os, OfflineMin seq)
 Print an OfflineMin sequence.
template<class View, class Tuple, bool Perm, bool shared>
bool array_assigned (Space *home, ViewArray< Tuple > &xz, ViewArray< View > &y, bool &subsumed, bool &match_fixed, bool &nofix)
 Check for assignment of a variable array.


Function Documentation

template<class View, class Tuple, bool Perm>
bool Gecode::Int::Sortedness::glover Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
int  tau[],
int  phi[],
OfflineMinItem  sequence[],
int  vertices[]
[inline]
 

Glover's maximum matching in a bipartite graph.

Compute a matching in the bipartite convex intersection graph with one partition containing the x views and the other containing the y views. The algorithm works with an implicit array structure of the intersection graph.

Union-Find Implementation of F.Glover's matching algorithm.

The idea is to mimick a priority queue storing x-indices $[i_0,\dots, i_{n-1}]$, s.t. the upper domain bounds are sorted $D_{i_0} \leq\dots\leq D_{i_{n-1}}$ where $ D_{i_0}$ is the top element

Definition at line 43 of file matching.icc.

template<class View, class Tuple, bool Perm>
bool Gecode::Int::Sortedness::revglover Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
int  tau[],
int  phiprime[],
OfflineMinItem  sequence[],
int  vertices[]
[inline]
 

Symmetric glover function for the upper domain bounds.

Definition at line 113 of file matching.icc.

template<class View, class Tuple>
void Gecode::Int::Sortedness::computesccs Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
int  phi[],
SccComponent  sinfo[],
int  scclist[]
[inline]
 

Compute the sccs of the oriented intersection-graph.

An y-node $y_j$ and its corresponding matching mate $x_{\phi(j)}$ form the smallest possible scc, since both edges $e_1(y_j, x_{\phi(j)})$ and $e_2(x_{\phi(j)},y_j)$ are both contained in the oriented intersection graph.

Hence a scc containg more than two nodes is represented as an array of SccComponent entries, $[ y_{j_0},x_{\phi(j_0)},\dots,y_{j_k},x_{\phi(j_k)}]$.

Parameters scclist ~ resulting sccs

Definition at line 64 of file narrowing.icc.

template<class View, class Tuple, bool Perm, bool shared>
bool Gecode::Int::Sortedness::narrow_domx Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
int  tau[],
int  phi[],
int  scclist[],
SccComponent  sinfo[],
bool &  nofix
[inline]
 

Narrowing the domains of the x variables.

Due to the correspondance between perfect matchings in the "reduced" intersection graph of x and y views and feasible assignments for the Sortedness constraint the new domain bounds for views in x are computed as

  • lower bounds: $ S_i = max(D_i, E_l) $ where $y_l$ is the leftmost neighbour of $x_i$
  • upper bounds: $ S_i = min(D_i, E_h) $ where $y_h$ is the rightmost neighbour of $x_i$

Definition at line 143 of file narrowing.icc.

template<class View, class Tuple, bool Perm, bool shared>
bool Gecode::Int::Sortedness::narrow_domy Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
int  phi[],
int  phiprime[],
bool &  nofix
[inline]
 

Narrowing the domains of the y views.

analogously to the x views we take

  • for the upper bounds the matching $\phi$ computed in glover and compute the new upper bound by $T_j=min(E_j, D_{\phi(j)})$
  • for the lower bounds the matching $\phi'$ computed in revglover and update the new lower bound by $T_j=max(E_j, D_{\phi'(j)})$

Definition at line 244 of file narrowing.icc.

template<class View, class Tuple, bool Perm>
void Gecode::Int::Sortedness::sort_sigma ViewArray< Tuple > &  xz,
bool  fixed
[inline]
 

Build $\sigma$.

Creates a sorting permutation $\sigma$ by sorting the views in x according to their lower bounds

Definition at line 35 of file order.icc.

template<class View, class Tuple, bool Perm>
void Gecode::Int::Sortedness::sort_tau ViewArray< Tuple > &  xz,
int  tau[]
[inline]
 

Build $\tau$.

Creates a sorting permutation $\tau$ by sorting a given array of indices in tau according to the upper bounds of the views in x

Definition at line 58 of file order.icc.

template<class View, class Tuple, bool shared>
bool Gecode::Int::Sortedness::normalize Space *  home,
ViewArray< View > &  y,
ViewArray< Tuple > &  xz,
bool &  nofix
[inline]
 

Performing normalization on the views in y.

The views in y are called normalized if $\forall i\in\{0,\dots, n-1\}: min(y_0) \leq \dots \leq min(y_{n-1}) \wedge max(y_0) \leq \dots \leq max(y_{n-1})$ holds.

Definition at line 73 of file order.icc.

template<class View, class Tuple, bool Perm, bool shared>
bool Gecode::Int::Sortedness::perm_bc Space *  home,
int  tau[],
ViewArray< Tuple > &  xz,
bool &  crossingedge,
bool &  nofix
[inline]
 

Bounds consistency on the permutation views.

Check, whether the permutation view are bounds consistent. This function tests, whether there are "crossing edges", i.e. whether the current domains permit matchings between unsorted views x and the sorted variables y violating the property that y is sorted.

Definition at line 131 of file order.icc.

template<class View, class Tuple, bool Perm, bool shared>
ExecStatus Gecode::Int::Sortedness::bounds_propagation Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
bool &  repairpass,
bool &  nofix,
bool &  match_fixed
 

Perform bounds consistent sortedness propagation.

Implements the propagation algorithm for Sortedness::Sortedness and is provided as seperate function, because a second pass of the propagation algorithm is needed in order to achieve idempotency in case explicit permutation variables are provided.

If Perm is true, permutation variables form the third argument which implies additional inferences, consistency check on the permutation variables and eventually a second pass of the propagation algorithm. Otherwise, the algorithm does not take care of the permutation variables resulting in a better performance.

Definition at line 58 of file sortedness.icc.

template<class View, class Tuple, bool Perm>
bool Gecode::Int::Sortedness::check_subsumption Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
bool &  subsumed,
int &  dropfst
[inline]
 

Subsumption test.

The propagator for Sortedness is subsumed if all variables of the ViewArrays x, y and z are determined and the Semantics of Sortedness are respected.
In addition to the subsumption test check_subsumption determines, whether we can reduce the orginial problem to a smaller one, by dropping already matched variables.

Definition at line 39 of file sortsup.icc.

std::ostream& Gecode::Int::Sortedness::operator<< std::ostream &  os,
OfflineMin  seq
[inline]
 

Print an OfflineMin sequence.

Definition at line 223 of file sortsup.icc.

template<class View, class Tuple, bool Perm, bool shared>
bool Gecode::Int::Sortedness::array_assigned Space *  home,
ViewArray< Tuple > &  xz,
ViewArray< View > &  y,
bool &  subsumed,
bool &  match_fixed,
bool &  nofix
[inline]
 

Check for assignment of a variable array.

Check whether one of the argument arrays is completely assigned and udpates the other array respectively.

Definition at line 298 of file sortsup.icc.