Gecode::Int::GCC::VarValGraph< View, Card, isView > Class Template Reference
Detailed Description
template<class View, class Card, bool isView>
class Gecode::Int::GCC::VarValGraph< View, Card, isView >
Variable-value-graph used during propagation.
Definition at line 469 of file graphsup.icc.
Graph-interface | |
| bool | failed (void) const |
| Check whether propagation failed This is actually needed to cope with failures occuring in functions returing only a boolean value and not an ExecStatus. | |
| void | failed (bool b) |
| Set the failure flag of the graph. | |
| bool | min_require (Space *home) |
| Check whether minimum requirements shrink variable domains. | |
| bool | sync (void) |
| the edges connecting the variable and the value partition | |
| void | print_graph (void) |
| Print graph information for debugging. | |
| template<BC > | |
| void | print_matching (void) |
| Print matching information for debugging. | |
| void | print_match (void) |
| Gather matching information. | |
| void | print_edges (void) |
| Print edge information. | |
| void * | operator new (size_t t) |
| Allocate memory for the graph. | |
| void | operator delete (void *p) |
| Free the memory for the graph. | |
| template<BC > | |
| bool | narrow (Space *) |
| Remove all those edges from the graph that do not belong to any possible maximum matching on the graph. | |
| template<BC > | |
| bool | 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 (VVGNode *) |
| Test whether the current maximal matching on the graph can be augmented by an alternating path starting and ending with a free node. | |
| template<BC > | |
| void | dfs (VVGNode *, bool[], bool[], int[], Support::StaticStack< VVGNode * > &, Support::StaticStack< VVGNode * > &, int &) |
| Perform depth-first search on the graph. | |
Constructors and Destructors | |
| VarValGraph (ViewArray< View > &, ViewArray< View > &, ViewArray< Card > &, int, int, int) | |
| Constructor for the variable-value-graph. | |
| ~VarValGraph (void) | |
| Destructor. | |
Public Member Functions | |
| size_t | allocated (void) const |
Constructor & Destructor Documentation
| Gecode::Int::GCC::VarValGraph< View, Card, isView >::VarValGraph | ( | ViewArray< View > & | xref, | |
| ViewArray< View > & | yref, | |||
| ViewArray< Card > & | kref, | |||
| int | noe, | |||
| int | smin, | |||
| int | smax | |||
| ) | [inline] |
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 v, where 
val_idx[i] is the index of 
in 
. nov denotes the cardinality of the value partition in the graph, noe the number of edges in the graph, min_occ the sum over the minimal occurences of all values and max_occ the sum over the maximal occurences of all values.
Definition at line 1277 of file graphsup.icc.
| Gecode::Int::GCC::VarValGraph< View, Card, isView >::~VarValGraph | ( | void | ) | [inline] |
Member Function Documentation
| size_t Gecode::Int::GCC::VarValGraph< View, Card, isView >::allocated | ( | void | ) | const [inline] |
Definition at line 1386 of file graphsup.icc.
| bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::failed | ( | void | ) | const [inline] |
Check whether propagation failed This is actually needed to cope with failures occuring in functions returing only a boolean value and not an ExecStatus.
Definition at line 1392 of file graphsup.icc.
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::failed | ( | bool | b | ) | [inline] |
| bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::min_require | ( | Space * | home | ) | [inline] |
Check whether minimum requirements shrink variable domains.
Definition at line 1406 of file graphsup.icc.
| bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::sync | ( | void | ) | [inline] |
the edges connecting the variable and the value partition
Synchronization of the graph.
If the graph has already been constructed and some edges have been removed during propagation that do not longer belong to the graph associated with the current variable domains.
Definition at line 1498 of file graphsup.icc.
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_graph | ( | void | ) | [inline] |
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_matching | ( | void | ) | [inline] |
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_match | ( | void | ) | [inline] |
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_edges | ( | void | ) | [inline] |
| void * Gecode::Int::GCC::VarValGraph< View, Card, isView >::operator new | ( | size_t | t | ) | [inline] |
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::operator delete | ( | void * | p | ) | [inline] |
| bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::narrow | ( | Space * | home | ) | [inline] |
Remove all those edges from the graph that do not belong to any possible maximum matching on the graph.
Definition at line 1719 of file graphsup.icc.
| bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::maximum_matching | ( | void | ) | [inline] |
Compute a maximum matching M on the graph.
- If BC=UBC then
- If BC=LBC then
![$|M|= \sum_{i\in \{ 0, \dots, |X|-1\}} k[i].min()$](form_150.png)
Definition at line 1867 of file graphsup.icc.
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::free_alternating_paths | ( | void | ) | [inline] |
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::strongly_connected_components | ( | void | ) | [inline] |
Compute possible strongly connected components of the graph.
Definition at line 2237 of file graphsup.icc.
| bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::augmenting_path | ( | VVGNode * | v | ) | [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 1940 of file graphsup.icc.
| void Gecode::Int::GCC::VarValGraph< View, Card, isView >::dfs | ( | VVGNode * | v, | |
| bool | inscc[], | |||
| bool | in_unfinished[], | |||
| int | dfsnum[], | |||
| Support::StaticStack< VVGNode * > & | roots, | |||
| Support::StaticStack< VVGNode * > & | unfinished, | |||
| int & | count | |||
| ) | [inline, protected] |
Perform depth-first search on the graph.
Depth first search used to compute the strongly connected components of the graph.
Definition at line 2159 of file graphsup.icc.
The documentation for this class was generated from the following file:
- gecode/int/gcc/graphsup.icc (Revision: 6323)