using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using HyperGraphModel;
namespace ConsoleTest
{
class Program
{
/* 6 7
0 0 1 0 1 0 0
0 0 0 0 0 1 0
1 1 1 0 0 0 0
0 0 0 1 0 1 1
0 1 1 1 0 0 0
0 0 0 0 1 0 1
*/
/* 11 3
1 1 1
1 0 0
1 0 0
1 0 0
0 1 0
0 1 0
0 1 0
0 1 0
0 0 1
0 0 1
1 1 1
*/
/*
1 0 0 0
1 0 0 0
1 0 0 0
0 1 0 0
0 1 0 0
0 1 0 0
0 0 1 0
0 0 1 0
0 0 1 0
0 0 0 1
0 0 0 1
0 0 0 1
1 1 1 1
*/
static void Main(string[] args)
{
Menu();
}
// Все перестановки графа вывести в файл
static void ExampleAllTranspos(HyperGraph graph, System.IO.StreamWriter output)
{
// Массив (лист) всех возможных перестановок одного множества (гипер-ребра)
List<List<string>> transpos;
// Обработать все гипер-ребра
for (int i = 0; i < graph.HyperEdge.Count; i++)
{
// Получить массив перестановок текущего гипер-ребра
transpos = Combinatorics<string>.Transposition(graph.HyperEdge[i]);
// Вывод всех вершин текущего гипер-ребра
output.Write("Текущее ребро включает вершины:");
for (int g = 0; g < graph.HyperEdge[i].Count; g++)
{
output.Write(" {0}", graph.HyperEdge[i][g]);
}
// Вывод всех перестановок текущего гипер-ребра
output.WriteLine();
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < graph.HyperEdge[i].Count; g++)
{
output.Write(" {0}", graph.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();
}
}
// Найти общие вершины для всех гипер-ребер, подсчитать количество автоморфизмов гипер-графа и вывести все перестановки оставшихся ребер
static void ExampleTheorema(HyperGraph graph, System.IO.StreamWriter output)
{
// Получить результат вычислений
var result = Theorem.TheoremAutomorphism(graph);
// Если удовлетворяет условию "в каждом гиперребре одинаковое количество вершин", то нужно применять не эту теорему (2), а другую (3)
if (Theorem.isEqualNumberOfVertices(graph))
{
Console.WriteLine("Согласно теореме 2: " + false);
Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 3.");
output.WriteLine("Согласно теореме 2: " + false);
}
else
{
// Выполняется ли условие согласно теореме 2
Console.WriteLine("Согласно теореме 2: " + result.isSatisfyTheorem);
if (result.isSatisfyTheorem)
{
// Вывод числа автоморфизмов в консоль
Console.WriteLine("Количество автоморфизмов: " + result.CountAutomorphism);
}
// Выполняется ли условие согласно теореме 2
output.WriteLine("Согласно теореме 2: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
// Вывод вершин и числа автоморфизмов в файл
output.WriteLine("Общие вершины автоморфизмов: ");
foreach (var node in result.AutomorphismNodes)
{
output.Write(node + " ");
}
output.WriteLine();
// Вывод всех перестановок общих вершин
List<List<string>> transpos = Combinatorics<string>.Transposition(result.AutomorphismNodes);
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < result.AutomorphismNodes.Count; g++)
{
output.Write(" {0}", result.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");
// Вывести перестановки в файл
ExampleAllTranspos(result.GraphWithoutAutoEdges, output);
}
}
// Уничтожить временный граф
result.GraphWithoutAutoEdges.Dispose();
}
static void ExampleTheoremaThird(HyperGraph Graph, System.IO.StreamWriter output)
{
// Подсчет количества и получение гипер-графа без общих вершин
var result = Theorem.TheoremAutomorphismForEqualNumberOfVertices(Graph);
// Если НЕ удовлетворяет условию "в каждом гиперребре одинаковое количество вершин", то нужно применять не эту теорему (3), а другую (2)
if (!Theorem.isEqualNumberOfVertices(Graph))
{
Console.WriteLine("Согласно теореме 3: " + false);
Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 2.");
output.WriteLine("Согласно теореме 3: " + false);
}
else
{
// Выполняется ли условие согласно теореме 3
output.WriteLine("Согласно теореме 3: " + result.isSatisfyTheorem);
if (result.isSatisfyTheorem)
{
// Вывод числа автоморфизмов в консоль
Console.WriteLine("Количество автоморфизмов: " + result.CountAutomorphism);
}
Console.WriteLine("Согласно теореме 3: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
// Вывод вершин и числа автоморфизмов в файл
output.WriteLine("Общие вершины автоморфизмов: ");
foreach (var node in result.AutomorphismNodes)
{
output.Write(node + " ");
}
output.WriteLine();
// Вывод всех перестановок общих вершин
List<List<string>> transpos = Combinatorics<string>.Transposition(result.AutomorphismNodes);
// Вывод начальной перестановки
output.Write("1:");
for (int g = 0; g < result.AutomorphismNodes.Count; g++)
{
output.Write(" {0}", result.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]);
}
}
}
static void Menu()
{
string inputPath = "D:\\input.txt", outputPath = "D:\\output.txt";
System.IO.StreamReader input;
System.IO.StreamWriter output;
// Экземпляр гипер-графа, созданный на основе загружаемой матрицы инцидентности
HyperGraph graph = null;
while (true)
{
Console.Write("Путь к файлу входных данных (матрица инцидентности): ");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine(inputPath);
Console.ResetColor();
Console.Write("Путь к файлу результатов: ");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine(outputPath);
Console.ResetColor();
Console.WriteLine("\nДля выбора пункта меню введите соответствующую цифру.\n");
Console.WriteLine("1. Изменить путь к файлу входных данных.");
Console.WriteLine("2. Изменить путь к файлу результатов.\n");
if (graph == null)
{
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("3. Выполнить загрузку гиперграфа из файла.\n");
Console.ResetColor();
}
else
{
Console.WriteLine("3. Выполнить загрузку гиперграфа из файла.\n");
}
Console.WriteLine("4. Выполнить расчет числа автоморфизмов согласно теореме 2.");
Console.WriteLine("5. Выполнить расчет числа автоморфизмов согласно теореме 3.\n");
if (graph == null)
{
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("6. Ввести данные гиперграфа вручную.");
Console.ResetColor();
}
else
{
Console.WriteLine("6. Ввести данные гиперграфа вручную.");
}
Console.WriteLine("\n0. Выход.\n");
ConsoleKeyInfo key = Console.ReadKey(true);
input = null; output = null;
switch (key.Key)
{
case ConsoleKey.D1:
{
Console.Clear();
Console.WriteLine("Пример: " + @"D:\\input.txt");
Console.WriteLine("Введите полный путь к файлу входных данных:");
var path = Console.ReadLine();
if (System.IO.File.Exists(path))
{
inputPath = path;
Console.WriteLine("Файл существует.");
}
else
{
PrintError("Файл не найден. Искомый путь: " + path);
}
}
break;
case ConsoleKey.D2:
{
Console.Clear();
Console.WriteLine("Пример: " + @"D:\\output.txt");
Console.ForegroundColor = ConsoleColor.Red;
Console.Write("Внимание!");
Console.ResetColor();
Console.WriteLine(" Файл будет перезаписан или создан.");
Console.WriteLine("Введите полный путь к файлу результатов:");
var path = Console.ReadLine();
if (LoadStreamWriter(out output, path))
{
outputPath = path;
}
}
break;
case ConsoleKey.D3:
{
Console.Clear();
if (LoadStreamReader(out input, inputPath))
{
input.BaseStream.Position = 0;
try
{
graph = new HyperGraph(Matrix<int>.LoadFromStream(input));
Console.WriteLine("Гиперграф загружен.");
}
catch (Exception e)
{
PrintError(e.Message);
}
input.Close();
}
}
break;
case ConsoleKey.D4:
{
Console.Clear();
if (graph != null)
{
try
{
LoadStreamWriter(out output, outputPath);
// Вычислить количество автоморфизмов графа и вывести перестановки
ExampleTheorema(graph, output);
output.Close();
Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
}
catch (Exception e)
{
PrintError(e.Message);
}
}
else
{
PrintError("Гиперграф не загружен.");
}
}
break;
case ConsoleKey.D5:
{
Console.Clear();
if (graph != null)
{
try
{
LoadStreamWriter(out output, outputPath);
// Вычислить количество автоморфизмов графа и вывести их
ExampleTheoremaThird(graph, output);
output.Close();
Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
}
catch (Exception e)
{
PrintError(e.Message);
}
}
else
{
PrintError("Гиперграф не загружен.");
}
}
break;
case ConsoleKey.D6:
{
string inputStr;
int sameVert = -1, edges = -1;
Console.Clear();
while (edges <= 0)
{
Console.Write("Количество ребер гиперграфа: ");
inputStr = Console.ReadLine();
if (!int.TryParse(inputStr, out edges) || edges <= 0)
{
Console.Clear();
Console.WriteLine("Введенное значение не может быть меньше или равно нуля.");
}
}
Console.Clear();
while (sameVert < 0)
{
Console.WriteLine($"Количество ребер гиперграфа: {edges}");
Console.Write("Количество общих вершин для всех ребер гиперграфа: ");
inputStr = Console.ReadLine();
if (!int.TryParse(inputStr, out sameVert) || sameVert < 0)
{
Console.Clear();
Console.WriteLine("Введенное значение не может быть меньше нуля.");
}
}
List<int> verticies = new List<int>(edges);
for (int i = 0; i < edges; i++)
{
verticies.Add(0);
while (verticies[i] <= 0)
{
Console.Clear();
Console.WriteLine($"Количество ребер гиперграфа: {edges}");
Console.WriteLine($"Количество общих вершин для всех ребер гиперграфа: {sameVert}");
Console.Write($"Количество вершин {i + 1} гиперребра: ");
inputStr = Console.ReadLine();
if (!int.TryParse(inputStr, out int h) || h <= 0)
{
Console.Clear();
Console.WriteLine("Введенное значение не может быть меньше или равно нуля.");
continue;
}
if (h < sameVert)
{
Console.Clear();
Console.WriteLine("Количество вершин ребра не может быть меньше числа вершин, общих для всех ребер гиперграфа.");
continue;
}
verticies[i] = h;
}
}
try
{
var vert = verticies.Sum(x => x - sameVert) + sameVert;
var 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;
using (var wr = new System.IO.StreamWriter(@"D:\test.txt"))
matrix.UnloadToStream(wr);
//int VertPerEdge = (matrix.countRow - sameVert) / matrix.countColumn;
//for (int i = 0; i < matrix.countRow - sameVert; i++)
//{
// matrix[i, i / VertPerEdge] = 1;
//}
//for (int i = matrix.countRow - sameVert; i < matrix.countRow; i++)
//{
// for (int j = 0; j < matrix.countColumn; j++)
// matrix[i, j] = 1;
//}
graph = new HyperGraph(matrix);
Console.WriteLine("Гиперграф загружен.");
}
catch (Exception e)
{
PrintError(e.Message);
}
}
break;
case ConsoleKey.D0: { if (input != null) { input.Close(); } if (output != null) { output.Close(); } Environment.Exit(0); } break;
default: break;
}
if (input != null)
{
input.Close();
}
if (output != null)
{
output.Close();
}
Console.WriteLine("\nДля продолжения нажмите любую клавишу.");
Console.ReadKey();
Console.Clear();
}
}
static bool LoadStreamReader(out System.IO.StreamReader stream, string path)
{
try
{
stream = new System.IO.StreamReader(path);
return true;
}
catch (Exception e)
{
PrintError(new string[] { e.Message, "Укажите корректный путь к файлу входных данных." });
stream = null;
return false;
}
}
static bool LoadStreamWriter(out System.IO.StreamWriter stream, string path)
{
try
{
stream = new System.IO.StreamWriter(path);
return true;
}
catch (Exception e)
{
PrintError(e.Message);
stream = null;
return false;
}
}
static void PrintError(string message)
{
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine(message);
Console.ResetColor();
}
static void PrintError(string[] messages)
{
Console.ForegroundColor = ConsoleColor.Red;
foreach (var message in messages)
{
Console.WriteLine(message);
}
Console.ResetColor();
}
}
}