|
Data Structures and Algorithms
with Object-Oriented Design Patterns in Python |
Program 
introduces the Graph class.
The abstract Graph class
extends the abstract Container class
introduced in Program .
Program: Abstract Graph, Graph.Vertex and Graph.Edge __init__ methods.
The abstract Graph class serves as the base class from which
the various concrete graph implementations
discussed in Section are derived.
The abstract Graph class also provides implementations
for the graph traversals described in Section
and for the algorithms that test for cycles and connectedness
described in Section .
As shown in Program ,
the abstract Graph class defines
two nested classes,
Vertex and Edge.
The concrete Graph.Vertex class extends
the abstract Vertex class
defined in Program .
It comprises three instance attributes--_graph, _number and _weight.
The _graph instance attribute
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 instance attribute records this number.
The _weight instance attribute is used to record
the weight on a weighted vertex.
The concrete Graph.Edge class extends
the abstract Edge class
defined in Program .
It comprises four instance attributes--_graph, _v0, _v1, and _weight.
The _graph instance attribute refers to
the graph instance that contains this edge.
The _v0 and _v1 attributes record the vertices
that are the end-points of the edge.
The _weight instance attribute is used to record
the weight on a weighted edge.
Copyright © 2003, 2004 by Bruno R. Preiss, P.Eng. All rights reserved.