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 ![]() | |
template<class View, class Tuple, bool Perm> | |
void | sort_tau (ViewArray< Tuple > &xz, int tau[]) |
Build ![]() | |
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
|
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 Definition at line 43 of file matching.icc. |
|
Symmetric glover function for the upper domain bounds.
Definition at line 113 of file matching.icc. |
|
Compute the sccs of the oriented intersection-graph.
An y-node
Hence a scc containg more than two nodes is represented as an array of SccComponent entries, Parameters scclist ~ resulting sccs Definition at line 64 of file narrowing.icc. |
|
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
Definition at line 143 of file narrowing.icc. |
|
Narrowing the domains of the y views. analogously to the x views we take
Definition at line 244 of file narrowing.icc. |
|
Build
Creates a sorting permutation |
|
Build
Creates a sorting permutation |
|
Performing normalization on the views in y.
The views in y are called normalized if |
|
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. |
|
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. |
|
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. Definition at line 39 of file sortsup.icc. |
|
Print an OfflineMin sequence.
Definition at line 223 of file sortsup.icc. |
|
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. |