Skip to content

Instantly share code, notes, and snippets.

@stash
Last active April 2, 2024 11:53
Show Gist options
  • Save stash/85fe1ea6423f350afc35e79aa0556332 to your computer and use it in GitHub Desktop.
Save stash/85fe1ea6423f350afc35e79aa0556332 to your computer and use it in GitHub Desktop.
Efficient distance matrix storage structure in C#
/// <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
}
}
@stash
Copy link
Author

stash commented Apr 14, 2023

@gfoidl updated, thank you

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment