CSCI 260 Fall 2022: Lab 4 -- Assignment 3: Graph Algorithms: BFS and DFS



Assignment 3 DUE Oct 20 midnight
65% correctness, 20% design decisions, 15% style.
Style includes use of white space, comments, variable naming, among other factors.
Design decisions include information hiding, modularization, efficiency considerations, data organization, proper use of vectors, among other factors.

Graph Algorithms This lab builds on your graph data structure from Lab3. You will implement Breadth-First Search and Depth-First Search.





The input format Your program will read in graph data in the following form: 

5
0 1 24
1 4 3 
1 2 16
3 2 14
4 2 6 
4 2 9 
5 5 5
This file is interpreted as follows:
5 vertices, (implicitly named 0, 1, 2, 3, 4)
vertex 0 has an edge to vertex 1 with weight 24 (implicitly, since the graph is undirected, vertex 1 has an edge to vertex 0 with weight 24 as well.) vertex 1 has an edge to vertex 4 with weight 3; etc. That is, integers are to be taken in triplets, where the first and second integers are the vertex numbers, and the third is the weight of the edge.

For ease of input, the file contains only integers.
The signal that the end of the file has been reached is when the first number in the triplet is any number ≥ n.

You are provided with a large graph, g2.in, and a randomized graph generator, gen. Use these to test your results with. The file g2.in can be used as a benchmark; contrast and compare your minimum spanning tree total weights with those of your classmates. You should also develop your own testing graphs, and push them with your code.

The most important thing is correctness; second is comprehensibility; third is software engineering principles like polymorphism.
Your graph code must be your own.


Your Task for Assignment 3
You have been provided with code structure to read in an unweighted graph and run graph algorithms on the graph. You have also been provided with a testapp program and a header file.
Debug-print the graph is provided for you. For example, the output for a graph could be: 
0:    1 (24),
1:    0 (24), 4 (3), 2 (16),
2:    1 (16), 3 (14), 4 (9),
3:    2 (14),
4:    1 (3), 2 (9),


Your main tasks are as follows:

  1. (This task is carried over from Lab3.) Build on the code from Lab3 that constructs a graph, given the name of a file of graph data -- return 0 if not found, 1 if found. You are to use the Adjacency List representation. Note that each edge must be entered into two adjacency lists.
  2. Implement BFS. Your program should just visit the vertices in the connected component containing the input vertex.
  3. Implement DFS. Your program should just visit the vertices in the connected component containing the input vertex.

You are to use the "testapp.cpp" and "graph.h" and "graph.cpp" files that you developed in Lab3 as a starting place. You will have to allow the edges to have weights, and ensure symmetry (for the undirected graphs that we assume). Weights will not be significant to BFS or DFS.

Duplicate edges, self-loops, and disconnected graphs
The input graphs may have any of the above. Your code should handle these situations gracefully. Your implementation from Lab3 should have dealt with duplicate edges: the 2nd edge overwrites the first. However, your program must be able to encounter self-loops.
For disconnected graphs, you should print out only the vertices reachable from the input vertex.

Test your code thoroughly.


Everything but the data files and the makefile should bear your complete name and student number. Code should be well-documented and well designed. Files are to be submitted via git.


Here is the perl file for generating a graph file at random.

#!/usr/bin/perl
use strict;
use warnings;

my $n;
my $m;
my $w;

# you may want to hash-out/ comment out the printing, or just remove
# the prompts from the files you generate, if you use >> to gen the
# data into a file
print "How many vertices: ";
$n = ;

print "How many edges: ";
$m = ;

print "max edge weight: ";
$w = ;



print $n;

my $count = 0;
while ($count < $m)
{
$count= $count + 1;
my $u = int(rand($n));
my $v = int(rand($n));
my $weight = int(rand($w));
print $u, " ", $v, " ", $weight,"\n";
}
print $n," ",$n," ",$w;

#end of gen
22
0 1 1
0 12 1
1 18 1
1 6 1
6 9 1
9 4 1
9 7 1
4 113 1
7 11 1
11 17 1
3 2 1
3 5 1
2 8 1
5 14 1
14 10 1
8 10 1
10 15 1
15 16 1
19 20 1
22 22 1