I'm writing code in C++ for a weighted graph. The graph is undirected. I've included instructions and a text file with all the edges and vertices. I need to implement this text file as per the instructions. The edges have all the weights associated. The graph is based off the children's TV show Thomas the Tank Engine.

Instructions:

The Great Northern Railway

Graph Analysis

The show and book series Thomas and Friends is based upon a fictional railroad on the fictional Isle of Sodor. For this assignment, you will write a program that will analyze various changes to the rail map using the graph algorithms we have discussed in class.

Task

The Earl wishes to make the GNR traversable in a loop for tourism. To facilitate this, he will add routes between:

Arlesdale Road and Peel Godred (a distance of 5),

Culdee Feel Summit and Lakeside (a distance of 3),

Ffarquhar and Wellsworth (a distance of 4),

Bendham and Wellsworth (Distance of 4), and

Norramby and Vicarstown (Distance of 4).

You are to, using the data from the input file(s), answer these questions:

Given that the trainyard is in Tidmouth, Sir Topham Hatt wants to know how the travel distance from Tidmouth to all the station changes. What are these routes, and did any get shorter with the new additions?

Is an Euler Circuit possible with the new routes?

Sir Hatt may decide that these new tracks are too expensive to maintain. What is the minimum amount of rail needed (in distance) for the original and new networks and which connections are different?

The Data

The data is in the soror.txt file. Each line stores the source, destination, and distance between stations, e.g.:

Barrow-in-Furness:Vicarstown:1

The string class' find and substr function can be useful in extracting the three sub-parts of the string; there are other ways.

Be sure to put a copy of the file in your code's working directory to load properly.

Implementation

When implementing this assignment, there are three major tasks:

1. Writing a data file loader. We have used several file opening bit of code before; you can use those as a base and refer to the text and online documentation for more information.

2. Write a graph class. It should represent an undirected graph; you can choose whether you use an adjacency matrix, adjacency list, or other. You'll need methods for adding nodes/edges, listing the nodes, finding an edge weight, and getting a node's neighbors at the minimum.

3. Write the algorithms to answer the questions above.

Text File: Vertices and Edges

Barrow-in-Furness:Vicarstown:1 Vicarstown:Ballahoo:5 Vicarstown:Crovan's Gate:7 Ballahoo:Norramby:2 Ballahoo:Crovan's Gate:2 Crovan's Gate:Cros-ny-Cuirn:2 Crovan's Gate:Kellsthorpe Road:4 Cros-ny-Cuirn:Glennock:3 Glennock:Rheneas:3 Rheneas:Skarloey:1 Skarloey:Lakeside:1 Lakeside:Rheneas:1 Kellsthorpe Road:Rolf's Castle:2 Rolf's Castle:Kirk Ronan:2 Kellsthorpe Road:Kildane:7 Kildane:Abbey:2 Abbey:Kirk Machan:4 Kirk Machan:Shiloh:1 Shiloh:Skarloey Road:2 Skarloey Road:Devil's Back:1 Devil's Back:Culdee Fell Summit:1 Kirk Machan:Peel Godred:2 Kildane:Cronk:1 Cronk:Maron:2 Maron:Wellsworth:4 Wellsworth:Suddery:3 Suddery:Brendam:4 Wellsworth:Crosby:2 Crosby:Knapford:4 Knapford:Dryaw:2 Dryaw:Toryreck:1 Toryreck:Elsbridge:2 Elsbridge:Hackenbeck:3 Hackenbeck:Ffarquhar:1 Knapford:Tidmouth:1 Tidmouth:Haultraugh:3 Haultraugh:Arlesburgh West:2 Arlesburgh West:Arlesburgh Bridge St.:1 Arlesburgh Bridge St.:Ffaquhar Road:1 Ffaquhar Road:Marthwaite:1 Marthwaite:Arlesdale Green:1 Arlesdale Green:Arlesdale:1