Generated on Sat Feb 7 2015 02:01:45 for Gecode by doxygen 1.8.9.1
Gecode::Int::BinPacking::ConflictGraph Class Reference

Graph containing conflict information. More...

#include <bin-packing.hh>

Classes

class  Clique
 Clique information. More...
 
class  Node
 Class for node in graph. More...
 
class  Nodes
 Iterator over node sets. More...
 
class  NodeSet
 Sets of graph nodes. More...
 

Public Member Functions

 ConflictGraph (Space &home, Region &r, const IntVarArgs &b, int m)
 Initialize graph. More...
 
void edge (int i, int j, bool add=true)
 Add or remove an edge between nodes i and j (i must be less than j) More...
 
bool adjacent (int i, int j) const
 Test whether nodes i and j are adjacent. More...
 
ExecStatus post (void)
 Post additional constraints. More...
 
IntSet maxclique (void) const
 Return maximal clique found. More...
 
 ~ConflictGraph (void)
 Destructor. More...
 

Protected Member Functions

int nodes (void) const
 Return number of nodes. More...
 

Protected Attributes

Spacehome
 Home space. More...
 
const IntVarArgsb
 Bin variables. More...
 
unsigned int bins
 Number of bins. More...
 
Nodenode
 The nodes in the graph. More...
 

Routines for Bosch-Kerbron algorithm

int pivot (const NodeSet &a, const NodeSet &b) const
 Find a pivot node with maximal degree from a or b. More...
 
ExecStatus bk (NodeSet &p, NodeSet &x)
 Run Bosch-Kerbron algorithm for finding max cliques. More...
 

Managing cliques

Clique cur
 Current clique. More...
 
Clique max
 Largest clique so far. More...
 
ExecStatus clique (void)
 Report the current clique. More...
 
ExecStatus clique (int i)
 Found a clique of node i. More...
 
ExecStatus clique (int i, int j)
 Found a clique of nodes i and j. More...
 
ExecStatus clique (int i, int j, int k)
 Found a clique of nodes i, j, and k. More...
 

Detailed Description

Graph containing conflict information.

Definition at line 183 of file bin-packing.hh.

Constructor & Destructor Documentation

Gecode::Int::BinPacking::ConflictGraph::ConflictGraph ( Space home,
Region r,
const IntVarArgs b,
int  m 
)
inline

Initialize graph.

Definition at line 143 of file conflict-graph.hpp.

Gecode::Int::BinPacking::ConflictGraph::~ConflictGraph ( void  )
inline

Destructor.

Definition at line 156 of file conflict-graph.hpp.

Member Function Documentation

int Gecode::Int::BinPacking::ConflictGraph::nodes ( void  ) const
inlineprotected

Return number of nodes.

Definition at line 46 of file conflict-graph.hpp.

int Gecode::Int::BinPacking::ConflictGraph::pivot ( const NodeSet a,
const NodeSet b 
) const
inlineprotected

Find a pivot node with maximal degree from a or b.

Definition at line 179 of file conflict-graph.hpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::bk ( NodeSet p,
NodeSet x 
)
protected

Run Bosch-Kerbron algorithm for finding max cliques.

Definition at line 43 of file conflict-graph.cpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( void  )
inlineprotected

Report the current clique.

Definition at line 205 of file conflict-graph.hpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( int  i)
inlineprotected

Found a clique of node i.

Definition at line 222 of file conflict-graph.hpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( int  i,
int  j 
)
inlineprotected

Found a clique of nodes i and j.

Definition at line 231 of file conflict-graph.hpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( int  i,
int  j,
int  k 
)
inlineprotected

Found a clique of nodes i, j, and k.

Definition at line 244 of file conflict-graph.hpp.

void Gecode::Int::BinPacking::ConflictGraph::edge ( int  i,
int  j,
bool  add = true 
)
inline

Add or remove an edge between nodes i and j (i must be less than j)

Definition at line 160 of file conflict-graph.hpp.

bool Gecode::Int::BinPacking::ConflictGraph::adjacent ( int  i,
int  j 
) const
inline

Test whether nodes i and j are adjacent.

Definition at line 173 of file conflict-graph.hpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::post ( void  )
inline

Post additional constraints.

Definition at line 260 of file conflict-graph.hpp.

IntSet Gecode::Int::BinPacking::ConflictGraph::maxclique ( void  ) const
inline

Return maximal clique found.

Definition at line 333 of file conflict-graph.hpp.

Member Data Documentation

Space& Gecode::Int::BinPacking::ConflictGraph::home
protected

Home space.

Definition at line 186 of file bin-packing.hh.

const IntVarArgs& Gecode::Int::BinPacking::ConflictGraph::b
protected

Bin variables.

Definition at line 188 of file bin-packing.hh.

unsigned int Gecode::Int::BinPacking::ConflictGraph::bins
protected

Number of bins.

Definition at line 190 of file bin-packing.hh.

Node* Gecode::Int::BinPacking::ConflictGraph::node
protected

The nodes in the graph.

Definition at line 241 of file bin-packing.hh.

Clique Gecode::Int::BinPacking::ConflictGraph::cur
protected

Current clique.

Definition at line 295 of file bin-packing.hh.

Clique Gecode::Int::BinPacking::ConflictGraph::max
protected

Largest clique so far.

Definition at line 297 of file bin-packing.hh.


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