Generated on Mon Jul 6 18:09:34 2009 for Gecode by doxygen 1.5.9
Gecode::Int::GCC::VarValGraph

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

Variable-value-graph used during propagation. More...

#include <graphsup.hpp>

List of all members.

Public Member Functions

size_t allocated (void) const

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 (Space &home)
 the edges connecting the variable and the value partition
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 &home)
 Remove all those edges from the graph that do not belong to any possible maximum matching on the graph.
template<BC >
bool 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, 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 *, Region > &, Support::StaticStack< VVGNode *, Region > &, 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.

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 443 of file graphsup.hpp.

Constructor & Destructor Documentation

template<class View , class Card , bool isView>
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 $ \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 1224 of file graphsup.hpp.

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

Destructor.

Definition at line 2214 of file graphsup.hpp.

Member Function Documentation

template<class View , class Card , bool isView>
size_t Gecode::Int::GCC::VarValGraph< View, Card, isView >::allocated ( void   )  const [inline]

Definition at line 1333 of file graphsup.hpp.

template<class View , class Card , bool isView>
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 1339 of file graphsup.hpp.

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 1345 of file graphsup.hpp.

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 1353 of file graphsup.hpp.

template<class View , class Card , bool isView>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::sync ( Space &  home  )  [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 1445 of file graphsup.hpp.

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 2220 of file graphsup.hpp.

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 2226 of file graphsup.hpp.

template<class View , class Card , bool isView>
template<BC direction>
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 1667 of file graphsup.hpp.

template<class View , class Card , bool isView>
template<BC direction>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::maximum_matching ( Space &  home  )  [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 1823 of file graphsup.hpp.

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

Compute possible free alternating paths in the graph.

Definition at line 2005 of file graphsup.hpp.

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

Compute possible strongly connected components of the graph.

Definition at line 2191 of file graphsup.hpp.

template<class View , class Card , bool isView>
template<BC direction>
bool Gecode::Int::GCC::VarValGraph< View, Card, isView >::augmenting_path ( Space &  home,
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 1897 of file graphsup.hpp.

template<class View , class Card , bool isView>
template<BC direction>
void Gecode::Int::GCC::VarValGraph< View, Card, isView >::dfs ( VVGNode *  v,
bool  inscc[],
bool  in_unfinished[],
int  dfsnum[],
Support::StaticStack< VVGNode *, Region > &  roots,
Support::StaticStack< VVGNode *, Region > &  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 2113 of file graphsup.hpp.

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