FibonacciHeap< State, Action > Class Template Reference

#include <FibonocciHeap.h>

Data Structures
struct	FibonacciNode

Public Types
typedef GenericStateGraph< State, Action >	StateGraph

Public Member Functions
	Fibonacci (StateGraph *_stateGraph)
void	fib_heap_insert (FibonacciNode *new_node, double key)
void	fib_heap_existing_to_root (FibonacciNode *new_node)
void	fib_heap_add_child (FibonacciNode *parent_node, FibonacciNode *new_child_node)
void	fib_heap_remove_node_from_root (FibonacciNode *node)
void	fib_heap_link (FibonacciNode *high_node, FibonacciNode *low_node)
void	fib_heap_consolidate ()
FibonacciNode *	fib_heap_extract_min ()
void	fib_heap_cut (FibonacciNode *node, FibonacciNode *node_parent)
void	fib_heap_cascading_cut (FibonacciNode *node)
void	fib_heap_decrease_key (FibonacciNode *node_inst, int new_key)
void	fib_heap_delete (FibonacciNode *node)
int	get_min_distant_unmarked_node (int *distance_to_dest, std::unordered_map< size_t, bool > marked)
int	get_min_distant_unmarked_node_fib_heap (std::unordered_map< size_t, FibonacciNode * > node_array, std::unordered_map< size_t, bool > marked)
void	dijkstra_fibanocci (int src)
bool	check_connected (graph *my_graph)

Member Typedef Documentation

StateGraph

template<typename State , typename Action >

typedef GenericStateGraph<State, Action> FibonacciHeap< State, Action >::StateGraph

Member Function Documentation

check_connected()

template<typename State , typename Action >

bool FibonacciHeap< State, Action >::check_connected

(

graph *

my_graph

)

This function runs the Depth-First-Search to find if the graph is completely connected.

This function runs the Depth-First-Search to find if the graph is completely connected. This function check if the graph is connected by running Depth-Frist-Search on the graph.

dijkstra_fibanocci()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::dijkstra_fibanocci

(

int

src

)

This function creates a graph with the number of vertices specified by the user. This function implements the Dijkstra algorithm using the routine array way for calculating the next minimum distant vertex from the source node. This function calculates the minimum distant node using the fibonacci heap. This function implements the Dijkstra algorithm using the fibonacci heap. Source vertex is specified by the user as input.

fib_heap_add_child()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_add_child	(	FibonacciNode *	parent_node,
		FibonacciNode *	new_child_node
	)

This function combines two fibonacci heaps. This function isn't required for Dijkstra implementation. This function adds the new_child_node to the parent_node child list. Degree of the parent in incremented by one as well to reflect to the node

fib_heap_cascading_cut()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_cascading_cut

(

FibonacciNode *

node

)

This recursive function removes the nodes from heap if the child mark values are true. It goes from child to parent until it sees a parent whose child mark value is false. It sets the child mark of last parent as true since it just lost a child.

fib_heap_consolidate()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_consolidate

(

)

This method is the crucial method for fibonacci heaps where all the actual time is spent in pairwise merging of all the trees, to ensure at the end of the operation there are no two trees with the same degree. we scan the root list with the help of min pointer in the heap and combine trees with same degree into a single tree. We do this with the help of a auxillary table to see if there is a tree with degree already existing in our heap.

fib_heap_cut()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_cut	(	FibonacciNode *	node,
		FibonacciNode *	node_parent
	)

This method removes the child node from its parent in the heap.

fib_heap_decrease_key()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_decrease_key	(	FibonacciNode *	node_inst,
		int	new_key
	)

This method sets the key field of node to amount specified as argument. Based on the new value it may be removed from the parent and called for cut and cascade methods.

fib_heap_delete()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_delete

(

FibonacciNode *

node

)

This function can be used to delete a key from the heap. This is achieved by decreasing the key value to the minimum value available in the data type being used. This function is not in use for our current implementation.

fib_heap_existing_to_root()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_existing_to_root

(

FibonacciNode *

new_node

)

This function deals with adding truncated nodes to the root list. mark value of the node is set to FALSE as it is equivalent to the node being insert first time.

fib_heap_extract_min()

template<typename State , typename Action >

FibonacciNode * FibonacciHeap< State, Action >::fib_heap_extract_min

(

)

This function extracts the minimum value from the heap based on the min_node pointer that each heap structure maintains. In order to verify the correctness of the fibonacci implementation with the array one, I am writing out each extracted min node to a file for making the comparision easier.

fib_heap_insert()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_insert	(	FibonacciNode *	new_node,
		double	key
	)

Node structure in a Graph. Instead, we are simplifying by representing each node by its index (int) Structure for each element in a Graph's adjacency list Adjacency list representation of the graph. We use a Hash Table to map each vertex to its adjacent nodes This is the fibonacci heap data structure which has min pointer of type fibonacci node and total nodes in the heap This function inserts a new node into the fibonacci heap. Depending on the key mentioned, heap min pointer is changed appropriately and degree incremented by one.

fib_heap_link()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_link	(	FibonacciNode *	high_node,
		FibonacciNode *	low_node
	)

This function links two nodes as part of the consolidation operation. First the larger node is sliced from its sibling list and is then added as a child to the smaller node

fib_heap_remove_node_from_root()

template<typename State , typename Action >

void FibonacciHeap< State, Action >::fib_heap_remove_node_from_root

(

FibonacciNode *

node

)

This function is used to truncate a child node from a sibling list. It could be a root list as well.

Fibonacci()

template<typename State , typename Action >

FibonacciHeap< State, Action >::Fibonacci ( StateGraph *  _stateGraph )

inline

get_min_distant_unmarked_node()

template<typename State , typename Action >

int FibonacciHeap< State, Action >::get_min_distant_unmarked_node	(	int *	distance_to_dest,
		std::unordered_map< size_t, bool >	marked
	)

This function calculates the min distant unmarked node using the normal array implementation. This uses the Greedy approach.

get_min_distant_unmarked_node_fib_heap()

template<typename State , typename Action >

int FibonacciHeap< State, Action >::get_min_distant_unmarked_node_fib_heap	(	std::unordered_map< size_t, FibonacciNode * >	node_array,
		std::unordered_map< size_t, bool >	marked
	)

This function calculates the minimum distant node using the fibonacci heap.

---

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

• /opt/actions-runner/_work/open-ppl/open-ppl/src/Utilities/FibonocciHeap.h
• /opt/actions-runner/_work/open-ppl/open-ppl/src/Utilities/FibonocciHeap.cpp