Kruskal.cs

using System;
using System.Collections.Generic;
using DataStructures.DisjointSet;

namespace Algorithms.Graph.MinimumSpanningTree;

/// <summary>
///     Algorithm to determine the minimum spanning forest of an undirected graph.
/// </summary>
/// <remarks>
///     Kruskal's algorithm is a greedy algorithm that can determine the
///     minimum spanning tree or minimum spanning forest of any undirected
///     graph. Unlike Prim's algorithm, Kruskal's algorithm will work on
///     graphs that are unconnected. This algorithm will always have a
///     running time of O(E log V) where E is the number of edges and V is
///     the number of vertices/nodes.
///     More information: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm .
///     Pseudocode and analysis: https://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/primAlgor.htm .
/// </remarks>
public static class Kruskal
{
    /// <summary>
    ///     Determine the minimum spanning tree/forest of the given graph.
    /// </summary>
    /// <param name="adjacencyMatrix">Adjacency matrix representing the graph.</param>
    /// <returns>Adjacency matrix of the minimum spanning tree/forest.</returns>
    public static float[,] Solve(float[,] adjacencyMatrix)
    {
        ValidateGraph(adjacencyMatrix);

        var numNodes = adjacencyMatrix.GetLength(0);
        var set = new DisjointSet<int>();
        var nodes = new Node<int>[numNodes];
        var edgeWeightList = new List<float>();
        var nodeConnectList = new List<(int, int)>();

        // Add nodes to disjoint set
        for (var i = 0; i < numNodes; i++)
        {
            nodes[i] = set.MakeSet(i);
        }

        // Create lists with edge weights and associated connectivity
        for (var i = 0; i < numNodes - 1; i++)
        {
            for (var j = i + 1; j < numNodes; j++)
            {
                if (float.IsFinite(adjacencyMatrix[i, j]))
                {
                    edgeWeightList.Add(adjacencyMatrix[i, j]);
                    nodeConnectList.Add((i, j));
                }
            }
        }

        var edges = Solve(set, nodes, edgeWeightList.ToArray(), nodeConnectList.ToArray());

        // Initialize minimum spanning tree
        var mst = new float[numNodes, numNodes];
        for (var i = 0; i < numNodes; i++)
        {
            mst[i, i] = float.PositiveInfinity;

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

        foreach (var (node1, node2) in edges)
        {
            mst[node1, node2] = adjacencyMatrix[node1, node2];
            mst[node2, node1] = adjacencyMatrix[node1, node2];
        }

        return mst;
    }

    /// <summary>
    ///     Determine the minimum spanning tree/forest of the given graph.
    /// </summary>
    /// <param name="adjacencyList">Adjacency list representing the graph.</param>
    /// <returns>Adjacency list of the minimum spanning tree/forest.</returns>
    public static Dictionary<int, float>[] Solve(Dictionary<int, float>[] adjacencyList)
    {
        ValidateGraph(adjacencyList);

        var numNodes = adjacencyList.Length;
        var set = new DisjointSet<int>();
        var nodes = new Node<int>[numNodes];
        var edgeWeightList = new List<float>();
        var nodeConnectList = new List<(int, int)>();

        // Add nodes to disjoint set and create list of edge weights and associated connectivity
        for (var i = 0; i < numNodes; i++)
        {
            nodes[i] = set.MakeSet(i);

            foreach(var (node, weight) in adjacencyList[i])
            {
                edgeWeightList.Add(weight);
                nodeConnectList.Add((i, node));
            }
        }

        var edges = Solve(set, nodes, edgeWeightList.ToArray(), nodeConnectList.ToArray());

        // Create minimum spanning tree
        var mst = new Dictionary<int, float>[numNodes];
        for (var i = 0; i < numNodes; i++)
        {
            mst[i] = new Dictionary<int, float>();
        }

        foreach (var (node1, node2) in edges)
        {
            mst[node1].Add(node2, adjacencyList[node1][node2]);
            mst[node2].Add(node1, adjacencyList[node1][node2]);
        }

        return mst;
    }

    /// <summary>
    ///     Ensure that the given graph is undirected.
    /// </summary>
    /// <param name="adj">Adjacency matrix of graph to check.</param>
    private static void ValidateGraph(float[,] adj)
    {
        if (adj.GetLength(0) != adj.GetLength(1))
        {
            throw new ArgumentException("Matrix must be square!");
        }

        for (var i = 0; i < adj.GetLength(0) - 1; i++)
        {
            for (var j = i + 1; j < adj.GetLength(1); j++)
            {
                if (Math.Abs(adj[i, j] - adj[j, i]) > 1e-6)
                {
                    throw new ArgumentException("Matrix must be symmetric!");
                }
            }
        }
    }

    /// <summary>
    ///     Ensure that the given graph is undirected.
    /// </summary>
    /// <param name="adj">Adjacency list of graph to check.</param>
    private static void ValidateGraph(Dictionary<int, float>[] adj)
    {
        for (var i = 0; i < adj.Length; i++)
        {
            foreach (var edge in adj[i])
            {
                if (!adj[edge.Key].ContainsKey(i) || Math.Abs(edge.Value - adj[edge.Key][i]) > 1e-6)
                {
                    throw new ArgumentException("Graph must be undirected!");
                }
            }
        }
    }

    /// <summary>
    ///     Determine the minimum spanning tree/forest.
    /// </summary>
    /// <param name="set">Disjoint set needed for set operations.</param>
    /// <param name="nodes">List of nodes in disjoint set associated with each node.</param>
    /// <param name="edgeWeights">Weights of each edge.</param>
    /// <param name="connections">Nodes associated with each item in the <paramref name="edgeWeights"/> parameter.</param>
    /// <returns>Array of edges in the minimum spanning tree/forest.</returns>
    private static (int, int)[] Solve(DisjointSet<int> set, Node<int>[] nodes, float[] edgeWeights, (int, int)[] connections)
    {
        var edges = new List<(int, int)>();

        Array.Sort(edgeWeights, connections);

        foreach (var (node1, node2) in connections)
        {
            if (set.FindSet(nodes[node1]) != set.FindSet(nodes[node2]))
            {
                set.UnionSet(nodes[node1], nodes[node2]);
                edges.Add((node1, node2));
            }
        }

        return edges.ToArray();
    }
}