Theorem.cs

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace HyperGraphModel
{
    public class Theorem
    {
        //  Структура для результурующих данных
        public struct TheoremAuto
        {
            //  Удовлетворяет ли гиперграф теореме
            public bool isSatisfyTheorem;
            //  Число автоморфизмов
            public Int64 CountAutomorphism;
            //  Список общих вершин
            public List<string> AutomorphismNodes;
            //  Гипер-граф, содержащий гипер-ребра без общих вершин
            public HyperGraph GraphWithoutAutoEdges;
        }

        public static TheoremAuto TheoremAutomorphism(HyperGraph Graph)
        {
            //  Копирую гипер-граф, чтобы не изменять исходный
            HyperGraph graph = new HyperGraph(Graph);
            //  Число автоморфизмов
            Int64 count;

            //  Список вершин 0-ого гипер-ребра
            List<string> intersect = new List<string>(graph.HyperEdge[0]);

            //  Находим пересечение множеств вершин гипер-ребер каждого с каждым
            for (int i = 1; i < graph.HyperEdge.Count; i++)
            {
                var res = intersect.Select(j => j.ToString()).Intersect(graph.HyperEdge[i]);
                //  Сохраняем резудьтат пересечения для дальнейшей операции
                intersect = new List<string>();
                foreach (var item in res)
                    intersect.Add(item);
            }
            //  В списке intersect расположены общие для всех гипер-ребер вершины

            //  Удаляем из каждого гипер-ребра все общие вершины
            foreach (var edge in graph.HyperEdge)
                foreach (var elem in intersect)
                    edge.RemoveAll(s => s.Equals(elem));

            //  Согласно формуле, подсчитываем количество автоморфизмов
            count = Factorial(intersect.Count);     //  !k, где k = количество общих вершин
            foreach (var edge in graph.HyperEdge)
                count *= Factorial(edge.Count);     //  *(n - k)!, где n = количество вершин в исходном гипер-ребер, 
                                                    //  а (n-k) = количество вершин в новом гипер-графе без общих вершин

            TheoremAuto result = new TheoremAuto
            {
                isSatisfyTheorem = (intersect.Count > 0) ? true : false,
                CountAutomorphism = count,
                AutomorphismNodes = intersect,
                GraphWithoutAutoEdges = graph
            };
            //  Вовращаемое значение в виде структуры
            return result;
        }

        public static TheoremAuto TheoremAutomorphismForEqualNumberOfVertices(HyperGraph Graph)
        {
            //  Копирую гипер-граф, чтобы не изменять исходный
            HyperGraph graph = new HyperGraph(Graph);
            //  Число автоморфизмов
            Int64 count = 1;

            //  Список вершин 0-ого гипер-ребра
            List<string> intersect = new List<string>(graph.HyperEdge[0]);

            //  Находим пересечение множеств вершин гипер-ребер каждого с каждым
            for (int i = 1; i < graph.HyperEdge.Count; i++)
            {
                var res = intersect.Select(j => j.ToString()).Intersect(graph.HyperEdge[i]);
                //  Сохраняем резудьтат пересечения для дальнейшей операции
                intersect = new List<string>();
                foreach (var item in res)
                    intersect.Add(item);
            }
            //  В списке intersect расположены общие для всех гипер-ребер вершины

            if (intersect.Count != 0)
            {
                int m = graph.HyperEdge.Count,      //  Общее количество ребер в гиперграфе
                    n = graph.HyperEdge[0].Count,   //  Количество вершин в каждом ребре
                    t = intersect.Count,            //  Количество вершин пересечения (t-пересекающийся гиперграф)
                    x = m * (n - t) + t;              //  Общее количество вершин в гиперграфе

                for (int k = 0; k < m; k++)
                    count *= x - t - k * (n - t);
                count *= Pow(Factorial(n - t - 1), m);
                count *= Factorial(t);

                //  Удаляем из каждого гипер-ребра все общие вершины
                foreach (var edge in graph.HyperEdge)
                    foreach (var elem in intersect)
                        edge.RemoveAll(s => s.Equals(elem));
            }
            else
                count = 0;

            TheoremAuto result = new TheoremAuto
            {
                isSatisfyTheorem = (intersect.Count > 0) ? true : false,
                CountAutomorphism = count,
                AutomorphismNodes = intersect,
                GraphWithoutAutoEdges = graph
            };
            //  Вовращаемое значение в виде структуры

            return result;
        }

        public static bool isEqualNumberOfVertices(HyperGraph Graph)
        {
            int count = Graph.HyperEdge[0].Count;
            foreach (var hyperedge in Graph.HyperEdge)
            {
                if (hyperedge.Count != count)
                    return false;
            }
            return true;
        }


        private static Int64 Factorial(int input)
        {
            //  Предрассчитанные значения
            switch (input)
            {
                case 1: return 1;
                case 2: return 2;
                case 3: return 6;
                case 4: return 24;
                case 5: return 120;
                case 6: return 720;
                case 7: return 5040;
                default:
                    break;
            }
            int x;
            Int64 fact = 1;
            try
            {
                //  Вдруг выйдем за пределы максимального значения
                for (x = input; x > 1; x--)
                    fact *= x;
            }
            catch (Exception e)
            {
                Console.WriteLine("\n" + e.Message);
                Console.ReadKey();
                return -1;
            }
            return fact;
        }

        private static Int64 Pow(Int64 input, Int64 grade)
        {
            if (grade < 0)
                throw new Exception("error");
            Int64 result = 1;
            for (int i = 0; i < grade; i++)
                result *= input;
            return result;
        }
    }
}