Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Abstract Graphs

Program gif introduces the AbstractGraph class. The AbstractGraph class extends the AbstractContainer class introduced in Program gif and it implements the Graph interface defined in Program gif.

   program49410
Program: AbstractGraph, GraphVertex, and GraphEdge classes.

The AbstractGraph class serves as the base class from which the various concrete graph implementations discussed in Section gif are derived. The AbstractGraph class also provides implementations for the graph traversals described in Section gif and for the algorithms that test for cycles and connectedness described in Section gif.

As shown in Program gif, the AbstractGraph class defines two nested classes, GraphVertex and GraphEdge. Both classes extend the ComparableObject class introduced in Program gif.

The GraphVertex class implements the Vertex interface. It comprises three fields--graph, number and weight. The graph field refers to the graph instance that contains this vertex. Each vertex in a graph with n vertices is assigned a unique number in the interval [0,n-1]. The number field records this number. The weight field is used to record the weight on a weighted vertex.

The GraphEdge class implements the Edge interface. It comprises four fields--graph, v0, v1, and weight. The graph field refers to the graph instance that contains this edge. The v0 and v1 record the vertices that are the end-points of the edge. The weight field is used to record the weight on a weighted edge.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.