1 |
8dc25caa
|
Vojtěch Bartička
|
using Core.Entities;
|
2 |
|
|
|
3 |
|
|
namespace Core.GraphUtils
|
4 |
|
|
{
|
5 |
|
|
public class Intersections
|
6 |
|
|
{
|
7 |
|
|
public static Dictionary<AnnotationTag, List<AnnotationTag>> FindIntersections(List<AnnotationTag> tags)
|
8 |
|
|
{
|
9 |
|
|
var intersections = new Dictionary<AnnotationTag, List<AnnotationTag>>();
|
10 |
|
|
|
11 |
|
|
for (int i = 0; i < tags.Count; i++)
|
12 |
|
|
{
|
13 |
|
|
var tagWho = tags[i];
|
14 |
|
|
intersections[tagWho] = new();
|
15 |
|
|
for (int j = 0; j < tags.Count; j++)
|
16 |
|
|
{
|
17 |
|
|
if (i == j) { continue; }
|
18 |
|
|
var tagWith = tags[j];
|
19 |
|
|
|
20 |
|
|
if (!((tagWho.Position + tagWho.Length < tagWith.Position) || (tagWith.Position + tagWith.Length < tagWho.Position)))
|
21 |
|
|
{
|
22 |
|
|
intersections[tagWho].Add(tagWith);
|
23 |
|
|
}
|
24 |
|
|
}
|
25 |
|
|
}
|
26 |
|
|
|
27 |
|
|
return intersections;
|
28 |
|
|
}
|
29 |
|
|
|
30 |
|
|
public static Dictionary<AnnotationTag, int> ColorGraph(Dictionary<AnnotationTag, List<AnnotationTag>> source)
|
31 |
|
|
{
|
32 |
|
|
var res = ConvertToMatrix(source);
|
33 |
|
|
var matrix = res.Item1;
|
34 |
|
|
var tagToIntDict = res.Item2;
|
35 |
|
|
var intToTagDict = res.Item3;
|
36 |
|
|
|
37 |
|
|
var colors = new int[matrix.GetLength(0)];
|
38 |
|
|
for (int i = 0; i < colors.Length; i++)
|
39 |
|
|
{
|
40 |
|
|
colors[i] = -1;
|
41 |
|
|
}
|
42 |
|
|
|
43 |
|
|
for (int coloredNode = 0; coloredNode < colors.Length; coloredNode++)
|
44 |
|
|
{
|
45 |
|
|
var neighbours = GetNeighbours(coloredNode, matrix);
|
46 |
|
|
var neighbourColors = GetNodeColors(neighbours, colors);
|
47 |
|
|
colors[coloredNode] = GetLowestUnusedColor(neighbourColors);
|
48 |
|
|
}
|
49 |
|
|
|
50 |
|
|
var coloring = new Dictionary<AnnotationTag, int>();
|
51 |
|
|
for (int i = 0; i < colors.Length; i++)
|
52 |
|
|
{
|
53 |
|
|
coloring[intToTagDict[i]] = colors[i];
|
54 |
|
|
}
|
55 |
|
|
|
56 |
|
|
return coloring;
|
57 |
|
|
}
|
58 |
|
|
|
59 |
|
|
private static int GetLowestUnusedColor(List<int> colors)
|
60 |
|
|
{
|
61 |
|
|
int lowestUnusedColor = 0;
|
62 |
|
|
colors.Sort();
|
63 |
|
|
for (int i = 0; i < colors.Count; i++)
|
64 |
|
|
{
|
65 |
|
|
if (colors[i] > i)
|
66 |
|
|
{
|
67 |
|
|
lowestUnusedColor = i;
|
68 |
|
|
break;
|
69 |
|
|
}
|
70 |
|
|
else
|
71 |
|
|
{
|
72 |
|
|
lowestUnusedColor++;
|
73 |
|
|
}
|
74 |
|
|
}
|
75 |
|
|
|
76 |
|
|
return lowestUnusedColor;
|
77 |
|
|
}
|
78 |
|
|
|
79 |
|
|
private static List<int> GetNodeColors(List<int> nodes, int[] colors)
|
80 |
|
|
{
|
81 |
|
|
var usedColors = new List<int>();
|
82 |
|
|
foreach (var node in nodes)
|
83 |
|
|
{
|
84 |
|
|
if (colors[node] != -1)
|
85 |
|
|
{
|
86 |
|
|
usedColors.Add(colors[node]);
|
87 |
|
|
}
|
88 |
|
|
}
|
89 |
|
|
|
90 |
|
|
return usedColors;
|
91 |
|
|
}
|
92 |
|
|
|
93 |
|
|
private static List<int> GetNeighbours(int node, int[,] matrix)
|
94 |
|
|
{
|
95 |
|
|
List<int> neighbours = new();
|
96 |
|
|
for (int i = 0; i < matrix.GetLength(0); i++)
|
97 |
|
|
{
|
98 |
|
|
if (matrix[node, i] == 1)
|
99 |
|
|
{
|
100 |
|
|
neighbours.Add(i);
|
101 |
|
|
}
|
102 |
|
|
}
|
103 |
|
|
|
104 |
|
|
return neighbours;
|
105 |
|
|
}
|
106 |
|
|
|
107 |
|
|
private static (int[,], Dictionary<AnnotationTag, int>, Dictionary<int, AnnotationTag>) ConvertToMatrix(Dictionary<AnnotationTag, List<AnnotationTag>> source)
|
108 |
|
|
{
|
109 |
|
|
int[,] matrix = new int[source.Count, source.Count];
|
110 |
|
|
for (int i = 0; i < source.Count; i++)
|
111 |
|
|
{
|
112 |
|
|
for (int j = 0; j < source.Count; j++)
|
113 |
|
|
{
|
114 |
|
|
matrix[i, j] = 0;
|
115 |
|
|
}
|
116 |
|
|
}
|
117 |
|
|
|
118 |
|
|
var tagToIntDict = new Dictionary<AnnotationTag, int>();
|
119 |
|
|
var intToTagDict = new Dictionary<int, AnnotationTag>();
|
120 |
|
|
|
121 |
|
|
int k = 0;
|
122 |
|
|
foreach (var key in source.Keys)
|
123 |
|
|
{
|
124 |
|
|
tagToIntDict[key] = k;
|
125 |
|
|
intToTagDict[k] = key;
|
126 |
|
|
k++;
|
127 |
|
|
}
|
128 |
|
|
|
129 |
|
|
foreach (var key in source.Keys)
|
130 |
|
|
{
|
131 |
|
|
int keyInt = tagToIntDict[key];
|
132 |
|
|
foreach (var neighbour in source[key])
|
133 |
|
|
{
|
134 |
|
|
int neighbourInt = tagToIntDict[neighbour];
|
135 |
|
|
matrix[keyInt, neighbourInt] = 1;
|
136 |
|
|
}
|
137 |
|
|
}
|
138 |
|
|
|
139 |
|
|
return (matrix, tagToIntDict, intToTagDict);
|
140 |
|
|
}
|
141 |
|
|
}
|
142 |
|
|
}
|