7/18/02
Amir Kamil

Topic: Graphs

Announcements:

Graph Representation:
- Since we've been doing graphs for a week, I'll assume you're familiar 
  with graph representations. If not, we can review them.
- I'll also assume you're familiar with graph vocabulary.
- You can use the adjacency matrix representation of a graph to find 
  all paths with a certain length. Represent an edge in the matrix with 
  a 1, and a non-edge with 0. Then M^n gives you all paths that are of 
  length n. If the position for A to B is nonzero, for example, then 
  there exists a path from A to B of length n. Actually, if you set up 
  the matrix in this way, the value at that position gives you the 
  number of possible paths from A to B.

  Ex:
     2<--1-->4
     |   ^   |   
     |   |   |
     --->3<---

  Adjacency Matrix:

    | 0 1 0 1 |
    | 0 0 1 0 |
    | 1 0 0 0 |
    | 0 0 1 0 |

  Find paths of length 2:

    | 0 1 0 1 | | 0 1 0 1 |      | 0 0 2 0 |
    | 0 0 1 0 | | 0 0 1 0 |  --  | 1 0 0 0 |
    | 1 0 0 0 | | 1 0 0 0 |  --  | 0 1 0 1 |
    | 0 0 1 0 | | 0 0 1 0 |      | 1 0 0 0 |

  The 2 means that there are two possible paths of length 2 from node 1 
  to node 3.

  Find paths of length 3:

    | 0 0 2 0 | | 0 1 0 1 |      | 2 0 0 0 |
    | 1 0 0 0 | | 0 0 1 0 |  --  | 0 1 0 1 |
    | 0 1 0 1 | | 1 0 0 0 |  --  | 0 0 2 0 |
    | 1 0 0 0 | | 0 0 1 0 |      | 0 1 0 1 |

  Since Mnn is nonzero for each n, that means that every node has a 
  path back to itself of length 3.


Graph Traversal:
- Algorithm the same for DFS and BFS, just different data structures.
- DFS uses stack, BFS uses queue.
- Algorithm:
  Clear all node marks.
  Insert start node into (stack/queue)
  While (stack/queue) is not empty:
    Remove a node n from (stack/queue)
    If n is not marked:
      Mark n
      For each edge incident on n, add the other incident node to the 
     (stack/queue)

  Ex:
  DFS on graph above.

  stack = {1}
  remove 1, mark it, add 2 and 4 to the stack
  order removed: 1

  stack = {2, 4}
  remove 2, mark it, add 3 to the stack
  order removed: 1, 2

  stack = {3, 4}
  remove 3, mark it, add 1 to the stack
  order removed: 1, 2, 3

  stack = {1*, 4}
  remove 1, it's marked, so do nothing
  order removed: 1, 2, 3

  stack = {4}
  remove 4, mark it, add 3 to the stack
  order removed: 1, 2, 3, 4

  stack = {3*}
  remove 3, it's marked, so do nothing
  order removed: 1, 2, 3, 4

  stack = {}
  done
  order removed: 1, 2, 3, 4


Topological Sort and DAGs:
- A simpler way to find out if a graph is a DAG is to try doing a 
  topological sort on the graph. If the sort fails, then the graph has 
  a cycle.
- Topological sort orders the nodes in such a way that you can't get 
  from a higher number node to a lower number node.
