Gecode::Int::GCC::VarValGraph< Card > Class Template Reference
Variable-value-graph used during propagation. More...
#include <dom-sup.hpp>
Public Member Functions | |
| void * | operator new (size_t t, Space &home) |
| Allocate memory for the graph. | |
| void | operator delete (void *, Space &) |
| Deallocation (void). | |
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 (Space &home, 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 (Space &home) |
| Compute a maximum matching M on the graph. | |
| template<BC > | |
| void | free_alternating_paths (Space &home) |
| Compute possible free alternating paths in the graph. | |
| template<BC > | |
| void | strongly_connected_components (Space &home) |
| Compute possible strongly connected components of the graph. | |
| template<BC > | |
| bool | augmenting_path (Space &home, Node *) |
| 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 (Node *, BitSet &, BitSet &, int[], NodeStack &, NodeStack &, int &) |
| Perform depth-first search on the graph. | |
Detailed Description
template<class Card>
class Gecode::Int::GCC::VarValGraph< Card >
Variable-value-graph used during propagation.
Definition at line 391 of file dom-sup.hpp.
Constructor & Destructor Documentation
| Gecode::Int::GCC::VarValGraph< Card >::VarValGraph | ( | Space & | home, | |
| ViewArray< IntView > & | x, | |||
| ViewArray< Card > & | k, | |||
| 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 k.
Definition at line 1009 of file dom-sup.hpp.
Member Function Documentation
| ExecStatus Gecode::Int::GCC::VarValGraph< Card >::min_require | ( | Space & | home, | |
| ViewArray< IntView > & | x, | |||
| ViewArray< Card > & | k | |||
| ) | [inline] |
Check whether minimum requirements shrink variable domains.
Definition at line 1083 of file dom-sup.hpp.
| ExecStatus Gecode::Int::GCC::VarValGraph< Card >::sync | ( | Space & | home, | |
| ViewArray< IntView > & | x, | |||
| ViewArray< Card > & | k | |||
| ) | [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 1149 of file dom-sup.hpp.
| ExecStatus Gecode::Int::GCC::VarValGraph< Card >::narrow | ( | Space & | home, | |
| ViewArray< IntView > & | x, | |||
| ViewArray< Card > & | k | |||
| ) | [inline] |
Remove edges that do not belong to any maximal matching.
Definition at line 1331 of file dom-sup.hpp.
| ExecStatus Gecode::Int::GCC::VarValGraph< Card >::maximum_matching | ( | Space & | home | ) | [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_100.png)
Definition at line 1515 of file dom-sup.hpp.
| void Gecode::Int::GCC::VarValGraph< Card >::free_alternating_paths | ( | Space & | home | ) | [inline] |
Compute possible free alternating paths in the graph.
Definition at line 1579 of file dom-sup.hpp.
| void Gecode::Int::GCC::VarValGraph< Card >::strongly_connected_components | ( | Space & | home | ) | [inline] |
Compute possible strongly connected components of the graph.
Definition at line 1749 of file dom-sup.hpp.
| bool Gecode::Int::GCC::VarValGraph< Card >::augmenting_path | ( | Space & | home, | |
| Node * | 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 1423 of file dom-sup.hpp.
| void Gecode::Int::GCC::VarValGraph< Card >::dfs | ( | Node * | v, | |
| BitSet & | inscc, | |||
| BitSet & | in_unfinished, | |||
| int | dfsnum[], | |||
| NodeStack & | roots, | |||
| NodeStack & | 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 1685 of file dom-sup.hpp.
| void * Gecode::Int::GCC::VarValGraph< Card >::operator new | ( | size_t | t, | |
| Space & | home | |||
| ) | [inline] |
Allocate memory for the graph.
Definition at line 1769 of file dom-sup.hpp.
| void Gecode::Int::GCC::VarValGraph< Card >::operator delete | ( | void * | , | |
| Space & | ||||
| ) | [inline] |
Deallocation (void).
Definition at line 502 of file dom-sup.hpp.
The documentation for this class was generated from the following file:
- gecode/int/gcc/dom-sup.hpp (Revision: 12384)