# 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++)
{

while(edge) {
nextEdge = edge->nextOut;
delete edge;
edge = nextEdge;
}
}
initVertices();
}

void DGraph::initVertices()
{
for(int i = 0; i < nVertices; i++)
{
vertices[i].outSize = vertices[i].inSize = 0;
}
}

// 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->outTail = newEdge ;
vertex->outSize++ ;

vertex = &vertices[target];
if(vertex->inTail)
{
vertex->inTail->nextIn = newEdge;
}
else
{
}

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

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++;

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);
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);
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

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

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

###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
Hi,

Sorry, I'm personally not good enough at C++ to answer this Q, however, you can request for this question to be moved to the C++ section (http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/).
You're must more likely to get a better and faster solution in that topic area than just here. :-)

Either way, good luck with it!
[r.D]
0
Commented:
Typically, when asking compiler error questions, one provides some basic information:

The compiler error
Where it appears (mark the source code you provided)
The version of the compiler
What you think it means

These pieces let someone with more experience zero in on the problem without having to reconstruct your project and attempt to compile it (and even then, get it to compile because they use a different compiler or set up the project differently).

-bcl
0
Commented:
As far as I can see there are some missing files:
- dijskstra.h
- dgraph.h

Bcl is right though. Instead of posting the entire project it would be better to specify the compiling errors and the framework you are working with.

Regards,
Bogdan
0
Author Commented:
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
0
Commented:
Check this line

vertices = new DGraphVertex[n];

I think it should be
vertices = new DGraphVertex(n);

Have you included the files dijkstra.h and dgraph.h and recompiled?

mlmcc
0
Commented:
mlmcc -
Without the header file this might be shooting in the dark but vertices certainly seems to be a collection of the vertices in the graph. As the delete uses the array version in the DGraph destructor, I would assume that using the array version of new would be appropriate. Just my read of the material presented. Near as I can figure, lines 26-29 of fheap.cpp are

trees = new (FHeapNode *)[maxTrees];
for(i = 0; i < maxTrees; i++) trees[i] =0;

nodes = new (FHeapNode *)[n];

And the first problem is on the first line. I don't know the solution but the first problem is a problem with (FHeapNode *) as a type for array new. One possible suggestion would be a typedef for the type. The second error is related to the first and I think the third is fundamentally the same as the first. At least that is how I read the errors and the post.

-bcl
0
Author Commented:
mlmcc-

I have all the files required....These are the list I have....I only posted some...If you want can post all.

Dijkstra.cpp,Dijkstra.h,dgraph.cpp,dgraph.h,fheap.cpp,fheap.h and for fheap the base class heap.h.

bcl--

When I change it to typedef....it says typedef keyword not permitted in cast...

Thanx

Harsimrat
0
Commented:
How about putting the typedef right after the definition of FHeapNode:

typedef FHeapNode * FHeapNodePtr;

Then try new with the typedef'd type:

trees = new FHeapNodePtr[maxTrees];

I am not sure this will fix the problem. In fact it should not be any different than what you already have. Try it and let us know.

-bcl
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Author Commented:

bcl--

I changed like this

typedef FHeapNode * FHeapNodePtr;

trees = new FHeapNodePtr [maxTrees];
for(i = 0; i < maxTrees; i++) trees[i] =0;

nodes = new FHeapNodePtr [n];
for(i = 0; i < n; i++) nodes[i] = 0;

it compiles not but gets stuck on the linker

Dijkstra's Algorithm with heaps error LNK2019: unresolved external symbol _main referenced in function _mainCRTStartup

What does this mean.....Thanx for your help

Thanx

Harsimrat
0
Author Commented:
This is the error I'm getting when I'm trying to compile...I think it compiles file but in linking it has this error.

LIBCD.lib(wincrt0.obj) : error LNK2019: unresolved external symbol _WinMain@16 referenced in function _WinMainCRTStartup
Debug/Dijkstra.exe : fatal error LNK1120: 1 unresolved externals.

Thanx

Harsimrat
0
Author Commented:
bcl--

Thanks it works...
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Java

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.