c++ Navigating a "Maze" of Nodes mysterious error

Question

I have an issue that I can't seem to figure out. Below is all of my code detailing two classes System and Node. What I am creating is a program that reads in a file and creates a "maze" (map rooms) of Nodes and then navigates from a specified starting node to a specified ending node.

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <sstream>
#include <array>
#include <map>
#include <stack>
#include <queue>
using namespace std;

class Node
{
   public:
      Node(string newName);
      Node();
      void setNodeName(string newName);
      string getNodeName();
      void attachNewNode(Node *newNode, int direction);
      Node *getAttachedNode(int direction);
      bool visited;
   private:
      string name;
      Node *attachedNodes[4];
};

Node::Node(string newName)
{
   name = newName;
   visited = false;
}

Node::Node()
{
   visited = false;
}

void Node::setNodeName(string newName)
{
   name = newName;
}

string Node::getNodeName()
{
   return name;
}

void Node::attachNewNode(Node *newNode, int direction)
{
   attachedNodes[direction] = newNode;
}

Node* Node::getAttachedNode(int direction)
{
   return attachedNodes[direction];
}

The node file format is as specified here:

9
A1
C3
A1 A2 B1 * *
A2 * B2 A1 *
A3 * B3 * *
B1 * * * A1
B2 B3 C2 * A2
B3 * * B2 A3
C1 C2 * * *
C2 C3 * C1 B2
C3 * * C2 *

Where 9 is the number of nodes to be created, A1 is the node we will begin navigation from, C3 is the node we will try to find a path to, and the following lines represent the nodes themselves and the pointers they have associated with them. For example:

A1 A2 B1 * *

represents node A1 has pointers to node A2 in the north, B1 in the east, null in the south, and null in the west.

A2 * B2 A1 *

represents node A2 has pointers to node null in the north, B2 in the east, A1 in the south, and null in the west.

The Maze file I am using title "maze1.txt" is as follows:

48 
A1 
H6 
A1 A2 B1 * * 
B1 B2 * * A1 
C1 C2 * * * 
D1 D2 E1 * * 
E1 * * * D1 
F1 F2 * * * 
G1 G2 H1 * * 
H1 * * * G1 
A2 A3 * A1 * 
B2 * C2 B1 * 
C2 * D2 C1 B2 
D2 D3 * D1 C2 
E2 E3 * * * 
F2 F3 G2 F1 * 
G2 * H2 G1 F2 
H2 H3 * * G2 
A3 * B3 A2 * 
B3 B4 * * A3 
C3 C4 D3 * * 
D3 * E3 D2 C3 
E3 * * E2 D3 
F3 F4 * F2 * 
G3 G4 * * * 
H3 H4 * H2 * 
A4 A5 B4 * * 
B4 B5 * B3 A4 
C4 * D4 C3 * 
D4 * E4 * C4 
E4 E5 F4 * D4 
F4 * G4 F3 E4 
G4 * * G3 F4 
H4 H5 * H3 * 
A5 A6 * A4 * 
B5 * C5 B4 * 
C5 C6 D5 * B5 
D5 * * * C5 
E5 E6 F5 E4 * 
F5 * * * E5 
G5 G6 H5 * * 
H5 * * H4 G5 
A6 * B6 A5 * 
B6 * * * A6 
C6 * * C5 * 
D6 * E6 * * 
E6 * F6 E5 D6 
F6 * * * E6 
G6 * H6 G5 * 
H6 * * * G6

As of yesterday, the code for buildGraph() worked and correctly supplied me with a map rooms of nodes and their respective string keys.

class System
{
   public:
      System();
      void displayWelcome();
      void displayExit();
      void buildGraph(string filename);
      string getFileName();
      string getPath();
      map<string,Node> rooms;
      void printMap(map<string,Node> nodes);
      bool canMove(string currentNode);
      string move(string currentNode);
      Node startNode;
      Node endNode;
      Node empt;
   private:
      int numNodes;
};

System::System()
{
    empt.setNodeName("null");
}

void System::displayWelcome()
{
   cout << endl;
   cout << "========================================================" << endl;
   cout << "|      Welcome to the Automatic Maze Path Finder!      |" << endl;
   cout << "========================================================" << endl;
   cout << endl;
}

