# depthFirstTraverse fully in C++?

Wondering if this is fully in C++, and if not can someone help me tell the differences. This was submitted by me last semester, and received a good grade. I'm currently trying to ensure I can tell C++ and C apart.

#include <fstream>
#include <stack>
#include <stdlib.h>  //Not neccessary in C++
#define swap(type, a, b) {type t = a; a = b; b = t;}
using namespace std;

typedef struct {
int degree, *adjList, //arraySize = degree
nextToVisit, //0 <=nextToVisit < degree
parent, dfLabel, nodeName;
} GraphNode;

int numNodes, startNode = 1;
GraphNode *nodes;

void depthFirstTraverse(int startNode);

int main() {
depthFirstTraverse(startNode);
}

void depthFirstTraverse(int startNode) {
int nextNode, dfLabels[numNodes], nextToVisit[numNodes], parents[numNodes], lastDFLabel = 0;
stack<int> stackArray;
for (int i = 0; i < numNodes; i++) dfLabels[i] = nextToVisit[i] = 0;
stackArray.push(startNode);
printf("startNode = %d, dfLabel(%d) = %d\n",startNode,startNode,1);
while (!stackArray.empty()) {
if (0 == dfLabels[stackArray.top()]) {
lastDFLabel++;
dfLabels[stackArray.top()] = lastDFLabel; }
if (nextToVisit[stackArray.top()] == nodes[stackArray.top()].degree) {
if (lastDFLabel < numNodes) {
printf("backtracking %d", stackArray.top());
stackArray.pop();
printf(" -> %d\n", stackArray.top()); }
else { printf("backtracking %d -> %d\n", stackArray.top(), startNode);
stackArray.pop(); }
}
nextToVisit[stackArray.top()]++;
if (0 == dfLabels[nextNode]) {
parents[nextNode] = stackArray.top();
printf("processing (%d, %d): tree-edge, dfLabel(%d) = %d\n",
stackArray.top(), nextNode, nextNode, lastDFLabel+1);
stackArray.push(nextNode); }
else if (dfLabels[nextNode] < dfLabels[stackArray.top()]) {
if (nextNode != parents[stackArray.top()])
printf("processing (%d, %d): back-edge\n", stackArray.top(), nextNode);
else printf("processing (%d, %d): tree-edge 2nd-visit\n", stackArray.top(), nextNode); }
else printf("processing (%d, %d): back-edge 2nd-visit\n", stackArray.top(), nextNode);
}
} for (int i = 0; i < 30; i++) printf("-");
}

char ignore;
ifstream digraph("digraph.data");
digraph >> numNodes;
nodes = new GraphNode[numNodes];
for (int i = 0; i < numNodes; i++) {
digraph >> nodes[i].nodeName >> ignore >> nodes[i].degree >> ignore;
for (int j = 0; j < nodes[i].degree; j++) digraph >> nodes[i].adjList[j];
} digraph.close();
printf ("Input Graph:\nnumNodes = %d\n", numNodes);
for (int i = 0; i< numNodes; i++) {
printf("%d (%d): ", nodes[i].nodeName, nodes[i].degree);
for (int j = 0; j < nodes[i].degree; j++)
for (int k = 0; k < j; k++)
for (int j = 0; j < nodes[i].degree; j++) printf("%d ", nodes[i].adjList[j]);
printf("\n");
} for (int i = 0; i < 30; i++) printf("-");
printf ("\n");
}

• For C++ code, you're using an awful lot of C functions and paradigms. You usually could tell by the excessive use of printf(), pointers, for loops, lack of classes and so on. Good C++ would not rely on these constructs as much if at all using things in the STL and algorithm more. A bigger C++ guru will be able to explain these more thoroughly. Commented Aug 14, 2011 at 23:41
• Originally it was different, but as I changed it to meet his demands, this was the result. Commented Aug 15, 2011 at 1:57
• Martin is right: Your code is more C with some C++ features than C++. You are thinking "functions with data". In C++, you should think "objects that hide their internals and know how to behave". Encapsulation should be your main concern. Who told you this was a C++ code? Commented Aug 15, 2011 at 7:51

It's still closer to C than C++ IMO.

### First of two non C++ issues:

1. You don't encapsulate your classes. Your whole interface is public. Thus you are now doomed to forever maintain this interface for eternity. Additionally it allows other people to accidentally modify your structure. Use the C++ class system to encapsulate your objects and at least protect your objects from accidental miss use.

2. Your tree-traversal actually depends on the node object to track traversal. Now that's a bad design thing. You are basically binding yourself to an implementation and limiting the usability of your code. You should most defiantly look up the Visitor Pattern.

