Efficient distance matrix storage structure in C#

DistanceMatrix.cs

/// <summary>
/// Efficient storage of a distance matrix.
/// </summary>
/// <remarks>
/// This is a storage space efficient data-structure for edge weights in an undirected graph, where edges are specified as a pair of integer verticies.
///
/// Let "dAB" be the distance from point A to point B, where A and B are positive integers indexing points.
///
/// A full, unoptimzied matrix would look like this:
/// <code>
///    [ d00 d10 d20 d30 ]
///    [ d01 d11 d21 d31 ]
///    [ d02 d12 d22 d32 ]
///    [ d03 d13 d23 d33 ]
/// </code>
/// Distance to the same point is always zero, so the matrix becomes:
/// <code>
///    [   0 d10 d20 d30 ]
///    [ d01   0 d21 d31 ]
///    [ d02 d12   0 d32 ]
///    [ d03 d13 d23   0 ]
/// </code>
/// Because dXY == dYX, the matrix can be further simplified into a lower triangular matrix. Note that A is the column and B is the row.
/// <code>
///    [ 0     .   .   . ]
///    [ d01   0   .   . ]
///    [ d02 d12   0   . ]
///    [ d03 d13 d23   0 ]
/// </code>
/// Therefore, distances can be stored in a lower triangular matrix of size n-1 where A < B, with a quick check for A == B
/// <code>
///    [ d01   .   . ]
///    [ d02 d12   . ]
///    [ d03 d13 d23 ]
/// </code>
/// This can be efficiently stored as an array, where the array grows by the size of the next row for each additional dimension!
/// <code>
///    [ d01 d02 d12 d03 d13 d23 ]
/// </code>
/// Growing and shrinking the data-structure is possible; the internal array just needs to be adjusted to the new dimension.
/// </remarks>
/// <typeparam name="Tdistance">Something representing a distance, e.g., <c>int</c>, <c>float</c>, <c>double</c></typeparam>
public class DistanceMatrix<Tdistance>
{
    private int dimension;
    private Tdistance[] distances = null; // lower triangular matrix

    /// <summary>
    /// Initializes a new instance of the <see cref="DistanceMatrix{Tdistance}"/> class.
    /// Creates a distance matrix of the specified dimension.
    /// </summary>
    /// <param name="dimension">Matrix dimension</param>
    /// <param name="reflexiveDistance">Reflexive distance (i.e., distance from "A" to "A"), defaults to <c>default</c> for the type.</param>
    public DistanceMatrix(int dimension, Tdistance reflexiveDistance = default)
    {
        this.Resize(dimension);
        this.ReflexiveDistance = reflexiveDistance;
    }

    /// <summary>
    /// Gets or sets the dimension of the matrix.
    /// Setting to a smaller dimension will discard values.
    /// New values, if any, are left at their default value.
    /// </summary>
    /// <seealso cref="Resize(int)"/>
    public int Dimension { get => this.dimension; set => this.Resize(value); }

    /// <summary>
    /// Gets or sets the distance from a vertex to itself
    /// </summary>
    public Tdistance ReflexiveDistance { get; set; }

    /// <summary>
    /// Gets or sets the distance between vertices <c>a</c> and <c>b</c>.
    /// Since distances are undirected, the order of <c>a</c> and <b>b</b> doesn't matter.
    /// </summary>
    /// <param name="a">The first vertex index</param>
    /// <param name="b">The second vertex index</param>
    /// <returns>The distance between the two vertices</returns>
    public Tdistance this[int a, int b]
    {
        get => (a == b) ? this.ReflexiveDistance : this.distances[Index(a, b, this.dimension)];

        set
        {
            if (a == b)
            {
                throw new ArgumentOutOfRangeException(nameof(b), b, "Cannot set reflexive values independently; use ReflexiveDistance property instead");
            }

            this.distances[Index(a, b, this.dimension)] = value;
        }
    }

    public static int Size(int dimension) => dimension * (dimension + 1) / 2;

    public static int SizeMinusOne(int dimension) => (dimension - 1) * dimension / 2;

    /// <summary>
    /// Sets all distances in the matrix.
    /// </summary>
    /// <param name="distance">The value to store</param>
    public void SetAll(Tdistance distance)
    {
        for (var i = 0; i < this.distances.Length; i++)
        {
            this.distances[i] = distance;
        }
    }

    /// <summary>
    /// Resizes the matrix.
    /// Setting to a smaller dimension will discard values.
    /// New values, if any, are left at their default value.
    /// </summary>
    /// <param name="dimension">The new dimension</param>
    public void Resize(int dimension)
    {
        if (dimension < 1)
        {
            throw new ArgumentOutOfRangeException(nameof(dimension), dimension, "Dimension must be >= 1");
        }
        else if (dimension == this.dimension)
        {
            return; // no change
        }

        this.dimension = dimension;
        var size = SizeMinusOne(dimension); // i.e., store a n-1 row, n-1 column lower triangular matrix
        Array.Resize(ref this.distances, size); // when this.distances = null, creates a new array
    }

    /// <summary>
    /// Resizes the matrix, setting the value of any new entries.
    /// </summary>
    /// <param name="dimension">The new dimension</param>
    /// <param name="initialDistance">The distance to set new entries to</param>
    public void Resize(int dimension, Tdistance initialDistance)
    {
        var lengthBefore = this.distances.Length;
        this.Resize(dimension);
        var delta = this.distances.Length - lengthBefore;
        if (delta > 0)
        {
            for (var i = lengthBefore; i < this.distances.Length; i++)
            {
                this.distances[i] = initialDistance;
            }
        }
    }

    private static int Index(int a, int b, int dimension)
    {
        if (a < 0 || a >= dimension)
        {
            throw new ArgumentOutOfRangeException(nameof(a), a, "Must be greater than 0 and less than the dimension");
        }
        else if (b < 0 || b >= dimension)
        {
            throw new ArgumentOutOfRangeException(nameof(b), b, "Must be greater than 0 and less than the dimension");
        }

        int row = (a < b) ? b : a; // row is maximum
        int col = (a < b) ? a : b; // col is minimum
        return SizeMinusOne(row) + col; // Thx to @gfoidl for the correction from row-1
    }
}

If this works for you, let me know if you want to turn it into a NuGet module!

Unfortunately there's a 🐛 in the index calculation.

Repro:

DistanceMatrix<double> dmat = new(dimension: 3);

dmat[1, 0] = 10d;
dmat[2, 0] = 20d;
dmat[2, 1] = 21d;

Console.WriteLine($"[1,0] <-> [0,1]: 10 <-> {dmat[0, 1]}");
Console.WriteLine($"[2,0] <-> [0,2]: 20 <-> {dmat[0, 2]}");
Console.WriteLine($"[2,1] <-> [1,2]: 21 <-> {dmat[1, 2]}");

outputs:

[1,0] <-> [0,1]: 10 <-> 20             <-- should be 10
[2,0] <-> [0,2]: 20 <-> 20
[2,1] <-> [1,2]: 21 <-> 21

Fix:

-return SizeMinusOne(row - 1) + col;
+return SizeMinusOne(row) + col;

@gfoidl updated, thank you