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 (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 | |
| 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. | |
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& Gecode::Int::BinPacking::ConflictGraph::home [protected] |
Home space.
Definition at line 185 of file bin-packing.hh.
const IntVarArgs& Gecode::Int::BinPacking::ConflictGraph::b [protected] |
Bin variables.
Definition at line 187 of file bin-packing.hh.
unsigned int Gecode::Int::BinPacking::ConflictGraph::bins [protected] |
Number of bins.
Definition at line 189 of file bin-packing.hh.
Node* Gecode::Int::BinPacking::ConflictGraph::node [protected] |
The nodes in the graph.
Definition at line 240 of file bin-packing.hh.
Clique Gecode::Int::BinPacking::ConflictGraph::cur [protected] |
Current clique.
Definition at line 294 of file bin-packing.hh.
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