Programming search heuristics for graph problems.
[Modelling problems involving graph variables and]

Collaboration diagram for Programming search heuristics for graph problems.:


Detailed Description

UnaryGraphBranching, a class inheriting from Branching is provided with CP(Graph). This class allows to define search heuristics which perform a binary choice of inclusion or exclusion of a node or arc from a single graph view.

It uses a BoundsGraphs::branch method which can use graph algorithms to decide on which node or arc to choose. This branch method must return a BranchingDesc a description of the branching decision. Two classes are provided for implementing branching Description for the UnaryGraphBranching: GraphBDSingle and GraphBDMultiple. GraphBDSingle should be used if your search heuristic always chooses arcs or always chooses nodes to branch on. If the search tree interleaves choices about the nodes and choices about the arcs, then GraphBDMultiple should be used. See CPGraphSimplePathHeur and PathHeurBoundsG for examples.


Classes

class  Gecode::Graph::UnaryGraphBranching< GView, BoundsG, GraphBD >
 Graph Branching which selects a node or an arc to branch on, includes or excludes it. More...
struct  Gecode::Graph::GraphBDSingle< Type >
 Single-type Graph Branching descriptions. More...
struct  Gecode::Graph::GraphBDMultiple
 Multiple-type Graph Branching descriptions. More...
struct  PathHeurBoundsG< GView >
 GraphBounds class used for branching on a constrained path problem. More...

Functions

 Gecode::Graph::GraphBDSingle::GraphBDSingle (Branching *, Type, bool)
 Initialize decsription.
 Gecode::Graph::GraphBDMultiple::GraphBDMultiple (Branching *, int, bool)
 Initialize decsription with a node.
 Gecode::Graph::UnaryGraphBranching::UnaryGraphBranching (Space *home, GView &g)
 Constructor for creation.


Function Documentation

template<class Type>
Gecode::Graph::GraphBDSingle< Type >::GraphBDSingle Branching b,
Type  val,
bool  inc
[inline, inherited]
 

Initialize decsription.

Graph Branching descriptions storing an arc or node and wether it must be included or excluded

Definition at line 105 of file branch.icc.

Gecode::Graph::GraphBDMultiple::GraphBDMultiple Branching b,
int  node,
bool  inc
[inline, inherited]
 

Initialize decsription with a node.

Graph Branching descriptions storing an arc or node and wether it must be included or excluded first

Definition at line 144 of file branch.icc.

template<class GView, class BoundsG, class GraphBD>
Gecode::Graph::UnaryGraphBranching< GView, BoundsG, GraphBD >::UnaryGraphBranching Space home,
GView &  g
[inline, inherited]
 

Constructor for creation.

Graph Branching which selects a node or an arc to branch on, includes or excludes it.

Definition at line 177 of file branch.icc.