PBQP::HeuristicSolverImpl< HImpl > Class Template Reference

Heuristic PBQP solver implementation. More...

#include <HeuristicSolver.h>

Inheritance diagram for PBQP::HeuristicSolverImpl< HImpl >:

Public Types
typedef SolverEdges::iterator	SolverEdgeItr
	Iterator type for edges in the solver graph. More...

Public Member Functions
	HeuristicSolverImpl (Graph &g)
	Construct a heuristic solver implementation to solve the given graph. More...
Graph &	getGraph ()
	Get the graph being solved by this solver. More...
HeuristicNodeData &	getHeuristicNodeData (Graph::NodeId nId)
	Get the heuristic data attached to the given node. More...
HeuristicEdgeData &	getHeuristicEdgeData (Graph::EdgeId eId)
	Get the heuristic data attached to the given edge. More...
SolverEdgeItr	solverEdgesBegin (Graph::NodeId nId)
	Begin iterator for the set of edges adjacent to the given node in the solver graph. More...
SolverEdgeItr	solverEdgesEnd (Graph::NodeId nId)
	End iterator for the set of edges adjacent to the given node in the solver graph. More...
void	removeSolverEdge (Graph::EdgeId eId)
	Remove a node from the solver graph. More...
Solution	computeSolution ()
	Compute a solution to the PBQP problem instance with which this heuristic solver was constructed. More...
void	pushToStack (Graph::NodeId nId)
	Add to the end of the stack. More...
unsigned	getSolverDegree (Graph::NodeId nId)
	Returns the solver degree of the given node. More...
void	setSolution (const Graph::NodeId &nId, unsigned selection)
	Set the solution of the given node. More...
void	applyR0 (Graph::NodeId nId)
	Apply rule R0. More...
void	applyR1 (Graph::NodeId xnId)
	Apply rule R1. More...
void	applyR2 (Graph::NodeId xnId)
	Apply rule R2. More...
void	recordRN ()
	Record an application of the RN rule. More...

Detailed Description

template<typename HImpl>
class PBQP::HeuristicSolverImpl< HImpl >

Heuristic PBQP solver implementation.

This class should usually be created (and destroyed) indirectly via a call to HeuristicSolver<HImpl>::solve(Graph&). See the comments for HeuristicSolver.

HeuristicSolverImpl provides the R0, R1 and R2 reduction rules, backpropagation phase, and maintains the internal copy of the graph on which the reduction is carried out (the original being kept to facilitate backpropagation).

Definition at line 37 of file HeuristicSolver.h.

Member Typedef Documentation

template<typename HImpl>

typedef SolverEdges::iterator PBQP::HeuristicSolverImpl< HImpl >::SolverEdgeItr

Iterator type for edges in the solver graph.

Definition at line 48 of file HeuristicSolver.h.

Constructor & Destructor Documentation

template<typename HImpl>

PBQP::HeuristicSolverImpl< HImpl >::HeuristicSolverImpl ( Graph &  g )

inline

Construct a heuristic solver implementation to solve the given graph.

Parameters

g	The graph representing the problem instance to be solved.

Definition at line 120 of file HeuristicSolver.h.

Member Function Documentation

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::applyR0 ( Graph::NodeId  nId )

inline

Apply rule R0.

Parameters

nId	Node id for node to apply R0 to.

Node will be automatically pushed to the solver stack.

Definition at line 223 of file HeuristicSolver.h.

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::applyR1 ( Graph::NodeId  xnId )

inline

Apply rule R1.

Parameters

xnId	Node id for node to apply R1 to.

Node will be automatically pushed to the solver stack.

Definition at line 237 of file HeuristicSolver.h.

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::applyR2 ( Graph::NodeId  xnId )

inline

Apply rule R2.

Parameters

xnId	Node id for node to apply R2 to.

Node will be automatically pushed to the solver stack.

Definition at line 286 of file HeuristicSolver.h.

