So the primary mission today is to get you guys to understand inheritance in C++. We've seen it before, but we've never solidified the rules. So lets take a moment to go through some examples so we all know exactly how things work.
First off, the basic idea is the same as it is in Java, although C++ allows you to inherit from multiple superclasses.
The syntax for inheritance in C++ is also less wordy. Instead of adding an extends SuperClass to the end of your class signature, you add a : [access specifier] Class1, [access specifier] Class2, ... [access specifier] ClassN
So lets play with some examples of basic inheritance
*gasp*! How come the last example did what it did?? Because, unlike Java, by default C++ decides which member function to call based on the type of the thing you call it off of (not what it points to). If you want to have Java-like behavior, you need to use the keyword virtual in front of your function prototypes to turn them into methods.
The access specifier states the access level of the public functions in the super class. Observe:
Ok, so now to breeze through the actual material in 10 seconds or less.
A graph is simply a set of vertices connected by edges.
In Lecture, Jason discussed two ways of implementing these things
So Jason decided to go with a Adjacency List-on-steroids approach.
If we have a look at the .h file, we should pay close attention to the general organization of things. Beyond organization, it's just simply maintenence of a bunch of linked lists (and review of that code is up to you.. Don't feel any intense obligation, there's a lot of code there. But if you're curious, by all means, go nuts).
So, some things to notice when looking at graph.h:
This is the main interface for this code. Lets first get an overview of the data structures, then we'll worry about interface later.
So these don't actually do anything as far as implementing the graph, they simply provide wrapper interfaces for the EdgeNode and VertexNode's.
Now we're getting to the meat of the implementation.
A VertexNode is made up of a list entering edges and departing edges, and also maintains the doubly linked list that we saw in the graph class.
There's also some member data to keep track of the key for this vertex (recall vertexKeyCounter in Graph), and a flag if this graph is directed or not.
So the EdgeNode has quite a bit of scary looking data in it. But we all know it's silly to be afraid of code right? Heck, the voltages that make up this code in the RAM are barely enough to feel if you stuck your tounge directly to the chip (not that I've tried or anything...), so why be scared of it when it's on a nice, safe CRT?
Ok, the pointers first. An edgenode is actually a member of the linked list in the graph class, just like the VertexNodes are. So to maintain this linked list, we have to have previous and next pointers for it. Those are at the bottom.
Then we have the pointers to the source vertex for this edge, and the target vertex for this edge. The EdgeNode ALSO maintains the linked list of departing edges and the linked lists of entering edges for the vertex.
So the EdgeNode is maintaining 3 SEPARATE linked lists, two for the VertexNode's lists, and one for the graph node's lists.
Why is all this needed instead of an single adjacency list for the whole Graph? Answer: because it actually makes it easier to implement graph algortihms that require you to traverse all the edges in a graph, all the edges for a vertex, etc.
Ok, so remember the keys in the EdgeNode and the VertexNode? Well those aren't publicly accessible data. If we want to actually attach information to our vertexes or edges, such as letters or weights, we need to define a helper data stucture that associates information in each item to it's key. How do we do this?