void System::displayExit()
{
   cout << "========================================================" << endl;
   cout << "|  Thank you for using the Automatic Maze Path Finder! |" << endl;
   cout << "========================================================" << endl;
   cout << endl;
}

void System::buildGraph(string filename)
{
   ifstream instream;
   instream.open(filename.c_str());
   string line;
   string data;
   int numLines = 1;
   int skipBlanks = 1;
   int numNodes;

   while(getline(instream, line))
   {
      if(line.empty() || line.length() < 2)
      {}
      else
      {
         istringstream iss(line);

         if(numLines == 1)
         {
            istringstream buffer(line);
            buffer >> numNodes;
            skipBlanks++;
         }
         if(numLines == 2)
         {
            startNode.setNodeName(line);
            skipBlanks++;
            //cout << "start node is: " << startNode.getNodeName() << endl;
         }
         if(numLines == 3)
         {
            endNode.setNodeName(line);
            skipBlanks++;
            //cout << "end node is: " << endNode.getNodeName() << endl;
         }

         if(numLines > 3 && skipBlanks > 3)
         {
            Node temp;
            string nodeName = line.substr(0,2);

            //cout << "Line number: " << numLines << "  nodeName: " << nodeName << endl;

            rooms[nodeName] = temp;
            rooms[nodeName].setNodeName(nodeName);
         }

         numLines++;
         iss.clear();
      }
   }   

   ifstream nextstream;
   nextstream.open(filename.c_str());
   numLines = 1;
   skipBlanks = 1;

   cout << endl;

   while(getline(nextstream, line))
   {
      if(line.empty() || line.length() < 2)
      {}
      else
      {
         istringstream iss(line);

         if(numLines == 1)
            skipBlanks++;
         if(numLines == 2)
            skipBlanks++;
         if(numLines == 3)
            skipBlanks++;

         if(numLines > 3 && skipBlanks > 3)
         {
            string thisNode = line.substr(0,2);

            int first = line.find(" ", 0);
            int second = line.find(" ", first + 1);
            int third = line.find(" ", second + 1);
            int fourth = line.find(" ", third + 1);

            string firstNode = line.substr(first+1,2);
            string secondNode = line.substr(second+1,2);
            string thirdNode = line.substr(third+1,2);
            string fourthNode = line.substr(fourth+1,2);

            cout << "Line contains: " << line << endl;
            cout << "Current Node: " << thisNode << endl;
            cout << "firstNode:  -" << firstNode << endl;
            cout << "secondNode: -" << secondNode << endl;
            cout << "thirdNode:  -" << thirdNode << endl;
            cout << "fourthNode: -" << fourthNode << endl << endl;

            for(map<string,Node>::iterator thing = rooms.begin(); thing != rooms.end(); thing++)
            {
               if(thing->second.getNodeName() == rooms[thisNode].getNodeName())
               {
                  if(firstNode != "* " && firstNode != " *" && firstNode != "*")
                     thing->second.attachNewNode(&rooms[firstNode],1);
                  else
                  {
                     thing->second.attachNewNode(&empt,1);
                  }
                  if(secondNode != "* " && secondNode != " *" && secondNode != "*")
                     thing->second.attachNewNode(&rooms[secondNode],2);
                  else
                  {
                     thing->second.attachNewNode(&empt,2);
                  }
                  if(thirdNode != "* " && thirdNode != " *" && thirdNode != "*")
                     thing->second.attachNewNode(&rooms[thirdNode],3);
                  else
                  {
                     thing->second.attachNewNode(&empt,3);
                  }
                  if(fourthNode != "* " && fourthNode != " *" && fourthNode != "*")
                     thing->second.attachNewNode(&rooms[fourthNode],4);
                  else
                  {
                     thing->second.attachNewNode(&empt,4);
                  }
               }
            }
         }

         numLines++;
         iss.clear();
      }
   }
   cout << "Exiting buildGraph()" << endl << endl;
}

string System::getFileName()
{
   string filename;

   cout << "Enter the name of the Maze configuration file: ";
   cin >> filename;
   cout << endl;

   return filename + ".txt";
}

