Last active
April 2, 2024 11:53
-
-
Save stash/85fe1ea6423f350afc35e79aa0556332 to your computer and use it in GitHub Desktop.
Efficient distance matrix storage structure in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/// <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 | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@gfoidl updated, thank you