### The rest are C++ issues:

You are doing resource management manually:

nodes = new GraphNode[numNodes];
// STUFF


It would be better to use a std::vector at least that would be exception safe in controlling the resource:

std::vector<GraphNode>   nodes(numNodes);


You are manually loading nodes. Should a node not know how to stream itself onto and off a stream?

    digraph >> nodes[i].nodeName >> ignore >> nodes[i].degree >> ignore;


I would expect it to look like this:

    digraph >> nodes[i];


Or even better create items and push them into the vector:
Since the only thing that seems to be in the file "digraph.data" seem to be GraphNodes then you could do something like this:

std::copy(std::istream_iterator<GraphNode>(digraph),
std::istream_iterator<GraphNode>(),
std::back_inserter(nodes)  // Assuming nodes is a vector described above.
);


This is not C++

    printf("%d (%d): ", nodes[i].nodeName, nodes[i].degree);


The problem with the printf style is that it is not type safe. The main advantage C++ has over C is the exceptional type safety of the language. Use this to your advantage.

This is so bad I nearly swallowed my tounge.:

                swap(int, nodes[i].adjList[j], nodes[i].adjList[k]);


You have #defined swap.

1. Use all caps for macros.
The reason is to make sure macros do not clash with any other identifiers.
2. Macros are not type safe.
If there was a conversion from this object to int the compiler will now happily do it.
3. There is already a type safe macro as part of the standard library.
If you want to override the default swap behavior you just need to rewrite your type specific version and Koenig lookup will automatically find it.

Not a big deal but prefer pre-increment. The reason is it does not matter for POD types but for user defined types it does (or potentially does) matter. If a maintainer at a latter stage changes the type of the loop variable then you don't have to go and change any of the code the pre-increment is already the correct type.

 for (int i = 0; i < 30; ++i)
// ^^^^ Prefer pre-increment here


Don't declare multiple variables on the same line:

int nextNode, dfLabels[numNodes], nextToVisit[numNodes], parents[numNodes], lastDFLabel = 0;


Every coding standard is going to tell you not to do it. So get used to it. Technically there are a few corner cases that will come and hit you and putting each variable on its own line makes it easier to read. Also note it looks like you are initializing all values to zero. That's not happening so all of these (apart from the last one) are undefined.

Also defining arrays with a non cost type is not technically allowed.

dfLabels[numNodes],


Some compilers allow it because it is C90 extension. But its not really portable. Use std::vector (or std::array) instead.

Don't put code on the same line as the close braces.
I dobt anybody is going to like that style even the people that want to save vertical line space.

} for (int i = 0; i < 30; i++) printf("-");


And I prefer to put the statement the for loop is going to run on the next line so it is obvious what is happening (but I am not going to care that much about it).

typedefing a structure is not needed in C++

typedef struct {
// BLAH
} GraphNode;


This is just

struct GraphNode
{
// BLAH
};


When you loop over your containers you are using a C style (ie you are using an index). It is usually more conventionally to use an iterator style to index over a container (even a simple array). Thus if you ever choose to move to another style of container the code itself does not need to be changed. The iterator style makes the code container agnostic.

Personally I don't think it is a big deal. In this limited context.

    for (int j = 0; j < nodes[i].degree; j++)


You implement (badly) a sort function:

    for (int j = 0; j < nodes[i].degree; j++)
for (int k = 0; k < j; k++)


Lets just say in both C/C++ you should probably use the built-in sorting algorithms:

std::sort(&nodes[i].adjList[0], &nodes[i].adjList[nodes[i].degree]);


Or am I reading your intention here incorrectly? Is it some sort of randomizing feature? Either way you should have probably documented this to explain what you are trying to achieve!

### Here is a more C++ like version

#include <vector>
#include <map>
#include <iterator>
#include <stdexcept>
#include <fstream>
#include <iostream>

class GraphVisitor; // We will implement the Visitor Pattern
class Graph
{
public:
class GraphNode
{
public:
// Allows us to visit each node.
// Don't need to track progress via modifying the node
void accept(GraphVisitor& visitor);
private:
// The streaming operators are defined so we can freeze and thaw data to a stream
friend std::istream& operator>>(std::istream& stream, Graph::GraphNode& node);
friend std::ostream& operator<<(std::ostream& stream, Graph::GraphNode const& node);

// The data is private nobody actually needs to see this
int                 nodeName;
};

// Graph knows how to implement depth first traversal.
// External entities can't do this because that requires knowledge of the implementation
void DepthFirstTraversal(size_t startNode);

private:
// The streaming operators are defined so we can freeze and thaw data to a stream
friend std::istream& operator>>(std::istream& stream, Graph& node);
friend std::ostream& operator<<(std::ostream& stream, Graph const & node);

// The data is just the nodes
std::vector<GraphNode>  nodes;

};
// A visitor is easy
// When you only have one node type.
// So we just have one visit method.
class GraphVisitor
{
public:
virtual ~GraphVisitor() {}
virtual void visit(Graph::GraphNode& node, int name, std::vector<int> const& links)    = 0;
};

