ICOM 4035 Ė Data Structures

Spring 2008

 

Laboratory 12: Graphs

 

1.    Objectives

 

  1. Understand the Graph data structure.
  2. Study the properties of a Graph.
  3. View some applications of the Graph.
  4. Implement some Graphs traversals.

 

2.    Overview

 

Like a tree, a graph is a non-linear data structure which provides the ability to model complex systems. We define a graph G as {V, E} a collection of vertices and edges. A vertex is an end node in the graph, while the edges are lines connecting two vertices together. In figure 1 G = {{A, C, S, P, M}, {(A, C), (C, S), (P, S). (A, P), (M, M)}}. This graph is undirected which means that the edges have no direction, in other words (A, C) = (C, A). When a graph is directed we can only travel an edge (V1, V2) from its source V1 (outgoing) to its destination V2 (incoming).

Figure 1

A vertex v has a degree d defined as the number of incidents of v. An incidence of v is an occurrence of v in either the source or the destination of an edge. We can have incidence that takes into account all occurrences of v, outgoing incidence taking only the times that v is the source of an edge and incoming incidence where v is the destination of an edge. Deg(v) = Odeg(v) + Ideg(v). If v1 and v2 share an edge they are adjacent to each other.

Graphs can also be weighted, where the edges are weighted according to the value of the element stored in it (figure 2). Such graphs are useful to computing optimal paths from a source vertex to a destination vertex. A path is a collection of edges that connect some vertex v1 with another v2. If all vertices have a path to each other then the graph is said to be connected. If a graph is not connected it can still be separated into sub-graphs which can be connected, these are called the strongly connected components of G.

 

Figure 2

A spanning tree is a root free tree that is composed of all the vertices G but has no cycles in it. If G is not connected then we get forests instead of a spanning tree.

 

Finally a graph also has traversals that allow us to run through the graph and determine its properties. The most common are the Depth First Search (DFS) and the Breadth First Search (BFS).

 

DFS:

1)      Start at a vertex v.

2)      Visit v and pass to one of its adjacent (non-visited) vertices and make it v.

3)      Repeat 2 until you have visited all the vertices in G. If you reach dead end, backtrack until you have a vertex with non-visited neighbors.

 

 

BFS:

1)      Start at a vertex v.

2)      Make a variable hop = 1 and visit all adjacent vertices that you can reach in 1 edge.

3)      Increase the value of hop by one and visit all non-visited vertices that you can reach in hop edges.

4)      Repeat 3 until you visit all vertices.

 

3.    Implementation

The implementation of a graph can be done with several techniques. In this laboratory you will learn three of them.

 

EdgeListGraph: Probably the easiest one of them but maybe not very efficient. It has the lowest space requirements in a system but also the slowest performance. We define our vertices and edges as follow:

 

Vertex: Has a reference to the object stored on it plus a reference to the position that it occupies in the collection of vertices in the graph.

 

Edge: Has a reference to its position in the collection of edges of the graph plus a reference to the object stored on it and the two vertices that form this edge.

 

AdjacencyListGraph: An extension of the edge list graph. The vertices and edges have the same references inside of them; however this type of graph reduces the search for incidences of a vertex by both the vertices and the edges having a reference to a collection of incidence formed by the edges of a given vertex v or the members of an edge e.

 

AdjacencyMatrixGraph: The concept of reference to incidence is pretty different in this one. Probably the most complex to understand and definitely the one with the most storage requirements. This type of graph uses the basics vertices and edges. In addition it also has a two dimensional (n x n) squared matrix, where n is the number of vertices in the graph. The positions A(I, J) inside of these matrix are either null if the vertices in the positions I and J are not adjacent or an incidence edge of both vertices I and J.

 

The implementation of knowing if an edge/vertex has being visited or not can be done either by having a Boolean value inside of them or a hash table with the vertices and edges that have been visited.

 

4.    Practice

In this laboratory you will need to implement both the DFS and the BFS traversals to use them in two applications of electrical and computer engineering.

 

For the DFS a power network is provided to you, the idea is to determine if all the destinations of a central power plant have energy and if not determine which ones donít.

 

For the BFS you will work on a computer network and find the best route from a router to all of its clients/neighbors according to the weight/cost (value stored in the edge). Also provide for the same network the best route according to number of hops (edges) between the same source router and its clients/neighbors.

 

The technique to implement the graph provided to you is the Edge List Graph. If you need to determine if a vertex of an edge have been visited or not use the hash table technique. Download the files here.