using System;
using System.Collections.Generic;
using System.Linq;

namespace My.Collections;

public class ColoredGraph<T> : Graph<T>
{
    public void GreedyColoring()
    {
        // Einfärbungen zurücksetzen
        Nodes.ForEach(node => (node as dynamic).Color = null);

        foreach (dynamic node in Nodes)
        {
            bool[] usedColors = new bool[Nodes.Count];

            foreach (var neighbor in node.Neighbors)
            {
                int? color = neighbor.Color;

                if (color != null)
                    usedColors[(int)color] = true;
            }

            for (int color = 0; color < usedColors.Length; color++)
            {
                if (usedColors[color] == false)
                {
                    node.Color = color;
                    break;
                }
            }
        }
    }

    public void WelshPowellColoring()
    {
        // Einfärbungen zurücksetzen
        Nodes.ForEach(node => (node as dynamic).Color = null);

        // Knoten nach Gradanzahl absteigend sortieren
        var sortedNodes = Nodes.OrderByDescending(node => node.Degree).ToList();

        int color = 0; // erste Farbe, z.B. 0 = rot, 1 = blau, 2 = gelb, 4 = grün

        // Farbzuweisung beginnend mit Knoten mit höchsten Grad
        for (int i = 0; i < sortedNodes.Count; i++)
        {
            dynamic node = sortedNodes[i];

            if (node.Color == null) // Knoten noch nicht eingefärbt
            {
                // aktuellen Knoten einfärben
                node.Color = color;

                // Färbe nicht benachbarte Knoten mit derselben Farbe
                for (int j = i + 1; j < sortedNodes.Count; j++)
                {
                    dynamic otherNode = sortedNodes[j];

                    if (otherNode.Color == null && !AreNeighbors(node, otherNode)
                        && !AreSameColoredNeighbors(otherNode.Neighbors, color))
                    {
                        otherNode.Color = color;
                    }
                }

                // nächste Farbe
                color++;
            }
        }
    }

    public bool BacktrackingColoring()
    {
        Nodes.ForEach(node => (node as dynamic).Color = null);

        int maxColors = 0;  // mit 1 Farbe beginnen und dann immer erhöhen
        while (!ColorGraphBacktracking(0, maxColors))
        {
            // Erhöhe die Anzahl der Farben, bis eine Lösung gefunden wird
            maxColors++;
        }
        return true;
    }

    bool ColorGraphBacktracking(int nodeIndex, int maxColors)
    {
        if (nodeIndex == Nodes.Count)
            return true; // Alle Knoten wurden erfolgreich gefärbt

        dynamic node = Nodes[nodeIndex];
        for (int color = 0; color <= maxColors; color++)
        {
            if (!AreSameColoredNeighbors(node.Neighbors, color))
            {
                node.Color = color;

                if (ColorGraphBacktracking(nodeIndex + 1, maxColors))
                    return true;   // Rekursiver Aufruf erfolgreich

                node.Color = null; // Backtracking
            }
        }
        return false; // Keine gültige Färbung mit maxColor gefunden
    }
    bool AreSameColoredNeighbors(List<Node<T>> neighbors, int color)
    {
        foreach (dynamic node in neighbors)
        {
            if (node.Color == color)
                return true;
        }
        return false;
    }

    // Prüft, ob zwei Knoten Nachbarn sind
    bool AreNeighbors(Node<T> node1, Node<T> node2)
    {
        return node1.Neighbors.Contains(node2) || node2.Neighbors.Contains(node1);
    }

    public string GenerateDotRepresentation()
    {
        // Graph aus DOT-Language erstellen: https://magjac.com/graphviz-visual-editor/
        // oder über GraphViw->Download (Kommandozeilenprogramm dot.exe)
        // Farben: https://graphviz.org/doc/info/colors.html
        string[] colors = { "red", "yellow", "green", "cyan", "pink", "aliceblue", "wheat", "violet", "snow", "plum1" };
        string dotCode = Directed == true ? "digraph G {\n" : "graph G {\n";

        foreach (dynamic node in Nodes)
        {
            string node1 = node.Item?.ToString() ?? "";

            if (node.Color != null)
                dotCode += $"  \"{node1}\" [shape=circle, style=filled, fillcolor={colors[node.Color]}];\n";

            for (int i = 0; i < node.Neighbors.Count; i++)
            {
                var neighbor = node.Neighbors[i];
                string node2 = neighbor.Item?.ToString() ?? "";
                var weight = node.Weights[i];

                string edge = $"  \"{node1}\" -> \"{node2}\" [label=\"{weight?.ToString() ?? ' '}\"];\n";
                if (Directed == false)  // umgekehrte gleiche Kanten ausfiltern
                {
                    string edgeInverted = $"  \"{node2}\" -> \"{node1}\" [label=\"{weight?.ToString() ?? ' '}\"];\n";
                    if (dotCode.Contains(edgeInverted))
                        continue;
                }
                dotCode += edge;
            }
        }
        if (Directed == false)
            dotCode = dotCode.Replace("->", "--");

        return dotCode + "}";
    }

}