zad5.5

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

namespace PW1
{
    class Program
    {

        static void Main(string[] args)
        {
            GraphM g1 = new GraphM(3, 0.5);
            GraphM g2 = new GraphM(3, 0.5);

            g1.Print();
            g2.Print();

            Isomorphism iso = new Isomorphism(g1, g2);
            iso.IsIsomorphicThreads();


            Console.ReadKey();
        }

    }

    class Isomorphism
    {
        GraphM g1;
        GraphM g2;
        int n;

        Thread[] watki;
        static readonly object syncObject = new object();

        public Isomorphism(GraphM gr1, GraphM gr2)
        {
            this.g1 = gr1;
            this.g2 = gr2;
            n = g1.n;
        }

        public void IsIsomorphic()
        {
            int[] t = new int[n];

            for (int i = 0; i < n; i++)
                t[i] = i;

            try
            {
                Permutacje.PermTab(t, n, 0, Out, -1);
            }
            catch (Exception e)
            {
                Console.WriteLine("Grafy sa izomorficzne");
                return;
            }
            Console.WriteLine("Grafy nie sa izomorficzne");
        }

        public void Out(int[] t, int w)
        {
            GraphM gTmp = new GraphM(Permutacje.GraphMatrixPerm(g2.t2, t, n), n);
            // gTmp = permutacja mcierzy g2

            for (int i = 0; i < n; i++) // sprawdzanie czy macierze sa rowne
            {
                for (int j = 0; j < n; j++)
                {
                    if (g1.t2[i, j] != gTmp.t2[i, j])
                        return;
                }
            }

            throw new Exception(); // jesli doszlo do tego momentu, to znacyz ze wszystkie pola w macierzach sa rowne wiec grafy sa izomorficzne
        }

        public void IsIsomorphicThreads()
        {
            watki = new Thread[n];

            for (int i = 0; i < n; i++)
            {
                int x = i;
                watki[i] = new Thread(() => F(x));
            }

            for (int i = 0; i < n; i++)
                watki[i].Start();


            for (int i = 0; i < n; i++)
                watki[i].Join();

        }

        public void OutT(int[] tOkrojone, int w)
        {
            int[] t = new int[n];

            t[0] = w;
            for (int i = 0; i < n - 1; i++)
            {
                t[i + 1] = tOkrojone[i];
            }

            GraphM gTmp = new GraphM(Permutacje.GraphMatrixPerm(g2.t2, t, n), n);
            // gTmp = permutacja mcierzy g2

            for (int i = 0; i < n; i++) // sprawdzanie czy macierze sa rowne
            {
                for (int j = 0; j < n; j++)
                {
                    if (g1.t2[i, j] != gTmp.t2[i, j])
                        return;
                }
            }

            throw new Exception(); // jesli doszlo do tego momentu, to znacyz ze wszystkie pola w macierzach sa rowne wiec grafy sa izomorficzne
        }

        public void F(int w)
        {
            int[] t = new int[n];

            for (int i = 0; i < n; i++)
                t[i] = i;

            Permutacje.InitPermForThread(t, n, w);

            int[] tOkrojone = new int[n - 1];
            for (int i = 0; i < n - 1; i++)
                tOkrojone[i] = t[i + 1];

            try
            {
                Permutacje.PermTab(tOkrojone, n - 1, 0, OutT, w);
            }
            catch (Exception e)
            {
                Console.WriteLine("W{0}: Grafy sa izomorficzne", w);

                return;
            }

            Console.WriteLine("W{0}: nie stwierdzono izomorfizmu", w);

        }

    }

    class GraphM
    {
        // GraphM - graf w reprezentacji Macierzy zerojedynkowej

        static Random rnd = new Random();

        public int n; // liczba wierzcholkow
        public int[,] t2; // macierz

        public GraphM(int[,] matrix, int n)
        {
            this.n = n;
            this.t2 = matrix;
        }

        public GraphM(int n, double p)
        {
            this.n = n;
            t2 = Gnp(n, p);
        }

        public int[,] Gnp(int n, double p)
        {
            int[,] t2 = new int[n, n];

            for (int i = 0; i < n - 1; i++)
                for (int j = i + 1; j < n; j++)
                {
                    if (rnd.Next(0, 10) <= (int)(p * 10))
                        t2[i, j] = t2[j, i] = 1;
                    else
                        t2[i, j] = t2[j, i] = 0;
                }

            return t2;
        }

        public void Print()
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                    Console.Write(t2[i, j] + " ");

                Console.WriteLine();
            }
            Console.WriteLine();
        }


    }

    class Permutacje
    {
        static void Swap(ref int a, ref int b)
        {
            int c = a;
            a = b;
            b = c;
        }

        public static void PermTab(int[] t, int n, int ix, Action<int[], int> Out, int w) // ix = 0..N-1, wywolujemy od 0, w wykorzystujemy tylko jak uzywamy watkow
        {
            if (ix < n - 1)
            {
                for (int i = ix; i < n; i++)
                {
                    Swap(ref t[ix], ref t[i]); // zamienia dwa elementy miejscami
                    PermTab(t, n, ix + 1, Out, w);
                    Swap(ref t[ix], ref t[i]); // przywracamy
                }
            }

            else Out(t, w);
            // powracamy do metody, w klasie ktora wywolala Permutacje
            // konieczne jest zaimplementowanie tej metody w klasie wywolujacej

        }

        public static int[,] GraphMatrixPerm(int[,] A, int[] perm, int n)
        {
            int[,] B = new int[n, n];
            int x, y;

            for (int i = 0; i < n - 1; i++)
            {
                for (int j = i + 1; j < n; j++)
                {
                    if (A[i, j] == 1)
                    {
                        x = perm[i];
                        y = perm[j];
                        B[x, y] = B[y, x] = 1;
                    }
                }
            }

            return B;
        }

        public static void InitPermForThread(int[] perm, int n, int w)
        {
            int i, poz = 1;
            perm[0] = w;
            for (i = 0; i < w; i++) { perm[poz] = i; poz++; }
            for (i = w + 1; i < n; i++) { perm[poz] = i; poz++; }
        }

    }

}