using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ASD.Graphs;

namespace ASD
{
    public static class MatchingGraphExtender
    {
        /// <summary>
        /// Podział grafu na cykle. Zakładamy, że dostajemy graf nieskierowany i wszystkie wierzchołki grafu mają parzyste stopnie
        /// (nie trzeba sprawdzać poprawności danych).
        /// </summary>
        /// <param name="G">Badany graf</param>
        /// <returns>Tablica cykli; krawędzie każdego cyklu powinny być uporządkowane zgodnie z kolejnością na cyklu, zaczynając od dowolnej</returns>
        /// <remarks>
        /// Metoda powinna działać w czasie O(m)
        /// </remarks>
        public static Edge[][] cyclePartition(this Graph g)
        {
            bool[] visited = new bool[g.VerticesCount];
            int[] from = new int[g.VerticesCount];
            bool[,] delEdges = new bool[g.VerticesCount, g.VerticesCount];
            int edgesLeft = g.EdgesCount;
            int cur = 0;
            Stack<int> s = new Stack<int>();
            List<Edge> edges = new List<Edge>();
            List<List<Edge>> cycles = new List<List<Edge>>();
            int cycleNum = 0;
            int leavesCount = 0;
            for (int i = 0; i < g.VerticesCount; i++)
            {
                if (edgesLeft < 3)
                    break;
                s.Clear();
                s.Push(i);
                for (int n = 0; n < visited.Length; n++)
                {
                    visited[n] = false;
                    from[n] = -1;
                }
                while (s.Count > 0)
                {
                    cur = s.Peek();
                    if (!visited[cur])
                    {
                        visited[cur] = true;
                        from[cur] = cur;
                    }
                    leavesCount = 0;
                    foreach (Edge e in g.OutEdges(cur))
                    {
                        if (delEdges[cur, e.To])
                            continue;
                        if(from[cur] != e.To)
                            leavesCount++;
                        if (visited[e.To] && from[cur] != e.To && !delEdges[cur,e.To])
                        {
                            int headC = e.To, fromHeadC = from[e.To], curFrom = e.To, curTo = cur, peeked = cur;
                            do
                            {
                                peeked = s.Pop();
                                if (peeked == curTo)
                                    foreach (Edge ed in g.OutEdges(curFrom))
                                    {
                                        if (delEdges[ed.From, ed.To])
                                            continue;
                                        if (ed.To == curTo)
                                        {
                                            edges.Add(ed);
                                            delEdges[ed.From, ed.To] = true;
                                            delEdges[ed.To, ed.From] = true;
                                            edgesLeft--;
                                            curFrom = curTo;
                                            curTo = from[curTo];
                                            break;
                                        }
                                    }
                                visited[peeked] = false;
                                from[peeked] = -1;
                            } while (peeked != fromHeadC);
                            visited[headC] = false;
                            from[headC] = -1;
                            foreach (Edge ed in g.OutEdges(fromHeadC))
                            {
                                if (delEdges[ed.From, ed.To])
                                    continue;
                                if (ed.To == headC)
                                {
                                    edges.Add(ed);
                                    edgesLeft--;
                                    delEdges[ed.From, ed.To] = true;
                                    delEdges[ed.To, ed.From] = true;
                                    break;
                                }
                            }
                            List<Edge> tmp = new List<Edge>();
                            foreach (Edge t in edges)
                                tmp.Add(t);
                            cycles.Add(tmp);
                            edges.Clear();
                            cycleNum++;
                            break;
                        }
                        else
                        {
                            visited[e.To] = true;
                            if (from[e.To] == -1)
                            {
                                s.Push(e.To);
                                from[e.To] = cur;
                            }
                        }
                    }
                    if (leavesCount < 1)
                        s.Pop();
                } //!while
            }
            if (cycleNum == 0)
                return null;
            Edge[][] retList = new Edge[cycleNum][];
            for (int i = 0; i < cycles.Count; i++)
            {
                retList[i] = cycles[i].ToArray();
            }
            return retList;
        }

        /// <summary>
        /// Szukanie skojarzenia doskonałego w grafie nieskierowanym o którym zakładamy, że jest dwudzielny i 2^r-regularny
        /// (nie trzeba sprawdzać poprawności danych)
        /// </summary>
        /// <param name="G">Badany graf</param>
        /// <returns>Skojarzenie doskonałe w G</returns>
        /// <remarks>
        /// Metoda powinna działać w czasie O(m), gdzie m jest liczbą krawędzi grafu G
        /// </remarks>
        public static Graph perfectMatching(this Graph G)
        {
            int r = (int)Math.Log(G.OutDegree(0), 2);
            for(int n = 0; n < r; n++)
            {
                Edge[][] cycles = cyclePartition(G);
                if (cycles == null)
                    return G;
                for (int i = 0; i < cycles.GetLength(0); i++)
                    for (int j = 0; j < cycles[i].Length; j += 2)
                    {
                        G.DelEdge(cycles[i][j]);
                    }
            }
            return G;
        }
    }
}