template<typename HImpl>

Solution PBQP::HeuristicSolverImpl< HImpl >::computeSolution ( )

inline

Compute a solution to the PBQP problem instance with which this heuristic solver was constructed.

Returns

A solution to the PBQP problem.

Performs the full PBQP heuristic solver algorithm, including setup, calls to the heuristic (which will call back to the reduction rules in this class), and cleanup.

Definition at line 180 of file HeuristicSolver.h.

Referenced by PBQP::HeuristicSolver< HImpl >::solve().

template<typename HImpl>

Graph& PBQP::HeuristicSolverImpl< HImpl >::getGraph ( )

inline

Get the graph being solved by this solver.

Returns

The graph representing the problem instance being solved by this solver.

Definition at line 125 of file HeuristicSolver.h.

template<typename HImpl>

HeuristicEdgeData& PBQP::HeuristicSolverImpl< HImpl >::getHeuristicEdgeData ( Graph::EdgeId  eId )

inline

Get the heuristic data attached to the given edge.

Parameters

eId

Edge id.

Returns

The heuristic data attached to the given node.

Definition at line 137 of file HeuristicSolver.h.

template<typename HImpl>

HeuristicNodeData& PBQP::HeuristicSolverImpl< HImpl >::getHeuristicNodeData ( Graph::NodeId  nId )

inline

Get the heuristic data attached to the given node.

Parameters

nId

Node id.

Returns

The heuristic data attached to the given node.

Definition at line 130 of file HeuristicSolver.h.

template<typename HImpl>

unsigned PBQP::HeuristicSolverImpl< HImpl >::getSolverDegree ( Graph::NodeId  nId )

inline

Returns the solver degree of the given node.

Parameters

nId	Node id for which degree is requested.

Returns

Node degree in the solver graph (not the original graph).

Definition at line 200 of file HeuristicSolver.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR0(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2().

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::pushToStack ( Graph::NodeId  nId )

inline

Add to the end of the stack.

Parameters

nId	Node id to add to the reduction stack.

Definition at line 192 of file HeuristicSolver.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR0(), PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR1(), PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2(), and PBQP::Heuristics::Briggs::heuristicReduce().

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::recordRN ( )

inline

Record an application of the RN rule.

For use by the HeuristicBase.

Definition at line 390 of file HeuristicSolver.h.

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::removeSolverEdge ( Graph::EdgeId  eId )

inline

Remove a node from the solver graph.

Parameters

eId	Edge id for edge to be removed.

Does not notify the heuristic of the removal. That should be done manually if necessary.

Definition at line 164 of file HeuristicSolver.h.

Referenced by PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR1(), and PBQP::HeuristicSolverImpl< PBQP::Heuristics::Briggs >::applyR2().

template<typename HImpl>

void PBQP::HeuristicSolverImpl< HImpl >::setSolution ( const Graph::NodeId &  nId, unsigned  selection  )

inline

Set the solution of the given node.

Parameters

nId	Node id to set solution for.
selection	Selection for node.

Definition at line 207 of file HeuristicSolver.h.

template<typename HImpl>

SolverEdgeItr PBQP::HeuristicSolverImpl< HImpl >::solverEdgesBegin ( Graph::NodeId  nId )

inline

Begin iterator for the set of edges adjacent to the given node in the solver graph.

Parameters

nId

Node id.

Returns

Begin iterator for the set of edges adjacent to the given node in the solver graph.

Definition at line 146 of file HeuristicSolver.h.

template<typename HImpl>

SolverEdgeItr PBQP::HeuristicSolverImpl< HImpl >::solverEdgesEnd ( Graph::NodeId  nId )

inline

End iterator for the set of edges adjacent to the given node in the solver graph.

Parameters

nId

Node id.

Returns

End iterator for the set of edges adjacent to the given node in the solver graph.

Definition at line 155 of file HeuristicSolver.h.

---

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

• HeuristicSolver.h