Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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...
 

Protected Member Functions

int nodes (void) const
 Return number of nodes.
 

Protected Attributes

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

Managing cliques

Clique cur
 Current clique.
 
Clique max
 Largest clique so far.
 
ExecStatus clique (void)
 Report the current clique.
 
ExecStatus clique (int i)
 Found a clique of node i.
 
ExecStatus clique (int i, int j)
 Found a clique of nodes i and j.
 
ExecStatus clique (int i, int j, int k)
 Found a clique of nodes i, j, and k.
 
 ConflictGraph (Home &home, Region &r, const IntVarArgs &b, int m)
 Initialize graph.
 
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)
 
bool adjacent (int i, int j) const
 Test whether nodes i and j are adjacent.
 
ExecStatus post (void)
 Post additional constraints.
 
IntSet maxclique (void) const
 Return maximal clique found.
 
 ~ConflictGraph (void)
 Destructor.
 

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.
 
ExecStatus bk (NodeSet &p, NodeSet &x)
 Run Bosch-Kerbron algorithm for finding max cliques.
 

Detailed Description

Graph containing conflict information.

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

Constructor & Destructor Documentation

◆ ConflictGraph()

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

Initialize graph.

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

◆ ~ConflictGraph()

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

Destructor.

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

Member Function Documentation

◆ nodes()

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

Return number of nodes.

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

◆ pivot()

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 175 of file conflict-graph.hpp.

◆ bk()

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

Run Bosch-Kerbron algorithm for finding max cliques.

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

◆ clique() [1/4]

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

Report the current clique.

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

◆ clique() [2/4]

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

Found a clique of node i.

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

◆ clique() [3/4]

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

Found a clique of nodes i and j.

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

◆ clique() [4/4]

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 240 of file conflict-graph.hpp.

◆ edge()

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 156 of file conflict-graph.hpp.

◆ adjacent()

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

Test whether nodes i and j are adjacent.

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

◆ post()

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

Post additional constraints.

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

◆ maxclique()

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

Return maximal clique found.

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

Member Data Documentation

◆ home

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

Home space.

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

◆ b

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

Bin variables.

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

◆ bins

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

Number of bins.

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

◆ node

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

The nodes in the graph.

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

◆ cur

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

Current clique.

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

◆ max

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

Largest clique so far.

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


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