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

Graph containing conflict information. More...

`#include <bin-packing.hh>`

## Classes

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

## Protected Member Functions

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

## Protected Attributes

Home & | home
| Home space.
const IntVarArgs & | b
| Bin variables.
unsigned int | bins
| Number of bins.
Node * | node
| 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

inline protected

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

inline protected

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 |  | ) |

inline protected

Report the current clique.

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

## clique() [2/4]

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.

## clique() [3/4]

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.

## clique() [4/4]

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.

## 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:

- gecode/int/bin-packing.hh
- gecode/int/bin-packing/conflict-graph.cpp
- gecode/int/bin-packing/conflict-graph.hpp