Generated on Wed Jan 4 17:49:21 2006 for Gecode by doxygen 1.4.6

Gecode::Int::GCC::VarValGraph< View, Card, isView > Class Template Reference

List of all members.

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 444 of file graphsup.icc.

Constructors and Destructors

 VarValGraph (ViewArray< View > &, ViewArray< View > &, Card &, int, int, int)
 Constructor for the variable-value-graph.
 ~VarValGraph (void)
 Destructor.

Graph-interface

bool failed (void)
 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)
 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 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 *)
 Narrow the variable domains 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 &)
 DFS on the graph.


Constructor & Destructor Documentation

template<class View, class Card, bool isView>
Gecode::Int::GCC::VarValGraph< View, Card, isView >::VarValGraph ViewArray< View > &  xref,
ViewArray< View > &  yref,
Card &  kref,
int  noe,
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 v, where $ \forall v_i\in V: val_idx[i] is the index of v_i in k $. 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 1230 of file graphsup.icc.

template<class View, class Card, bool isView>
Gecode::Int::GCC::VarValGraph< View, Card, isView >::~VarValGraph void   )  [inline]
 

Destructor.

Definition at line 2367 of file graphsup.icc.


Member Function Documentation

template<class View, class Card, bool isView>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::failed void   )  [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 1337 of file graphsup.icc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::failed bool  b  )  [inline]
 

Set the failure flag of the graph.

Definition at line 1343 of file graphsup.icc.

template<class View, class Card, bool isView>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::min_require Space home  )  [inline]
 

Check whether minimum requirements shrink variable domains.

Definition at line 1349 of file graphsup.icc.

template<class View, class Card, bool isView>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::sync void   )  [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 1406 of file graphsup.icc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_graph void   )  [inline]
 

Print graph information for debugging.

Definition at line 2314 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_matching void   )  [inline]
 

Print matching information for debugging.

Definition at line 2279 of file graphsup.icc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_match void   )  [inline]
 

Gather matching information.

Definition at line 2253 of file graphsup.icc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::print_edges void   )  [inline]
 

Print edge information.

Definition at line 2261 of file graphsup.icc.

template<class View, class Card, bool isView>
void * Gecode::Int::GCC::VarValGraph< View, Card, isView >::operator new size_t  t  )  [inline]
 

Allocate memory for the graph.

Definition at line 2373 of file graphsup.icc.

template<class View, class Card, bool isView>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::operator delete void *  p  )  [inline]
 

Free the memory for the graph.

Definition at line 2379 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::narrow Space  )  [inline]
 

Narrow the variable domains Remove all those edges from the graph that do not belong to any possible maximum matching on the graph.

Definition at line 1747 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::maximum_matching void   )  [inline]
 

Compute a maximum matching M on the graph.

If BC=UBC then $|M|= |X|$ If BC=LBC then $|M|= \sum_{i\in \{ 0, \dots, |X|-1\}} k[i].min()$

Definition at line 1867 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::free_alternating_paths void   )  [inline]
 

Compute possible free alternating paths in the graph.

Definition at line 2049 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::strongly_connected_components void   )  [inline]
 

Compute possible strongly connected components of the graph.

Definition at line 2228 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::augmenting_path VVGNode  )  [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 1939 of file graphsup.icc.

template<class View, class Card, bool isView>
template<BC direction>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::dfs VVGNode ,
bool  [],
bool  [],
int  [],
Support::StaticStack< VVGNode * > &  ,
Support::StaticStack< VVGNode * > &  ,
int & 
[inline, protected]
 

DFS on the graph.

Depth first search used to compute the strongly connected components of the graph.

Definition at line 2150 of file graphsup.icc.


The documentation for this class was generated from the following file: