I am brand new at C++ and I have a programming assignment I have to do. I have to create a directed graph and perform a breadth-first traversal. I have to use an adjacency linked list implementation without using any existing libraries as Standard Template Library. Where do I begin? Sorry, for the silly question, but I am not sure where to even begin. Thanks for any help whatsoever.

Are you sure you have the prequisits for that course? It sounds pretty advanced for a beginner.

Yes, we have always programmed in java, but never in C++. For this course we are expected to learn a new programming language and it is C/C++. This is our first assignment and honestly only assignment in C++.

Then make a directed graph based on that, and implement the traversal function.

How should I go about creating the adjacency linked list? Should I create a structure that is a node. How do I use the main method to initiate the nodes?

Tell me, if the task was to implement it in Java, would you need the same amount of help?

Just do some research (I already gave you one link) and then try and implement it.

Yes, things like
- create list, add node, remove node
would seem like reasonable interfaces to the list class.

Okay, gonna see if I can get a little help here. I am creating an array to store each node in my directed graph. Off each one these nodes I am going to create a linked list.

Does this look like a good approach? How would I use a breadth first traversal to perform my traversals. I also have to print out number of nodes, name of each node, and a list of node, node pairs that represent edges.

For example:
5 would be

5
One
Two
Three
Four
Five
1,2
1,3
2,4
3,5
4,5

Thanks for help.

``````#include <cstdlib>
#include <iostream>

using namespace std;

int getSize ()
{
int r;
cout << "Please enter an integer value for amount of nodes: ";
cin >> r;
return (r);
//return (nodes);
}

void fun(string *arr, int len)
{
for (int i = 0; i < len; i++) {
string name;
cout << "Enter node name: ";
cin >> name;
arr[i] = name;
}
}

int main()//int argc, char *argv[])
{
int nodes;
nodes = getSize();
string graph[nodes];
fun(graph, nodes);
system("PAUSE");
}``````

I really need help with this. I am at a point where I am not sure what to do for creating my edges. I have created all my nodes in a linked list with a down pointer. What to do?

``````using namespace std;

struct node
{
int pointer;
string name;
struct edge *down;
struct node *next;
};

struct edge
{
int pointer;
};

node *graph;

int setNodeSize ()
{
int r;
cout << "Please enter an integer value for amount of nodes: ";
cin >> r;
return (r);
}

void setNodes(int i)
{
string value;
for (int j=1; j <= i;j++){
node * curr = new node;
curr->pointer=j;
cout << "What is name of node: ";
cin >> value;
curr->name=value;
}
for (int j=1; j <= i;j++){
}

}

int setEdgeSize()
{
int amount;

cout << "How many edges are you going to enter? ";
cin >> amount;
return amount;
}

int getPointA(string input)
{
string sub;
sub = input.at(0);
return atoi(sub.c_str());
}

int getPointB(string input)
{
string sub;
sub = input.at(2);
return atoi(sub.c_str());
}

void setEdges(int a,int b) {
cout << "hey";
cout << "get you";
}
}

}

int main(int argc, char *argv[])
{

int a,b;
int amount = setNodeSize();
string input;

setNodes(amount);

amount = setEdgeSize();

for (int i = 0; i < amount; i++) {
cout << "Please enter the edges: ";
cin >> input;
a = getPointA(input);
b = getPointB(input);
setEdges (a, b);
}

//traverse();
//print();

system("PAUSE");
return EXIT_SUCCESS;
}``````

Ok. I now have a new problem. I am try to read a character at a time from a file redirection and I am unable to get this to work. I keep getting segmentation faults and invalid conversion from char to const_char errors. I am sure this deals with pointers, but I have no idea what I am doing. Here is code for where errors occur:

The actual input is:
1,2
1,3
2,4
3,5
4,5

I want to get a=1 and b=2.

