hthukral
asked on
Solve this Dijkstra Algorithm using heaps....
I have Dijkstra Algorithm....I m not able to compile it using fibonacci heap...I m attaching the files....Early help will be really appreciated...I m doing Uni project....
// Directed Graphs
# include <cstdio>
#include "dgraph.h"
// Constructor
DGraph::DGraph(int n)
{
nVertices = n;
vertices = new DGraphVertex[n];
initVertices();
}
//Destructor
DGraph::~DGraph()
{
clear();
delete [] vertices;
}
// Clear all edges from the graphs
void DGraph::clear()
{
DGraphEdge *edge, *nextEdge;
for (int i = 0; i < nVertices; i++)
{
edge = vertices[i].outHead;
while(edge) {
nextEdge = edge->nextOut;
delete edge;
edge = nextEdge;
}
}
initVertices();
}
void DGraph::initVertices()
{
for(int i = 0; i < nVertices; i++)
{
vertices[i].outHead = vertices[i].outTail = 0;
vertices[i].inHead = vertices[i].inTail = 0;
vertices[i].outSize = vertices[i].inSize = 0;
}
}
// AddnewEdge()
// Adds a new edge from vertex 'source' to vertex 'target' with a corresponding
// distance of dist.
void DGraph::addNewEdge(int source, int target, int dist)
{
DGraphEdge *newEdge = new DGraphEdge;
newEdge->source = source;
newEdge->target = target;
newEdge->dist = dist;
newEdge->nextOut = NULL;
newEdge->nextIn = NULL;
DGraphVertex *vertex = &vertices[source];
if(vertex->outTail) {
vertex->outTail->nextOut = newEdge;
}
else
{
vertex->outHead = newEdge;
}
vertex->outTail = newEdge ;
vertex->outSize++ ;
vertex = &vertices[target];
if(vertex->inTail)
{
vertex->inTail->nextIn = newEdge;
}
else
{
vertex->inHead = newEdge;
}
vertex->inTail = newEdge ;
vertex->inSize++ ;
};
bool DGraph::edgeExists(int v, int w) const
{
// Check all existing edges from v to determine whether an edge to w exists
const DGraphEdge *edge = vertices[v].outHead;
while(edge)
{
if(edge->target == w) return true;
edge = edge->nextOut;
}
return false;
}
// Check whether all vertices are reachable from the source vertex s.
bool DGraph::reachable(int s) const
{
int *stack = new int[nVertices];
int tos = 0;
int *visited = new int[nVertices];
for(int i =0; i < nVertices; i++) visited[i] = 0;
int vertexCount = 0;
visited[s] = 1;
stack[tos++] = s;
DGraphEdge *edge;
int v,w;
while(tos)
{
v = stack[--tos];
vertexCount++;
edge = vertices[v].outHead;
while(edge)
{
w = edge->target;
if(!visited[w])
{
visited[w] = 1;
stack[tos++] = w;
}
edge = edge->nextOut;
}
}
delete [] stack;
delete [] visited;
return vertexCount == nVertices;
}
// Print a text representation of the graph to the standard output
void DGraph::print() const
{
const DGraphEdge *edge;
printf("Graph (vertex: edge list) = \n");
for (int i = 0; i < nVertices; i++)
{
printf("%d: ", i);
edge = vertices[i].outHead;
while(edge)
{
printf(" %d", edge->target);
edge = edge->nextOut;
}
putchar('\n');
}
printf("Graph (vertex: edge{dist} list) = \n");
for(int i = 0; i < nVertices; i++)
{
printf("%d: ", i);
edge = vertices[i].outHead;
while(edge)
{
printf(" %d{%d}", edge->target, edge->dist);
edge = edge->nextOut;
}
putchar('\n');
}
}
#include "dijkstra.h"
#include "dgraph.h"
#include "fheap.h"
// Constructor
// Allocate the algorithm for use on graph of n vertices. The parameter heap D(points
// to heap descriptor object) specifies then heap to be used by Dijkstra's Algorithm
Dijkstra::Dijkstra(int n, HeapDesc *heapD)
{
heap = heapD->newInstance (n);
s = new bool [n];
f = new bool [n];
}
// Destructor
Dijkstra::~Dijkstra()
{
delete [] s;
delete [] f;
delete heap;
}
// init ()
// Initialize the algorithm for use with the graph pointed to by g.
void Dijkstra::init(const DGraph *g)
{
graph = g;
}
// run()
// Run the algorithm, computing single-source from the starting vertex v0.
// This assumes that array has been initialized with d[v] = INFINITE_DIST for all
// vertices v ! = v0
void Dijkstra::run(long *d, int v0)
{
//Indexes counters and pointers
int v, w;
long dist;
const DGraphEdge *edge;
// Initialisation
// Optimise access to the data structure allocated for the algorithm
const int n = graph->nVertices;
const DGraphVertex *vertices = graph->vertices;
// Algorithm
// Initialise all vertices as unexplored
for (v = 0; v < n; v++) s[v] = false;
for (v = 0; v < n; v++) f[v] = false;
// Place v0 into the frontier set with a distance of zero
d[v0] = 0;
heap->insert(v0, 0);
f[v0] = true;
// Repeatedly update distances from the minimum remaining trigger vertex
while(heap->nItems () > 0)
{
// Delete the Vertex in frontier that has minimum distance
v = heap->deleteMin ();
// The selected vertex moves from the frontier to the solution set
s[v] = true;
f[v] = false;
// explore the OUT set of V
edge = vertices[v].outHead;
while(edge)
{
w = edge->target;
if(s[w] == false)
{
dist = d[v] + edge->dist;
if(dist < d[w])
{
d[w] = dist;
if(f[w])
{
heap->decreaseKey(w, dist);
}
else
{
heap->insert(w, dist);
f[w] = true;
}
}
}
edge = edge->nextOut;
}// end of while
} // while
}
#include <cstdlib>
#include <cmath>
#if FHEAP_DUMP
#include <cstdio>
#endif
#include "fheap.h"
/*--- FHeap (public methods) -------------------------- ---------- ---------- --*/
/* --- Constructor ---
* Creates an FHeap object capable of holding up to $n$ items.
*/
FHeap::FHeap(int n)
{
int i;
#if FHEAP_DUMP
printf("new, ");
#endif
maxTrees = 1 + (int)(1.44 * log(n)/log(2.0));
maxNodes = n;
trees = new (FHeapNode *)[maxTrees];
for(i = 0; i < maxTrees; i++) trees[i] =0;
nodes = new (FHeapNode *)[n];
for(i = 0; i < n; i++) nodes[i] = 0;
itemCount = 0;
/* The $treeSum$ of the heap helps to keep track of the maximum rank while
* nodes are inserted or deleted.
*/
treeSum = 0;
/* For experimental purposes, we keep a count of the number of key
* comparisons.
*/
compCount = 0;
#if FHEAP_DUMP
printf("new-exited, ");
#endif
}
/* --- Destructor ---
*/
FHeap::~FHeap()
{
int i;
#if FHEAP_DUMP
printf("delete, ");
#endif
for(i = 0; i < maxNodes; i++) delete nodes[i];
delete [] nodes;
delete [] trees;
#if FHEAP_DUMP
printf("delete-exited, ");
#endif
}
/* --- insert() ---
* Inserts an item $item$ with associated key $k$ into the heap.
*/
void FHeap::insert(int item, long k)
{
FHeapNode *newNode;
#if FHEAP_DUMP
printf("insert, ");
#endif
/* create an initialise the new node */
newNode = new FHeapNode;
newNode->child = NULL;
newNode->left = newNode->right = newNode;
newNode->rank = 0;
newNode->item = item;
newNode->key = k;
/* maintain a pointer to $item$'s new node in the heap */
nodes[item] = newNode;
/* meld the new node into the heap */
meld(newNode);
/* update the heaps node count */
itemCount++;
#if FHEAP_DUMP
printf("insert-exited, ");
#endif
}
/* --- deleteMin() ---
* Deletes and returns the minimum item from the heap.
*/
int FHeap::deleteMin()
{
FHeapNode *minNode, *child, *next;
long k, k2;
int r, v, item;
#if FHEAP_DUMP
printf("deleteMin, ");
#endif
/* First we determine the maximum rank in the heap. */
v = treeSum;
r = -1;
while(v) {
v = v >> 1;
r++;
};
/* Now determine which root node is the minimum. */
minNode = trees[r];
k = minNode->key;
while(r > 0) {
r--;
next = trees[r];
if(next) {
if((k2 = next->key) < k) {
k = k2;
minNode = next;
}
compCount++;
}
}
/* We remove the minimum node from the heap but keep a pointer to it. */
r = minNode->rank;
trees[r] = NULL;
treeSum -= (1 << r);
child = minNode->child;
if(child) meld(child);
/* Record the vertex no of the old minimum node before deleting it. */
item = minNode->item;
nodes[item] = NULL;
delete minNode;
itemCount--;
#if FHEAP_DUMP
printf("deleteMin-exited, ");
#endif
return item;
}
/* --- decreaseKey() ---
* Decreases the key used for item $item$ to the value newValue. It is left
* for the user to ensure that newValue is in-fact less than the current value
*/
void FHeap::decreaseKey(int item, long newValue)
{
FHeapNode *cutNode, *parent, *newRoots, *r, *l;
int prevRank;
#if FHEAP_DUMP
printf("decreaseKey on vn = %d, ", item);
#endif
/* Obtain a pointer to the decreased node and its parent then decrease the
* nodes key.
*/
cutNode = nodes[item];
parent = cutNode->parent;
cutNode->key = newValue;
/* No reinsertion occurs if the node changed was a root. */
if(!parent) {
#if FHEAP_DUMP
printf("decreaseKey-exited , ");
#endif
return;
}
/* Update the left and right pointers of cutNode and its two neighbouring
* nodes.
*/
l = cutNode->left;
r = cutNode->right;
l->right = r;
r->left = l;
cutNode->left = cutNode->right = cutNode;
/* Initially the list of new roots contains only one node. */
newRoots = cutNode;
/* While there is a parent node that is marked a cascading cut occurs. */
while(parent && parent->marked) {
/* Decrease the rank of cutNode's parent and update its child pointer.
*/
parent->rank--;
if(parent->rank) {
if(parent->child == cutNode) parent->child = r;
}
else {
parent->child = NULL;
}
/* Update the cutNode and parent pointers to the parent. */
cutNode = parent;
parent = cutNode->parent;
/* Update the left and right pointers of cutNodes two neighbouring
* nodes.
*/
l = cutNode->left;
r = cutNode->right;
l->right = r;
r->left = l;
/* Add cutNode to the list of nodes to be reinserted as new roots. */
l = newRoots->left;
newRoots->left = l->right = cutNode;
cutNode->left = l;
cutNode->right = newRoots;
newRoots = cutNode;
}
/* If the root node is being relocated then update the trees[] array.
* Otherwise mark the parent of the last node cut.
*/
if(!parent) {
prevRank = cutNode->rank + 1;
trees[prevRank] = NULL;
treeSum -= (1 << prevRank);
}
else {
/* Decrease the rank of cutNode's parent an update its child pointer.
*/
parent->rank--;
if(parent->rank) {
if(parent->child == cutNode) parent->child = r;
}
else {
parent->child = NULL;
}
parent->marked = 1;
}
/* Meld the new roots into the heap. */
meld(newRoots);
#if FHEAP_DUMP
printf("decreaseKey-exited , ");
#endif
}
/*--- FHeap (private methods) -------------------------- ---------- ---------- -*/
/* --- meld() ---
* melds the linked list of trees pointed to by $treeList$ into the heap.
*/
void FHeap::meld(FHeapNode *treeList)
{
FHeapNode *first, *next, *nodePtr, *newRoot, *temp, *temp2, *lc, *rc;
int r;
#if FHEAP_DUMP
printf("meld: ");
#endif
/* We meld each tree in the circularly linked list back into the root level
* of the heap. Each node in the linked list is the root node of a tree.
* The circularly linked list uses the sibling pointers of nodes. This
* makes melding of the child nodes from a deleteMin operation simple.
*/
nodePtr = first = treeList;
do {
#if FHEAP_DUMP
printf("%d, ", nodePtr->item);
#endif
/* Keep a pointer to the next node and remove sibling and parent links
* from the current node. nodePtr points to the current node.
*/
next = nodePtr->right;
nodePtr->right = nodePtr->left = nodePtr;
nodePtr->parent = NULL;
/* We merge the current node, nodePtr, by inserting it into the
* root level of the heap.
*/
newRoot = nodePtr;
r = nodePtr->rank;
/* This loop inserts the new root into the heap, possibly restructuring
* the heap to ensure that only one tree for each degree exists.
*/
do {
/* Check if there is already a tree of degree r in the heap.
* If there is then we need to link it with newRoot so it will be
* reinserted into a new place in the heap.
*/
if((temp = trees[r])) {
/* temp will be linked to newRoot and relocated so we no
* longer will have a tree of degree r.
*/
trees[r] = NULL;
treeSum -= (1 << r);
/* Swap temp and newRoot if necessary so that newRoot always
* points to the root node which has the smaller key of the
* two.
*/
if(temp->key < newRoot->key) {
temp2 = newRoot;
newRoot = temp;
temp = temp2;
}
compCount++;
/* Link temp with newRoot, making sure that sibling pointers
* get updated if rank is greater than 0. Also, increase r for
* the next pass through the loop since the rank of new has
* increased.
*/
if(r++ > 0) {
rc = newRoot->child;
lc = rc->left;
temp->left = lc;
temp->right = rc;
lc->right = rc->left = temp;
}
newRoot->child = temp;
newRoot->rank = r;
temp->parent = newRoot;
temp->marked = 0;
}
/* Otherwise if there is not a tree of degree r in the heap we
* allow newRoot, which possibly carries moved trees in the heap,
* to be a tree of degree r in the heap.
*/
else {
trees[r] = newRoot;
treeSum += (1 << r);;
/* NOTE: Because newRoot is now a root we ensure it is
* marked.
*/
newRoot->marked = 1;
}
/* Note that temp will be NULL if and only if there was not a tree
* of degree r.
*/
} while(temp);
nodePtr = next;
} while(nodePtr != first);
#if FHEAP_DUMP
printf("meld-exited, ");
#endif
}
/*--- FHeap (debugging) -------------------------- ---------- ---------- -------*/
/* --- dumpNodes() ---
* Recursively print a text representation of the node subtree starting at the
* node poined to by $node$, using an indentationlevel of $level$.
*/
void FHeap::dumpNodes(FHeapNode *node, int level)
{
#if FHEAP_DUMP
FHeapNode *childNode, *partner;
int i, childCount;
/* Print leading whitespace for this level. */
for(i = 0; i < level; i++) printf(" ");
printf("%d(%ld)[%d]\n", node->item, node->key, node->rank);
if((childNode = node->child)) {
childNode = node->child->right;
childCount = 0;
do {
dumpNodes(childNode, level+1);
if(childNode->dim > node->dim) {
for(i = 0; i < level+1; i++) printf(" ");
printf("error(dim)\n"); exit(1);
}
if(childNode->parent != node) {
for(i = 0; i < level+1; i++) printf(" ");
printf("error(parent)\n");
}
childNode = childNode->right;
childCount++;
} while(childNode != node->child->right);
if(childCount != node->dim) {
for(i = 0; i < level; i++) printf(" ");
printf("error(childCount)\ n"); exit(1);
}
}
else {
if(node->dim != 0) {
for(i = 0; i < level; i++) printf(" ");
printf("error(dim)\n"); exit(1);
}
}
#endif
}
/* --- dump() ---
* Print a text representation of the heap to the standard output.
*/
void FHeap::dump() const
{
#if FHEAP_DUMP
int i;
FHeapNode *node;
printf("\n");
printf("treeSum = %d\n", treeSum);
printf("array entries 0..maxTrees =");
for(i = 0; i < maxTrees; i++) {
printf(" %d", trees[i] ? 1 : 0 );
}
printf("\n\n");
for(i = 0; i < maxTrees; i++) {
if((node = trees[i])) {
printf("tree %d\n\n", i);
dumpNodes(node, 0);
printf("\n");
}
}
fflush(stdout);
#endif
}
/*------------------------ ---------- ---------- ---------- ---------- ---------- -*/
#ifndef FHEAP_H
#define FHEAP_H
#include "heap.h" /* Defines the base class for heaps. */
/* Option to allow printing of debugging information. Use 1 for yes, or 0 for
* no.
*/
#define FHEAP_DUMP 0
/* --- FHeapNode ---
* Fibonacci heap node class.
*
* A nodes has the following pointers:
* parent - a pointer to the nodes parent node (if any).
* child - a pointer to a child node (typically the highest rank child).
* left, right - sibling pointers which provide a circular doubly linked list
* containing all the parents nodes children.
*
* The remaining fields are:
* rank - the nodes rank, that is, the number of children it has.
* key - the nodes key.
* item - the number of the item that the node is associated with.
*/
class FHeapNode {
public:
FHeapNode *parent;
FHeapNode *left, *right;
FHeapNode *child;
int rank;
int marked;
long key;
int item;
};
/* --- FHeap ---
* Fibonacci heap class.
*
* trees - An array of pointers to trees at root level in the heap. Entry i
* in the array points to the root node of a tree that has nodes of
* dimension i on the main trunk.
* nodes - An array of pointers to nodes in the heap. Nodes are indexed
* according to their vertex number. This array can then be used to
* look up the node for corresponding to a vertex number, and is
* useful when freeing space taken up by the heap.
* maxNodes - The maximum number of nodes allowed in the heap.
* maxTrees - The maximum number of trees allowed in the heap (calculated from
* maxNodes).
* itemCount - The current number of nodes in the heap.
* treeSum - The binary value represented by trees in the heap.
* By maintaining this it is easy to keep track of the maximum rank
* tree in the heap.
* compCount - can be used for experimental purposes when counting the number
* of key comparisons.
*/
class FHeap: public Heap {
public:
FHeap(int n);
~FHeap();
int deleteMin();
void insert(int item, long k);
void decreaseKey(int item, long newValue);
int nItems() const { return itemCount; }
long nComps() const { return compCount; }
void dump() const;
private:
FHeapNode **trees;
FHeapNode **nodes;
int maxNodes, maxTrees, itemCount, treeSum;
long compCount;
void meld(FHeapNode *treeList);
static void dumpNodes(FHeapNode *node, int level);
};
/*------------------------ ---------- ---------- ---------- ---------- ---------- -*/
#endif
# ifndef HEAP_H
# define HEAP_H
class Heap
{
public:
virtual ~Heap() { };
virtual int deleteMin() = 0;
virtual void insert(int item, long key) = 0;
virtual void decreaseKey(int item, long newKey) = 0;
virtual int nItems() const = 0;
virtual long nComps() const = 0;
};
class HeapDesc
{
public:
virtual ~HeapDesc() { };
virtual Heap *newInstance(int n) const = 0;
};
template <class T>
class HeapD: public HeapDesc
{
public:
Heap *newInstance(int n) const { return new T(n); };
};
#endif
I have files dijkstra.h and dgraph.h...
I have Visual.Net compiler 7.0 . When I compile I get errors in fheap.cpp
fheap.cpp(26): error C2143: syntax error : missing ';' before '['
fheap.cpp(26): error C2337: 'maxTrees' : attribute not found; it is neither a built-in nor a custom attribute that is accessible in the current namespace
fheap.cpp(29): error C2337: 'n' : attribute not found; it is neither a built-in nor a custom attribute that is accessible in the current namespace
and I have no clue what to correct.....
Thanx
Harsimrat
// Directed Graphs
# include <cstdio>
#include "dgraph.h"
// Constructor
DGraph::DGraph(int n)
{
nVertices = n;
vertices = new DGraphVertex[n];
initVertices();
}
//Destructor
DGraph::~DGraph()
{
clear();
delete [] vertices;
}
// Clear all edges from the graphs
void DGraph::clear()
{
DGraphEdge *edge, *nextEdge;
for (int i = 0; i < nVertices; i++)
{
edge = vertices[i].outHead;
while(edge) {
nextEdge = edge->nextOut;
delete edge;
edge = nextEdge;
}
}
initVertices();
}
void DGraph::initVertices()
{
for(int i = 0; i < nVertices; i++)
{
vertices[i].outHead = vertices[i].outTail = 0;
vertices[i].inHead = vertices[i].inTail = 0;
vertices[i].outSize = vertices[i].inSize = 0;
}
}
// AddnewEdge()
// Adds a new edge from vertex 'source' to vertex 'target' with a corresponding
// distance of dist.
void DGraph::addNewEdge(int source, int target, int dist)
{
DGraphEdge *newEdge = new DGraphEdge;
newEdge->source = source;
newEdge->target = target;
newEdge->dist = dist;
newEdge->nextOut = NULL;
newEdge->nextIn = NULL;
DGraphVertex *vertex = &vertices[source];
if(vertex->outTail) {
vertex->outTail->nextOut = newEdge;
}
else
{
vertex->outHead = newEdge;
}
vertex->outTail = newEdge ;
vertex->outSize++ ;
vertex = &vertices[target];
if(vertex->inTail)
{
vertex->inTail->nextIn = newEdge;
}
else
{
vertex->inHead = newEdge;
}
vertex->inTail = newEdge ;
vertex->inSize++ ;
};
bool DGraph::edgeExists(int v, int w) const
{
// Check all existing edges from v to determine whether an edge to w exists
const DGraphEdge *edge = vertices[v].outHead;
while(edge)
{
if(edge->target == w) return true;
edge = edge->nextOut;
}
return false;
}
// Check whether all vertices are reachable from the source vertex s.
bool DGraph::reachable(int s) const
{
int *stack = new int[nVertices];
int tos = 0;
int *visited = new int[nVertices];
for(int i =0; i < nVertices; i++) visited[i] = 0;
int vertexCount = 0;
visited[s] = 1;
stack[tos++] = s;
DGraphEdge *edge;
int v,w;
while(tos)
{
v = stack[--tos];
vertexCount++;
edge = vertices[v].outHead;
while(edge)
{
w = edge->target;
if(!visited[w])
{
visited[w] = 1;
stack[tos++] = w;
}
edge = edge->nextOut;
}
}
delete [] stack;
delete [] visited;
return vertexCount == nVertices;
}
// Print a text representation of the graph to the standard output
void DGraph::print() const
{
const DGraphEdge *edge;
printf("Graph (vertex: edge list) = \n");
for (int i = 0; i < nVertices; i++)
{
printf("%d: ", i);
edge = vertices[i].outHead;
while(edge)
{
printf(" %d", edge->target);
edge = edge->nextOut;
}
putchar('\n');
}
printf("Graph (vertex: edge{dist} list) = \n");
for(int i = 0; i < nVertices; i++)
{
printf("%d: ", i);
edge = vertices[i].outHead;
while(edge)
{
printf(" %d{%d}", edge->target, edge->dist);
edge = edge->nextOut;
}
putchar('\n');
}
}
#include "dijkstra.h"
#include "dgraph.h"
#include "fheap.h"
// Constructor
// Allocate the algorithm for use on graph of n vertices. The parameter heap D(points
// to heap descriptor object) specifies then heap to be used by Dijkstra's Algorithm
Dijkstra::Dijkstra(int n, HeapDesc *heapD)
{
heap = heapD->newInstance (n);
s = new bool [n];
f = new bool [n];
}
// Destructor
Dijkstra::~Dijkstra()
{
delete [] s;
delete [] f;
delete heap;
}
// init ()
// Initialize the algorithm for use with the graph pointed to by g.
void Dijkstra::init(const DGraph *g)
{
graph = g;
}
// run()
// Run the algorithm, computing single-source from the starting vertex v0.
// This assumes that array has been initialized with d[v] = INFINITE_DIST for all
// vertices v ! = v0
void Dijkstra::run(long *d, int v0)
{
//Indexes counters and pointers
int v, w;
long dist;
const DGraphEdge *edge;
// Initialisation
// Optimise access to the data structure allocated for the algorithm
const int n = graph->nVertices;
const DGraphVertex *vertices = graph->vertices;
// Algorithm
// Initialise all vertices as unexplored
for (v = 0; v < n; v++) s[v] = false;
for (v = 0; v < n; v++) f[v] = false;
// Place v0 into the frontier set with a distance of zero
d[v0] = 0;
heap->insert(v0, 0);
f[v0] = true;
// Repeatedly update distances from the minimum remaining trigger vertex
while(heap->nItems () > 0)
{
// Delete the Vertex in frontier that has minimum distance
v = heap->deleteMin ();
// The selected vertex moves from the frontier to the solution set
s[v] = true;
f[v] = false;
// explore the OUT set of V
edge = vertices[v].outHead;
while(edge)
{
w = edge->target;
if(s[w] == false)
{
dist = d[v] + edge->dist;
if(dist < d[w])
{
d[w] = dist;
if(f[w])
{
heap->decreaseKey(w, dist);
}
else
{
heap->insert(w, dist);
f[w] = true;
}
}
}
edge = edge->nextOut;
}// end of while
} // while
}
#include <cstdlib>
#include <cmath>
#if FHEAP_DUMP
#include <cstdio>
#endif
#include "fheap.h"
/*--- FHeap (public methods) --------------------------
/* --- Constructor ---
* Creates an FHeap object capable of holding up to $n$ items.
*/
FHeap::FHeap(int n)
{
int i;
#if FHEAP_DUMP
printf("new, ");
#endif
maxTrees = 1 + (int)(1.44 * log(n)/log(2.0));
maxNodes = n;
trees = new (FHeapNode *)[maxTrees];
for(i = 0; i < maxTrees; i++) trees[i] =0;
nodes = new (FHeapNode *)[n];
for(i = 0; i < n; i++) nodes[i] = 0;
itemCount = 0;
/* The $treeSum$ of the heap helps to keep track of the maximum rank while
* nodes are inserted or deleted.
*/
treeSum = 0;
/* For experimental purposes, we keep a count of the number of key
* comparisons.
*/
compCount = 0;
#if FHEAP_DUMP
printf("new-exited, ");
#endif
}
/* --- Destructor ---
*/
FHeap::~FHeap()
{
int i;
#if FHEAP_DUMP
printf("delete, ");
#endif
for(i = 0; i < maxNodes; i++) delete nodes[i];
delete [] nodes;
delete [] trees;
#if FHEAP_DUMP
printf("delete-exited, ");
#endif
}
/* --- insert() ---
* Inserts an item $item$ with associated key $k$ into the heap.
*/
void FHeap::insert(int item, long k)
{
FHeapNode *newNode;
#if FHEAP_DUMP
printf("insert, ");
#endif
/* create an initialise the new node */
newNode = new FHeapNode;
newNode->child = NULL;
newNode->left = newNode->right = newNode;
newNode->rank = 0;
newNode->item = item;
newNode->key = k;
/* maintain a pointer to $item$'s new node in the heap */
nodes[item] = newNode;
/* meld the new node into the heap */
meld(newNode);
/* update the heaps node count */
itemCount++;
#if FHEAP_DUMP
printf("insert-exited, ");
#endif
}
/* --- deleteMin() ---
* Deletes and returns the minimum item from the heap.
*/
int FHeap::deleteMin()
{
FHeapNode *minNode, *child, *next;
long k, k2;
int r, v, item;
#if FHEAP_DUMP
printf("deleteMin, ");
#endif
/* First we determine the maximum rank in the heap. */
v = treeSum;
r = -1;
while(v) {
v = v >> 1;
r++;
};
/* Now determine which root node is the minimum. */
minNode = trees[r];
k = minNode->key;
while(r > 0) {
r--;
next = trees[r];
if(next) {
if((k2 = next->key) < k) {
k = k2;
minNode = next;
}
compCount++;
}
}
/* We remove the minimum node from the heap but keep a pointer to it. */
r = minNode->rank;
trees[r] = NULL;
treeSum -= (1 << r);
child = minNode->child;
if(child) meld(child);
/* Record the vertex no of the old minimum node before deleting it. */
item = minNode->item;
nodes[item] = NULL;
delete minNode;
itemCount--;
#if FHEAP_DUMP
printf("deleteMin-exited, ");
#endif
return item;
}
/* --- decreaseKey() ---
* Decreases the key used for item $item$ to the value newValue. It is left
* for the user to ensure that newValue is in-fact less than the current value
*/
void FHeap::decreaseKey(int item, long newValue)
{
FHeapNode *cutNode, *parent, *newRoots, *r, *l;
int prevRank;
#if FHEAP_DUMP
printf("decreaseKey on vn = %d, ", item);
#endif
/* Obtain a pointer to the decreased node and its parent then decrease the
* nodes key.
*/
cutNode = nodes[item];
parent = cutNode->parent;
cutNode->key = newValue;
/* No reinsertion occurs if the node changed was a root. */
if(!parent) {
#if FHEAP_DUMP
printf("decreaseKey-exited
#endif
return;
}
/* Update the left and right pointers of cutNode and its two neighbouring
* nodes.
*/
l = cutNode->left;
r = cutNode->right;
l->right = r;
r->left = l;
cutNode->left = cutNode->right = cutNode;
/* Initially the list of new roots contains only one node. */
newRoots = cutNode;
/* While there is a parent node that is marked a cascading cut occurs. */
while(parent && parent->marked) {
/* Decrease the rank of cutNode's parent and update its child pointer.
*/
parent->rank--;
if(parent->rank) {
if(parent->child == cutNode) parent->child = r;
}
else {
parent->child = NULL;
}
/* Update the cutNode and parent pointers to the parent. */
cutNode = parent;
parent = cutNode->parent;
/* Update the left and right pointers of cutNodes two neighbouring
* nodes.
*/
l = cutNode->left;
r = cutNode->right;
l->right = r;
r->left = l;
/* Add cutNode to the list of nodes to be reinserted as new roots. */
l = newRoots->left;
newRoots->left = l->right = cutNode;
cutNode->left = l;
cutNode->right = newRoots;
newRoots = cutNode;
}
/* If the root node is being relocated then update the trees[] array.
* Otherwise mark the parent of the last node cut.
*/
if(!parent) {
prevRank = cutNode->rank + 1;
trees[prevRank] = NULL;
treeSum -= (1 << prevRank);
}
else {
/* Decrease the rank of cutNode's parent an update its child pointer.
*/
parent->rank--;
if(parent->rank) {
if(parent->child == cutNode) parent->child = r;
}
else {
parent->child = NULL;
}
parent->marked = 1;
}
/* Meld the new roots into the heap. */
meld(newRoots);
#if FHEAP_DUMP
printf("decreaseKey-exited
#endif
}
/*--- FHeap (private methods) --------------------------
/* --- meld() ---
* melds the linked list of trees pointed to by $treeList$ into the heap.
*/
void FHeap::meld(FHeapNode *treeList)
{
FHeapNode *first, *next, *nodePtr, *newRoot, *temp, *temp2, *lc, *rc;
int r;
#if FHEAP_DUMP
printf("meld: ");
#endif
/* We meld each tree in the circularly linked list back into the root level
* of the heap. Each node in the linked list is the root node of a tree.
* The circularly linked list uses the sibling pointers of nodes. This
* makes melding of the child nodes from a deleteMin operation simple.
*/
nodePtr = first = treeList;
do {
#if FHEAP_DUMP
printf("%d, ", nodePtr->item);
#endif
/* Keep a pointer to the next node and remove sibling and parent links
* from the current node. nodePtr points to the current node.
*/
next = nodePtr->right;
nodePtr->right = nodePtr->left = nodePtr;
nodePtr->parent = NULL;
/* We merge the current node, nodePtr, by inserting it into the
* root level of the heap.
*/
newRoot = nodePtr;
r = nodePtr->rank;
/* This loop inserts the new root into the heap, possibly restructuring
* the heap to ensure that only one tree for each degree exists.
*/
do {
/* Check if there is already a tree of degree r in the heap.
* If there is then we need to link it with newRoot so it will be
* reinserted into a new place in the heap.
*/
if((temp = trees[r])) {
/* temp will be linked to newRoot and relocated so we no
* longer will have a tree of degree r.
*/
trees[r] = NULL;
treeSum -= (1 << r);
/* Swap temp and newRoot if necessary so that newRoot always
* points to the root node which has the smaller key of the
* two.
*/
if(temp->key < newRoot->key) {
temp2 = newRoot;
newRoot = temp;
temp = temp2;
}
compCount++;
/* Link temp with newRoot, making sure that sibling pointers
* get updated if rank is greater than 0. Also, increase r for
* the next pass through the loop since the rank of new has
* increased.
*/
if(r++ > 0) {
rc = newRoot->child;
lc = rc->left;
temp->left = lc;
temp->right = rc;
lc->right = rc->left = temp;
}
newRoot->child = temp;
newRoot->rank = r;
temp->parent = newRoot;
temp->marked = 0;
}
/* Otherwise if there is not a tree of degree r in the heap we
* allow newRoot, which possibly carries moved trees in the heap,
* to be a tree of degree r in the heap.
*/
else {
trees[r] = newRoot;
treeSum += (1 << r);;
/* NOTE: Because newRoot is now a root we ensure it is
* marked.
*/
newRoot->marked = 1;
}
/* Note that temp will be NULL if and only if there was not a tree
* of degree r.
*/
} while(temp);
nodePtr = next;
} while(nodePtr != first);
#if FHEAP_DUMP
printf("meld-exited, ");
#endif
}
/*--- FHeap (debugging) --------------------------
/* --- dumpNodes() ---
* Recursively print a text representation of the node subtree starting at the
* node poined to by $node$, using an indentationlevel of $level$.
*/
void FHeap::dumpNodes(FHeapNode
{
#if FHEAP_DUMP
FHeapNode *childNode, *partner;
int i, childCount;
/* Print leading whitespace for this level. */
for(i = 0; i < level; i++) printf(" ");
printf("%d(%ld)[%d]\n", node->item, node->key, node->rank);
if((childNode = node->child)) {
childNode = node->child->right;
childCount = 0;
do {
dumpNodes(childNode, level+1);
if(childNode->dim > node->dim) {
for(i = 0; i < level+1; i++) printf(" ");
printf("error(dim)\n"); exit(1);
}
if(childNode->parent != node) {
for(i = 0; i < level+1; i++) printf(" ");
printf("error(parent)\n");
}
childNode = childNode->right;
childCount++;
} while(childNode != node->child->right);
if(childCount != node->dim) {
for(i = 0; i < level; i++) printf(" ");
printf("error(childCount)\
}
}
else {
if(node->dim != 0) {
for(i = 0; i < level; i++) printf(" ");
printf("error(dim)\n"); exit(1);
}
}
#endif
}
/* --- dump() ---
* Print a text representation of the heap to the standard output.
*/
void FHeap::dump() const
{
#if FHEAP_DUMP
int i;
FHeapNode *node;
printf("\n");
printf("treeSum = %d\n", treeSum);
printf("array entries 0..maxTrees =");
for(i = 0; i < maxTrees; i++) {
printf(" %d", trees[i] ? 1 : 0 );
}
printf("\n\n");
for(i = 0; i < maxTrees; i++) {
if((node = trees[i])) {
printf("tree %d\n\n", i);
dumpNodes(node, 0);
printf("\n");
}
}
fflush(stdout);
#endif
}
/*------------------------
#ifndef FHEAP_H
#define FHEAP_H
#include "heap.h" /* Defines the base class for heaps. */
/* Option to allow printing of debugging information. Use 1 for yes, or 0 for
* no.
*/
#define FHEAP_DUMP 0
/* --- FHeapNode ---
* Fibonacci heap node class.
*
* A nodes has the following pointers:
* parent - a pointer to the nodes parent node (if any).
* child - a pointer to a child node (typically the highest rank child).
* left, right - sibling pointers which provide a circular doubly linked list
* containing all the parents nodes children.
*
* The remaining fields are:
* rank - the nodes rank, that is, the number of children it has.
* key - the nodes key.
* item - the number of the item that the node is associated with.
*/
class FHeapNode {
public:
FHeapNode *parent;
FHeapNode *left, *right;
FHeapNode *child;
int rank;
int marked;
long key;
int item;
};
/* --- FHeap ---
* Fibonacci heap class.
*
* trees - An array of pointers to trees at root level in the heap. Entry i
* in the array points to the root node of a tree that has nodes of
* dimension i on the main trunk.
* nodes - An array of pointers to nodes in the heap. Nodes are indexed
* according to their vertex number. This array can then be used to
* look up the node for corresponding to a vertex number, and is
* useful when freeing space taken up by the heap.
* maxNodes - The maximum number of nodes allowed in the heap.
* maxTrees - The maximum number of trees allowed in the heap (calculated from
* maxNodes).
* itemCount - The current number of nodes in the heap.
* treeSum - The binary value represented by trees in the heap.
* By maintaining this it is easy to keep track of the maximum rank
* tree in the heap.
* compCount - can be used for experimental purposes when counting the number
* of key comparisons.
*/
class FHeap: public Heap {
public:
FHeap(int n);
~FHeap();
int deleteMin();
void insert(int item, long k);
void decreaseKey(int item, long newValue);
int nItems() const { return itemCount; }
long nComps() const { return compCount; }
void dump() const;
private:
FHeapNode **trees;
FHeapNode **nodes;
int maxNodes, maxTrees, itemCount, treeSum;
long compCount;
void meld(FHeapNode *treeList);
static void dumpNodes(FHeapNode *node, int level);
};
/*------------------------
#endif
# ifndef HEAP_H
# define HEAP_H
class Heap
{
public:
virtual ~Heap() { };
virtual int deleteMin() = 0;
virtual void insert(int item, long key) = 0;
virtual void decreaseKey(int item, long newKey) = 0;
virtual int nItems() const = 0;
virtual long nComps() const = 0;
};
class HeapDesc
{
public:
virtual ~HeapDesc() { };
virtual Heap *newInstance(int n) const = 0;
};
template <class T>
class HeapD: public HeapDesc
{
public:
Heap *newInstance(int n) const { return new T(n); };
};
#endif
I have files dijkstra.h and dgraph.h...
I have Visual.Net compiler 7.0 . When I compile I get errors in fheap.cpp
fheap.cpp(26): error C2143: syntax error : missing ';' before '['
fheap.cpp(26): error C2337: 'maxTrees' : attribute not found; it is neither a built-in nor a custom attribute that is accessible in the current namespace
fheap.cpp(29): error C2337: 'n' : attribute not found; it is neither a built-in nor a custom attribute that is accessible in the current namespace
and I have no clue what to correct.....
Thanx
Harsimrat
The same applies for the line
nodes = new (FHeapNode *)[n];
nodes = FHeapNode[n];
To look for additional errors the file dgraph.h is missing.
nodes = new (FHeapNode *)[n];
nodes = FHeapNode[n];
To look for additional errors the file dgraph.h is missing.
ASKER
Steh
after doing that I get these errors
fheap.cpp(23): error C2440: '=' : cannot convert from 'FHeapNode *' to 'FHeapNode ** '
Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast
I have dgraph.h...if you want I can post all the files I have.......
Thanx
Harsimrat
after doing that I get these errors
fheap.cpp(23): error C2440: '=' : cannot convert from 'FHeapNode *' to 'FHeapNode ** '
Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast
I have dgraph.h...if you want I can post all the files I have.......
Thanx
Harsimrat
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
trees = new (FHeapNode *)[maxTrees];
trees: variable for storage
new is creating some object on the heap:
(FHeapNode*) is a C-style cast
[maxTrees] is an array size.
I guess you meant
trees = new FHeapNode[maxTrees];