Top Up Prev Next Bottom Contents Index Search

6.3 Galaxies and their relationship to Adjacency Lists

To define graph algorithms, adjacency-lists and adjacency-matrices are commonly used to represent a directed graph [Cor90]. An adjacency-matrix is a square matrix where there is one column, i, and one row, j, for each node, i, the graph. An element (i, j) in this matrix is either 1 if there is an arc from i to j, or 0 if no arc exists. The second representation is an adjacency-list in which each node has a list containing the nodes to which it is connected. Thus an adjacency-list is better suited for sparse graphs, whereas adjacency-matrices are well suited for dense graphs.

Blocks with their PortLists can be viewed as equivalent to the adjacency-list data structure. A PortHole, in most domains, is either an input or an output. It contains a farSidePort pointer to the PortHole it is connected to (NULL if it is not connected). To traverse the adjacency-list, a scheduler writer must make use of two iterators in Ptolemy (See "Iterators" on page 3-10): GalStarIter and SuccessorIter. By using a GalStarIter a scheduler writer can iterate over the nodes in the user-specified graph. Then on each of these nodes we can find the adjacent nodes using the SuccessorIter. Although it is not necessary for adjacency-list equivalence, the PredecessorIter is provided to iterate over the nodes that are predecessors to a given node.

There is slight overhead in accessing the graph using both GalStarIter and SuccessorIter over a straight forward implementation of an adjacency-list class. This overhead has a constant cost which is not dependent on the size of the graph. Thus we feel that the robustness achieved by not having two parallel representations of the same graph far outweigh this small overhead.

Top Up Prev Next Bottom Contents Index Search

Copyright © 1990-1997, University of California. All rights reserved.