depth-first search algorithm

[Lelly]

Hello,
I started my homework and I couldn't complete it. Can anyone help me with it??

the question is:
Implement the depth-first search algorithm so that it accepts input from text file in the following format:
List all distinct vertex symbols (use just a single symbol: A-Z and 0-9) one per line followed the list of edges. An edge is formatted as either v1 - v2 or v1 > v2 or v1 < v2. Note the necessary spaces around the middle symbols. Directed edges are indicated by the < and > symbols. Undirected edges use the dash symbol, not the underscore. In the following example, vertex 4 is connected only to itself as a self-loop.
1
2
3
4
1 > 3
2 < 3
4 - 4

Do you think the order of the input edges will change the DFS search order?
------------------------------------------
my code is:

#include <iostream>
#include <string>
#include <stdio.h>
#include<fstream>

#define MAXNODES 256
using namespace std;
enum ColorEnum {WHITE, GRAY, BLACK};

struct GraphNode {
int discovery, finish;
ColorEnum color;
string symbol; // A-Z, a-z, 0-9
char edgeType; // Tree, Back, Forward, Cross
GraphNode *adjList;
int adjListCounter;
};

void initializeNode( GraphNode& node, string symbol);
int readGraphfile(const char* fileName, GraphNode* nodeList);
void printNodeList(GraphNode* nodeList, int count);

void initializeNode( GraphNode& node, string symbol )
{
node.discovery = INT_MAX;
node.finish = INT_MAX;
node.color = WHITE;
node.symbol = symbol;
node.edgeType = ' ';
node.adjList = new GraphNode[MAXNODES];
node.adjListCounter = 0;
}

// Also initializes graph nodes
int readGraphfile(const char* fileName, GraphNode* nodeList)
{
string s;
GraphNode u;
int vertices = 0;

ifstream inputData(fileName, ios::in);
// don't read lines using iterator because of embedded spaces.
while (inputData.good()) {
getline(inputData, s);
if (s.length() == 0) continue;
if (s.length() == 1) { // then read vertex name
initializeNode(nodeList[vertices], s); // does not handle duplicate vertices
vertices++;
// cout << s << endl;
} else { // then process edges
char *p = strtok((char*)s.c_str(), " ");
// look for this node in list
int ndx = 0;
while ( (strcmp(nodeList[ndx].symbol.c_str(), p) != 0) && (ndx < vertices) ) ndx++;
// cout << p << " ";
p = strtok(NULL, " "); // < > - relation
// cout << p << " ";
p = strtok(NULL, " "); // target node name
// cout << p << " ";
int mdx = 0;
while ( (strcmp(nodeList[mdx].symbol.c_str(), p) != 0) && (mdx < vertices) ) mdx++;
nodeList[ndx].adjList[nodeList[ndx].adjListCounter++] = nodeList[mdx];
// cout << endl;
} // if-else
} // while
inputData.close();
return vertices;
}

[daviddoria]

Please use code tags when posting code. Also, what is the problem? Please give us example input, current output, expected output, any errors, etc.

[mike_2000_17]

**PLEASE USE CODE TAGS** it's horrible to read this post.

I did manage to spot this: char *p = strtok((char*)s.c_str(), " "); You cannot use strtok() with an std::string! What is returned by c_str() is a read-only char array. The c_str function returns a constant pointer, but it should return a constant pointer to constant, meaning you should not modify the characters it points to (the reason why it doesn't is for compatibility with C).

Basically, the C++ std::string is not anything like a C-string (const char*) and should not be used as such. The c_str() function is just provided for convenience of being able to _read_ the string as a C-string, it is not for writing. It might work, but that is just accidental.

C++ has it's own set of functions for extracting different things from a std::string, and those are the functions you should use. Most of them are collected in an object of class "std::stringstream" (in #include <sstream>) which can be used in a similar fashion as cin or cout (or any other IO stream), but from or to a string instead of the console or file. Here is how to extract that first token from the C++ string:

std::stringstream ss(s);   //create a stringstream from the string s that you have.
std::string p;             //create a string to hold the first token.
std::getline(ss, p, ' ');  //extract string up to the first space character from ss.