[Last Call] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 693
  • Last Modified:

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

0
hthukral
Asked:
hthukral
  • 3
1 Solution
 
SteHCommented:
The following line is missing a class to create:
    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];
0
 
SteHCommented:
The same applies for the line
    nodes = new (FHeapNode *)[n];

nodes = FHeapNode[n];

To look for additional errors the file dgraph.h is missing.
0
 
hthukralAuthor Commented:
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
0
 
SteHCommented:
In that case you need to define a variable type FHeapNode* like

typedef FHeapNode* pFHeapNode;
trees = new pFHeapNode[maxTrees];
nodes = new pFHeapNode[n];
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now