Traversing Property Graphs

Learning Objectives

Implement a data structure to meet given specifications

Design, implement, and use a graph data structure

Utilize Dijkstra's algorithm

Overview

Your task for this assignment is to implement a graph data structure and find appropriate shortest paths, while accounting for property-labelled edges.

The Graph class

At this point in the course, I leave it to your discretion to choose an appropriate implementation (i.e. array vs linked). Note that you may need a class for Nodes or Edges. Furthermore, you may use vectors, hashtables, or any other data structure used in class. Any manually implemented classes beyond the Graph shall be inline.

6 Alice Brent Calvin Deborah Everett Frank 4 ParentOf 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 BrotherOf 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 SisterOf 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 FriendOf 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 

The first block consists of an integer telling the reader how many people (nodes) to expect, followed by that many names. It is not guaranteed that only first names will be in the file. The second block consists of an integer that tells the reader how many properties to expect. Then, for that many properties, the property name is given, followed by an adjacency matrix for that property. Of course the adjacency matrix is square, with rows and columns equal to the number of nodes in the graph. No property is reflexive.

Using the information in this file, you are to construct a directed graph, where the property names label edges connecting nodes.

Alice ParentOf Brent BrotherOf Calvin SisterOf Brent FriendOf Frank Brent . . . 

I obviously made up the property names after drawing the graph... hahaha

bool Graph::construct(string filename) construct the graph from the file called filename and return false if the graph construction failed. The file will have the following structure.

Node* Graph::findPerson(string name) If there is a node with the given name in the graph, it is returned, otherwise the function returns nullptr.

bool Graph::findPath(string name, string other) If both people are in the graph, find the shortest path between them.

Your Graph should overload operator<< such that cout << myGraph prints all the nodes in the graph, along with their related nodes. See below for an excerpt.

Your Graph also should overload operator== such that mG1 == mG2 is accurately determined.

Turn in and Grading

The Graph class should be implemented as an inline class in the file Graph.h.

This project is worth 50 points, distributed as follows:

Task	Points
Graph::construct properly constructs the graph from the given file.	10
Graph::findPerson successfully determines if a person is in a graph.	5
Graph::findPath correctly finds the shortest path between two nodes. It shall print out the path or state that no path could be found.	15
operator<< is correctly overloaded to print the graph. Each node and their relationship to other nodes shall be printed.	5
operator== is correctly overloaded to determine equivalence between two graphs.	5
Code is well organized, well documented, and properly formatted. Variable names are clear, and readable.	10