help with c++ classes, pointers n such

Question

I have a project where I'm implementing Dijkstra's shortest path algorithm using C++ classes. It uses OpenGL but that is surely separate from my problems. I need some insight on what I'm doing wrong in my Dijkstra class method. Here is my relevant code:

class Node {
    public: 
        GLfloat x, y, z;
        int numLinks;
        Node *link1;
        Node *link2;
        GLfloat distance;
        Node *previous;

        Node(GLfloat x, GLfloat y, Node *link1, Node *link2);
        Node(GLfloat x, GLfloat y, Node *link1);
        Node();
        Node(GLfloat x, GLfloat y);
        ~Node();

        bool dijkstra(Node* graph[], Node *source, Node *target); //returns true if a path to target is found
        int dist(Node &n1, Node &n2);
};

int Node::dist(Node &n1, Node &n2) {
    GLfloat d = sqrt((pow((n2.x - n1.x), 2)) + (pow((n2.y - n1.y), 2)));
    return d;
}

bool Node::dijkstra(Node* graph[], Node *source, Node *target) {
    queue<Node> q;
    int i;
    for (i = 0; i < NUM_NODES; i++) {
        graph[i]->distance = INFIN;
    }
    source->distance = 0;   
    i = 0;
    q.push(*source);
    while (!q.empty()) {
        Node temp = q.front();

        GLfloat d1 = dist(temp, temp->link1);
        GLfloat d2 = dist(temp, temp->link2);
        temp.link1.distance = d1;
        temp.link1.distance = d2;

        GLfloat alt = temp.distance + temp->link1.distance;
        if (alt < temp->link1.distance) {
            temp->link1.distance = alt;
            temp->previous = temp;
        }

        alt = temp->distance + temp->link2->distance;
        if (alt < temp->link2->distance) {
            temp->link2->distance = alt;
            temp->previous = temp;
        }

        if(d1 > d2) {
            q.push(temp->link2);
            q.push(temp->link1);
        } else {
            q.push(temp->link1);
            q.push(temp->link2);
        }
        q.pop();
        i++;
    }

    return true;
}

My guess is that I'm using "->" and "." operators all wrong. I get a lot of these errors when I try to compile:

error: base operand of ‘->’ has non-pointer type ‘Node’

My implementation of Dijkstra's algorithm is somewhat retrofitted to meet my needs and is probably wrong, but I need this to compile so I can debug it.

The code listed is the only code giving me grief but if you would like to see another part of it just ask. A good explanation of what im doing wrong will be greatly appreciated.

Dijkstra's algorithm is not your immediate problem. You might want to pick up a good C++ book and familiarize yourself with the basics first. It will surely help you along and solve most of the problems you're experiencing. — Bart, Jul 17 '11 at 18:42
[The books that Bart was referring to](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) — Benjamin Lindley, Jul 17 '11 at 18:50

score 0 · Accepted Answer · answered Jul 17 '11 at 18:52

0

You should use the '->' operator when accessing data through a pointer. Otherwise you should use the '.' opearator.

For example these following lines are identical

Node *node = &q.front();

(*node).link1->distance = 1;
node1->link1->distance = 1;

As for your compilation problems, the problem is with how you are accessing temp. temp is declaired as

Node temp = q.front();

Which means that temp is a copy of the node at the front of the queue and is not a pointer to it. This is why the compiler is complaining when you attempt to access it like it is a pointer. For example:

temp->link1.distance = alt;

should look like

temp.link1->distance = alt;

because temp is not a pointer but link1 is.

answered Jul 17 '11 at 18:52

xunil154

527
3
6

Yeah i figured that out and got it to compile, but one quick question if you dont mind, by making a copy of q.front(), will that mean that anything I do to temp is not going to propagate to whatever is at q.front()? – Matt Jul 17 '11 at 19:05
That is correct, q.front() will return a copy of the front of the queue, so any changes made to it will not reflect on the internal copy on the queue. If you had a queue of pointers to objects, then q.front() would point you to the actual object that would get modified. If you go this route, don't forget to free your memory once you are done if necissary. – xunil154 Jul 17 '11 at 19:09

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

Some Questions on your design:

`dijkstra` really a method that can be applied to a node?

It seems that this is an operation that is applied to a graph as a whole.

class Graph
{
    std::vector<NodeId> dijkstra(NodeId const& start, NodeId const& target);
};

What is `previous`?

The node seems to have some internal pointer that is just used for the algorithm Node *previous; The node should not contain this type of information.

Line1/Link2

Does this mean the nodes can only link to two other nodes. Does not seem like this is a graph but more like a tree?

class Node
{
    std::vector<LinkId>   links;
};

So my starting point would be:

class Graph
{
    class Link
    {
          NodeId   src;
          NodeId   dst;
          float    dist; // only calculate once for each link
    };
    class Node
    {
          float   x,y;
          std::vector<boost::shard_ptr<Link> >   links;
    };
    typedef  std::vector<Node>   GraphContainer;
    GraphContainer   graphPoints;

    public:
       typedef GraphContainer::size_type  NodeId;

       NodeId   addNode(float x, float y);
       void     link(NodeId& p1, NodeId& p2);

       std::vector<NodeId> dijkstra(NodeId const& start, NodeId const& target);
};

Now it should be a lot simpler to write cleanly.

help with c++ classes, pointers n such

2 Answers2

dijkstra really a method that can be applied to a node?

What is previous?

Line1/Link2

So my starting point would be:

`dijkstra` really a method that can be applied to a node?

What is `previous`?