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.

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