Local Definition

A binary relationship $ a \rightarrow b $ (read as a is adjacent to b) indicates that there is a direct connection from a to b. In general, an object is not adjacent to itself, that is, $ a \not\rightarrow a $.

In some cases, an adjacency relations may be symmetric; that is, if $ a \rightarrow b $, it follows that $ b \rightarrow a $. In this case, one may write $ a \leftrightarrow b $.

In general, an adjacency relation is explicitly defined by the programmer.

Mathematical Definition

There is no mathematical definition of a general adjacency relation as there is no rule which define the relationship. Further restrictions such as undirected graphs are symmetric or bipartite graphs may have additional mathematical constraints. For example, in a bipartite graph, if $ a \leftrightarrow c $ and $ b \leftrightarrow c $, it follows that $ a \not\leftrightarrow b $.

Operations

Operations on containers storing objects which are related using an adjacency relation include:

• Given an object $a$ in the container:
• return the number of objects $b$ such that $ a \rightarrow b $,
• provide a means for iterating through all $ b $ such that $ a \rightarrow b $,
• return the number of objects $ b $ such that $ b \rightarrow a $,
• Given two objects $ a $ and $ b $ in the container, are they connected; that is, is there a sequence of objects $ a = v_0, v_1, v_2, \ldots, v_{n - 1}, v_n = b $ such that $ v_0 \rightarrow v_1 \rightarrow v_2 \rightarrow \ldots \rightarrow v_{n - 1} \rightarrow v_n $, or, can one get to $ b $ from $ a $?
• If the previous sequence exists, iterate through the objects $ a = v_0, v_1, v_2, \ldots, v_{n - 1}, v_n = b $.

Operations on Symmetric Adjacency Relations

An adjacency relation which is also symmetric defines an equivalence relation where $ a \sim b $ if $ a $ is connected to $ b $ according to the definition of connected above. The relationship of connectedness is an equivalence relations and therefore, any of the operations on an equivalence relation may also be imposed on a container with objects related with a symmetric adjacency relationship.