// All the node does with the visitor is tell it that it can visit.
void Graph::GraphNode::accept(GraphVisitor& visitor)
{
}

// Stream Nodes
std::ostream& operator<<(std::ostream& stream, Graph::GraphNode const& node)
{
stream << node.nodeName << ":" << node.link.size() << ":";
return stream;
}
std::istream& operator>>(std::istream& stream, Graph::GraphNode& node)
{
char ignore;
int  count;

stream >> node.nodeName >> ignore >> count >> ignore;

for(std::istream_iterator<int> loop(stream); count != 0; --count, ++loop)
}
// For some reason you sort your nodes so I am sorting them here.
return stream;
}
// Stream the whole graph.
// This is simply the number of nodes followed by a list of nodes.
std::ostream& operator<<(std::ostream& stream, Graph const & graph)
{
stream << graph.nodes.size() << " ";
std::copy(graph.nodes.begin(), graph.nodes.end(), std::ostream_iterator<Graph::GraphNode>(stream, " "));
return stream;
}
std::istream& operator>>(std::istream& stream, Graph& graph)
{
int nodeCount;
stream >> nodeCount;

// We could implement it like this.
// As this would match your current file format nicely and if their
// is anything after the nodes it still works.
/*
for(int loop=0;loop < nodeCount; ++loop)    // I implemented it like this becuase
{
Graph::GraphNode    node;
stream >> node;
graph.nodes.push_back(node);
}
*/
// But if there is nothing after the nodes it could be implemented like this:
std::copy(std::istream_iterator<Graph::GraphNode>(stream),
std::istream_iterator<Graph::GraphNode>(),
std::back_inserter(graph.nodes)
);
}

// A visitor object used by Graph::DepthFirstTraversal
// It tracks which nodes it has already seen.
// So you do not need to visit them again.
// When a node says it can visit then just visit all the linked nodes.
// If you get a call from a node that has already visited then just exit.
class DepthFirstVisitor: public GraphVisitor
{
public:
DepthFirstVisitor(std::vector<Graph::GraphNode>& n)
: nodes(n)
{}
private:
virtual void visit(Graph::GraphNode& node, int name, std::vector<int> const& links)
{
if (visited[&node])
{   return;
}

visited[&node]  = true;
std::cout << "Visiting Node: " << name << "\n";

{
nodes[*loop].accept(*this);
}
}
std::map<Graph::GraphNode const*, bool>     visited;
std::vector<Graph::GraphNode>&              nodes;
};

// Implementing the Depth First traversal is easy as calling the first node with the
// the correct visitor object
void Graph::DepthFirstTraversal(size_t startNode)
{
if (startNode >= nodes.size())
{   throw std::runtime_error("Failed");
}
DepthFirstVisitor   visitor(nodes);
nodes[startNode].accept(visitor);
};

int main()
{
Graph   graph;

std::ifstream digraph("digraph.data");
digraph >> graph;                   // Very easy to load a graph.
std::cout << graph << "\n\n\n";     // Printing it out is also easy

graph.DepthFirstTraversal(1); // start at node one instead of zero for some reason!!!!!.
}

• +1 for the thorough answer. typedefing a structure is not needed in C++ : More important, if the structure is anonymous (and only has a typedef-ed name), it can't be forward declared!... Also, shouldn't the startNode parameter of Graph::DepthFirstTraversal be a size_t ? Commented Aug 15, 2011 at 7:47
• @Martin Thanks. Very clear, and appreciate the example. Commented Aug 15, 2011 at 22:54

using printf is C like.

using a function like readGraph that does a lot of magic as well as printing things is C like.

For this kind of thing to be C++ like, then you'd consider how to write these functions generically. Giving your graph an STL like feel.

This code here is more about your attempts at learning traversal than writing a good useful function. For instance, the whole point of traversal is to do something with each node visited, here you have no facilities for injecting functionality as you reach each node.

So a C++ approach, in the sense of a modern approach, would look quite different. This would be templated, it would accept lambdas or functors, it would use/provide iterators etc.