using System;
using System.Collections.Generic;
using System.Linq;
using WPF.ViewModel;
using System.IO;
using HyperGraphModel;
using TheoremAuto = HyperGraphModel.Theorem.TheoremAuto;
namespace WPF.Model
{
/// <summary>
/// Класс работы с гиперграфом.
/// Выполняет создание, наполнение гиперграфа, запускает расчет теорем, выполняет экспорт данных.
/// </summary>
public static class Calculate
{
// Статичный объект гиперграф
public static HyperGraph Graph { get; private set; } = new HyperGraph(new Matrix<int>(), 0);
/// <summary>
/// Создание и наполнение гиперграфа по вводным данным
/// </summary>
/// <param name="Edges">Число гиперребер</param>
/// <param name="SameVert">Число общих или пересекающихся вершин</param>
/// <param name="Verticies">Список числа вершин для каждого ребра</param>
/// <param name="SelectedTheorem">Тип выбранной теоремы. Влияет на наполнение графа (для общих верешин или для пересекающихся).</param>
public static void CreateGraph(int Edges, int SameVert, List<int> Verticies, EnumTheorem SelectedTheorem)
{
try
{
var matrix = new Matrix<int>(0, 0);
if (Verticies.Any())
{
if (SelectedTheorem == EnumTheorem.Second || SelectedTheorem == EnumTheorem.Third)
{
// Общие вершины являются общими для всех ребер
// заполнение ребер отдельными вершинами
var vert = Verticies.Sum(x => x - SameVert) + SameVert;
matrix = new Matrix<int>(vert, Edges);
for (int j = 0, i = 0; j < Verticies.Count; j++)
{
int k = 0;
while (Verticies[j] - SameVert > k)
{
matrix[i++, j] = 1;
k++;
}
}
// заполнение ребер общими вершинами
for (int i = vert - SameVert; i < vert; i++)
for (int j = 0; j < matrix.countColumn; j++)
matrix[i, j] = 1;
}
else if (SelectedTheorem == EnumTheorem.Forth || SelectedTheorem == EnumTheorem.Fifth)
{
// Смежные вершины являются общими между смежными ребрами
var vert = Verticies.Sum(x => x - SameVert * 2) + SameVert * Edges;
matrix = new Matrix<int>(vert, Edges);
for (int j = 0, i = 0; j < Verticies.Count; j++)
{
int k = 0;
if (j != 0) i -= SameVert;
while (Verticies[j] > k)
{
matrix[i++ % vert, j] = 1;
k++;
}
}
}
}
Graph = new HyperGraph(matrix, SameVert, swapLastEdge: SelectedTheorem == EnumTheorem.Forth || SelectedTheorem == EnumTheorem.Fifth);
}
catch (Exception e)
{
MainViewModel.Current.Status = Common.Status.Error;
MainViewModel.Current.StatusMessage = e.Message;
}
}
/// <summary>
/// Запускает расчет теорем
/// </summary>
/// <param name="SelectedTheorem">Тип выбранной теоремы</param>
/// <returns>Значение либо положительное, либо default</returns>
public static TheoremAuto GetTheoremResult(EnumTheorem SelectedTheorem)
{
try
{
if (Graph == null)
throw new Exception("Гипер граф не существует");
switch (SelectedTheorem)
{
case EnumTheorem.Second:
{
return Theorem.TheoremSecond(Graph);
}
case EnumTheorem.Third:
{
return Theorem.TheoremThird(Graph);
}
case EnumTheorem.Forth:
{
return Theorem.TheoremForth(Graph);
}
case EnumTheorem.Fifth:
{
return Theorem.TheoremFifth(Graph);
}
}
throw new Exception("Не обработан тип теоремы");
}
catch (Exception e)
{
MainViewModel.Current.Status = Common.Status.Error;
MainViewModel.Current.StatusMessage = e.Message;
return default;
}
}
/// <summary>
/// Выполняет экспорт результатов расчета в поток в оперативной памяти
/// </summary>
/// <param name="result">Результат расчета теоремой</param>
/// <param name="theorem">Тип теоремы</param>
/// <remarks>Нет реализации для пятой теоремы</remarks>
/// <returns>Если экспорт успешный, поток будет закрыт для чтения и записи</returns>
public static MemoryStream Export(TheoremAuto result, EnumTheorem theorem)
{
MemoryStream memoryStream = new MemoryStream();
switch (theorem)
{
case EnumTheorem.Second:
{
using (StreamWriter sw = new StreamWriter(memoryStream))
{
ExportTheoremaSecond(result, sw);
}
break;
}
case EnumTheorem.Third:
{
using (StreamWriter sw = new StreamWriter(memoryStream))
{
ExportTheoremaThird(result, sw);
}
break;
}
case EnumTheorem.Forth:
{
using (StreamWriter sw = new StreamWriter(memoryStream))
{
ExportTheoremaForth(result, sw);
}
break;
}
case EnumTheorem.Fifth:
{
using (StreamWriter sw = new StreamWriter(memoryStream))
{
ExportTheoremaFifth(result, sw);
}
break;
}
}
return memoryStream;
}
#region Private методы
/// <summary>
/// Вывод результата второй теоремы
/// </summary>
/// <param name="result">Результат расчета</param>
/// <param name="output">Поток вывода</param>
static void ExportTheoremaSecond(TheoremAuto result, StreamWriter output)
{
// Выполняется ли условие согласно теореме 2
output.WriteLine("Согласно теореме 2: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
var AutomorphismNodes = (result.AutomorphismNodes as List<object>).OfType<string>().ToList();
// Вывод вершин и числа автоморфизмов в файл
output.WriteLine("Общие вершины автоморфизмов: ");
foreach (var node in AutomorphismNodes)
{
output.Write(node + " ");
}
output.WriteLine();
// Вывод всех перестановок общих вершин
List<List<string>> transpos = Combinatorics<string>.Transposition(AutomorphismNodes);
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < AutomorphismNodes.Count; g++)
{
output.Write(" {0}", AutomorphismNodes[g]);
}
output.WriteLine("\r\n\t-----------");
// Алгоритм перестановок не учитывает начальную, а начинает со следующей
for (int g = 0; g < transpos.Count; g++)
{
output.Write("{0}: ", g + 2);
for (int f = 0; f < transpos[g].Count; f++)
{
output.Write("{0} ", transpos[g][f]);
}
output.WriteLine("\r\n\t-----------");
}
output.WriteLine("\r\nКоличество автоморфизмов: " + result.CountAutomorphism + "\r\n");
// Обработать все гипер-ребра
for (int i = 0; i < result.GraphWithoutAutoEdges.HyperEdge.Count; i++)
{
// Получить массив перестановок текущего гипер-ребра
transpos = Combinatorics<string>.Transposition(result.GraphWithoutAutoEdges.HyperEdge[i]);
// Вывод всех вершин текущего гипер-ребра
output.Write("Текущее ребро включает вершины:");
for (int g = 0; g < result.GraphWithoutAutoEdges.HyperEdge[i].Count; g++)
{
output.Write(" {0}", result.GraphWithoutAutoEdges.HyperEdge[i][g]);
}
// Вывод всех перестановок текущего гипер-ребра
output.WriteLine();
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < result.GraphWithoutAutoEdges.HyperEdge[i].Count; g++)
{
output.Write(" {0}", result.GraphWithoutAutoEdges.HyperEdge[i][g]);
}
output.WriteLine("\r\n\t-----------");
// Алгоритм перестановок не учитывает начальную, а начинает со следующей
for (int g = 0; g < transpos.Count; g++)
{
output.Write("{0}: ", g + 2);
for (int f = 0; f < transpos[g].Count; f++)
{
output.Write("{0} ", transpos[g][f]);
}
output.WriteLine("\r\n\t-----------");
}
output.WriteLine();
}
}
}
/// <summary>
/// Вывод результата третьей теоремы
/// </summary>
/// <param name="result">Результат расчета</param>
/// <param name="output">Поток вывода</param>
static void ExportTheoremaThird(TheoremAuto result, StreamWriter output)
{
// Выполняется ли условие согласно теореме 3
output.WriteLine("Согласно теореме 3: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
var AutomorphismNodes = (result.AutomorphismNodes as List<object>).OfType<string>().ToList();
// Вывод вершин и числа автоморфизмов в файл
output.WriteLine("Общие вершины автоморфизмов: ");
foreach (var node in AutomorphismNodes)
{
output.Write(node + " ");
}
output.WriteLine();
// Вывод всех перестановок общих вершин
List<List<string>> transpos = Combinatorics<string>.Transposition(AutomorphismNodes);
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < AutomorphismNodes.Count; g++)
{
output.Write(" {0}", AutomorphismNodes[g]);
}
output.WriteLine("\r\n\t-----------");
// Алгоритм перестановок не учитывает начальную, а начинает со следующей
for (int g = 0; g < transpos.Count; g++)
{
output.Write("{0}: ", g + 2);
for (int f = 0; f < transpos[g].Count; f++)
{
output.Write("{0} ", transpos[g][f]);
}
output.WriteLine("\r\n\t-----------");
}
output.WriteLine("\r\nКоличество автоморфизмов: " + result.CountAutomorphism + "\r\n");
// Получаю гипер-граф, автоморфизмы которого нужно получить
// Это гипер-граф, из которого удалены общие для всех ребер вершины
HyperGraph graph = new HyperGraph(result.GraphWithoutAutoEdges);
// Список со всеми автоморфизмами
List<string> automorphism = new List<string>();
// Трехмерный список, содержащий для каждого ребра (aka 'список ребер') список всех возможных транспозиций (aka перестановки, число которых n!) всех вершин данного ребра (а вершины также заключены в список)
// т.е. обращение comboVertInEdges[0] - список всех возможных перестановок 0-ого гипер-ребра графа
// comboVertInEdges[0][1] - список вершин, входящих в 2-ю (по очередности с 0) перестановку вершин 0-ого ребра
// comboVertInEdges[4] - список всех возможных перестановок 4-ого гипер-ребра графа....
// Этот список заполняется один раз сразу для всех ребер, т.к. содержимое ребер (вершин) неизменно
List<List<List<string>>> comboVertInEdges = new List<List<List<string>>>();
// Двумерный список - список всех возможных перестановок n-ого ребра
List<List<string>> vertInEdge;
// Количество перестановок n-ого ребра, одинаково для всех ребер (т.к. мощность каждого ребра равна)
int size = 0;
// Перебор всех ребер гипер-графа для заполнения трехмерного списка
for (int i = 0; i < graph.HyperEdge.Count; i++)
{
// Получаем текущую перестановку
vertInEdge = Combinatorics<string>.Transposition(graph.HyperEdge[i]);
// Добавляем 0-ю перестановку, которую не учитывает алгоритм
vertInEdge.Insert(0, graph.HyperEdge[i]);
// Помещаем все перестановки ребра в общий список
comboVertInEdges.Add(vertInEdge);
// Запоминаем значение на будущее
size = vertInEdge.Count;
}
// Получив все перестановки каждого из ребер, нужно сформировать автоморфизмы гипер-графа
// Учитывая порядок ребер 0,1,2,3,...,n (где n - количество ребер) и то, что для каждого ребра существует X перестановок
// существует X^n комбинаций перестановок гипер-графа
//
// Если два ребра по 3 вершины, то количество перестановок = 3!= 6 и есть 6*6 комбинаций этих перестановок
// Если 3 ребра по 8 вершин, то количество перестановок = 8! и есть 8! * 8! * 8! = (8!)^3 комбинаций этих перестановок
//
// В качестве аргументов передаются n='количество комбинаций' и m='количество ребер'
// Результат - двумерный список, где каждый список содержит последовательность вида
// 0 0 0 (для трех ребер), что предполагает комбинацию 0-х перестановок каждого ребра
// 0 0 1 - комбинация 0-й перестановки 0-ого и 1-ого ребра И 1-й перестановки 2-ого ребра
// 0 0 2 - комбинация 0-й перестановки 0-ого и 1-ого ребра И 2-й перестановки 2-ого ребра
// 0 1 0 - комбинация 0-й перестановки 0-ого ребра; 1-й перестановки 1-ого ребра; 0-й перестановки 2-ого ребра
// ...
var combination = Combinatorics<int>.CombinationWithReplays(size, graph.HyperEdge.Count);
// Однако, выше приведенные комбинации работают лишь с перестановками непосредственно вершин, сохраняя позиции ребер
// Порядок (1-е ребро)-(2-е ребро)-(3-е ребро) остается неизменным. Меняется лишь 'порядок' внутри ребер
// Чтобы добавить движение в плоскости ребер, нужно найти все возможные перестановки (без повторений) ребер
// И применить это условие к выше приведенным результатам
// Подготовка массива для создания перестановок ребер
List<int> tmp = new List<int>();
for (int i = 0; i < graph.HyperEdge.Count; i++)
tmp.Add(i);
// Список перестановок ребер
// Вида:
// 0 1 2 (для трех ребер)
// 0 2 1
// 1 0 2
// 1 2 0
// 2 0 1
// 2 1 0 = 3! = 6 штук
var comboEdges = Combinatorics<int>.Transposition(tmp);
comboEdges.Insert(0, tmp);
// т.е. сначала мы выбираем комбинации перестановок вершин ребра, учитывая 0-ю перестановку ребер
// потом выбираем комбинации перестановок вершин ребра, учитывая 1-ю перестановку ребер
// то же самое, учитывая 2-ю перестановку ребер
List<string> edge; // Одно конкретное ребро из графа
string fullString = "", edgeString; // Строковые представления
// Перебор всех перестановок последовательностей ребер
for (int k = 0; k < comboEdges.Count; k++)
{
// Для k-й перестановки ребер перебираем все возможные комбинации перестановок вершин
for (int i = 0; i < combination.Count; i++)
{
// Строковое представление одного автоморфизма
fullString = "";
// Для k-й перестановки ребер и для i-й комбинации перестановок вершин
// Должны перебрать все гипер-ребра
for (int j = 0; j < combination[i].Count; j++)
{
// Строковое представление одного гипер-ребра
edgeString = "(";
// edge - это упорядоченный список вершин определенной перестановки определенного гипер-ребра
// comboVertInEdges - трехмерный список, где первые [] отвечают за номер гипер-ребра
// аргумент [ comboEdges[k][j] ] говорит, что нужно получить j-й номер гипер-ребра из k-й перестановки гипер-ребер
// т.е. итератор j осуществляет обработку всех гипер-ребер конкретного автоморфизма,
// а итератор k указывает, в какой последовательности нужно перебирать гипер-ребра (0-1-2 или 0-2-1 или 2-0-1 или ...)
//
// аргумент [ combination[i][j] ] говорит, что при обращении к определенному гипер-ребру нужно получить номер некоторой из возможных комбинаций вершин данного гипер-ребра
// где итератор i отвечает за номер комбинации (от 0 до (8!)^3, если 3 ребра по 8 вершин)
// а итератор j отвечает за номер перестановки данного гипер-ребра (от 0 до мощности ребер)
edge = comboVertInEdges[comboEdges[k][j]][combination[i][j]];
// Получив конкретное гипер-ребро, перебираем его вершины
foreach (var vert in edge)
edgeString += vert + '-'; // Записываем в строку
// Добавляем в общую строку данного автоморфизма
fullString += edgeString.Remove(edgeString.Length - 1, 1) + ") ";
}
// Записываем строковый вид автоморфизма в общий список
automorphism.Add(fullString);
}
}
// Вывод
for (int i = 0; i < automorphism.Count; i++)
output.WriteLine(i + 1 + ") : " + automorphism[i]);
}
}
/// <summary>
/// Вывод результата четвертой теоремы
/// </summary>
/// <param name="result">Результат расчета</param>
/// <param name="output">Поток вывода</param>
static void ExportTheoremaForth(TheoremAuto result, StreamWriter output)
{
// Выполняется ли условие согласно теореме 4
output.WriteLine("Согласно теореме 4: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
List<List<string>> AutomorphismNodesList = (result.AutomorphismNodes as List<object>).OfType<List<string>>().ToList();
List<List<string>> transpos;
output.WriteLine("\nПересекающиеся вершины автоморфизмов: ");
foreach (var AutomorphismNodes in AutomorphismNodesList)
{
// Вывод вершин и числа автоморфизмов в файл
output.Write("Группа вершин: ");
foreach (var node in AutomorphismNodes)
{
output.Write(node + " ");
}
output.WriteLine();
// Вывод всех перестановок общих вершин
transpos = Combinatorics<string>.Transposition(AutomorphismNodes);
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < AutomorphismNodes.Count; g++)
{
output.Write(" {0}", AutomorphismNodes[g]);
}
output.WriteLine("\r\n\t-----------");
// Алгоритм перестановок не учитывает начальную, а начинает со следующей
for (int g = 0; g < transpos.Count; g++)
{
output.Write("{0}: ", g + 2);
for (int f = 0; f < transpos[g].Count; f++)
{
output.Write("{0} ", transpos[g][f]);
}
output.WriteLine("\r\n\t-----------");
}
}
output.WriteLine("\r\nКоличество автоморфизмов: " + result.CountAutomorphism + "\r\n");
// Обработать все гипер-ребра
for (int i = 0; i < result.GraphWithoutAutoEdges.HyperEdge.Count; i++)
{
// Получить массив перестановок текущего гипер-ребра
transpos = Combinatorics<string>.Transposition(result.GraphWithoutAutoEdges.HyperEdge[i]);
// Вывод всех вершин текущего гипер-ребра
output.Write("Текущее ребро включает вершины:");
for (int g = 0; g < result.GraphWithoutAutoEdges.HyperEdge[i].Count; g++)
{
output.Write(" {0}", result.GraphWithoutAutoEdges.HyperEdge[i][g]);
}
// Вывод всех перестановок текущего гипер-ребра
output.WriteLine();
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < result.GraphWithoutAutoEdges.HyperEdge[i].Count; g++)
{
output.Write(" {0}", result.GraphWithoutAutoEdges.HyperEdge[i][g]);
}
output.WriteLine("\r\n\t-----------");
// Алгоритм перестановок не учитывает начальную, а начинает со следующей
for (int g = 0; g < transpos.Count; g++)
{
output.Write("{0}: ", g + 2);
for (int f = 0; f < transpos[g].Count; f++)
{
output.Write("{0} ", transpos[g][f]);
}
output.WriteLine("\r\n\t-----------");
}
output.WriteLine();
}
}
}
/// <summary>
/// Вывод результата пятой теоремы
/// </summary>
/// <param name="result">Результат расчета</param>
/// <param name="output">Поток вывода</param>
static void ExportTheoremaFifth(TheoremAuto result, StreamWriter output)
{
// Выполняется ли условие согласно теореме 5
output.WriteLine("Согласно теореме 5: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
List<List<string>> AutomorphismNodesList = (result.AutomorphismNodes as List<object>).OfType<List<string>>().ToList();
var sameVertCount = AutomorphismNodesList.First().Count;
var length = result.GraphWithoutAutoEdges.HyperEdge.Count;
List<string> automorphism = new List<string>();
List<int> _default = new List<int>();
for (int i = 0; i < length; i++)
_default.Add(i);
List<List<int>> comboEdges = new List<List<int>>()
{
_default
};
for (int l = 0; l < length; l++)
{
if (l > 0)
{
// swap edge
var swap = new List<int>(comboEdges[comboEdges.Count - 2]);
var item = swap.Last();
swap = swap.Take(swap.Count - 1).ToList();
swap.Insert(0, item);
comboEdges.Add(swap);
}
var reverse = new List<int>(comboEdges.Last());
reverse.Reverse();
comboEdges.Add(reverse);
// reverse
}
var comboVerticies = new Dictionary<int, List<List<string>>>();
int size = 0;
for (int i = 0; i < _default.Count; i++)
{
var edge = new List<string>(result.GraphWithoutAutoEdges.HyperEdge[i]);
var sameFirst = edge.Take(sameVertCount).ToList();
var firstTranspose = Combinatorics<string>.Transposition(sameFirst);
firstTranspose.Insert(0, sameFirst);
var sameLast = edge.Skip(edge.Count - sameVertCount).ToList();
var lastTranspose = Combinatorics<string>.Transposition(sameLast);
lastTranspose.Insert(0, sameLast);
edge = edge.Except(sameFirst).Except(sameLast).ToList();
List<List<string>> transposIndividual = Combinatorics<string>.Transposition(edge);
transposIndividual.Insert(0, edge);
List<List<string>> transpose = new List<List<string>>();
List<List<int>> transposSame = Combinatorics<int>.CombinationWithReplays(sameVertCount, 2);
for (int j = 0; j < transposSame.Count; j++)
{
for (int k = 0; k < transposIndividual.Count; k++)
{
transpose.Add(new List<string>(firstTranspose[transposSame[j][0]]));
transpose.Last().AddRange(new List<string>(transposIndividual[k]));
transpose.Last().AddRange(new List<string>(lastTranspose[transposSame[j][1]]));
}
}
comboVerticies.Add(_default[i], transpose);
size = transpose.Count;
}
var combination = Combinatorics<int>.CombinationWithReplays(size, length);
List<List<string>> djasd = new List<List<string>>();
// Перебор всех перестановок последовательностей ребер
for (int k = 0; k < comboEdges.Count; k++)
{
// Для k-й перестановки ребер перебираем все возможные комбинации перестановок вершин
for (int i = 0; i < combination.Count; i++)
{
var comb = combination[i];
var splitEdges = new List<List<string>>(comb.Count);
splitEdges.AddRange(comb.Select((t, j) => new List<string>(comboVerticies[comboEdges[k][j]][t])));
if (!splitEdges.First().First().Equals(splitEdges.Last().Last()))
{
foreach (var t in splitEdges)
t.Reverse();
}
var _length = splitEdges.Count;
var _len = splitEdges.First().Count;
bool res = true;
for (int j = 0; res && j < _length; j++)
{
for (int l = 0; res && l < sameVertCount; l++)
{
res = splitEdges[j % _length][_len - sameVertCount + l].Equals(
splitEdges[(j + 1) % _length][sameVertCount - 1 - l]);
}
}
if (!res)
continue;
var fullString = "(" + string.Join(") (", splitEdges.Select(lst => string.Join("-", lst))) + ")";
// Записываем строковый вид автоморфизма в общий список
automorphism.Add(fullString);
}
}
output.WriteLine("\r\nКоличество автоморфизмов: " + result.CountAutomorphism + "\r\n");
var y = automorphism.Distinct().ToList();
var ksmkd = (int) Math.Log10(automorphism.Count) + 1;
// Вывод
for (int i = 0; i < automorphism.Count; i++)
{
var iskf = String.Format("{0," + ksmkd + ":0}", i + 1);
output.WriteLine(iskf + ") : " + automorphism[i]);
}
}
}
#endregion
}
}