Section notes for Week 10: Graphs!

Section Notes for Week 10: Graphs!

Story thus far

  1. Conversion of Java into C++
  2. C++ I/O
  3. C++ Preprocessor
  4. Pointers, local variables, and the stack
  5. new and delete
  6. Code Review
  7. More Example Code
  8. Reference Variables and Method invocation
  9. Const keyword
  10. Constructors, copy constructors, and destructors
  11. Operator Overloading and the string class
  12. Big 3
  13. Templates and the array class
  14. Discussion of the List ADT
  15. A look at an array list implementation
  16. A look at the Linked List implementation
  17. Brief Discussion of Doubly Linked Lists
  18. Iterators
  19. Function Objects
  20. Generic Programming
  21. Trees
  22. Binary Search Trees
  23. Tree Traversal
  24. Trees with Back Pointers
  25. Exam Review
  26. Motivation
  27. Cases
  28. Rotations
  29. The Big Picture
  30. Iterators in AVL FIXME: Broken

Today:

  1. Inheritance
  2. Graphs
  3. Graph Implementation

Inheritance

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

  • Constructor order
  • What constructor gets called when (and with init lists)
  • How to call the superclass code
  • function invocation off of pointers

    *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.

  • Example of virtual in superclass and subclass
  • Example of virtual constructors and destructors with init lists

    The access specifier states the access level of the public functions in the super class. Observe:

  • Examples playing with access specifiers

    Graphs

    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

    1. Adjacency Matrix
      So this is a 2D array where each entry in the array represents an edge between two vertices. You can store arbitrary information in that index as well, such as the number of edges, and/or their weight, and/or some info. This implementation is only useful if |E| is =~ |V|^2, or if you need to do a lot of quick lookups between vertices to determine their edge information.
    2. Adjacency List
      This is an array of linked lists for each source vertex. Each node in the linked lists represents a destination of an edge.

    Graph Implementation

    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:

    The graph class

    This is the main interface for this code. Lets first get an overview of the data structures, then we'll worry about interface later.

    1. We have a list of all verticies, and a list of all edges.
    2. The total number of vertices and edges are stored.
    3. We can represent directed and undirected graphs
    4. We have these two integers that apparently keep track of the highest "key" to assign to a vertex.

    The Vertex and Edge Classes

    So these don't actually do anything as far as implementing the graph, they simply provide wrapper interfaces for the EdgeNode and VertexNode's.

    The VertexNode Class

    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.

  • Purty picture on the board of what this thing looks like

    The EdgeNode Class

    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.

    InfoGraphs

    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?

    Inheritance!

  • Quick Tour of the InfoGraph class and interface
  • If time and motivation, write code using the interface. Otherwise, a small amount of mumbling should suffice.