Welcome to part II of my graph series. Here I’ll be explore the nuts and bolts of setting up the two classes (vertex, and the graph) for a graph structure.
Now like any good programmer, before we jump in let’s familiarize ourselves with what we’ll want our classes to do.
Our vertex much like nodes will hold our information. They will know their immediate neighbors, and we can also set their weight. As we build our structure we’ll also want the ability to add an edge to our graph.
Now what about our Graph class? It acts much like the map of our structure, so it’ll store all the vertices, and know if it’s a directional map or not (one way or bidirectional). Our Graph should be able to add a new vertex, a new edge, and tell me if a path exist among two vertices anywhere within the Graph.
I don’t know about you, but the first thing that pops into my mind as I think about a graph is a railroad network. First let’s establish our vertices. It’ll take in a value as the parameter, and for the edges we’ll set an empty dictionary. It’s our Graph Class’ job to set that up. Our vertex will be responsible for knowing which other vertex it is directly connected to. Since I’m just setting it up I’ll set it to True as a default.

I’ll use a simple get_edges method to find what my vertex is connected too.
There’s more to do, but let’s move in order, and set up a Graph class. Our Graph holds the bigger picture of our structure. It’ll keep a dictionary of our vertices, and let us know if it’s direction or undirectional. Let’s start by giving it the ability to take in a vertex.

Alright, so our Graph should be able to add an edge. As you can see in the Vertex Class we already have an add_edge function, so we can delegate the responsible upon there. What we have to keep track of is if our Graph is one-way or bidirectional (nothing wrong either way). By default it’s bidirectional, but if it isn’t I used an if statement in our function on defining the edge.

Now, I forgot about the weight! That’s an easy fix. I’ll just add it to the add_edge function on the Vertex Class as a default of zero. I’ll then add the real weight on the Graph Class (since our graph should be where it’s assigned), and pass it down to the Vertex Class from there.

Next I want my graph structure to tell me if there is a path connecting my vertices. My find_path function will take in two vertices, start and end. I’ll create a list variable holding the start_vertex. I’ll repopulate this list as I do a while loop to keep checking until I get a match with the end_vertex. That way I’ll know there is a path. When it doesn’t match I’ll use the vertex’s get_edges function to add to the start list.

This is all well-and-good, but what if my Graph is one of those cis-directional Graphs that goes in circles? Well, our while loop will just keep going forever in a circle if there ends up being no path connecting the start_vertex, and end_vertex.
I’ll refactor this this with a seen dictionary that I’ll add every current_vertex too. I’ll then compare the next vertex with the vertices in the seen dictionary before I add it to the start list. Pretty clever, huh?

And that’s a basic Graph and Vertex Class working in tandem to complete your Python data structure known as Graph.