Variable-value-graph used during propagation. More...
#include <dom-sup.hpp>
Constructors and Destructors | |
VarValGraph (Space &home, ViewArray< IntView > &x, ViewArray< Card > &k, int smin, int smax) | |
Constructor for the variable-value-graph. | |
Graph-interface | |
ExecStatus | min_require (Space &home, ViewArray< IntView > &x, ViewArray< Card > &k) |
Check whether minimum requirements shrink variable domains. | |
ExecStatus | sync (ViewArray< IntView > &x, ViewArray< Card > &k) |
Synchronization of the graph. | |
template<BC > | |
ExecStatus | narrow (Space &home, ViewArray< IntView > &x, ViewArray< Card > &k) |
Remove edges that do not belong to any maximal matching. | |
template<BC > | |
ExecStatus | maximum_matching (void) |
Compute a maximum matching M on the graph. | |
template<BC > | |
void | free_alternating_paths (void) |
Compute possible free alternating paths in the graph. | |
template<BC > | |
void | strongly_connected_components (void) |
Compute possible strongly connected components of the graph. | |
template<BC > | |
bool | augmenting_path (Node *) |
Test whether the current maximal matching on the graph can be augmented by an alternating path starting and ending with a free node. | |
void * | operator new (size_t t, Space &home) |
Allocate memory for the graph. | |
void | operator delete (void *, Space &) |
Deallocation (void) | |
template<BC > | |
void | dfs (Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &) |
Perform depth-first search on the graph. | |
Variable-value-graph used during propagation.
Definition at line 387 of file dom-sup.hpp.
Gecode::Int::GCC::VarValGraph< Card >::VarValGraph | ( | Space & | home, |
ViewArray< IntView > & | x, | ||
ViewArray< Card > & | k, | ||
int | smin, | ||
int | smax ) |
Constructor for the variable-value-graph.
The variable parition is initialized with the variables from x, the value partition is initialized with the values from k.
Definition at line 1004 of file dom-sup.hpp.
|
inline |
Check whether minimum requirements shrink variable domains.
Definition at line 1078 of file dom-sup.hpp.
|
inline |
Synchronization of the graph.
If the graph has already been constructed and some edges have been removed during propagation, this function removes those edges that do not longer belong to the graph associated with the current variable domains.
Definition at line 1237 of file dom-sup.hpp.
|
inline |
Remove edges that do not belong to any maximal matching.
Definition at line 1417 of file dom-sup.hpp.
|
inline |
Compute a maximum matching M on the graph.
Definition at line 1511 of file dom-sup.hpp.
|
inline |
Compute possible free alternating paths in the graph.
Definition at line 1575 of file dom-sup.hpp.
|
inline |
Compute possible strongly connected components of the graph.
Definition at line 1745 of file dom-sup.hpp.
|
inline |
Test whether the current maximal matching on the graph can be augmented by an alternating path starting and ending with a free node.
Definition at line 1144 of file dom-sup.hpp.
|
protected |
Perform depth-first search on the graph.
Depth first search used to compute the strongly connected components of the graph.
Definition at line 1681 of file dom-sup.hpp.
|
inline |
Allocate memory for the graph.
Definition at line 1765 of file dom-sup.hpp.
|
inline |
Deallocation (void)
Definition at line 497 of file dom-sup.hpp.