PermutationStrategy Class Reference

Node-elimination ordering strategy using a priority queue. More...

#include "PermutationStrategy.h"

Classes
struct	node_type
	Entry in the priority queue. More...

Public Member Functions
void	init_permutation (Graph &graph)
	Populate the priority queue with all nodes in graph.
unsigned long	emptyQ ()
	Pop and discard the top node, returning the new queue size.
virtual void	recompute (const std::unordered_set< unsigned long > &nodes, Graph &graph)
	Recompute statistics for a subset of nodes and update the queue.
unsigned long	get_next ()
	Pop and return the node with the smallest statistic.
unsigned long	get_next_wo_delete ()
	Peek at the node with the smallest statistic (without removing it).
unsigned long	get_second_next_delete ()
	Pop the top node, then pop and return the new top node.
unsigned long	get_second_next ()
	Peek at the node with the second-smallest statistic (no removal).
unsigned long	Q_siz ()
	Return the current number of nodes in the queue.
bool	empty_but1 ()
	Return true if the queue contains exactly one node.
bool	empty ()
	Return true if the queue is empty.

Protected Member Functions
unsigned long	compute_statistic (unsigned long node, Graph &graph)
	Compute the priority statistic for node in graph.

Protected Attributes
boost::heap::fibonacci_heap< node_type >	queue
	The priority queue holding all not-yet-eliminated nodes.
std::unordered_map< unsigned long, boost::heap::fibonacci_heap< node_type >::handle_type >	queue_nodes
	Maps node IDs to their heap handles for O(1) key updates.

Detailed Description

Node-elimination ordering strategy using a priority queue.

Maintains a Fibonacci heap of nodes prioritised by a user-defined statistic. The main consumer is TreeDecomposition, which calls init_permutation() once and then repeatedly calls get_next() to obtain the next node to eliminate.

Definition at line 38 of file PermutationStrategy.h.

Member Function Documentation

compute_statistic()

unsigned long PermutationStrategy::compute_statistic ( unsigned long  node, Graph &  graph  )

inlineprotected

Compute the priority statistic for node in graph.

The default implementation returns the degree (number of neighbours) of the node. Override in subclasses to implement other heuristics.

Parameters

node	Node whose statistic is needed.
graph	Current graph state.

Returns

Non-negative statistic value (smaller ⇒ eliminate sooner).

Definition at line 196 of file PermutationStrategy.h.

Here is the call graph for this function:

Here is the caller graph for this function:

empty()

bool PermutationStrategy::empty ( )

inline

Return true if the queue is empty.

Returns

true iff no nodes remain.

Definition at line 183 of file PermutationStrategy.h.

Here is the caller graph for this function:

empty_but1()

bool PermutationStrategy::empty_but1 ( )

inline

Return true if the queue contains exactly one node.

Returns

true iff exactly one node remains.

Definition at line 178 of file PermutationStrategy.h.

emptyQ()

unsigned long PermutationStrategy::emptyQ ( )

inline

Pop and discard the top node, returning the new queue size.

Returns

Number of remaining nodes after the pop.

Definition at line 86 of file PermutationStrategy.h.

get_next()

unsigned long PermutationStrategy::get_next ( )

inline

Pop and return the node with the smallest statistic.

Returns

ID of the eliminated node.

Definition at line 116 of file PermutationStrategy.h.

Here is the caller graph for this function:

get_next_wo_delete()

unsigned long PermutationStrategy::get_next_wo_delete ( )

inline

Peek at the node with the smallest statistic (without removing it).

Returns

ID of the top node.

Definition at line 128 of file PermutationStrategy.h.

get_second_next()

unsigned long PermutationStrategy::get_second_next ( )

inline

Peek at the node with the second-smallest statistic (no removal).

Temporarily pops the top, peeks at the new top, then re-inserts.

Returns

ID of the second-smallest node.

Definition at line 160 of file PermutationStrategy.h.

get_second_next_delete()

unsigned long PermutationStrategy::get_second_next_delete ( )

inline

Pop the top node, then pop and return the new top node.

The first (smallest) node is temporarily removed, the second-smallest is popped and returned, and the first is re-inserted.

Returns

ID of the second-smallest node.

Definition at line 142 of file PermutationStrategy.h.

init_permutation()

void PermutationStrategy::init_permutation ( Graph &  graph )

inline

Populate the priority queue with all nodes in graph.

Must be called once before any calls to get_next().

Parameters

graph

The graph whose nodes should be enqueued.

Definition at line 72 of file PermutationStrategy.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Q_siz()

unsigned long PermutationStrategy::Q_siz ( )

inline

Return the current number of nodes in the queue.

Returns

Number of nodes remaining in the priority queue.

Definition at line 173 of file PermutationStrategy.h.

recompute()

virtual void PermutationStrategy::recompute ( const std::unordered_set< unsigned long > &  nodes, Graph &  graph  )

inlinevirtual

Recompute statistics for a subset of nodes and update the queue.

Called after a node is eliminated to refresh the priorities of its former neighbours.

Parameters

nodes	Set of node IDs whose statistics need updating.
graph	The current (modified) graph.

Definition at line 103 of file PermutationStrategy.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

queue

boost::heap::fibonacci_heap<node_type> PermutationStrategy::queue

protected

The priority queue holding all not-yet-eliminated nodes.

Definition at line 59 of file PermutationStrategy.h.

queue_nodes

std::unordered_map<unsigned long, boost::heap::fibonacci_heap<node_type>::handle_type> PermutationStrategy::queue_nodes

protected

Maps node IDs to their heap handles for O(1) key updates.

Definition at line 62 of file PermutationStrategy.h.

---

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

• /home/pierre/git/software/provsql/src/PermutationStrategy.h