- Topological sort algorithm:
  Let S be a stack
  Add all vertices in the graph with no incoming edges to the stack
  Let i = 1
  While the stack is not empty
    Remove a vertex v from the stack, number it i
    Increment i
    Remove v from the graph
    Add all vertices in the resulting graph with no incoming edges to 
    the stack

  Ex:
          A-->D-->F
          |   |   |
          V   V   V
          B-->C-->E

  S = {A}
  Remove A from stack, number it 1.
  Result:
              D-->F
              |   |
              V   V
          B-->C-->E
  Now B and D have no incoming edges, so add them to the stack.
  Ordering so far: A

  S = {B, D}
  Remove B from stack, number it 2.
  Result:
              D-->F
              |   |
              V   V
              C-->E
  No new nodes with no incoming edges, so continue.
  Ordering so far: A, B
  
  S = {D}
  Remove D from stack, number it 3.
  Result:
                  F
                  |
                  V
              C-->E
  Now C and F have no incoming edges, so add them to the stack.
  Ordering so far: A, B, D

  S = {C, F}
  Remove C from stack, number it 4.
  Result:
                  F
                  |
                  V
                  E
  No new nodes with no incoming edges, so continue.
  Ordering so far: A, B, D, C

  S = {F}
  Remove F from stack, number it 5.
  Result:
                  
                  
                  
                  E
  Now E has no incoming edges, so add it to the stack.
  Ordering so far: A, B, D, C, F

  S = {E}
  Remove E from stack, number it 6.
  Result:

  Graph is empty, so we're done.
  Ordering: A, B, D, C, F, E

  Since the topological sort was successful, the graph is a DAG.


Djikstra:
- Compute shortest path.
- Algorithm:
  Construct an array D[] with one cell for each vertex.
  Set D[s] = 0 where s is the starting node.
  Set D[u] = (really big) for all vertices u except the starting 
  vertex.
  Construct a min priority queue P containing each node n, with D[n] as 
  its priority.
  While P is not empty:
    Remove a vertex v from P.
    For each vertex z still in P adjacent to v:
      If D[u] + w(u, z) < D[z] then
        D[z] = D[u] + w(u, z)
        Change the piority of z to the new value of D[z]

  w(u, z) above refers to the weight of the edge connecting u and z.

  Ex:
  Let the adjacency matrix for a graph be:
       A B C D E F
   A | 0 2 0 7 0 9 |  where 0 refers to no edge.
   B | 2 0 8 4 0 1 |
   C | 0 8 0 3 0 6 |
   D | 7 4 3 0 8 0 |
   E | 0 0 0 8 0 5 |
   F | 9 1 6 0 5 0 |

  Construct an array D[] with 6 cells, initialize assuming start node 
  is A.
       ---  ---  ---  ---  ---  ---
  D = | 0 || b || b || b || b || b |  b = really big
       ---  ---  ---  ---  ---  ---

  Construct a priority queue:
  P = {[A, 0], [B, b], [C, b], [D, b], [E, b], [F, b]}

  Remove A from P, it has adjacent vertices B, D, and F still in P.
  For B: 0 + 2 < b so set D[B] = 2.
  For D: 0 + 7 < b so set D[D] = 7.
  For F: 0 + 9 < b so set D[F] = 9.
       ---  ---  ---  ---  ---  ---
  D = | 0 || 2 || b || 7 || b || 9 |  b = really big
       ---  ---  ---  ---  ---  ---
  Reorder P: {[B, 2], [D, 7], [F, 9], [C, b], [E, b]}

  Remove B from P, it has adjacent vertices C, D, and F still in P.
  For C: 2 + 8 < b so set D[C] = 10.
  For D: 2 + 4 < 7 so set D[D] = 6.
  For F: 2 + 1 < 9 so set D[F] = 3.
       ---  ---  ---  ---  ---  ---
  D = | 0 || 2 || 10|| 6 || b || 3 |  b = really big
       ---  ---  ---  ---  ---  ---
  Reorder P: {[F, 3], [D, 6], [C, 10], [E, b]}

  Remove F from P, it has adjacent vertices C and E still in P.
  For C: 3 + 6 < 10 so set D[C] = 9.
  For E: 3 + 5 < b so set D[E] = 8.
       ---  ---  ---  ---  ---  ---
  D = | 0 || 2 || 9 || 6 || 8 || 3 |  b = really big
       ---  ---  ---  ---  ---  ---
  Reorder P: {[D, 6], [E, 8], [C, 9]}

  Remove D from P, it has adjacent vertices C and E still in P.
  For C: 6 + 3 = 9 so leave D[C] alone.
  For E: 6 + 8 > 8 so leave D[E] alone.
       ---  ---  ---  ---  ---  ---
  D = | 0 || 2 || 9 || 6 || 8 || 3 |  b = really big
       ---  ---  ---  ---  ---  ---
  Reorder P: {[E, 8], [C, 9]}

  Remove E from P, it has no adjacent vertices still in P.
       ---  ---  ---  ---  ---  ---
  D = | 0 || 2 || 9 || 6 || 8 || 3 |  b = really big
       ---  ---  ---  ---  ---  ---
  Reorder P: {[C, 9]}

  Remove C from P, it has no adjacent vertices still in P.
       ---  ---  ---  ---  ---  ---
  D = | 0 || 2 || 9 || 6 || 8 || 3 |  b = really big
       ---  ---  ---  ---  ---  ---
  Reorder P: {}

  Done.
  So the shortest path from A to B is 2, from A to C is 9, from A to D 
  is 6, from A to E is 8, and from A to F is 3 (assuming I didn't make 
  a mistake).


