CS 131 LECTURE 10 - GRAPHS

Terminology:

Undirected Graph: An Undirected Graph Is An Ordered Pair <V,E> Of Vertices And Edges, Where The Edges Are Unordered Pairs Of Vertices

Adjacent: If (v1,v2) Is An Edge Of A Graph, Then The Vertices v1 And v2 Are Adjacent

Path: The Sequence Of Vertices (v1,v2... vn) Is A Path If For 1 ² i < n, vi And vi+1 Are Adjacent

Connected: An Undirected Graph Is Connected If There Is A Path Between Any Two Vertices

Simple Path: A Simple Path Is A Path In Which Each Edge Is Distinct

Cycle: A Cycle Is A Simple Path In Which The First And Last Vertices Are The Same

Tree: An Undirected Graph Is A Tree If It Is Connected And Contains No Cycles

Important Point:

1. This Definition Of A Tree Differs From Prior Definitions, In That None Of The Vertices Can Be Designated As The Root

Graph Package Specification

GENERIC
  TYPE Vertices IS (<>);
PACKAGE Graph_Package IS
  TYPE Graphs IS PRIVATE;
  PROCEDURE Add_Edge(Graph: IN OUT Graphs;
    Left,Right: IN Vertices);
  FUNCTION Connected(Graph: Graphs;
    Left,Right: Vertices) RETURN Boolean;
PRIVATE
  TYPE Graphs IS ARRAY(Vertices,Vertices)
    OF Boolean;
END Graph_Package;

Adjacency Matrix For Example 3:

Graph Package Body

PACKAGE BODY Graph_Package IS
  Marked: ARRAY(Vertices) OF Boolean;
  FUNCTION Adjacent(Graph: Graphs;
    Left,Right: Vertices) RETURN Boolean IS
  BEGIN
    RETURN Graph(Left,Right);
  END Adjacent;
  PROCEDURE Add_Edge(Graph: IN OUT Graphs;
    Left,Right: IN Vertices) IS
  BEGIN
    Graph(Left,Right) := True;
    Graph(Right,Left) := True;
  END Add_Edge;
  PROCEDURE Search(Graph: IN Graphs;
    Last,This: IN Vertices) IS SEPARATE;
  FUNCTION Connected(Graph: Graphs;
    Left,Right: Vertices) RETURN Boolean IS
  BEGIN
    Marked := (OTHERS => False);
    Search(Graph,Left,Left);
    RETURN Marked(Right) = True;
  END Connected;
END Graph_Package;

Important Point:

1. Marked Array Is Accessed By The Depth First Search

Graph Package Specification

GENERIC
  -- Same As Adjacency Matrix
PRIVATE
  TYPE Nodes;
  TYPE Lists IS ACCESS Nodes;
  TYPE Nodes IS
    RECORD
      Vertex: Vertices;
      Next: Lists;
    END RECORD;
  TYPE Graphs IS ARRAY(Vertices)
    OF Lists;
END Graph_Package;

Adjacency List For Example 3:

Graph Package Body

PACKAGE BODY Graph_Package IS
  Marked: ARRAY(Vertices) OF Boolean;
  FUNCTION Adjacent(Graph: Graphs;
    Left,Right: Vertices) RETURN Boolean IS
    Pointer: Lists;
    Edge: Boolean;
  BEGIN
    Edge := False;
    Pointer := Graph(Left);
    WHILE Pointer /= NULL AND NOT Edge LOOP
      Edge := Pointer.Vertex = Right;
      Pointer := Pointer.Next;
    END LOOP;
    RETURN Edge;
  END Adjacent;
  PROCEDURE Add_Edge(Graph: IN OUT Graphs;
    Left,Right: IN Vertices) IS
    Edge: Lists;
  BEGIN
    Edge := NEW Nodes;
    Edge.Vertex := Right;
    Edge.Next := Graph(Left);
    Graph(Left) := Edge;
    -- Make Reverse Connection
  END Add_Edge;
END Graph_Package;
 

Search Procedure

SEPARATE (Graph_Package)
PROCEDURE Search(Graph: IN Graphs; Last,This: IN Vertices) IS
BEGIN
  IF NOT Marked(This) THEN
    Marked(This) := True;
    FOR Next IN Vertices LOOP
      IF Last /= Next AND THEN
        Adjacent(Graph,This,Next) THEN
        Search(Graph,This,Next);
      END IF;
    END LOOP;
  END IF;
END Search;

Important Points:

1. The Depth First Search Uses Recursion

2. The Breadth First Search Requires A Queue

3. The Depth First Search Is Similar To The Preorder, Inorder Or Postorder Trees Traversals

4. The Breadth First Search Is Similar To The Level Order Tree Traversal

5. Both Searches Work With Either Representation

Search Procedure

WITH FIFO_Queue_Package;
SEPARATE (Graph_Package)
PROCEDURE Search(Graph: IN Graphs;
  Last,This: IN Vertices) IS
  PACKAGE VQ IS NEW
    FIFO_Queue_Package(Vertices);
  Queue: VQ.Queues;
  Previous,Current,Next: Vertices;
BEGIN
  Previous := Last; Current := This;
  Marked(Current) := True;
  VQ.Enqueue(Queue,Previous);
  VQ.Enqueue(Queue,Current);
  WHILE NOT VQ.Empty(Queue) LOOP
    VQ.Dequeue(Queue,Previous);
    VQ.Dequeue(Queue,Current);
    FOR Next IN Vertices LOOP
      IF Previous /= Next AND THEN
        Adjacent(Graph,Current,Next) AND
        THEN NOT Marked(Next) THEN
        VQ.Enqueue(Queue,Current);
        VQ.Enqueue(Queue,Next);
        Marked(Next) := True;
      END IF;
    END LOOP;
  END LOOP;
END Search;

Terminology:

Directed Graph: A Directed Graph Is An Ordered Pair <v,e> Of Vertices And Edges, Where The Edges Are Ordered Pairs Of Vertices, (E Is A Relation On V ´ V)

Transitive Closure: For Any Relation r, The Transitive Closure Of r Is The Relation s Defined As Follows: s Êr, <x,y> Î s, <y,z> Î s Þ <x,z> Î s

Precedence Relation: The Transitive Closure Of The Edges Of Any Directed Graph Is A Precedence Relation

Partial Order: A Precedence Relation > On V ´ V Is A Partial Order If " v Î V, v > v Is False

Topological Order: A Linear Order >>, Is A Topological Order Of A Partial Order > On V´ V, If It Preserves The Partial Order," v,w Î V, v > w, v >> w

Adjacency Matrix Representation

Adjacency List Representation

Transitive Closure For Example 4

Topological Orders For Example 4

1. 1 2 3 4 5 6 7 8
2. 1 2 3 4 5 7 6 8
3. 1 3 2 4 5 6 7 8
4. 1 3 2 4 5 7 6 8
5. 3 1 2 4 5 6 7 8
6. 3 1 2 4 5 7 6 8

Important Point:

1. In Ada, The Compilation Order Dependency Relation Can Be Illustrated By A Directed Graph, The Topological Orders Represent Correct Compilation Orders