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 long CountAutomorphism;
// Список общих вершин
public object AutomorphismNodes;
// Гипер-граф, содержащий гипер-ребра без общих вершин
public HyperGraph GraphWithoutAutoEdges;
}
public static TheoremAuto TheoremSecond(HyperGraph Graph)
{
if (Theorem.IsEqualNumberOfVertices(Graph))
{
return default;
}
// Копирую гипер-граф, чтобы не изменять исходный
HyperGraph graph = new HyperGraph(Graph);
// Число автоморфизмов
long 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.OfType<object>().ToList(),
GraphWithoutAutoEdges = graph
};
// Вовращаемое значение в виде структуры
return result;
}
public static TheoremAuto TheoremThird(HyperGraph Graph)
{
if (!Theorem.IsEqualNumberOfVertices(Graph))
{
return default;
}
// Копирую гипер-граф, чтобы не изменять исходный
HyperGraph graph = new HyperGraph(Graph);
// Число автоморфизмов
long 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.OfType<object>().ToList(),
GraphWithoutAutoEdges = graph
};
// Вовращаемое значение в виде структуры
return result;
}
public static TheoremAuto TheoremForth(HyperGraph Graph)
{
if (Theorem.IsEqualNumberOfVertices(Graph))
{
return default;
}
// Список общих вершин : Пара <гиперребро, гиперребро>, каждое из которых содержит общие вершины
Dictionary<List<string>, KeyValuePair<List<string>, List<string>>> Pain
= new Dictionary<List<string>, KeyValuePair<List<string>, List<string>>>();
foreach (var edge in Graph.HyperEdge)
{
var intersectedVerticies = Graph.HyperEdge.Where(x => x != edge && x.Intersect(edge).Any()).Select(x => x.Intersect(edge).ToList()).ToList();
foreach (var inter in intersectedVerticies)
{
// Если комбинация общих вершин еще не была добавлена
if (Pain.Keys.FirstOrDefault(key => key.SequenceEqual(inter)) == null)
Pain.Add
(
inter,
new KeyValuePair<List<string>, List<string>>
(
edge,
Graph.HyperEdge.FirstOrDefault(x => x != edge && x.Intersect(inter).Count() == inter.Count)
)
);
}
}
// Берем число общих вершин для первой пары смежных ребер
int k = Pain.Keys.First().Count;
// Если число общих вершин хотя бы для одной пары смежных ребер отличается от первой пары
if (Pain.Keys.Any(x => x.Count != k))
{
// То гиперграф не k-пересекающийся
return default;
}
// Копирую гипер-граф, чтобы не изменять исходный
HyperGraph graph = new HyperGraph(Graph);
foreach (var edge in graph.HyperEdge)
foreach (var same in Pain.Keys)
foreach (var vert in same)
edge.RemoveAll(s => s.Equals(vert));
// Число автоморфизмов
long count = Graph.HyperEdge.Aggregate((long)1, (sum, x) => sum *= Factorial(x.Count - 2 * k)) * Factorial(k);
TheoremAuto result = new TheoremAuto
{
isSatisfyTheorem = true,
CountAutomorphism = count,
AutomorphismNodes = Pain.Keys.OfType<object>().ToList(),
GraphWithoutAutoEdges = graph
};
// Вовращаемое значение в виде структуры
return result;
}
public static TheoremAuto TheoremFifth(HyperGraph Graph)
{
if (!Theorem.IsEqualNumberOfVertices(Graph))
{
return default;
}
// Список общих вершин : Пара <гиперребро, гиперребро>, каждое из которых содержит общие вершины
Dictionary<List<string>, KeyValuePair<List<string>, List<string>>> Pain
= new Dictionary<List<string>, KeyValuePair<List<string>, List<string>>>();
foreach (var edge in Graph.HyperEdge)
{
var intersectedVerticies = Graph.HyperEdge.Where(x => x != edge && x.Intersect(edge).Any()).Select(x => x.Intersect(edge).ToList()).ToList();
foreach (var inter in intersectedVerticies)
{
// Если комбинация общих вершин еще не была добавлена
if (Pain.Keys.FirstOrDefault(key => key.SequenceEqual(inter)) == null)
Pain.Add
(
inter,
new KeyValuePair<List<string>, List<string>>
(
edge,
Graph.HyperEdge.FirstOrDefault(x => x != edge && x.Intersect(inter).Count() == inter.Count)
)
);
}
}
// Берем число общих вершин для первой пары смежных ребер
int k = Pain.Keys.First().Count;
// Если число общих вершин хотя бы для одной пары смежных ребер отличается от первой пары
if (Pain.Keys.Any(x => x.Count != k))
{
// То гиперграф не k-пересекающийся
return default;
}
// Копирую гипер-граф, чтобы не изменять исходный
HyperGraph graph = new HyperGraph(Graph);
var m = Graph.HyperEdge.Count;
var n = Graph.HyperEdge.First().Count;
var X = Graph.HyperEdge.Sum(x => x.Count() - k * 2) + k * Graph.HyperEdge.Count;
// Число автоморфизмов
long count = 0;
if (n - 2 * k == 1)
count = 2 * (X - m * k) * Pow(Factorial(k), m);
else
{
count = 2 * (X - m * k) * Pow((n - 2 * k), m - 1);
for (int i = 1; i < n - 2 * k - 1; i++)
{
count *= Pow((n - 2 * k - i), m) * Pow(Factorial(k), m);
}
}
TheoremAuto result = new TheoremAuto
{
isSatisfyTheorem = true,//(intersect.Count > 0) ? true : false,
CountAutomorphism = count,
AutomorphismNodes = null,
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 long 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;
long 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 long Pow(long input, long grade)
{
if (grade < 0)
throw new Exception("error");
long result = 1;
for (int i = 0; i < grade; i++)
result *= input;
return result;
}
}
}