0

I've been working on a problem which involves an size-N square matrix maze with N^2 nodes and 2N(N-1) edges connecting vertical and horizontal neighbours. The codes are as follows:

//Node.h
#pragma once
#define NULL 0
using namespace std;
class Edge;
class Node {
public:
    int id, row, col;
    Edge* EL, * ER, * EU, * ED;
    vector<int> connected;

    Node(int id, int row, int col);
    Node* get_L();
    Node* get_R();
    Node* get_U();
    Node* get_D();
    void print();
};

//Edge.h
#pragma once
#include "Node.h"
class Edge {
public:
    int id, type;
    bool state;
    Node* N1, * N2;

    Edge(int id, Node n1, Node n2, int type);
    void setState(bool b);
    void print();
};

//Maze.h
#pragma once
#include <vector>
#include "Node.h"
#include "Edge.h"
using namespace std;
class Maze {
public:
    int size;
    vector<Node> nodes;
    vector<Edge> edges;
    Maze(int N);
    void print();
};

//main.cpp
#include <iostream>
#include <vector>
#include "Node.h"
#include "Edge.h"
#include "Maze.h"
Node::Node(int id, int row, int col) {
    this->id = id;
    this->row = row;
    this->col = col;
    this->EL = NULL;
    this->ER = NULL;
    this->EU = NULL;
    this->ED = NULL;
}

Node* Node::get_L() {
    if (EL) {
        return EL->N1;
    }
    else {
        cerr << "Node " << id << "does not have left neighbour.";
    }
}

Node* Node::get_R() {
    if (ER) {
        return ER->N2;
    }
    else {
        cerr << "Node " << id << "does not have right neighbour.";
    }
}

Node* Node::get_U() {
    if (EU) {
        return EU->N1;
    }
    else {
        cerr << "Node " << id << "does not have up neighbour.";
    }
}

Node* Node::get_D() {
    if (ED) {
        return ED->N2;
    }
    else {
        cerr << "Node " << id << "does not have down neighbour.";
    }
}

void Node::print() {
    int l, r, u, d;
    l = EL ? EL->N1->id : -1;
    r = ER ? ER->N2->id : -1;
    u = EU ? EU->N1->id : -1;
    d = ED ? ED->N2->id : -1;
    cout << "Node " << id << " (Row " << row << " Col " << col << "), neighbours <L,R,U,D>: <" << l << "," << r << "," << u << "," << d << ">" << endl;
}

Edge::Edge(int id, Node n1, Node n2, int type) {
    this->id = id;
    this->N1 = &n1;
    this->N2 = &n2;
    this->state = false;
    this->type = type;
}

void Edge::print() {
    if (type == 0) {
        cout << "Horizontal ";
    }
    else {
        cout << "Vertical ";
    }
    cout << "edge " << id << " between <" << N1->id << ", " << N2->id << ">, " << state << endl;
}

void Edge::setState(bool b) {
    this->state = b;
}

Maze::Maze(int N) {
    size = N;

    for (int i = 0; i < N * N; ++i) {
        Node n = Node(i, i / N, i % N);
        nodes.push_back(n);
    }
    int eid = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N - 1; ++j) {
            Node n1 = nodes[i * N + j];
            Node n2 = nodes[i * N + j + 1];
            Edge e = Edge(eid, n1, n2, 0);
            /*
            // &n1 and &n2 retain the same throughout the loop
            cout << &n1 << endl;
            cout << &n2 << endl;
            cout << e.N1->id << "," << e.N2->id << endl;    // This line gives correct result
            e.print();  // Incorrect
            */
            n1.ER = &e;
            n2.EL = &e;
            edges.push_back(e);
            eid++;
        }
    }
    cout << nodes[0].ER << endl;
    for (int i = 0; i < N - 1; ++i) {
        for (int j = 0; j < N; ++j) {
            Node n1 = nodes[i * N + j];
            Node n2 = nodes[i * N + j + 1];
            Edge e = Edge(eid, n1, n2, 1);
            n1.ED = &e;
            n2.EU = &e;
            edges.push_back(e);
            eid++;
        }
    }
}

void Maze::print() {
    cout << size << " x " << size << " Maze" << endl;
    cout << nodes.size() << " nodes:" << endl;
    for (auto& i : nodes) {
        i.print();
    }
    cout << edges.size() << " edges:" << endl;
    for (auto& i : edges) {
        i.print();
    }
}

int main()
{
    Maze m = Maze(8);
    m.print();
}

However after compiling and running I found out that the nodes and edges are NOT connected to each other as I expected. In the codes of creating edges I tried to figure out the reason (see the commented part), I found that in the entire loop, the addresses of n1 and n2 always retain the same. Still have no idea why this is happening. Please help.

  • About [using namespace std](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... – Aconcagua Oct 16 '19 at 07:56
  • You should get used to the constructor's initialiser list (`Node(...) : id(id), row(row), ... { }`, you avoid default initialisation + assignment in favour of direct value initialisation. Be aware that some types (non-default-constructible ones, constant members or references) *only* can be initialised that way. Additionally, prefer C++ *keywords* (`nullptr`) over old (obsolete?) C *macros* (`NULL`). – Aconcagua Oct 16 '19 at 07:59
  • Have a look at your node getters (all of!): You do not return if there's no neighbour. Make sure that no matter how you traverse through the function you always return something (e. g. `nullptr` in the else branch), otherwise you end up in undefined behaviour. – Aconcagua Oct 16 '19 at 08:03
  • Ugh screw it.. I tried answering, but just felt dirty in the end. Maybe OP should back off on the heavy pointer usage. There's no need to go crazy on this stuff when simple arrays and indices would suffice for a graph. – paddy Oct 16 '19 at 08:08
  • Pretty heavy design for rather simple problem... Why do you need all those edges? Nodes can refer to their neighbours directly by pointer to other nodes – if you need them at all, you always could calculate the neighbours from col and row as well. Are you going to reflect a wall being in between two nodes by not setting the pointers? – Aconcagua Oct 16 '19 at 08:14
  • 1
    As @paddy didn't restore his answer: You are creating pointers to variables with local storage duration several times (function parameters are as well!) which get dangling as soon as the variables run out of scope, and using them afterwards results in undefined behaviour. – Aconcagua Oct 16 '19 at 08:19
  • `#define NULL 0` Don't do that. Make every header *self-sufficient*, that is, a source file that only includes your header and nothing else should compile cleanly. – n. m. could be an AI Oct 16 '19 at 10:17
  • @Aconcagua Thank you very much for your comments and suggestions! However I still cannot figure out where exactly did I create pointers to variables with local duration (or I'm not quite clear on the scopes of variables, I'm just a C++ beginner). I tried to call print() during the call of Edge constructors and it works fine. How should I modify the programme with the above design to make it valid? – user3458994 Oct 16 '19 at 14:05
  • Simple example: `class C { }; void f(C c) { C d; }` – note that both `c` and `d` are neither references nor pointers. Thus you create two objects that only exist as long as you are in the scope of the function. References or pointers to these get invalid as soon as the function exits, using them results in undefined behaviour (and this applies, too, if you *return* pointers or references to such objects). – Aconcagua Oct 16 '19 at 14:18

0 Answers0