aswi20220x00-gitlab/Backend/Core/GraphUtils/Intersections.cs @ a35cb648

using Core.Entities;

namespace Core.GraphUtils
{
    public class Intersections
    {
        /// <summary>
        /// Finds intersections between 1D segments
        /// </summary>
        /// <param name="tags"></param>
        /// <returns></returns>
        public static Dictionary<AnnotationTagGeneric, List<AnnotationTagGeneric>> FindIntersections(List<AnnotationTagGeneric> tags)
        {
            var intersections = new Dictionary<AnnotationTagGeneric, List<AnnotationTagGeneric>>();

            for (int i = 0; i < tags.Count; i++)
            {
                var tagWho = tags[i];
                intersections[tagWho] = new();
                for (int j = 0; j < tags.Count; j++)
                {
                    if (i == j) { continue; }
                    var tagWith = tags[j];

                    if (!((tagWho.Position + tagWho.Length < tagWith.Position) || (tagWith.Position + tagWith.Length < tagWho.Position)))
                    {
                        intersections[tagWho].Add(tagWith);
                    }
                }
            }

            return intersections;
        }

        /// <summary>
        /// Graph coloring
        /// </summary>
        /// <param name="source"></param>
        /// <returns></returns>
        public static Dictionary<AnnotationTagGeneric, int> ColorGraph(Dictionary<AnnotationTagGeneric, List<AnnotationTagGeneric>> source)
        {
            var res = ConvertToMatrix(source);
            var matrix = res.Item1;
            var tagToIntDict = res.Item2;
            var intToTagDict = res.Item3;

            var colors = new int[matrix.GetLength(0)];
            for (int i = 0; i < colors.Length; i++)
            {
                colors[i] = -1;
            }

            for (int coloredNode = 0; coloredNode < colors.Length; coloredNode++)
            {
                var neighbours = GetNeighbours(coloredNode, matrix);
                var neighbourColors = GetNodeColors(neighbours, colors);
                colors[coloredNode] = GetLowestUnusedColor(neighbourColors);
            }

            var coloring = new Dictionary<AnnotationTagGeneric, int>();
            for (int i = 0; i < colors.Length; i++)
            {
                coloring[intToTagDict[i]] = colors[i];
            }

            return coloring;
        }

        private static int GetLowestUnusedColor(List<int> colors)
        {
            int lowestUnusedColor = 0;
            colors.Sort();
            for (int i = 0; i < colors.Count; i++)
            {
                if (colors[i] > i)
                {
                    lowestUnusedColor = i;
                    break;
                }
                else
                {
                    lowestUnusedColor++;
                }
            }

            return lowestUnusedColor;
        }

        private static List<int> GetNodeColors(List<int> nodes, int[] colors)
        {
            var usedColors = new List<int>();
            foreach (var node in nodes)
            {
                if (colors[node] != -1)
                {
                    usedColors.Add(colors[node]);
                }
            }

            return usedColors;
        }

        private static List<int> GetNeighbours(int node, int[,] matrix)
        {
            List<int> neighbours = new();
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                if (matrix[node, i] == 1)
                {
                    neighbours.Add(i);
                }
            }

            return neighbours;
        }

        private static (int[,], Dictionary<AnnotationTagGeneric, int>, Dictionary<int, AnnotationTagGeneric>) ConvertToMatrix(Dictionary<AnnotationTagGeneric, List<AnnotationTagGeneric>> source)
        {
            int[,] matrix = new int[source.Count, source.Count];
            for (int i = 0; i < source.Count; i++)
            {
                for (int j = 0; j < source.Count; j++)
                {
                    matrix[i, j] = 0;
                }
            }

            var tagToIntDict = new Dictionary<AnnotationTagGeneric, int>();
            var intToTagDict = new Dictionary<int, AnnotationTagGeneric>();

            int k = 0;
            foreach (var key in source.Keys)
            {
                tagToIntDict[key] = k;
                intToTagDict[k] = key;
                k++;
            }

            foreach (var key in source.Keys)
            {
                int keyInt = tagToIntDict[key];
                foreach (var neighbour in source[key])
                {
                    int neighbourInt = tagToIntDict[neighbour];
                    matrix[keyInt, neighbourInt] = 1;
                }
            }

            return (matrix, tagToIntDict, intToTagDict);
        }
    }
}