Generated on Thu Apr 11 14:00:02 2019 for Gecode by doxygen 1.6.3

Gecode::Int::GCC::VarValGraph< Card > Class Template Reference

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

#include <dom-sup.hpp>

List of all members.

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 (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.
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 387 of file dom-sup.hpp.


Constructor & Destructor Documentation

template<class Card >
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 1004 of file dom-sup.hpp.


Member Function Documentation

template<class Card >
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 1078 of file dom-sup.hpp.

template<class Card >
ExecStatus Gecode::Int::GCC::VarValGraph< Card >::sync ( 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 1237 of file dom-sup.hpp.

template<class Card >
template<BC bc>
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 1417 of file dom-sup.hpp.

template<class Card >
template<BC bc>
ExecStatus Gecode::Int::GCC::VarValGraph< Card >::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 1511 of file dom-sup.hpp.

template<class Card >
template<BC bc>
void Gecode::Int::GCC::VarValGraph< Card >::free_alternating_paths ( void   )  [inline]

Compute possible free alternating paths in the graph.

Definition at line 1575 of file dom-sup.hpp.

template<class Card >
template<BC bc>
void Gecode::Int::GCC::VarValGraph< Card >::strongly_connected_components ( void   )  [inline]

Compute possible strongly connected components of the graph.

Definition at line 1745 of file dom-sup.hpp.

template<class Card >
template<BC bc>
bool Gecode::Int::GCC::VarValGraph< Card >::augmenting_path ( 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 1144 of file dom-sup.hpp.

template<class Card >
template<BC bc>
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 1681 of file dom-sup.hpp.

template<class Card >
void * Gecode::Int::GCC::VarValGraph< Card >::operator new ( size_t  t,
Space home 
) [inline]

Allocate memory for the graph.

Definition at line 1765 of file dom-sup.hpp.

template<class Card >
void Gecode::Int::GCC::VarValGraph< Card >::operator delete ( void *  ,
Space  
) [inline]

Deallocation (void).

Definition at line 497 of file dom-sup.hpp.


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