Graph

This is my personal implementation of a templated graph class. The graph class has quickly become one of my favorite data structures over the last few years. I have used this class for a few projects now and have been adding new functionality to it each time to handle new challenges. At this point it is a fairly robust implementation

First lets set up the basics. the Edge, Vertex, and Graph classes.

So let’s start adding some functionality to this. Let’s just start with the access, construction, destruction, assignment, and copying of the class.

Well now, let’s get to the point of the class. This class isn't just to store information. it is all about how the information is modified and the relationships between everything. So let’s give us the ability to modify our information.

I have this class set up to use function pointers to get modify the information inside of the graph. However while inside this class we really don't know how much access the person calling the functions has. We don't know if they want to deal with the vertex class so if can have access to the list of edges or if it just wants to modify the element held in the vertex. So let’s override this for both situations.

Find functions so now that we can call functions on our information how are we gona get to the information we want. Graphs can get fairly large so we are going to want to be able to find the information we need.

Here I create two different types of find functions, one that takes in a value and finds all instances of that value and another that takes in a function pointer to a comparison function that will return any values that respond true to that comparison function. That can be very helpful for finding all values less that a specified number of anything similar.

So now that we can find anything we want and update single elements in the graph what about things that aren’t so targeted. What about when we want to modify/use everything in the graph the same way.

Let’s start with the most basic. The For Each In Order functions will handle calling a function on every vertex/element in the graph in the order that they were added to the graph. This is the fastest traversal though the graph and should be the one used whenever position in the graph does not matter.

Additionally I added functions that will only run up to a specified depth into the graph. this functionality can be used to aide in performance or simply to cap the function to ensure there isn't a stack overflow when dealing with recursion.

Let’s start with the second type of traversal through the graph. For Each Breadth First traversal will call the function passed in on every vertex/element in the graph in order of relationship where the starting node is specified when the function is called. It will call the function on the first node then it will traverse though its neighbors calling the function on them, then to those neighbors neighbors calling the function on them and so on until reaching the final vertex/element or until reaching the specified depth.

Let’s start with the third type of traversal through the graph. For Each Depth First traversal will call the function passed in on every vertex/element in the graph in order of relationship where the starting node is specified when the function is called. Then it will traverse though its neighbors, then to those neighbors neighbors and so on until reaching the final vertex/element or until reaching the specified depth. Once it has reached the end or reached the specified depth then it will unwind and call the function on each vertex/element traversed to in order furthest from the start to the start.

So that is is the graph class in all of its glory. here is the compiled class.