string System::getPath()
{
   string path;
   stack<string> pathNodes;
   string currentNode = startNode.getNodeName();

   cout << "added startNode" << endl;
   pathNodes.push(startNode.getNodeName());

   while(currentNode != endNode.getNodeName())
   {
      if(canMove(currentNode))
      {
         currentNode = move(currentNode);
         pathNodes.push(rooms[currentNode].getNodeName());
      }
      else
      {
         while(!canMove(currentNode))
         {
            pathNodes.pop();
            currentNode = pathNodes.top();
         }
      }
   }

   for(int i = 0; i < pathNodes.size(); i++)
   {
      path += pathNodes.top() + " ";
      pathNodes.pop();
   }

   return path;
}

void System::printMap(map<string,Node> nodes)
{
   cout << endl << "The nodes in the current map are:" << endl;
   for(map<string,Node>::iterator it = nodes.begin(); it != nodes.end(); it++)
   {
      cout << "current node: " << it->second.getNodeName() << endl;
      if(it->second.getAttachedNode(1)->getNodeName().length() < 3)
         cout << it->second.getAttachedNode(1)->getNodeName() << endl;
      if(it->second.getAttachedNode(2)->getNodeName().length() < 3)
         cout << it->second.getAttachedNode(2)->getNodeName() << endl;
      if(it->second.getAttachedNode(3)->getNodeName().length() < 3)
         cout << it->second.getAttachedNode(3)->getNodeName() << endl;
      if(it->second.getAttachedNode(4)->getNodeName().length() <  3)
         cout << it->second.getAttachedNode(4)->getNodeName() << endl;
   }
   cout << endl;

   cout << "Exited for in printMap." << endl << endl;
}

bool System::canMove(string currentNode)
{
   if(!rooms[currentNode].getAttachedNode(1)->visited ||\
      !rooms[currentNode].getAttachedNode(2)->visited ||\
      !rooms[currentNode].getAttachedNode(3)->visited ||\
      !rooms[currentNode].getAttachedNode(4)->visited)
         return true;

   return false;
}

string System::move(string currentNode)
{
   string newSpot;

   if(!rooms[currentNode].getAttachedNode(1)->visited)
      newSpot = rooms[currentNode].getAttachedNode(1)->getNodeName();
   if(!rooms[currentNode].getAttachedNode(2)->visited)
      newSpot = rooms[currentNode].getAttachedNode(2)->getNodeName();
   if(!rooms[currentNode].getAttachedNode(3)->visited)
      newSpot = rooms[currentNode].getAttachedNode(3)->getNodeName();
   if(!rooms[currentNode].getAttachedNode(4)->visited)
      newSpot = rooms[currentNode].getAttachedNode(4)->getNodeName();

   return newSpot;
}

However, today upon compilation and execution of main:

main ()
{
   System system;
   system.displayWelcome();
   string file;

   while(1)
   {
      file = system.getFileName();

      if(file == "Quit.txt" || file == "quit.txt")
         break;


      system.buildGraph(file);

      cout << "Made it through buildGraph()" << endl;


      system.printMap(system.rooms);
      string path = system.getPath();

      cout << "The Start Node is: " << system.startNode.getNodeName() << endl;
      cout << "The Destination Node is: " << system.endNode.getNodeName() << endl;
      cout << "Finding a path from the Start to the Destination node ... " << endl;

      if(path.length() > 1)
      {
         cout << "Congratulations: Found path successfully." << endl;
         cout << "The path is: " << path << endl;
      }
      else
         cout << "Unsuccessful: No path can be found." << endl;
   }

   system.displayExit();
}

I receive the following output.

========================================================
|      Welcome to the Automatic Maze Path Finder!      |
========================================================

Enter the name of the Maze configuration file: maze1


Line contains: A1 A2 B1 * * 
Current Node: A1
firstNode:  -A2
secondNode: -B1
thirdNode:  -* 
fourthNode: -* 

Line contains: B1 B2 * * A1 
Current Node: B1
firstNode:  -B2
secondNode: -* 
thirdNode:  -* 
fourthNode: -A1

Line contains: C1 C2 * * * 
Current Node: C1
firstNode:  -C2
secondNode: -* 
thirdNode:  -* 
fourthNode: -* 

Line contains: D1 D2 E1 * * 
Current Node: D1
firstNode:  -D2
secondNode: -E1
thirdNode:  -* 
fourthNode: -* 

Line contains: E1 * * * D1 
Current Node: E1
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -D1

