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;
}

Edited 5 Years Ago by WaltP: Added CODE Tags - learn to use them, even though your formatting makes the code impossible to follow.

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

**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.
Comments
So I added CODE tags for him. Did it help?
This article has been dead for over six months. Start a new discussion instead.