Minimum Spanning Trees:
- Prim's algorithm is very similar to Djikstra's, so we'll skip it.
- Kruskal's algorithm:
  For each vertex in the graph, create a set with that vertex in it.
  Construct a min priority queue P containing all edges (u, v), with 
  their weights as priorities.
  Construct an empty tree T.
  While the tree doesn't contain all the vertices in the graph:
    Remove an edge (u, v) from P.
    If u and v are not in the same set:
      Add (u, v) to T.
      Merge the sets containing u and v.

  Ex:
  Same graph as above:
       A B C D E F
   A | 0 2 0 7 0 9 |  where 0 refers to no edge.
   B | 2 0 8 4 0 1 |
   C | 0 8 0 3 0 6 |
   D | 7 4 3 0 8 0 |
   E | 0 0 0 8 0 5 |
   F | 9 1 6 0 5 0 |

  Create 6 sets {A}, {B}, {C}, {D}, {E}, and {F}.
  Create the priority queue:
  P = {[B, F, 1], [A, B, 2], [C, D, 3], [B, D, 4], [E, F, 5], 
       [C, F, 6], [A, D, 7], [B, C, 8], [D, E, 8], [A, F, 9]}
  Create empty tree:
  T = 

  Remove (B, F) from P. Since B and F are in different sets, add (B, F) 
  to the tree.
  T =        B
              \ 
               F
  P = {[A, B, 2], [C, D, 3], [B, D, 4], [E, F, 5], [C, F, 6], 
       [A, D, 7], [B, C, 8], [D, E, 8], [A, F, 9]}
  Merge the sets containing B and F:
  {B, F}, {A}, {C}, {D}, {E}

  Remove (A, B) from P. Since A and B are in different sets, add (A, B) 
  to the tree.
  T =        B
            / \ 
           A   F
  P = {[C, D, 3], [B, D, 4], [E, F, 5], [C, F, 6], [A, D, 7], 
       [B, C, 8], [D, E, 8], [A, F, 9]}
  Merge the sets containing A and B:
  {B, F, A}, {C}, {D}, {E}

  Remove (C, D) from P. Since C and D are in different sets, add (C, D) 
  to the tree.
  T =        B     C
            / \     \
           A   F     D
  P = {[B, D, 4], [E, F, 5], [C, F, 6], [A, D, 7], [B, C, 8], 
       [D, E, 8], [A, F, 9]}
  Merge the sets containing C and D:
  {B, F, A}, {C, D}, {E}

  Remove (B, D) from P. Since B and D are in different sets, add (B, D) 
  to the tree.
  T =        B--D--C
            / \     
           A   F     
  P = {[E, F, 5], [C, F, 6], [A, D, 7], [B, C, 8], [D, E, 8], 
       [A, F, 9]}
  Merge the sets containing B and D:
  {B, F, A, C, D}, {E}

  Remove (E, F) from P. Since E and F are in different sets, add (E, F) 
  to the tree.
  T =        B--D--C
            / \     
           A   F--E     
  P = {[C, F, 6], [A, D, 7], [B, C, 8], [D, E, 8], [A, F, 9]}
  Merge the sets containing B and D:
  {B, F, A, C, D, E}

  Since the tree contains all the nodes in the graph, we're done.

  Resulting tree, with weights:
              4  3
            B--D--C
           / \     
         2/  1\  5
         A     F--E