This is my full working code. I am a bit confused about how I was able to use the structure MinHeapNode
's variable in my Graph.cpp file. I used its v
and key
variables in the PrimMST()
function.
I need suggestions regarding definition of MinHeapNode
as a class. And how safe it is to use this structure to define its pointer type variable in Graph.cpp file (in function PrimMST()
).
Also, please give some suggestions regarding better implementation of the given code in general. What can I do make it more concise and portable.
This code is for solving this graph:
Graph.h
/***************GRAPH.H*******************************/
#ifndef GRAPH_H_
#define GRAPH_H_
#include <list>
#include <map>
using namespace std;
class AdjListNode{
int v;
int weight;
public:
AdjListNode(int _v, int _w){ v = _v; weight = _w; }
int getV() { return v; }
int getWeight() { return weight; }
};
class Graph{
int V; // To store number of vertices in the graph
list<AdjListNode> *adj; // This is a map for storing the adjacency list
map<int,int> mapping; // A map to form a dictionary of vertex values to their array indexes for look ups.
map<int,int> parent; // A map to store the parent child for a given edge in the graph
public:
Graph(int); // Class constructor
void HashTable(int *, int); // This method uses the map library in STL to create a mappinh
// of arbitrary integers to zero based array indexes
int getHashedElt(int); // This method returns the value corresponding to a given
// key in a hash table
void addEdge(int, int, int); // This method adds the second arg to the adj list of first arg.
void printGraph(); // This method prints the adjacency list of all the vertices
void PrimMST(int *, int); // This function will perform the Prim's MST algorithm and optimize
// the number of nodes in the graph
};
#endif
Graph.cpp
/****************GRAPH.CPP*************************/
#include <iostream>
#include <climits>
#include <list>
#include <map>
#include "Graph.h"
#include "MinHeap.h"
using namespace std;
Graph::Graph(int v){
V = v;
adj = new list<AdjListNode>[V];
}
// This function takes in a pointer to array and its size as its arguments to create a hashtable.
// So. if you have 10,11,12,13,14,15 as the nodes.
// Create an array int arr[] {10,11,12,13,14,15}, and int size = sizeof(arr)/sizeof(arr[0])
// And pass it to this function this creates a dictionary named mapping for O(1) look up of
// index by other functions.
void Graph::HashTable(int *nodeData, int size){
for (int i = 0; i < size; i++){
mapping[nodeData[i]] = i;
}
return;
}
// This method returns the value corresponding to a particular node in constant time.
int Graph::getHashedElt(int data){
return mapping[data];
}
// This function creates an adjacency list for every vertex in the graph
void Graph::addEdge(int node1, int node2, int weight){
AdjListNode node(node2, weight);
int index = getHashedElt(node1);
adj[index].push_back(node);
}
void Graph::printGraph(){
list<AdjListNode>::iterator j;
int i = 0;
while (i<V){
for (j = adj[i].begin(); j != adj[i].end(); j++){
cout <<"(" << j->getV() << "," << j->getWeight() << ")->";
}
if (!adj[i].empty())
cout << "NULL\n";
i++;
}
}
void Graph::PrimMST(int *arr, int size){
MinHeap minHeap(arr,size);
size_t key[V]; // Key values to pick minimum weight edge in cut
for (int i = 1; i < V; i++){
parent[arr[i]] = -1; // All the parents are -1 initially
key[i] = INT_MAX; // Initially all the keys are initialised to positive infinity
MinHeapNode *newNode = minHeap.newMinHeapNode(arr[i],key[i]);
minHeap.insertNode(i, newNode);
}
// Make key value of 0th vertex as 0 so that it is extracted first.
key[0] = 0;
// This function insertNode creates a newNode with vertex number and associated key value.
MinHeapNode *newNode = minHeap.newMinHeapNode(arr[0],key[0]);
minHeap.insertNode(0, newNode);
while (!minHeap.isEmpty()){
// Extract the vertex with minimum key value
minHeap.printHeap();
MinHeapNode *minNode = minHeap.extractMin();
// Get the vertex of this minNode.
int u = minNode->v;
// Traverse through all the adjacent vertices of u (extended vertex)
// and update their key values
list<AdjListNode>::iterator j;
for (j = adj[mapping[u]].begin(); j != adj[mapping[u]].end(); j++) {
int v = j->getV();
// If v is not yet included in the MST and weight of u-v
// is less than key value of v, then update key value
// and parent of v
if (minHeap.isInMinHeap(v) && j->getWeight() < key[mapping[v]]){
key[mapping[v]] = j->getWeight();
parent[v] = u;
minHeap.decreaseKey(v,key[mapping[v]]);
}
}
}
for (int k = 1; k < size; k++){
//cout <<parent[arr[k]]<<"---"<<arr[k]<< "\n";
}
return;
}
MinHeap.h
/*************MINHEAP.H**************************/
#ifndef MINHEAP_H_
#define MINHEAP_H_
#include <map>
using namespace std;
struct MinHeapNode{
int v;
size_t key;
};
class MinHeap{
int size; // Number of heap nodes present in the heap at any given time
int capacity; // Capacity of min heap
map<int,int> pos; // This is map which stores the array index of a given vertex, for O(1) look up
MinHeapNode **MinHeapArray; // This array containe pointers to all the heap nodes.
public:
MinHeap(int*,int); // Class constructor, it will allocate space to minHeap and initialise all the variables.
// It also creates the map of every vertex to an index, so that there is O(1) look up.
MinHeapNode *newMinHeapNode(int,size_t); // This function creates a new min heap node with a given value of vertex and weight
int getIndex(int); // This function returns the index of a given vertex in pos map.
void insertNode(int,MinHeapNode *); // This function inserts a node into the MinHeapArray.
void printHeap();
void swapMinHeapNode(MinHeapNode **, MinHeapNode **); // It will perform swap operation in the heap.
void minHeapify(int); // Standard function to heapify at given idx.
bool isEmpty(); // A utility function to check whether given heap is empty or not.
bool isInMinHeap(int); // Checks whether given vertex in the heap or not
MinHeapNode *extractMin(); // Std func to extract to minimum node from the heap.
void decreaseKey(int,int); // This func performs the decreaseKey op by making use of pos map.
};
#endif
MinHeap.cpp
/***************MINHEAP.CPP***************************/
#include <iostream>
#include <cstdlib>
#include <climits>
#include <map>
#include "MinHeap.h"
using namespace std;
MinHeap::MinHeap(int *arr,int s){
size = 0;
capacity = s;
MinHeapArray = (MinHeapNode **)malloc(sizeof(MinHeapNode *)*s);
for (int i = 0; i < s; i++){
pos[arr[i]] = i; // This is a mapping from vertex to array index i. This will enable O(1) access of any var in heap.
}
}
MinHeapNode *MinHeap::newMinHeapNode(int v, size_t key){
MinHeapNode *node = new MinHeapNode;
node->v = v;
node->key = key;
return node;
}
int MinHeap::getIndex(int v){
return pos[v];
}
void MinHeap::insertNode(int idx, MinHeapNode *node){
MinHeapArray[idx] = node;
size++;
}
bool MinHeap::isEmpty(){
return size == 0;
}
bool MinHeap::isInMinHeap(int v){
if (pos[v] < size)
return true;
return false;
}
void MinHeap::printHeap(){
for (int i = 0; i < size; i++){
cout << MinHeapArray[i]->v << ", "<< MinHeapArray[i]->key << "\n";
}
}
void MinHeap::swapMinHeapNode(MinHeapNode **a, MinHeapNode **b){
MinHeapNode *t = *a;
*a = *b;
*b = t;
}
// A standard function to heapify at given index idx
// This function also updates position of nodes when they are swapped.
void MinHeap::minHeapify(int idx){
int smallest, left, right;
left = (2*idx + 1);
right = (2*idx + 2);
smallest = idx;
if (left < size && MinHeapArray[left]->key < MinHeapArray[smallest]->key)
smallest = left;
if (right < size && MinHeapArray[right]->key < MinHeapArray[smallest]->key)
smallest = right;
if (smallest != idx){
// To nodes to be swapped in min heap
MinHeapNode *smallestNode = MinHeapArray[smallest];
MinHeapNode *idxNode = MinHeapArray[idx];
// Change the mapping of vertices in pos map.
pos[smallestNode->v] = idx;
pos[idxNode->v] = smallest;
// Swap Nodes using swapMinHeapNode utility function
MinHeap::swapMinHeapNode(&smallestNode, &idxNode);
minHeapify(smallest);
}
return;
}
MinHeapNode *MinHeap::extractMin(){
if (isEmpty())
return NULL;
// Store the root node
MinHeapNode *root = MinHeapArray[0];
// Replace the root with last node
MinHeapNode *lastNode = MinHeapArray[size-1];
MinHeapArray[0] = lastNode;
// Update position of last node
pos[root->v] = size - 1;
pos[lastNode->v] = 0;
// Reduce heap size and heapify root
size--;
MinHeap::minHeapify(0);
return root;
}
void MinHeap::decreaseKey(int v, int key){
// Get the index of v in heap array
int i = pos[v];
// Get the node and update its key value
MinHeapArray[i]->key = key;
// Travel up till the complete tree is not heapified.
// This is O(logn) loop
while (i && MinHeapArray[i]->key < MinHeapArray[(i-1)/2]->key){
// Swap this node with its parent
// First update the pos matrix
pos[MinHeapArray[i]->v] = (i-1)/2;
pos[MinHeapArray[(i-1)/2]->v] = i;
// Do the swapping now.
MinHeap::swapMinHeapNode(&MinHeapArray[i], &MinHeapArray[(i-1)/2]);
// move to the parent index in the next iteration
i = (i - 1)/2;
}
return;
}
main.cpp
/**********************MAIN FUNCTION CALL***************/
#include <iostream>
#include "Graph.h"
#include "MinHeap.h"
using namespace std;
int main(){
int arr[] = {0,1,2,3,4,5,6,7,8}; // An array with all the vertices
int size = sizeof(arr)/sizeof(arr[0]);
Graph g(size);
g.HashTable(arr,size);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
//g.printGraph();
g.PrimMST(arr,size);
return 0;
}
I specifically don't know how to use debug flags in my code, such that I can use some compiler options to perform better debug. Instead of writing print statements and checking out output, and then commenting them out. Also, if you can give some specific debugger suggestion, which I can use to perform easy debugs will be very much appreciated.
I specifically don't know how to use debug flags in my code, such that I can use some compiler options to perform better debug.
- that is a tool chain/IDE question (SO tag debugging?) rather than a code question. Coding, stick to clearly say what I mean, debugging, have some tool show me what's happening/going wrong, with assertions somewhere in the middle. (With archaic tools, it helped to have a name for something to watch, like a variable that gets assigned to rather than just an expression in, say, an elaborate condition.) \$\endgroup\$ – greybeard Jan 7 '16 at 5:06