CS310 The Graph

1 Overview

The Graph Abstract Data Type (ADT) introduces a method for modeling the relationship between a set of vertices and the edges connecting them. It builds upon the idea introduced with the liked list where we store dynamic links to the the actual data in memory. No longer bound to simply one connection, however, the dynamic nature of the connections introduces the possibility of wildly diverse shapes. Any vertex in a graph may connect to paths that circle back upon itself.

A,B,3
A,C,1
B,B,1
B,C,5
C,D,3
C,E,7
D,D,1
D,A,9
E,A,2

Figure: see image.

In this extensive programming assignment, students shall build an ap- plication which constructs a weighted, directed graph from a single CSV file. Students must build both the driver application, responsible for load- ing the data and displaying information about the graph, as well as the weighted-directed graph itself.

2 Requirements

This assignment incorporates several abstractions, and it necessitates several ADTs covered throughout the semester. Students must implement the graph and application identified in this assignment directly from scratch. Students need not implement underlying data structures, like the list, vector, map, or queue, however, and may instead use the versions provided in the standard library.

After prompting the user for the relative path to an input file, the ap- plication shall construct a graph from the data contained therein. It shall extract the vertex and edge information from the comma-delineated input file as defined in section 2.1.1. With the graph constructed in the program's memory, the program shall then print several characteristics about the graph as defined below:

• The total number of vertices in the graph.
• List any vertices with exactly zero inbound edges.
• List any vertices with self edges.
• List any vertices with exactly zero outbound edges.

2.1 Coding Style

Software quality strengthens program security, reliability, and maintainabil- ity. In general, all submitted software must:

• Adhere to a consistent naming convention and follow best practices for variable naming.
• Use private, or protected, internal methods to help clean the code.
• Remain free of commented out blocks of code.
• Use consistent formatting.
• The maximum column width is 80 characters.

Basic
Basic,Grimer,0
Basic,Tapu Koko,0
Basic,Jirachi,0
Basic,Charmander,0
Stage 1
Basic,Stage 1,1
Grimer,Muk,1
Stage 1,Muk,0
Stage 1,Charmeleon,0
Charmander,Charmeleon,1
Stage 2
Stage 1,Stage 2,1
Stage 2,Charizard,0
Charmeleon,Charizard,1

Figure 1: An example of an arbitrary input file meeting the format.

2.1.1 Input File Format

Each line in the file serves as either a single vertex entry (introducing a vertex) or a connection entry (identifying a link between two vertex points). Vertex entries contain only one string value indicating the name to associate with the vertex. The label is case-sensitive and may contain spaces and special characters. The comma shall not appear in a label name. Connection entries contain three values: The string name of the source vertex, the string name of the destination vertex, and the integer movement cost to traverse the edge. The program shall ignore lines failing to meet either of these formats.

The newline character denotes the end of an entry, so only one vertex or connection appears on any given line. Vertex names need not appear before being introduced in a connection. Thus, a single entry may lead to the creation of two new vertices and one edge between them.

3 Delivery

At the start of class on the due date, students shall submit a legible, physical ASCII printout of their source code. Do not submit screen-shots of source code or the development environment. Do not copy the source into a word- processor. Simply print the source file, which is ASCII, directly. The 80 character line limit in defined in the coding standard ensures that the source file prints as it appears on screen.