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 void DFSEuler(Graph g, int u, Stack<int> S, int[] wierz)
        {
            wierz[u] = 1;
            foreach (Edge e in g.OutEdges(u))
            {
                g.DelEdge(e);
                DFSEuler(g, e.To, S, wierz);
            }
            S.Push(u);
        }

        public static Edge[][] cyclePartition(this Graph G)
        {
            List<Edge[]> cyklList = new List<Edge[]>();
            Graph g = G.Clone();
            Stack<int> S = new Stack<int>();
            int[] wierz = new int[g.VerticesCount];
            for (int i = 0; i < g.VerticesCount; i++)
                if (wierz[i] == 0)
                {
                    DFSEuler(g, i, S, wierz);
                    List<Edge> lista = new List<Edge>();
                    while (S.Count > 1)
                        lista.Add(new Edge(S.Pop(), S.Peek()));
                    Edge[] cyklTab = new Edge[lista.Count];
                    for (int j = 0; j < lista.Count; j++)
                        cyklTab[j] = lista[j];
                    cyklList.Add(cyklTab);
                    S.Clear();
                }
            Edge[][] cykleZwr = new Edge[cyklList.Count][];
            for (int j = 0; j < cyklList.Count; j++)
                cykleZwr[j] = cyklList[j];
            return cykleZwr;
        }





        /// <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)
        {
            Graph g = G.Clone();
            Edge[][] tab = g.cyclePartition();
            foreach (Edge[] cykl in tab)
            {
                int suma = 0;
                foreach (Edge e in g.OutEdges(cykl[0].From))
                    suma++;
                for (int i = 0; i < cykl.Length; i+=2)
                    g.DelEdge(cykl[i]);
            }
            return g;
        }
    }
}