In this lesson, we’ll build a robust implementation of the graph data structure. With just two classes, Vertex and Graph, we can implement a variety of graphs that satisfy the requirements of many algorithms.

Let’s detail the functionality we require from these classes:

• Vertex stores some data.
• Vertex stores the edges to connected vertices and their weight.
• Vertex can add a new edge to its collection.
• Graph stores all the vertices.
• Graph knows if it is directed or undirected.
• Graph can add a new vertex to its collection.
• Graph can add a new edge between stored vertices.
• Graph can tell whether a path exists between stored vertices.

Since we’re dealing with multiple classes, we’ll use multiple files for this implementation. To keep the concepts grounded in a real-world application, we’ll build up a transportation network of railroads and train stations as we go.