## 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.