CSC301.01 2015F, Class 25: Implementing the Graph ADT
=====================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Traversal algorithms.
* Marking vertices and edges.
* Three graph implementations and their costs.

Preliminaries
-------------

### Admin

* Hallow Happyween!
* Friday PSA.

### Upcoming Work

* HW (Due Monday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28
* Finish chapter 5 for Monday.

### Extra Credit

#### Academic

* R.L. Stephens II events Friday.
* CS Table next Tuesday: Why is everyone so mean on the Internet?
* Sexual Misconduct at Grinnell College: Results from the 2013 and 2015

#### Peer Support

* Metal Show tonight at 11pm.
* Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
* Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)
* Halloween Day on Saturday.

### Questions

Traversal algorithms
--------------------

* Two kinds: Breadth-first and depth-first.
    * Differ in the order in which we visit nodes.
    * In breadth first, you process the neighbors before processing
      the descendants.  (Visit all the nodes one edge away, then all
      the nodes two edges away, then all the nodes three edges away.)
    * In depth-first traversal, you follow one child as far as you can
      before proceding on to the next child
    * We can think of each traversal as making a tree.
* How do we implement each? (see below)
* How do the implementations differ from the similar algorithms for
  trees? (see below)

Breadth-First Search

   define bfs(Vertex v)
   {
     Queue q = new Queue();
     q.enqueue(v);
     mark(v,"discovered");
     while (!q.isEmpty())
       {
         c = q.dequeue();
         for each n in c.neighbors()
           {
             if (! (marked(n, "processed") || marked(n, "discovered")))
               {
                 mark(n, "discovered");
                 q.enqueue(n);
               }
           }
         mark(c, "processed");
       } // while
   }

  define bfs(Vertex v)
  {
    bfsKernel(v, new Queue())
  }

  define bfs(Vertex v, Queue q)
  {
    mark(v, "visited");
    for each n in v.neighbors()
      {
        if (! marked(n, "visited"))
          {
            q.enqueue(n);
          }
      } // for
    bfs(q.dequeue(), q);
  } // bfs

Depth-First Search

Key operations

* mark(Vertex, Mark)
* marked?(Vertex, Mark)
* neighbors iterator

Breadth-First Search (Trees vs. Graphs)

Depth-First Search (Trees vs. Graphs)

Marking vertices and edges
--------------------------

Three graph implementations and their costs
-------------------------------------------

* Edge list: List of all the edges in the graph (and maybe a list of all
  the vertices)
* Neighbor list: Array/hash of all the vertices, each vertex has a 
  list of its neighbors
* Adjacency matrix: Two-dimensional array.  A cell holds the weight
  of an edge if there is an edge, holds some special value if there is
  no edge.

What is the cost of the key operations for each of these representations?

* Iterate all the neighbors of a node
* Get the weight of the edge from A to B
* Iterate all of the edges in the graph
* Add a vertex
* Add an edge

Group 1: Edge list
Group 2: Neighbor list
Group 3: Adjacency Matrix
Group 4: Neighbor list
Group 5: Adjacency Matrix

In terms of n - number of vertices, m - number of edges

Edge list

* Iterate all the neighbors of a node:
* Get the weight of the edge from A to B: O(m)
* Iterate all of the edges in the graph: O(m)
* Add a vertex: O(1)
* Add an edge: O(1)

Neighbor list

* Iterate all the neighbors of a node:
* Get the weight of the edge from A to B: O(n)
* Iterate all of the edges in the graph: O(n*n), O(n+m)
* Add a vertex: O(1)
* Add an edge: O(1) if we don't have to check, O(n) otherwise

Adjacency matrix

* Iterate all the neighbors of a node:
* Get the weight of the edge from A to B: O(1)
* Iterate all of the edges in the graph: O(n*n)
* Add a vertex: Potentially O(n^2)
* Add an edge: O(1)