In this lesson, we’ll build a robust implementation of the graph data structure. With just two classes,
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:
Vertexstores some data.
Vertexstores the edges to connected vertices and their weight.
Vertexcan add a new edge to its collection.
Graphstores all the vertices.
Graphknows if it is directed or undirected.
Graphcan add a new vertex to its collection.
Graphcan add a new edge between stored vertices.
Graphcan 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.
The files vertex.py and graph.py contain the classes we’ll be building through the lesson. script.py has some utility code to build a random graph and print its vertices and edges to the console.
Run that code a few times to see different graphs printed and continue when you’re ready.