Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   C++ (http://www.programmingforums.org/forum15.html)
-   -   STL priority queue structure question (http://www.programmingforums.org/showthread.php?t=7160)

dayrinni Nov 23rd, 2005 9:18 PM
STL priority queue structure question
 
I am trying to use a PQ with a structure, VERTEX.

Here is the code for VERTEX:

:
struct edge
{
        int start; //contains the indexs to the vertices
        int end;
        int cost;
};

typedef edge EDGE;
struct vertex
{
        vector<EDGE> edgeList;
        int cost;

        int operator==(const vertex &rhs) const
        {
                if( this->cost != rhs.cost) return 0;
                 
                return 1;
        }

        int operator<(const vertex &rhs) const
        {
                if( this->cost < rhs.cost)
                        return 1;
                return 0;
        }
       

        vertex& operator=(const vertex &rhs) const
        {

        }


};

typedef vertex VERTEX;

I am have several problems with using VERTEX in my priority queue.

1.) I need to write several functions to overload my ==. = and > operators. I believe I have done this correctly, but I am not too sure, I also cannot seem to write the '=' one.

2.) When I do the declaration priority_queue<VERTEX> pq;

it compiles. However, I begin having problems when I push elements into the que, for example:
The vertex information before the push is:
:
displayVertex(vertList[0]);
        pq.push(vertList[0]);
Vert has 2 edges, with a cost of: 0.
Then, when I do the following:
:
vert = pq.top();
        displayVertex(vert);
the output is this:
Vert has 0 edges, with a cost of: 0.

vertList is a list of the vertices, in an array. I have checked the contents of this before pushing the elements and they are correct.

It seems that somehow, something is being lost and I am not entirely sure why, or how. If anyone could explain this to me, that'd be great.

Thank you for any of your help, I have included the code under this so you can look at it. It has been cleaned up, so it should be easy to read.

Thanks

:
//a program
#include <iostream>
#include <stdio.h>
#include <ctime>
#include <vector>
#include <queue>
#include "stdlib.h"
using namespace std;


struct edge
{
        int start; //contains the indexs to the vertices in vertList
        int end;
        int cost;
};

typedef edge EDGE;

struct vertex
{
        vector<EDGE> edgeList;
        int cost;

        int operator==(const vertex &rhs) const
        {
                if( this->cost != rhs.cost) return 0;
                 
                return 1;
        }

        int operator<(const vertex &rhs) const
        {
                if( this->cost < rhs.cost)
                        return 1;
                return 0;
        }
       

        vertex& operator=(const vertex &rhs) const
        {

        }


};

typedef vertex VERTEX;

#define        NO_LENGTH        -1


//function definitions
void    initialize(int vertices, int edges);
void        displayEdge(EDGE *edge);
void        displayVertices(VERTEX *vertList, int vertices);
void        displayAll(VERTEX *vertList, int vertices);
void        dijkstras(VERTEX *vertList, int vertices, int edges);
void        displayVertex(VERTEX vertex);

int main(int argc, char *argv[])
{
        int vertices;
        int edges;

        cin >> vertices;
        cin >> edges;



        initialize(vertices, edges);

}

void initialize(int vertices, int edges)
{
        //make an array of vertices.
        VERTEX *vertList = new VERTEX[vertices];               
        int i = -1;

        printf("Initialize: About to load in the files.\n\r");



        //load the edges into the array of vertices.
        while(++i <= edges-1)
        {

                EDGE newEdge;



                cin >> newEdge.start;
                cin >> newEdge.end;
                cin >> newEdge.cost;


                if(vertList[newEdge.start].edgeList.size() == 0)
                {
                        VERTEX *newVertex = new VERTEX;

                        vertList[newEdge.start] = *newVertex;

                }
                if(vertList[newEdge.end].edgeList.size() == 0)
                {
                        VERTEX *newVertex = new VERTEX;

                        vertList[newEdge.end] = *newVertex;


                }

               
                //add the 2 edges
                vertList[newEdge.start].edgeList.push_back(newEdge);

                vertList[newEdge.end].edgeList.push_back(newEdge);
        }


        printf("Initialize: File loaded!\n\r");

        displayAll(vertList, vertices);


        dijkstras(vertList, vertices, edges);

}