Line contains: F1 F2 * * * 
Current Node: F1
firstNode:  -F2
secondNode: -* 
thirdNode:  -* 
fourthNode: -* 

Line contains: G1 G2 H1 * * 
Current Node: G1
firstNode:  -G2
secondNode: -H1
thirdNode:  -* 
fourthNode: -* 

Line contains: H1 * * * G1 
Current Node: H1
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -G1

Line contains: A2 A3 * A1 * 
Current Node: A2
firstNode:  -A3
secondNode: -* 
thirdNode:  -A1
fourthNode: -* 

Line contains: B2 * C2 B1 * 
Current Node: B2
firstNode:  -* 
secondNode: -C2
thirdNode:  -B1
fourthNode: -* 

Line contains: C2 * D2 C1 B2 
Current Node: C2
firstNode:  -* 
secondNode: -D2
thirdNode:  -C1
fourthNode: -B2

Line contains: D2 D3 * D1 C2 
Current Node: D2
firstNode:  -D3
secondNode: -* 
thirdNode:  -D1
fourthNode: -C2

Line contains: E2 E3 * * * 
Current Node: E2
firstNode:  -E3
secondNode: -* 
thirdNode:  -* 
fourthNode: -* 

Line contains: F2 F3 G2 F1 * 
Current Node: F2
firstNode:  -F3
secondNode: -G2
thirdNode:  -F1
fourthNode: -* 

Line contains: G2 * H2 G1 F2 
Current Node: G2
firstNode:  -* 
secondNode: -H2
thirdNode:  -G1
fourthNode: -F2

Line contains: H2 H3 * * G2 
Current Node: H2
firstNode:  -H3
secondNode: -* 
thirdNode:  -* 
fourthNode: -G2

Line contains: A3 * B3 A2 * 
Current Node: A3
firstNode:  -* 
secondNode: -B3
thirdNode:  -A2
fourthNode: -* 

Line contains: B3 B4 * * A3 
Current Node: B3
firstNode:  -B4
secondNode: -* 
thirdNode:  -* 
fourthNode: -A3

Line contains: C3 C4 D3 * * 
Current Node: C3
firstNode:  -C4
secondNode: -D3
thirdNode:  -* 
fourthNode: -* 

Line contains: D3 * E3 D2 C3 
Current Node: D3
firstNode:  -* 
secondNode: -E3
thirdNode:  -D2
fourthNode: -C3

Line contains: E3 * * E2 D3 
Current Node: E3
firstNode:  -* 
secondNode: -* 
thirdNode:  -E2
fourthNode: -D3

Line contains: F3 F4 * F2 * 
Current Node: F3
firstNode:  -F4
secondNode: -* 
thirdNode:  -F2
fourthNode: -* 

Line contains: G3 G4 * * * 
Current Node: G3
firstNode:  -G4
secondNode: -* 
thirdNode:  -* 
fourthNode: -* 

Line contains: H3 H4 * H2 * 
Current Node: H3
firstNode:  -H4
secondNode: -* 
thirdNode:  -H2
fourthNode: -* 

Line contains: A4 A5 B4 * * 
Current Node: A4
firstNode:  -A5
secondNode: -B4
thirdNode:  -* 
fourthNode: -* 

Line contains: B4 B5 * B3 A4 
Current Node: B4
firstNode:  -B5
secondNode: -* 
thirdNode:  -B3
fourthNode: -A4

Line contains: C4 * D4 C3 * 
Current Node: C4
firstNode:  -* 
secondNode: -D4
thirdNode:  -C3
fourthNode: -* 

Line contains: D4 * E4 * C4 
Current Node: D4
firstNode:  -* 
secondNode: -E4
thirdNode:  -* 
fourthNode: -C4

Line contains: E4 E5 F4 * D4 
Current Node: E4
firstNode:  -E5
secondNode: -F4
thirdNode:  -* 
fourthNode: -D4

Line contains: F4 * G4 F3 E4 
Current Node: F4
firstNode:  -* 
secondNode: -G4
thirdNode:  -F3
fourthNode: -E4

Line contains: G4 * * G3 F4 
Current Node: G4
firstNode:  -* 
secondNode: -* 
thirdNode:  -G3
fourthNode: -F4

Line contains: H4 H5 * H3 * 
Current Node: H4
firstNode:  -H5
secondNode: -* 
thirdNode:  -H3
fourthNode: -* 

