Lecture 26 - November 28, 2007

 

Quiz - Question 24 on page 762

 

Went over quiz

Went over terms related to graphs

  • graph
  • vertex
  • edge
  • undirected graph
  • directed graph
  • adjacent vertices
  • path
  • complete graph
  • weighted graph
  • adjacency matrix representation
  • adjacency list

Discussed the adjacency matrix representation

Discussed the use  of a matrix to indicate the length of the paths between vertices

Computed the formula for the number of edges in a complete undirected graph

 

NOTE:  all of the links point to .txt files which you need to rename appropriately to compile and run in Ada.  LOOK AT PROBLEM 28 AT THE END OF CHAPTER 11!

 

Looked at the package specification for a weighted digraph

(page 731ff - Specification 11.3)

 

weighted digraph specification

 

weighted digraph body

 

queue specification

 

queue body

 

Discussed the generic parameters

  • those between the word generic and the word package
    • types
    • functions

Discussed the other

  • type declarations
    • graph_type
    • edge_type
  • package instantiation
    • for Queue
  • user-defined Exceptions
    • VERTEX_ERROR
    • EDGE_ERROR
    • OVERFLOW
  • procedures and their purpose ,preconditions, postconditions, exceptions
    • Clear
      • like MakeEmpty in our Queues
    • Add_Vertex
      • in this case, a city
      • can't have duplicates
      • can't have more than allowed for
    • Add_Edge
      • needs cities it connects to be in as vertices
    • Retrieve
      • get a copy of a vertex
    • Get_Adjacent_Vertices
      • vertex has to be there
  • function
    • Weight_of
      • distance declared as a natural because there might be an edge from a node to itself which has a distance of 0.

 

Looked at 3 graph_Drivers written by professor Adams

 

driver0

 

driver

 

driver2

 

Homework: 

  • study the code in the graph specification, graph body,  and professor Adams' programs THEN
    • either run the code for
      • depth first search
      • breadth first search
      • shortest path
    • or
      • draw a complicated graph and trace the code for a
        • depth first search
        • breadth first search
        • shortest path

 

  • There is nothing to turn in BUT there will be a quiz on the searches on Monday