Depth First and Breadth First Spanning trees

mullinsn2000 (4)
I will preface this by saying that I am a student and this is a homework assignment. I am not looking for someone to just give me code, but I am looking for a little guidance.

The assignment is for a discrete mathematics course which has a prerequisite of two c++ courses. Everything I find online is talking about using vectors and recursion and other things that we have not covered in my programming classes. We have not covered any c++ containers. I have tried to research them on my own, but I am not sure how to implement them into my code.

For the assignment we had to create a graph (undirected) and an input file that looks like this:

node node //this shows that there is an edge connecting these two nodes

I have got some of the code to work by changing my input file to this:

node node (1 or 0) //1 saying there is an edge and 0 saying no edge

The user inputs a starting node and then we proceed to build the spanning tree. I am having trouble traversing back up to look at other possible nodes that have yet to be reached. I get to the bottom of the tree, but I am unsure how to go back up.

The code is very messed up. I believe I have way too many variables, but I am unsure what to do. I am only asking for a little nudge in the right direction. If I wanted to cheat on the assignment I could have just copied some of the code that I have found on the internet because the professor does not care about how it is coded, but I am trying to use the things that I have learned and not just things I find online.

Here is my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <cmath>



using namespace std;

int main()
{
	int node1[50], node2[50]; //node1 is the first node in the graph file and node2 is the second
	int matrix[50][50]= {0,0};//matrix initialized to 0


	
	int start, index=0, indexB=0, startB;

    
	int tree[50], usedNodes[50], treeB[50], usedNodesB[50], path[50];

	
	
	double numNodes=0, graphEDGE=0; 

	
	bool edge[50] = {0};

	ifstream graphINfile;
	ofstream outFILE;

	string graphFname, outFname;
	cout << "Please enter the name of your OUTPUT file:" << endl; 
	cin >> outFname; //input of path filename
	cout << endl; //creating a space for easier reading
	outFILE.open(outFname.c_str());
	

	
	for (int i=1; !graphINfile.eof(); i++) 
	{
		graphINfile >> node1[i] >> node2[i] >> edge[i];
		if (edge[i] != 0)
		{
			outFILE << "NODE: " << node1[i] << "   NODE: " << node2[i] << endl;
		}
		matrix[node1[i]][node2[i]] = edge[i];
		graphEDGE++;
	}
	
		numNodes = sqrt(graphEDGE);

	//BELOW:  Adjacency Matrix
	outFILE << "~~~~~~~~~~~~~~~~~~~~ ADJACENCY MATRIX: ~~~~~~~~~~~~~~~~~~~~" << endl << endl;
	for (int i=1; i <= numNodes; i++)
	{
		outFILE << "          ";
		for (int j=1; j <= numNodes; j++)
		{
			
				outFILE << setw(3) <<	matrix[i][j] << "   ";
		
		}
		outFILE << endl << endl;
	}



	cout << "Please enter a starting node from 1 to " << numNodes << endl;
	cin >> start;
	startB=start; //initializing the startB variable for Breadth-First spanning tree


	for (int i=1; i <= numNodes; i++)
	{
		usedNodes[i] = i;
		usedNodesB[i] = i;
	}

	


	for (int i=start; index <= numNodes; index++)
	{
		for (int j=1; j <= numNodes; j++)
		{
			if (matrix[start][j] == 1 && start != tree[index] && start != usedNodes[j] && usedNodes[j] !=0)
			{
					tree[index] = start;
					start = j;
					path[j] = tree[index]; //TRYING TO SHOW PATH
					cout << tree[index] << " Tree" << endl;
					cout << start << " is a child of " << tree[index] << endl;
					outFILE << tree[index] << " Tree" << endl;
					outFILE << start << " is a child of " << tree[index] << endl;
					outFILE << "The path is: " << path[j] << endl;
					for (int k=1; k <= numNodes; k++)
					{
						if (usedNodes[k] == tree[index])
						{
							usedNodes[k] = 0;
						}
					}
					if (usedNodes[j] != 0)//TEST
					{
					cout << "USED NODES: " << usedNodes[j] << endl << endl;
					}
					/*if (tree[index-1] == start)
					{			
						if (matrix[start][j] == 1 && start != tree[index] && start != usedNodes[j] && usedNodes[j] !=0)
						{
							tree[index] = start;
							start = j;
							path[j] = tree[index]; //TRYING TO SHOW PATH
							cout << tree[index] << " Tree" << endl;
							cout << start << " is a child of " << tree[index] << endl;
							outFILE << tree[index] << " Tree" << endl;
							outFILE << start << " is a child of " << tree[index] << endl;
							outFILE << "The path is: " << path[j] << endl;
							for (int k=1; k <= numNodes; k++)
							{
								if (usedNodes[k] == tree[index])
								{
									usedNodes[k] = 0;
								}
							}
						}
					}*/
			}
			if (usedNodes[index]=0)
			{
				break;
			}
		}
	}
	for (int i=1; i<numNodes; i++)
	{
		cout << path[i] << " :PATH TAKEN" << endl;
	}


	outFILE << "~~~~~~~~~~~~~~~~~~~~~ BREADTH-FIRST: ~~~~~~~~~~~~~~~~~~~~~~" << endl;

	for (int i=startB; indexB <= numNodes; indexB++)
	{
		for (int j=1; j <= numNodes; j++)
		{
			if (matrix[startB][j] == 1 && start != treeB[indexB]&& startB != usedNodesB[j] && usedNodesB[j] !=0)
			{
					treeB[indexB] = startB;
					cout << treeB[indexB] << " Tree" << endl;
					cout << j << " is a child of " << treeB[indexB] << endl;
					outFILE << treeB[indexB] << " Tree" << endl;
					outFILE << j << " is a child of " << treeB[indexB] << endl;
					startB = j;
					
					if (matrix[startB][j] != 0)
					{
						treeB[indexB] = startB;
						for (int k=1; k <= numNodes; k++)
						{
							if (usedNodesB[k] == treeB[indexB])
							{
								usedNodesB[k] = 0;
							}
						}
						if (usedNodesB[j] != 0)//TEST
						{
							cout << "USED NODES: " << usedNodesB[j] << endl << endl;
						}
						
					}
			}
			
		}
	}
	outFILE << "* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl;

	outFILE.close();


	system ("PAUSE");
	return 0;
}