Line contains: A5 A6 * A4 * 
Current Node: A5
firstNode:  -A6
secondNode: -* 
thirdNode:  -A4
fourthNode: -* 

Line contains: B5 * C5 B4 * 
Current Node: B5
firstNode:  -* 
secondNode: -C5
thirdNode:  -B4
fourthNode: -* 

Line contains: C5 C6 D5 * B5 
Current Node: C5
firstNode:  -C6
secondNode: -D5
thirdNode:  -* 
fourthNode: -B5

Line contains: D5 * * * C5 
Current Node: D5
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -C5

Line contains: E5 E6 F5 E4 * 
Current Node: E5
firstNode:  -E6
secondNode: -F5
thirdNode:  -E4
fourthNode: -* 

Line contains: F5 * * * E5 
Current Node: F5
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -E5

Line contains: G5 G6 H5 * * 
Current Node: G5
firstNode:  -G6
secondNode: -H5
thirdNode:  -* 
fourthNode: -* 

Line contains: H5 * * H4 G5 
Current Node: H5
firstNode:  -* 
secondNode: -* 
thirdNode:  -H4
fourthNode: -G5

Line contains: A6 * B6 A5 * 
Current Node: A6
firstNode:  -* 
secondNode: -B6
thirdNode:  -A5
fourthNode: -* 

Line contains: B6 * * * A6 
Current Node: B6
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -A6

Line contains: C6 * * C5 * 
Current Node: C6
firstNode:  -* 
secondNode: -* 
thirdNode:  -C5
fourthNode: -* 

Line contains: D6 * E6 * * 
Current Node: D6
firstNode:  -* 
secondNode: -E6
thirdNode:  -* 
fourthNode: -* 

Line contains: E6 * F6 E5 D6 
Current Node: E6
firstNode:  -* 
secondNode: -F6
thirdNode:  -E5
fourthNode: -D6

Line contains: F6 * * * E6 
Current Node: F6
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -E6

Line contains: G6 * H6 G5 * 
Current Node: G6
firstNode:  -* 
secondNode: -H6
thirdNode:  -G5
fourthNode: -* 

Line contains: H6 * * * G6 
Current Node: H6
firstNode:  -* 
secondNode: -* 
thirdNode:  -* 
fourthNode: -G6

Exiting buildGraph()

*** Error in `./lab03.out': free(): invalid size: 0x000000000106ca80 ***
Aborted (core dumped)

Everything before the final two lines are as expected and you can see the lines appear to be read and processed correctly. Notice that the print statement at the end of the buildGraph() function successfully prints, but the next print statement immediately following in the main() does not. What could be causing this issue? How should I go about remedying this problem? Thanks.

score 1 · Answer 1 · answered Nov 10 '15 at 21:47

1

You cannot do this:

{
    Node empt;
    empt.setNodeName("null");
    thing->second.attachNewNode(&empt,1);
}

empt is a local variable, which is destroyed after block finishes, so you have dangling pointers. One of possible solutions to keep a container of unnamed nodes somewhere in function (with proper lifetime) and add them:

{
    unnamedNodes.emplace_back( "null" );
    thing.second.attachNeNode( &unnamedNodes.back(), 1 );
}

and define:

std::list<Node> unnamedNodes;

in your class. You may use std::vector instead but you have to make sure that no reallocation occurs (enough size is reserved in advance)

answered Nov 10 '15 at 21:47

Slava

43,454
1
47
90

If I were to create the Node empt before the loop (perhaps as a private variable), could I attach it everywhere there should be a blank node? Am I attaching other nodes correctly and not locally? – Cameron Jewell Nov 10 '15 at 21:55
If you do not modify that object yes it can be just one instance of `Node empt` as a member variable. Other nodes are owned by `std::map`, so they are fine. – Slava Nov 10 '15 at 21:59
So what exactly was causing the error? Was it trying to access a node that is null? What exactly did the error mean? After replacing the empt node assignment to a class variable empt instead, I still receive the same error. – Cameron Jewell Nov 10 '15 at 22:03
@CameronJewell read here http://stackoverflow.com/questions/17997228/what-is-a-dangling-pointer – Slava Nov 10 '15 at 22:04

c++ Navigating a "Maze" of Nodes mysterious error

1 Answers1