Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Directed Graphs

Program  introduces the Digraph class. The abstract Digraph class extends the abstract Graph class defined in Programs , and .

  
Program: Abstract Digraph class.

The abstract Digraph class adds the following operations which apply only to directed graphs:

isStronglyConnected

This bool-valued property is True if the directed graph is strongly connected. Strong connectedness is discussed in Section .

topologicalOrderTraversal

A topological sort is an ordering of the nodes of a directed graph. This traversal visits the nodes of a directed graph in the order specified by a topological sort.

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