andywestken (4094)
You say you haven't covered stl containers yet.

But have you covered structs?

Andy
Last edited on
mullinsn2000 (4)
We have covered structs and arrays. We also covered how to use arrays or linked lists to create our own stacks, dequeues and queues, but not the actual containers that are already in the stl.

Actually structs were covered in the previous semester.
Last edited on
andywestken (4094)
OK, then I'd think about using a small struct to represent each edge. This might make the code easier to follow than using two (or more) parallel arrays. You could also add control flags to the structure if you need to multi-pass the nodes (e.g. a visited flag).

A similar treatment could be given to the nodes, and even the tree/tree nodes. (I am using a struct based approach to store small trees in a piece of code that I'm currently working on)

I have seen graphs stored as node set + edge set more often than adjacency matrices, for scalability I presume. It should be easy enough to wrap these up in a "graph" structure. This would then allow you to pass the graph around and split your main function up a bit.

Can your algorithm work against the edge set rather than the matrix?

Regarding the input file. Was the original file format specifying a set of edges by their end points? If so, could the 1 could be assumed rather than read from the file? (Or do you need to store the fact that an edge does not exist?)

Andy
Last edited on
mullinsn2000 (4)
The "non-existence" of an edge does not have to be in the file. The file could just be:
node node (only where edges exist)

As for the struct - do you mean that the struct would have a node and a bool visited inside of it, and then I create an array of structs? If so, I have done this on another attempt, but got messed up after I created the adjacency matrix.

As for the adjacency matrix I must print it to an output file, but I believe I could do that without using the matrix for the algorithms.
mullinsn2000 (4)
Here is the code for the attempt I made with a struct and a deque. Maybe it is better to work with. At this point I am unsure because I am stuck in both attempts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
 
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <deque>

using namespace std;

struct edge
{
	int node;
	bool visited;
};


int main()
{
	int matrix[30][30];
	int spanTree[30][30];
	int numNodes = 0, row = 0, column = 0;;
	deque<int> deck;
	ifstream graphINfile;
	ofstream outFILE; 
	string graphFname, outFname;

	bool found = false;
	int start, treeStart;
	edge vertex[30];

	cout << "Please enter the name of your OUTPUT file:" << endl; 
	cin >> outFname; 
	cout << endl; 
	outFILE.open(outFname.c_str());
	if (!outFILE.is_open()) 
	{
		cout << "Unable to open the file." << endl << endl;
	}
	else if (outFILE.is_open()) 
	{
		cout << "Your file " << outFname << " is open." << endl << endl;
	}


	cout << "Please enter the name of your GRAPH file:" << endl; 
	cin >> graphFname;
	cout << endl; 
	graphINfile.open(graphFname.c_str()); 

	if (!graphINfile.is_open()) 
	{
		cout << "Unable to open the file." << endl << endl;
	}
	else if (graphINfile.is_open())
	{
		cout << "Your file " << graphFname << " is open." << endl << endl;
	}

	for(int i = 0; i < 30; i++)
	{
		vertex[i].visited = false;
		vertex[i].node = -1;

		for(int j = 0; j < 30; j++)
		{
			matrix[i][j] = 0;
			spanTree[i][j] = 0;
		}
	}
		

	for(int i = 0; !graphINfile.eof() && i < 30 ;i++)
	{
		row = 0, column = 0;				
										
		for(int j = 0; j < 2; j++)								
		{
			found = false;	
			graphINfile >> start;

			cout << start << " ";

			for(int k = 0; k < 30; k++)									
			{
				
				if(vertex[k].node == start)	
				{
					found = true;				
					if(j == 0)
	                                {										
						row = k;
					}
					else
                                       {
						column = k;
                                       }
				}

			}

			if(found == false)							
						
			{
				
				vertex[numNodes].node = start;
				vertex[numNodes].visited = false;

				if(j == 0)
				{
					row = numNodes;
				}
				else
				{
					column = numNodes;
				}
				numNodes++;
				
			}
		}	

		matrix[row][column] = 1;
		matrix[column][row] = 1;
			

		if(row == column)
		{
			matrix[row][column] = 0;
		}


		cout << endl;
	}

	graphINfile.close();

	found = false;

	cout << "Please enter a starting node from 1 to " << numNodes << ":    ";
	cin >> start;
	treeStart = start;
	cout << "~~~~~~~~~~~~~~~~~~~~~ STARTING NODE: ~~~~~~~~~~~~~~~~~~~~~" << endl;
	cout << "The user chose " << start << " as the starting node." << endl << endl;
	cout << "* * * * * * * * * * * * * * * * * * * * * * * * * * * * * *" << endl << endl;
	cout << endl << endl;
	for (int i=0; i<numNodes; i++)
	{
		if (vertex[i].node == start)
		{
			found = true;
			start = i;
		}
	}


	vertex[start].visited = true;

	cout << "Adjacency Matrix: " << endl;

	cout << endl;
	cout << "         ";
	for(int i=0; i < numNodes; i++) 
	{
		cout << setw(4)<< "  [" << vertex[i].node << "]";
	}

	cout << endl;

	for(int i = 0; i < numNodes; i++)
	{
		cout << "     ";
		cout << "["<< vertex[i].node << "]";
		for(int j = 0; j < numNodes; j++)
		{
			if (matrix[i][j] == 1)
			{
				cout << setw(6) << 1;
			}
			else
			{
				cout << setw(6) << "~";
			}
		}
		cout << endl << endl << endl;
	}

	outFILE.close();

	system("PAUSE");
	return 0;
}
andywestken (4094)
do you mean that the struct would have a node and a bool visited inside of it, and then I create an array of structs?

Yes

But I would go one step further and make the array of node structs a member of another struct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
struct Node
{
	int nodeId;
	bool visited;
	...
};

struct Graph
{
	Node nodes[30];
	int nodeCount;
	Edge edges[30];
	int edgeCount;
	...
};


(Note that I use names beginning with an upper case letter to make them look different to variables.).

Using a structure makes it easier to pass to other functions, for example:

void DisplayAdjMatrix(const Graph& graph, ostream& os);

cf.

void DisplayAdjMatrix( Node nodes[], int nodeCount, Edge edges[], int edgeCount, ..., ostream& os);

A similar treatment could be used for the tree.

As for the adjacency matrix I must print it to an output file, but I believe I could do that without using the matrix for the algorithms.


The two approaches should use similar code to work out what to set or display.

I would consider loading the node pairs as a separate step to creating the adjacency matrix; it should make the sequence easier to follow.

While I'm here, you could also:
- chop your main function up!!
- make sure your variable names make sense (node and vertex mean the same thing, so I would use just one of this pair)
- replace the numeric literals with consts (so you can change (e.g.) the node storage limit by editing in a single place)
- ...

Better stop here, as you don't want too much detail (or am I too late?)

Andy

P.S. It's been a while since I looked at the maths; I use a graph library for processing this kind of information. So I had a quick go at adding a routine to your code to dump a (depth first) tree using the adjacency matrix. I ended up using recursion.
Topic archived. No new replies allowed.