Gecode::Int::Sorted Namespace Reference

Sorted propagators More...

## Classes

class | Sorted
| Bounds consistent sortedness propagator. More...
class | Rank
| Storage class for mininmum and maximum of a variable. More...
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 | TupleMaxIncExt
| Extended Index comparison for ViewArray<Tuple>. More...
class | TupleMinInc
| View comparison on ViewTuples. More...
class | ViewPair
| Pair of views. More...
class | TupleMinIncExt
| Extended view comparison on pairs of views. More...

## Functions

template<class View>
bool | glover (ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
| Glover's maximum matching in a bipartite graph.
template<class View>
bool | revglover (ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
| Symmetric glover function for the upper domain bounds.
template<class View>
void | computesccs (ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
| Compute the sccs of the oriented intersection-graph.
template<class View, bool Perm>
bool | narrow_domx (Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, int tau[], int[], int scclist[], SccComponent sinfo[], bool &nofix)
| Narrowing the domains of the x variables.
template<class View>
bool | narrow_domy (Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
| Narrowing the domains of the y views.
template<class View, bool Perm>
void | sort_sigma (ViewArray< View > &x, ViewArray< View > &z)
| Build .
template<class View, bool Perm>
void | sort_tau (ViewArray< View > &x, ViewArray< View > &z, int tau[])
| Build .
template<class View>
bool | normalize (Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
| Performing normalization on the views in y.
template<class View>
bool | perm_bc (Space &home, int tau[], SccComponent sinfo[], int scclist[], ViewArray< View > &x, ViewArray< View > &z, bool &crossingedge, bool &nofix)
| Bounds consistency on the permutation views.
template<class View, bool Perm>
ExecStatus | bounds_propagation (Space &home, Propagator &p, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &repairpass, bool &nofix, bool &match_fixed)
| Perform bounds consistent sortedness propagation.
template<class View, bool Perm>
bool | check_subsumption (ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, int &dropfst)
| Subsumption test.
template<class View, bool Perm>
bool | array_assigned (Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &subsumed, bool &match_fixed, bool &, bool &noperm_bc)
| Check for assignment of a variable array.
template<class View>
bool | channel (Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
| Channel between x, y and z.

## Detailed Description

Sorted propagators

## Function Documentation

## glover()

template<class View>

bool Gecode::Int::Sorted::glover | ( | ViewArray< View > & | x,
|  | 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 , s.t. the upper domain bounds are sorted where is the top element

Definition at line 55 of file matching.hpp.

## revglover()

template<class View>

bool Gecode::Int::Sorted::revglover | ( | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | int | tau[],
|  | int | phiprime[],
|  | OfflineMinItem | sequence[],
|  | int | vertices[] )

inline

Symmetric glover function for the upper domain bounds.

Definition at line 114 of file matching.hpp.

## computesccs()

template<class View>

void Gecode::Int::Sorted::computesccs | ( | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | int | phi[],
|  | SccComponent | sinfo[],
|  | int | scclist[] )

inline

Compute the sccs of the oriented intersection-graph.

An y-node and its corresponding matching mate form the smallest possible scc, since both edges and are both contained in the oriented intersection graph.

Hence a scc containg more than two nodes is represented as an array of SccComponent entries, .

Parameters scclist ~ resulting sccs

Definition at line 54 of file narrowing.hpp.

## narrow_domx()

template<class View, bool Perm>

bool Gecode::Int::Sorted::narrow_domx | ( | Space & | home,
|  | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | ViewArray< View > & | z,
|  | int | tau[],
|  | int | [],
|  | 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 sorted constraint the new domain bounds for views in x are computed as

- lower bounds: where is the leftmost neighbour of
- upper bounds: where is the rightmost neighbour of

Definition at line 130 of file narrowing.hpp.

## narrow_domy()

template<class View>

bool Gecode::Int::Sorted::narrow_domy | ( | Space & | home,
|  | ViewArray< View > & | x,
|  | 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 computed in glover and compute the new upper bound by
- for the lower bounds the matching computed in revglover and update the new lower bound by

Definition at line 222 of file narrowing.hpp.

## sort_sigma()

template<class View, bool Perm>

void Gecode::Int::Sorted::sort_sigma | ( | ViewArray< View > & | x,
|  | ViewArray< View > & | z )

inline

Build .

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

Definition at line 45 of file order.hpp.

## sort_tau()

template<class View, bool Perm>

void Gecode::Int::Sorted::sort_tau | ( | ViewArray< View > & | x,
|  | ViewArray< View > & | z,
|  | int | tau[] )

inline

Build .

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

Definition at line 74 of file order.hpp.

## normalize()

template<class View>

bool Gecode::Int::Sorted::normalize | ( | Space & | home,
|  | ViewArray< View > & | y,
|  | ViewArray< View > & | x,
|  | bool & | nofix )

inline

Performing normalization on the views in y.

The views in y are called normalized if holds.

Definition at line 93 of file order.hpp.

## perm_bc()

template<class View>

bool Gecode::Int::Sorted::perm_bc | ( | Space & | home,
|  | int | tau[],
|  | SccComponent | sinfo[],
|  | int | scclist[],
|  | ViewArray< View > & | x,
|  | ViewArray< View > & | z,
|  | 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 140 of file order.hpp.

## bounds_propagation()

template<class View, bool Perm>

ExecStatus Gecode::Int::Sorted::bounds_propagation | ( | Space & | home,
|  | Propagator & | p,
|  | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | ViewArray< View > & | z,
|  | bool & | repairpass,
|  | bool & | nofix,
|  | bool & | match_fixed )

Perform bounds consistent sortedness propagation.

Implements the propagation algorithm for Sorted::Sorted 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 73 of file propagate.hpp.

## check_subsumption()

template<class View, bool Perm>

bool Gecode::Int::Sorted::check_subsumption | ( | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | ViewArray< View > & | z,
|  | bool & | subsumed,
|  | int & | dropfst )

inline

Subsumption test.

The propagator for sorted is subsumed if all variables of the ViewArrays x, y and z are determined and the constraint holds. 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 78 of file sortsup.hpp.

## array_assigned()

template<class View, bool Perm>

bool Gecode::Int::Sorted::array_assigned | ( | Space & | home,
|  | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | ViewArray< View > & | z,
|  | bool & | subsumed,
|  | bool & | match_fixed,
|  | bool & | ,
|  | bool & | noperm_bc )

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 378 of file sortsup.hpp.

## channel()

template<class View>

bool Gecode::Int::Sorted::channel | ( | Space & | home,
|  | ViewArray< View > & | x,
|  | ViewArray< View > & | y,
|  | ViewArray< View > & | z,
|  | bool & | nofix )

inline

Channel between x, y and z.

Keep variables consisting by channeling information

Definition at line 489 of file sortsup.hpp.