130 lines
4.0 KiB
C#
130 lines
4.0 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
using System.Linq;
|
|
|
|
public static class GraphColoring
|
|
{
|
|
public static void Main(string[] args)
|
|
{
|
|
Colorize("0-1 1-2 2-0 3");
|
|
Colorize("1-6 1-7 1-8 2-5 2-7 2-8 3-5 3-6 3-8 4-5 4-6 4-7");
|
|
Colorize("1-4 1-6 1-8 3-2 3-6 3-8 5-2 5-4 5-8 7-2 7-4 7-6");
|
|
Colorize("1-6 7-1 8-1 5-2 2-7 2-8 3-5 6-3 3-8 4-5 4-6 4-7");
|
|
}
|
|
|
|
private static void Colorize(string graphRepresentation)
|
|
{
|
|
List<Node> graph = InitializeGraph(graphRepresentation);
|
|
List<Node> nodes = new List<Node>(graph);
|
|
while (nodes.Any())
|
|
{
|
|
Node maxNode = nodes.OrderByDescending(n => n.Saturation).First();
|
|
maxNode.Color = MinColor(maxNode);
|
|
UpdateSaturation(maxNode, nodes);
|
|
nodes.Remove(maxNode);
|
|
}
|
|
|
|
Console.WriteLine("Graph: " + graphRepresentation);
|
|
Display(graph);
|
|
}
|
|
|
|
private static Color MinColor(Node node)
|
|
{
|
|
HashSet<Color> colorsUsed = ColorsUsed(node);
|
|
foreach (Color color in Enum.GetValues(typeof(Color)))
|
|
{
|
|
if (!colorsUsed.Contains(color))
|
|
{
|
|
return color;
|
|
}
|
|
}
|
|
return Color.NoColor;
|
|
}
|
|
|
|
private static HashSet<Color> ColorsUsed(Node node)
|
|
{
|
|
return new HashSet<Color>(node.Neighbours.Select(n => n.Color));
|
|
}
|
|
|
|
private static void UpdateSaturation(Node node, List<Node> nodes)
|
|
{
|
|
foreach (Node neighbour in node.Neighbours)
|
|
{
|
|
if (neighbour.Color == Color.NoColor)
|
|
{
|
|
neighbour.Saturation = ColorsUsed(neighbour).Count;
|
|
}
|
|
}
|
|
}
|
|
|
|
private static void Display(List<Node> nodes)
|
|
{
|
|
HashSet<Color> graphColors = new HashSet<Color>(nodes.Select(n => n.Color));
|
|
foreach (Node node in nodes)
|
|
{
|
|
Console.Write($"Node {node.Index}: color = {node.Color}");
|
|
if (node.Neighbours.Any())
|
|
{
|
|
var indexes = node.Neighbours.Select(n => n.Index).ToList();
|
|
Console.Write(new string(' ', 8 - node.Color.ToString().Length) + "neighbours = " + string.Join(", ", indexes));
|
|
}
|
|
Console.WriteLine();
|
|
}
|
|
|
|
Console.WriteLine("Number of colours used: " + graphColors.Count);
|
|
Console.WriteLine();
|
|
}
|
|
|
|
private static List<Node> InitializeGraph(string graphRepresentation)
|
|
{
|
|
SortedDictionary<int, Node> map = new SortedDictionary<int, Node>();
|
|
foreach (string element in graphRepresentation.Split(' '))
|
|
{
|
|
if (element.Contains("-"))
|
|
{
|
|
string[] parts = element.Split('-');
|
|
int index1 = int.Parse(parts[0]);
|
|
int index2 = int.Parse(parts[1]);
|
|
Node node1 = map.GetOrAdd(index1, () => new Node(index1));
|
|
Node node2 = map.GetOrAdd(index2, () => new Node(index2));
|
|
node1.Neighbours.Add(node2);
|
|
node2.Neighbours.Add(node1);
|
|
}
|
|
else
|
|
{
|
|
int index = int.Parse(element);
|
|
map.GetOrAdd(index, () => new Node(index));
|
|
}
|
|
}
|
|
|
|
return new List<Node>(map.Values);
|
|
}
|
|
|
|
public enum Color { Blue, Green, Red, Yellow, Cyan, Orange, NoColor }
|
|
|
|
public class Node
|
|
{
|
|
public Node(int index)
|
|
{
|
|
Index = index;
|
|
Color = Color.NoColor;
|
|
Neighbours = new HashSet<Node>();
|
|
}
|
|
|
|
public int Index { get; }
|
|
public int Saturation { get; set; }
|
|
public Color Color { get; set; }
|
|
public HashSet<Node> Neighbours { get; }
|
|
}
|
|
|
|
private static TValue GetOrAdd<TKey, TValue>(this IDictionary<TKey, TValue> dictionary, TKey key, Func<TValue> valueFactory)
|
|
{
|
|
if (!dictionary.TryGetValue(key, out TValue value))
|
|
{
|
|
value = valueFactory();
|
|
dictionary[key] = value;
|
|
}
|
|
return value;
|
|
}
|
|
}
|