Composition Graphs

Why

We want to visualize function composition.

Definition

A composition graph (or composition diagram) is a directed graph along with a map from vertices to the powerset of a set and a map from edges to functions between sets associated with incident vertices.

Example

For example, let $A$ and $R$ be sets and let $i: A \to A$, $f: A \to R$ and $g: R \to A$ be functions. We can consider the diagram whose graph is $(\set{1, 2, 3}, \set{(1, 2), (2, 3), (1, 3)})$, with vertices one and three corresponding to $A$, vertex 2 corresponding to $R$, edge $(1, 2)$ corresponding to $f$, edge $(2, 3)$ corresponding to $g$ and edge $(1, 3)$ corresponding to $i$. ¹

Path composition

The function associated with a path (or path composition) is the composition of the functions corresponding to the edges along the path. The digram is commutative (call a commutative diagram) if the composition of any two paths between any two vertices result in identical functions.

1. Future editions will include the highly important figures associated with function diagrams. ↩︎