I got an assignment but I'm stuck in the titled problem. It will be very glad that you will help me to solve this. The quick over review I have provided the classes and main file for which I have to implemented the function and run the code. There are two files named fheap.hpp and djstra.hpp and the main file.
int main(){
// Fibonacci Heap
FibonacciHeap<int> heap(3);
std::cout<<(heap.get_min()==std::nullopt)<<std::endl;
std::vector<int> inserted;
for(int i = 0 ; i < 15 ; ++i) {
int temp = rand() % 100+1;
heap.insert(temp);
cout << temp;
cout << "inserted & min :";
cout << heap.get_min().value() << endl;
}
std::cout<<heap.get_min().value()<<std::endl;
for (int j = 0; j < 15; ++j) {
int min_value = heap.extract_min().value();
cout << "min_value: ";
std::cout << min_value;
cout << " size: ";
cout << heap.size()<<endl;
}
// Dijkstra's Algorithm
edges_t edges1 = {{0, 1, 3.0f},
{0, 2, 1.0f},
{1, 2, 7.0f},
{1, 3, 5.0f},
{1, 4, 1.0f},
{2, 3, 2.0f},
{3, 4, 7.0f}};
Graph g1(5, edges1, GraphType::UNDIRECTED);
std::unordered_map<vertex_t, std::optional<std::tuple<vertex_t, edge_weight_t>>> result
= dijkstra_shortest_path(g1, 2);
// Previous vertex of src are not checked.
std::vector<vertex_t> previous = {2, 0, (vertex_t)-1, 2, 1};
std::vector<edge_weight_t> dist = {1.0f, 4.0f, 0.0f, 2.0f, 5.0f};
// The printed result should be same as above.
for(size_t i = 0 ; i < 5 && i!=2 ; ++i) {
std::cout<<"[vertex i] ";
std::cout<<"previous: "<<std::get<0>(result[i].value())<<", ";
std::cout<<"distance: "<<std::get<1>(result[i].value())<<std::endl;
}
return 0;
}
Suprisingly the djstra part is giving me the required output. second file loop in the main section throws memory error Edit: ( meaning it exits the program with some memory address and sometimes show what() std:: optional error). The fheap class is below that are responsible for it are below:
#ifndef __FHEAP_H_
#define __FHEAP_H_
#include <iostream>
#include <initializer_list>
#include <optional>
#include <vector>
#include <cmath>
#include <memory>
#include <queue>
#include <list>
template <typename T>
class PriorityQueue {
public:
virtual void insert(const T& item) = 0;
virtual std::optional<T> extract_min() = 0;
virtual bool is_empty() const = 0;
};
template <typename T>
class FibonacciNode {
public:
// Constructors
FibonacciNode()
:key(), degree(0), marked(false), child(nullptr), right(nullptr) {}
FibonacciNode(const T& item)
:key(item), degree(0), marked(false), child(nullptr), right(nullptr) {}
// Destructor
~FibonacciNode() = default;
T key;
size_t degree;
bool marked;
std::shared_ptr<FibonacciNode<T>> right;
std::shared_ptr<FibonacciNode<T>> child;
// NOTE: To prevent circular reference, left/parent pointer should be set to weak_ptr.
std::shared_ptr<FibonacciNode<T>> left;
std::shared_ptr<FibonacciNode<T>> parent;
};
template <typename T>
class FibonacciHeap : public PriorityQueue<T> {
public:
// Constructors
FibonacciHeap()
: min_node(nullptr), size_(0) {}
FibonacciHeap(const T& item)
: min_node(nullptr), size_(0) { insert(item); }
// Disable copy constructor.
FibonacciHeap(const FibonacciHeap<T> &);
// Destructor
//~FibonacciHeap();
void insert(const T& item) override;
void insert(std::shared_ptr<FibonacciNode<T>>& node);
// Return raw pointer of the min_node.
FibonacciNode<T>* get_min_node() { return min_node.get(); }
std::optional<T> get_min() const;
std::optional<T> extract_min() override;
std::optional<T> extract_min1();
void decrease_key(std::shared_ptr<FibonacciNode<T>>& x, T new_key);
void remove(std::shared_ptr<FibonacciNode<T>>& node);
bool is_empty() const override { return !size_; }
size_t size() const { return size_; }
private:
std::shared_ptr<FibonacciNode<T>> min_node;
std::shared_ptr<FibonacciNode<T>> min;
size_t size_;
void consolidate();
void merge(std::shared_ptr<FibonacciNode<T>>& x, std::shared_ptr<FibonacciNode<T>>& y);
void cut(std::shared_ptr<FibonacciNode<T>>& x);
void recursive_cut(std::shared_ptr<FibonacciNode<T>>& x);
};
template <typename T>
void FibonacciHeap<T>::insert(const T& item) {
std::shared_ptr<FibonacciNode<T>> node = std::make_shared<FibonacciNode<T>>(item);
insert(node);
}
template <typename T>
std::optional<T> FibonacciHeap<T>::get_min() const {
if (min_node) {
return min_node->key;
} else {
return std::nullopt;
}
}
template <typename T>
void FibonacciHeap<T>::insert(std::shared_ptr<FibonacciNode<T>>& node) {
// Make the new node the right sibling of the min_node, if it exists
if (min_node) {
node->right = min_node->right;
min_node->right = node;
node->left = min_node;
node->right->left = node;
}
// Otherwise, make the new node the min_node and its own right sibling
else {
min_node = node;
node->right = node;
node->left = node;
}
// If the new node has a smaller key than the current min_node, update min_node
if (node->key < min_node->key) {
min_node = node;
}
// Increase the size of the heap
++size_;
}
template <typename T>
std::optional<T> FibonacciHeap<T>::extract_min() {
// Return nullopt if the heap is empty
if (!min_node) {
return std::nullopt;
}
// Store the min_node in a temporary variable
std::shared_ptr<FibonacciNode<T>> z = min_node;
// If the min_node has children, add them to the root list
if (z->child) {
std::shared_ptr<FibonacciNode<T>> child = z->child;
do {
child->parent.reset();
child = child->right;
} while (child != z->child);
merge(min_node, z->child);
}
// Remove the min_node from the root list
std::shared_ptr<FibonacciNode<T>> left = z->left;
std::shared_ptr<FibonacciNode<T>> right = z->right;
left->right = right;
right->left = left;
// If the min_node was the only node in the heap, set min_node to nullptr
if (z == right) {
min_node.reset();
}
// Otherwise, set the new min_node to be the node that was previously to the right of z
else {
min_node = right;
consolidate();
}
// Decrease the size of the heap
--size_;
// Return the key of the extracted min_node
return z->key;
}
template <typename T>
void FibonacciHeap<T>::decrease_key(std::shared_ptr<FibonacciNode<T>>& x, T new_key) {
// If the new key is greater than the current key, throw an exception
if (new_key > x->key) {
throw std::invalid_argument("New key is greater than current key.");
}
// Update the key of the node
x->key = new_key;
// If the node has a parent and its new key is smaller than its parent's key, cut it from its parent and add it to the root list
auto parent = x->parent.lock();
if (parent && x->key < parent->key) {
cut(x);
}
// If the node's new key is smaller than the current min_node's key, update min_node
if (x->key < min_node->key) {
min_node = x;
}
}
template <typename T>
void FibonacciHeap<T>::remove(std::shared_ptr<FibonacciNode<T>>& x) {
// Set the key of the node to be removed to the minimum value
x->key = std::numeric_limits<T>::min();
// Perform a decrease key operation on the node to be removed
decrease_key(x, std::numeric_limits<T>::min());
// Extract the minimum value, which should be the node to be removed
extract_min();
}
template <typename T>
void FibonacciHeap<T>::consolidate() {
float phi = (1 + sqrt(5)) / 2.0;
int len = int(log(size_) / log(phi)) + 10;
std::vector<std::shared_ptr<FibonacciNode<T>>> A(len, nullptr);
std::shared_ptr<FibonacciNode<T>> w = min_node;
std::shared_ptr<FibonacciNode<T>> x = w;
do {
x = x->right;
std::shared_ptr<FibonacciNode<T>> y = x;
int d = y->degree;
while (A[d]) {
std::shared_ptr<FibonacciNode<T>> z = A[d];
if (y->key > z->key) {
std::swap(y, z);
}
merge(y, z);
A[d] = nullptr;
++d;
}
A[d] = y;
} while (w != x);
min_node.reset();
for (int i = 0; i < len; ++i) {
if (A[i]) {
if (min_node) {
A[i]->right = min_node->right;
min_node->right = A[i];
A[i]->left = min_node;
A[i]->right->left = A[i];
if (A[i]->key < min_node->key) {
min_node = A[i];
}
}
else {
min_node = A[i];
min_node->right = min_node;
min_node->left = min_node;
}
}
}
}
template <typename T>
void FibonacciHeap<T>::merge(std::shared_ptr<FibonacciNode<T>>& x, std::shared_ptr<FibonacciNode<T>>& y) {
// Make x the right sibling of y
x->right = y->right;
y->right->left = x;
y->right = x;
x->left = y;
// If x has a smaller key than y, make x the new min_node
if (x->key < y->key) {
min_node = x;
}
// Otherwise, make y the new min_node
else {
min_node = y;
}
// Increase the size of the heap
size_ += 2;
}
template <typename T>
void FibonacciHeap<T>::cut(std::shared_ptr<FibonacciNode<T>>& x) {
// Get a pointer to the parent of x
auto parent = x->parent;
// If x has no parent, we do not need to cut it
if (!parent) return;
// Remove x from the child list of parent
if (x->right == x) {
parent->child = nullptr;
}
else {
x->right->left = x->left;
x->left->right = x->right;
if (parent->child == x) {
parent->child = x->right;
}
}
// Decrease the degree of parent
--parent->degree;
// Add x to the root list of the heap
x->right = min_node->right;
min_node->right = x;
x->left = min_node;
x->right->left = x;
// Clear the parent and marked fields of x
x->parent.reset();
x->marked = false;
}
template <typename T>
void FibonacciHeap<T>::recursive_cut(std::shared_ptr<FibonacciNode<T>>& x) {
// Get the parent of the node
auto parent = x->parent.lock();
// If the node has a parent, cut it from the parent and perform a recursive cut on the parent
if (parent) {
if (x->marked) {
// Cut the node from the parent
cut(x);
// Perform a recursive cut on the parent
recursive_cut(parent);
}
// If the node is not marked, mark it
else {
x->marked = true;
}
}
}
#endif // __FHEAP_H_
I know, I'm asking a very long question. I've tried every approach but it's not solving.
I Tried debugging the code and introducing cout operations where I think is error after debugging is in the line `
std::shared_ptr<FibonacciNode<T>> z = A[d];
I tried ArrayList but still no change.
Edit: Second for loop means the 2nd loop in int main ()