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. | |
| 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 | |
| Space & | 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 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 [inline, protected] |
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 [inline, protected] |
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 42 of file conflict-graph.cpp.
| ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique | ( | void | ) | [inline, protected] |
Report the current clique.
Definition at line 205 of file conflict-graph.hpp.
| ExecStatus Gecode::Int::BinPacking::ConflictGraph::clique | ( | int | i | ) | [inline, protected] |
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 | |||
| ) | [inline, protected] |
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 | |||
| ) | [inline, protected] |
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:
- gecode/int/bin-packing.hh (Revision: 14203)
- gecode/int/bin-packing/conflict-graph.cpp (Revision: 14203)
- gecode/int/bin-packing/conflict-graph.hpp (Revision: 14471)