``````char input;
while (input = getchar() != EOF){
string stuff = string(input);
int a,b;
a= int( input );
input= getchar();
input = getchar();
b= int(input);
cout<< "a " <<a << " b" << b <<endl;``````

To convert an ascii digit to numeris, all you have to do is subtract '0'. Here's one way to do it. Note that getchar() returns an int, not char.

``````int a = -1, b = -1;
int input.
while( (input = getchar()) != EOF)
{
if( isdigit(a) )
{
if( a == -1)
{
a = input - '0'; // convert input to binary digit
}
else
{
b = input - '0'; // convert input to binary digit
}
if( a > -1 && b > -1)
{
cout<< "a " <<a << " b" << b <<endl;
a = -1, b = -1;
}
} // end if( isdigit() )
} // end while loop``````

Another issue that i have no idea on what to do. I have an intense while loop. I keep getting segmentation faults whenever I perform this loop. What can I do to solve? Thanks for the help Ancient Dragon. That really helped me along. When performing the one while loop everything worked well, but adding everything caused errors. Here is full code for what I need to do.

``````int a = -1, b = -1;
char input;
while( (input = getchar()) != EOF)
{
if( isdigit(input) )
{
cout << "Input is " << input << endl;
if( a == -1)
{
a = input - '0'; // convert input to binary digit
}
else
{
b = input - '0'; // convert input to binary digit
}
if( a > -1 && b > -1)
{
cout<< "a " <<a << " b" << b <<endl;
a = -1, b = -1;
}
} // end if( isdigit() )

int count=0;

while (nodePtr->pointer != a)
{
nodePtr = nodePtr->next;
}
while (a == nodePtr->pointer && count ==0)
{
newNode = new ListNode;
newNode->pointer = b;
newNode->next = NULL;
newNode->down = NULL;

if (nodePtr->down == NULL)
{
nodePtr->down=newNode;
}
else
{
while(nodePtr->down != NULL)
{
nodePtr=nodePtr->down;
}
nodePtr->down= newNode;
}
a++;
count++;
}
}
}``````

Should I use a debugging tool to try and solve this?

``````while (nodePtr->pointer != a)
{
nodePtr = nodePtr->next;
}``````

What happens when thre are no nodes whose value is equal to variable a? Answer: infinite loop that will eventually crash your program. That loop needs to also check for end-of-linked-list, which is normally indicated by NULL nodePtr

``````while ( (nodePtr != NULL) & (nodePtr->pointer != a) )
{
nodePtr = nodePtr->next;
}``````

What kind of object is nodePtr->pointer ? Is it a pointer to something? If it is, it can't normally be compared to an integer.

I have been using same example and it works fine until I add the edge feature with the getting character from input. This throws the program totally off and I am not sure why.

It is my while loop with the getchar. It keeps look when I redirect with a text file. How do I get the loop to stop. I know the EOF is -1, but it conflicts with changing my char to decimal. Is there a better way to go about this.

Big Picture
Do you have any kind of a design for this assignment?
Because it seems like a large problem, one which isn't going to be solved just by bashing in random code until it works (because it won't).

- create
- destroy
- print nodes
- remove nodes
- and so on...

When you have a class, write a simple test for it, something like

``````int main ( ) {
myAdjList list;  // should call constructor
list.print( );  // should see 1,2,3,4
list.remove( 1 );
list.print( );  // only 3,4 left
// destructor called round about now
}``````

When you have a class which works, then you can use it in anger to solve your assignment, knowing that the basic components are going to work.

Do you need other classes, or just the one and a main() to sequence everything together?
If you need other classes, how are they going to interact with one another.

Draw some diagrams on paper, index cards, post-it notes to remind you of what the overall design of the program is supposed to be.

----- ----- ----- -----
Little Picture

As this appears to be C++, then use C++ I/O.

Eg.

``````int a, b;
char burnAComma;
while ( cin >> a >> burnAComma >> b ) {
// do stuff with a and b
}``````

Not the most robust way of doing things, but it's simple enough for you to use with the next stage of your assignment.

One more thing.
The linked list loop you have inlined should be in a class, if you're really using C++.

Eg.

``````myAdjList list;
int a, b;
char burnAComma;
while ( cin >> a >> burnAComma >> b ) {