# Distances, Paths and Circuits in a Graph

The distance functions apply to graphs as well as to digraphs.

## Distances, Paths and Circuits in a Possibly Weighted Graph

There are a few distance and path functions that take into account the fact that the edges of the graph under consideration may be weighted. If the graph is not weighted, then the distance between two vertices is taken to be the length of the shortest path between the vertices. For more details on distance and paths functions in weighted graphs, refer to Section [Distances, Shortest Paths and Minimum Weight Trees](../Multigraphs/shortest-paths.md#multigraph-sec-shortp) in Chapter [Multigraphs](../Multigraphs/index-multigraphs.md#multigraph).

### `Reachable(u, v): GrphVert, GrphVert -> BoolElt`

Return `true` if and only if vertices $u$ and $v$ of a graph $G$ are in the same component of $G$.

### `Distance(u, v): GrphVert, GrphVert -> RngIntElt`

Given two vertices $u$ and $v$ belonging to a graph $G$, return the length of a shortest path from $u$ to $v$. If the graph is weighted, the function returns the total weight of the path from $u$ to $v$. Results in an error if there is no path in $G$ from $u$ to $v$.

### `Geodesic(u, v): GrphVert, GrphVert -> [GrphVert]`

Given vertices $u$ and $v$ belonging to the graph $G$, return a sequence of vertices $u = v_1, v_2, \ldots, v_n = v$ such that the sequence of edges $v_1v_2, v_2v_3, \ldots v_{n-1}v_n$ forms a shortest path joining $u$ and $v$. Results in an error if there is no path in $G$ from $u$ to $v$.

## Distances, Paths and Circuits in a Non-Weighted Graph

The *distance* between two vertices is understood in its usual meaning of being the length of a shortest path between the vertices. The *diameter* of a graph is the maximum of the distances between every pair of vertices in the graph. Alternatively, it is the length of the longest geodesic in the graph. The distance and path functions listed below do not take account of the fact that the graph edges may be weighted.

### `Diameter(G): Grph -> RngIntElt`

The maximum of the distances between every two vertices in the graph $G$ is returned. If $G$ is not connected, the value $-1$ is returned.

### `DiameterPath(G): Grph -> [GrphVert]`

A sequence of vertices defining a longest geodesic in the graph $G$, if the $G$ is connected, or the empty sequence if $G$ is not connected.

### `Ball(u, n): GrphVert, RngIntElt -> { GrphVert}`

Given a vertex $u$ belonging to a graph $G$, and a non-negative integer $n$, return the set of vertices of $G$ that are at distance $n$ or less from $u$.

### `Sphere(u, n): GrphVert, RngIntElt -> { GrphVert}`

Given a vertex $u$ belonging to the graph $G$, and a non-negative integer $n$, return the set of vertices of $G$ that are at distance $n$ from $u$.

### `DistancePartition(u): GrphVert -> [ { GrphVert} ]`

Given a vertex $u$ belonging to the graph $G$, return the partition $P_0 \cup P_1 \cup \ldots \cup P_d$ of the vertex-set of $G$, where $P_i$ is the set of vertices lying at distance $i$ from vertex $u$. The partition is returned as a sequence of sets. Any vertices not connected to $u$ are treated as being at infinite distance from $u$ and are returned as the last set of the partition.

### `IsEquitable(G, P): GrphUnd, { { GrphVert}} -> BoolElt`

### `IsEquitable(G, P): GrphUnd, { { RngIntElt}} -> BoolElt`

Given a partition $P$ of the vertex-set $V(G)$ of the graph $G$, return the value `true` if $P$ is an equitable partition.

### `EquitablePartition(P, G): { { GrphVert}}, GrphUnd -> { { GrphVert}}`

### `EquitablePartition(P, G): { { RngIntElt}}, GrphUnd -> { { GrphVert}}`

Given a partition $P$ of the vertex-set $V(G)$ of the graph $G$, return the coarsest partition of $V(G)$ that refines $P$ and which is equitable.

### `Girth(G): GrphUnd -> RngIntElt`

The girth of graph $G$, i.e. the length of a shortest cycle. To see how the automorphism group of $G$ is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).

### `GirthCycle(G): GrphUnd -> [GrphVert]`

A cycle of shortest length in the graph $G$. To see how the automorphism group of $G$ is computed see Subsection [Graph Colouring and Automorphism Group](automorphism-group-graph.md#graph-subsec-auto-grp-colours).