DFS Recursion of a Tree, need assistance with visited issue

Question

I'm having issues when trying to navigate a tree that contains cycles. My code enters an infinite loop and core dumps. My problem is that my code isnt setting the nodes to visited after actually visiting them so it just loops forever. Any help is greatly appreciated.

#include "GraphCode.h"
//#define EBUG

/******************************************************************************
static const string TAG = "GraphCode: ";

/******************************************************************************
 * Constructor
**/
GraphCode::GraphCode()
{
}

/******************************************************************************
 * Destructor
**/
GraphCode::~GraphCode()
{
}

/******************************************************************************
 * Accessors and Mutators
**/

/******************************************************************************
 * General functions.
**/

/******************************************************************************
 * Function 'createGraph'.
 * We read data from the input stream and create a graph.
 *
 * Parameter:
**/
void GraphCode::createGraph(Scanner& inStream)
{
  int nodeCount = -10;
  double connectivity = -3.5;

  MyRandom myRandom;
#ifdef EBUG
#endif
  cout << TAG << "enter createGraph\n"; 

  if (inStream.hasNext())
  {
    nodeCount = inStream.nextInt();
    connectivity = inStream.nextDouble();
    cout << TAG << "Create a graph of " << nodeCount
                << " nodes and " << connectivity << " percent connections"
                << endl;
  }
  else
  {
    cout << TAG << "NO DATA\n"; 
  }

  // first we create the vector of empty nodes
  for (int fromNum = 0; fromNum < nodeCount; ++fromNum)
  {
    Node node = Node(fromNum);
    this->theGraph.push_back(node);
  }

  // now we have a vector so we know we can subscript
  for (int fromNum = 0; fromNum < nodeCount; ++fromNum)
  {
    Node node = this->theGraph.at(fromNum);
    for (int toNum = 0; toNum < nodeCount; ++toNum)
    {
      if (fromNum == toNum) continue;
      double r = myRandom.randomUniformDouble(0.0, 1.0);
      if (r <= connectivity)
      {
        node.addChildSub(toNum);
      }
    }
    this->theGraph[fromNum] = node;
  }

#ifdef EBUG
#endif
  cout << TAG << "leave createGraph " << nodeCount << " " << connectivity << endl; 
} // void GraphCode::createGraph(Scanner& inStream)

/******************************************************************************
 * Function 'descendFrom'.
**/
void GraphCode::descendFrom(ofstream& outStream, string blanks, Node& parentNode)
{
#ifdef EBUG
  cout << blanks << TAG << "enter descendFrom\n" << this->toStringPath(blanks) << endl;
#endif

  vector<int> listOfChildren = parentNode.getChildSubs();
  vector<int>::const_iterator iter;
  if (parentNode.hasBeenVisited() == false) 
  {
    path.push_back(Utils::Format(parentNode.getNodeNumber()));
    parentNode.setVisited(true);
    if (listOfChildren.empty())
    {
      outStream << "Path""\n" << toStringPath(blanks) << endl;
      path.pop_back();
    }

    else
    {
      for (iter = listOfChildren.begin(); iter != listOfChildren.end(); iter++)
      {
        Node& n = theGraph.at(*iter);
        descendFrom(outStream, blanks, n);
      }
     path.pop_back();
    }
  }
 #ifdef EBUG
  cout << blanks << TAG << "leave descendFrom\n"; 
#endif

} // GraphCode::descendFrom()

/******************************************************************************
 * Function 'doSearch'.
**/
void GraphCode::doSearch(ofstream& outStream)
{
#ifdef EBUG
  cout << TAG << "enter doSearch\n"; 
#endif

Node& node = theGraph.at(0);
string blanks = "     ";
descendFrom(outStream, blanks, node);


#ifdef EBUG
  cout << TAG << "leave doSearch\n"; 
#endif

} // void GraphCode::doSearch()

/******************************************************************************
 * Function 'readGraph'.
**/
void GraphCode::readGraph(Scanner& inStream)
{
  ScanLine scanLine;

#ifdef EBUG
  cout << TAG << "enter readGraph\n"; 
#endif

  int firstNode, lastNode;
  firstNode = inStream.nextInt();
  lastNode = inStream.nextInt();
  assert ( 0 == firstNode);
  for(int i = 0; i <= lastNode; ++i)
  {
    Node node = Node(i);
    this->theGraph.push_back(node);
  }

  while (inStream.hasNext())
  {
    string theLine = inStream.nextLine();

    scanLine.openString(theLine);
    int parentNodeNum = scanLine.nextInt();
    Node node = this->theGraph.at(parentNodeNum);
    while( scanLine.hasNext())
    {
      int theChild = scanLine.nextInt();

      node.addChildSub(theChild);
    }
    this->theGraph.at(parentNodeNum) = node;
  }

#ifdef EBUG
  cout << TAG << "leave readGraph " << endl;
#endif
} // void GraphCode::readGraph(Scanner& inStream)

/******************************************************************************
 * Function 'toString'.
**/
string GraphCode::toString()
{
  Node node;
  string s = "     ";
#ifdef EBUG
  cout << TAG << "enter toString\n"; 
#endif
  vector<Node>::const_iterator iter;
  for (iter = theGraph.begin(); iter != theGraph.end(); iter++)
  {
    node = *iter;
    s += "Node:  (" + node.toString() + ")" + "\n";
  }
#ifdef EBUG
  cout << TAG << "leave toString\n"; 
#endif
  return s;
} // string GraphCode::toString()

/******************************************************************************
 * Function 'toStringChildren'.
**/
string GraphCode::toStringChildren(string blanks, const vector<int>& children)
{
  string s = "";
#ifdef EBUG
  cout << TAG << "enter toStringChildren\n"; 
#endif
  Node node;
  vector<int>::const_iterator iter;
  for (iter = children.begin(); iter != children.end(); ++iter)
  { 
    s += Utils::Format((*iter), 6);
  }
#ifdef EBUG
  cout << TAG << "leave toStringChildren\n"; 
#endif
  return s;
} // string GraphCode::toStringChildren()

/******************************************************************************
 * Function 'toStringPath'.
**/
string GraphCode::toStringPath(string blanks)
{
  string s = "     ";
#ifdef EBUG
  cout << TAG << "enter toStringPath\n"; 
#endif
  Node node;
  for (int index = 0; index < this->path.size(); ++index)
  {
    s += this->path.at(index) + "\n" + blanks;
  } 
  s += "LEAF\n";
#ifdef EBUG
  cout << TAG << "leave toStringPath\n"; 
#endif
  return s;
} // string GraphCode::toStringPath()

//expected output:

//PATH TO LEAF 
                           // PATH (   0:  T    1   2   6   9 XXX)
                            //From (   1:  T  XXX)
                           // LEAF

//PATH TO LEAF 
                              //PATH (   0:  T    1   2   6   9 XXX)
                              //From (   2:  T    3   4   5 XXX)
                              //From (   3:  T  XXX)
                              //LEAF

//my output:  
//Path
   //  0
   //  1
   //  LEAF

//Path
    // 0
    // 2
    // 3
    // LEAF

I have mine printing out the path correctly but I can't get the 'T' (basically calling parentNode.toString()) and the children to print on the same line as the path

Answer 1

void Node::setVisited(bool what)
{
  what = visited; 
}

That assignment is backwards. You meant

visited = what;