void dijkstras(VERTEX *vertList, int vertices, int edges)
{
        priority_queue<VERTEX> pq;
        VERTEX vert;
        int i;


        //init the list
        vertList[0].cost = 0;
        for(i=1;i < vertices;i++)
                vertList[i].cost = NO_LENGTH;

        //display to see if they are all right
        displayAll(vertList, vertices);

        //test vertex
        displayVertex(vertList[0]);
        pq.push(vertList[0]);
        vert = pq.top();
        displayVertex(vert);

/*        //put the whole vertLst into the que.
        for(i=0;i<vertices;i++)
        {
                pq.push(vertList[i]);
        }
               

        //display the que
        for(i=0;i<vertices;i++)
        {
                VERTEX vert;

                vert = pq.top();
                displayVertex(vert);
                pq.pop();
        }
*/


}

void displayEdge(EDGE *edge)
{

        if(edge)
        {
                printf("Start: %d. End: %d. Cost: %d\n\r", edge->start, edge->end, edge->cost);
        }
        else
                printf("NULL EDGE!\n\r");
}


void displayVertex(VERTEX vertex)
{
        printf("Vert has %d edges, with a cost of: %d.\n\r",
        vertex.edgeList.size(), vertex.cost);
}

void displayVertices(VERTEX *vertList, int vertices)
{
        int i;

        for(i = 0;i<vertices;i++)
        {
                if(vertList[i].edgeList.size() != 0)
                {
                        printf("Vert %d has %d edges, with a cost of: %d.\n\r", i,
                        vertList[i].edgeList.size(), vertList[i].cost);
                }
        }


}

void displayAll(VERTEX *vertList, int vertices)
{
        int i;

        for(i = 0;i<vertices;i++)
        {
                if(vertList[i].edgeList.size() != 0)
                {
                        int j;
                        printf("Vert %d cost: %d,  has these edges:\n\r", i,
                        vertList[i].cost);
                        for(j = 0; j < vertList[i].edgeList.size(); j++)
                        {
                                printf("Edge %d: Start: %d. End: %d. Cost: %d\n\r",
                                j,
                                vertList[i].edgeList[j].start,
                                vertList[i].edgeList[j].end,
                                vertList[i].edgeList[j].cost);
                        }
                        printf("-------------\n\r");
                }

        }


}

DaWei Nov 23rd, 2005 9:56 PM
I haven't really looked at your post in detail, because I'm cooking. I can recommend this for material on overloading operators. Very good.

dayrinni Nov 23rd, 2005 10:02 PM
I am not using classes though and I'm not entirely sure how to do it with structures, and then have the PQ recognize that they are overloaded, or in general.

I have tried to do as described above, then have a > b, but that doesn't seem to be working either.

If you have any websites for structures, that'd be great!

DaWei Nov 23rd, 2005 10:12 PM
In C++, a structure and a class are the same thing. The difference is that class members are, by default, private. Structure members are, by default, public. The fact that you haven't written any "methods" for the structure is totally immaterial to the underlying situation.

Animatronic Nov 23rd, 2005 10:25 PM
I havent checked it all just what I think is going wrong.

The compiler will always try to generate the standard operators for you, unless you define your own.

With a simple POD (plain old data) structure like yours the compiler generated = operator should work fine. But you have defined your own = operator that does nothing, so bits in your code like this:

:
vert = pq.top();

are just using the empty operator and nothing is really being copied. Either have another look at the article Dawei posted or get rid of your = operator and let the compiler do it for you.

dayrinni Nov 23rd, 2005 10:51 PM
DOH!!!!

Thank you to the both of you. I removed the one I wrote and it works now LOL. I can go and finish up the rest of the program now.

I am thankful that it was something stupid that was occuring.

I will try to play around with structures in C++ since you said it doesn't matter. I find that very interesting.

Thank you again guys. I'll post again if I have problems.

I do have another quick question - how do I make the que sort from least to most? In the default mode it is from highest to lowest.

Thanks


All times are GMT -5. The time now is 10:31 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC