Generated on Fri Oct 19 11:26:06 2018 for Gecode by doxygen 1.6.3

Gecode::Int::BinPacking::ConflictGraph Class Reference

Graph containing conflict information. More...

#include <bin-packing.hh>

List of all members.

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 (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.

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.

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

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.

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

Destructor.

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


Member Function Documentation

int Gecode::Int::BinPacking::ConflictGraph::nodes ( void   )  const [inline, protected]

Return number of nodes.

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

int Gecode::Int::BinPacking::ConflictGraph::pivot ( const NodeSet a,
const NodeSet b 
) const [inline, protected]

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

Definition at line 175 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 38 of file conflict-graph.cpp.

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( void   )  [inline, protected]

Report the current clique.

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

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( int  i  )  [inline, protected]

Found a clique of node i.

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

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( int  i,
int  j 
) [inline, protected]

Found a clique of nodes i and j.

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

ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique ( int  i,
int  j,
int  k 
) [inline, protected]

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

Definition at line 240 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 156 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 169 of file conflict-graph.hpp.

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

Post additional constraints.

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

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 space.

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

Bin variables.

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

Number of bins.

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

The nodes in the graph.

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

Current clique.

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

Largest clique so far.

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


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