PrimMatrix.cs

using System;

namespace Algorithms.Graph.MinimumSpanningTree;

/// <summary>
///     Class that uses Prim's (Jarnik's algorithm) to determine the minimum
///     spanning tree (MST) of a given graph. Prim's algorithm is a greedy
///     algorithm that can determine the MST of a weighted undirected graph
///     in O(V^2) time where V is the number of nodes/vertices when using an
///     adjacency matrix representation.
///     More information: https://en.wikipedia.org/wiki/Prim%27s_algorithm
///     Pseudocode and runtime analysis: https://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm .
/// </summary>
public static class PrimMatrix
{
    /// <summary>
    ///     Determine the minimum spanning tree for a given weighted undirected graph.
    /// </summary>
    /// <param name="adjacencyMatrix">Adjacency matrix for graph to find MST of.</param>
    /// <param name="start">Node to start search from.</param>
    /// <returns>Adjacency matrix of the found MST.</returns>
    public static float[,] Solve(float[,] adjacencyMatrix, int start)
    {
        ValidateMatrix(adjacencyMatrix);

        var numNodes = adjacencyMatrix.GetLength(0);

        // Create array to represent minimum spanning tree
        var mst = new float[numNodes, numNodes];

        // Create array to keep track of which nodes are in the MST already
        var added = new bool[numNodes];

        // Create array to keep track of smallest edge weight for node
        var key = new float[numNodes];

        // Create array to store parent of node
        var parent = new int[numNodes];

        for (var i = 0; i < numNodes; i++)
        {
            mst[i, i] = float.PositiveInfinity;
            key[i] = float.PositiveInfinity;

            for (var j = i + 1; j < numNodes; j++)
            {
                mst[i, j] = float.PositiveInfinity;
                mst[j, i] = float.PositiveInfinity;
            }
        }

        // Ensures that the starting node is added first
        key[start] = 0;

        // Keep looping until all nodes are in tree
        for (var i = 0; i < numNodes - 1; i++)
        {
            GetNextNode(adjacencyMatrix, key, added, parent);
        }

        // Build adjacency matrix for tree
        for (var i = 0; i < numNodes; i++)
        {
            if (i == start)
            {
                continue;
            }

            mst[i, parent[i]] = adjacencyMatrix[i, parent[i]];
            mst[parent[i], i] = adjacencyMatrix[i, parent[i]];
        }

        return mst;
    }

    /// <summary>
    ///     Ensure that the given adjacency matrix represents a weighted undirected graph.
    /// </summary>
    /// <param name="adjacencyMatrix">Adjacency matric to check.</param>
    private static void ValidateMatrix(float[,] adjacencyMatrix)
    {
        // Matrix should be square
        if (adjacencyMatrix.GetLength(0) != adjacencyMatrix.GetLength(1))
        {
            throw new ArgumentException("Adjacency matrix must be square!");
        }

        // Graph needs to be undirected and connected
        for (var i = 0; i < adjacencyMatrix.GetLength(0); i++)
        {
            var connection = false;
            for (var j = 0; j < adjacencyMatrix.GetLength(0); j++)
            {
                if (Math.Abs(adjacencyMatrix[i, j] - adjacencyMatrix[j, i]) > 1e-6)
                {
                    throw new ArgumentException("Adjacency matrix must be symmetric!");
                }

                if (!connection && float.IsFinite(adjacencyMatrix[i, j]))
                {
                    connection = true;
                }
            }

            if (!connection)
            {
                throw new ArgumentException("Graph must be connected!");
            }
        }
    }

    /// <summary>
    ///     Determine which node should be added next to the MST.
    /// </summary>
    /// <param name="adjacencyMatrix">Adjacency matrix of graph.</param>
    /// <param name="key">Currently known minimum edge weight connected to each node.</param>
    /// <param name="added">Whether or not a node has been added to the MST.</param>
    /// <param name="parent">The node that added the node to the MST. Used for building MST adjacency matrix.</param>
    private static void GetNextNode(float[,] adjacencyMatrix, float[] key, bool[] added, int[] parent)
    {
        var numNodes = adjacencyMatrix.GetLength(0);
        var minWeight = float.PositiveInfinity;

        var node = -1;

        // Find node with smallest node with known edge weight not in tree. Will always start with starting node
        for (var i = 0; i < numNodes; i++)
        {
            if (!added[i] && key[i] < minWeight)
            {
                minWeight = key[i];
                node = i;
            }
        }

        // Add node to mst
        added[node] = true;

        // Update smallest found edge weights and parent for adjacent nodes
        for (var i = 0; i < numNodes; i++)
        {
            if (!added[i] && adjacencyMatrix[node, i] < key[i])
            {
                key[i] = adjacencyMatrix[node, i];
                parent[i] = node;
            }
        }
    }
}