HyperGraph
Changes
HyperGraph/Program.cs 397(+218 -179)
Details
HyperGraph/Program.cs 397(+218 -179)
diff --git a/HyperGraph/Program.cs b/HyperGraph/Program.cs
index e7c31a2..ed9fd2d 100644
--- a/HyperGraph/Program.cs
+++ b/HyperGraph/Program.cs
@@ -102,187 +102,244 @@ namespace HyperGraph
{
// Получить результат вычислений
var result = Theorem.TheoremAutomorphism(graph);
- // Выполняется ли условие согласно теореме 2
- Console.WriteLine("Is Theorem 2: " + result.isSatisfyTheorem);
- if (result.isSatisfyTheorem)
+
+ // Если удовлетворяет условию "в каждом гиперребре одинаковое количество вершин", то нужно применять не эту теорему (2), а другую (3)
+ if (Theorem.isEqualNumberOfVertices(graph))
{
- // Вывод числа автоморфизмов в консоль
- Console.WriteLine("Count of automorphism: " + result.CountAutomorphism);
+ Console.WriteLine("Is Theorem 2: " + false);
+ Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 3.");
+ output.WriteLine("Is Theorem 2: " + false);
}
- // Выполняется ли условие согласно теореме 2
- output.WriteLine("Is Theorem 2: " + result.isSatisfyTheorem);
- // Если да, то вывести
- if (result.isSatisfyTheorem)
+ else
{
- // Вывод вершин и числа автоморфизмов в файл
- output.WriteLine("Automorphism with nodes: ");
- foreach (var node in result.AutomorphismNodes)
+ // Выполняется ли условие согласно теореме 2
+ Console.WriteLine("Is Theorem 2: " + result.isSatisfyTheorem);
+ if (result.isSatisfyTheorem)
{
- output.Write(node + " ");
+ // Вывод числа автоморфизмов в консоль
+ Console.WriteLine("Count of automorphism: " + result.CountAutomorphism);
}
-
- output.WriteLine();
- // Вывод всех перестановок общих вершин
- List<List<string>> transpos = Combinatorics<string>.Transposition(result.AutomorphismNodes);
- // Вывод начальной перестановки
- output.Write("1:");
- for (int g = 0; g < result.AutomorphismNodes.Count; g++)
+ // Выполняется ли условие согласно теореме 2
+ output.WriteLine("Is Theorem 2: " + result.isSatisfyTheorem);
+ // Если да, то вывести
+ if (result.isSatisfyTheorem)
{
- output.Write(" {0}", result.AutomorphismNodes[g]);
- }
+ // Вывод вершин и числа автоморфизмов в файл
+ output.WriteLine("Automorphism with nodes: ");
+ foreach (var node in result.AutomorphismNodes)
+ {
+ output.Write(node + " ");
+ }
- 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.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} ", transpos[g][f]);
+ 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\nCount of automorphism: " + result.CountAutomorphism + "\r\n");
+ output.WriteLine("\r\nCount of automorphism: " + result.CountAutomorphism + "\r\n");
- // Вывести перестановки в файл
- ExampleAllTranspos(result.GraphWithoutAutoEdges, output);
+ // Вывести перестановки в файл
+ ExampleAllTranspos(result.GraphWithoutAutoEdges, output);
+ }
}
// Уничтожить временный граф
result.GraphWithoutAutoEdges.Dispose();
}
static void ExampleTheoremaThird(HyperGraph Graph, System.IO.StreamWriter output)
- {
+ {
// Подсчет количества и получение гипер-графа без общих вершин
- var result = Theorem.TheoremAutomorphismForEqualNumberOfVertices(Graph);
- // Выполняется ли условие согласно теореме 2
- output.WriteLine("Is Theorem 3: " + result.isSatisfyTheorem);
- Console.WriteLine("Is Theorem 3: " + result.isSatisfyTheorem);
- // Если да, то вывести
- if (result.isSatisfyTheorem)
+ var result = Theorem.TheoremAutomorphismForEqualNumberOfVertices(Graph);
+
+ // Если НЕ удовлетворяет условию "в каждом гиперребре одинаковое количество вершин", то нужно применять не эту теорему (3), а другую (2)
+ if (!Theorem.isEqualNumberOfVertices(Graph))
{
- output.WriteLine("\r\nCount of automorphism: " + result.CountAutomorphism + "\r\n");
- // Получаю гипер-граф, автоморфизмы которого нужно получить
- // Это гипер-граф, из которого удалены общие для всех ребер вершины
- HyperGraph graph = new HyperGraph(result.GraphWithoutAutoEdges);
+ Console.WriteLine("Is Theorem 3: " + false);
+ Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 2.");
+ output.WriteLine("Is Theorem 3: " + false);
+ }
+ else
+ {
+ // Выполняется ли условие согласно теореме 3
+ output.WriteLine("Is Theorem 3: " + result.isSatisfyTheorem);
+ if (result.isSatisfyTheorem)
+ {
+ // Вывод числа автоморфизмов в консоль
+ Console.WriteLine("Count of automorphism: " + result.CountAutomorphism);
+ }
+ Console.WriteLine("Is Theorem 3: " + result.isSatisfyTheorem);
+ // Если да, то вывести
+ if (result.isSatisfyTheorem)
+ {
+ // Вывод вершин и числа автоморфизмов в файл
+ output.WriteLine("Automorphism with nodes: ");
+ foreach (var node in result.AutomorphismNodes)
+ {
+ output.Write(node + " ");
+ }
- // Список со всеми автоморфизмами
- List<string> automorphism = new List<string>();
+ 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]);
+ }
- // Трехмерный список, содержащий для каждого ребра (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>>>();
+ 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]);
+ }
- // Двумерный список - список всех возможных перестановок n-ого ребра
- List<List<string>> vertInEdge;
+ output.WriteLine("\r\n\t-----------");
+ }
- // Количество перестановок n-ого ребра, одинаково для всех ребер (т.к. мощность каждого ребра равна)
- int size = 0;
+ output.WriteLine("\r\nCount of automorphism: " + result.CountAutomorphism + "\r\n");
- // Перебор всех ребер гипер-графа для заполнения трехмерного списка
- 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;
- }
+ // Получаю гипер-граф, автоморфизмы которого нужно получить
+ // Это гипер-граф, из которого удалены общие для всех ребер вершины
+ HyperGraph graph = new HyperGraph(result.GraphWithoutAutoEdges);
- // Получив все перестановки каждого из ребер, нужно сформировать автоморфизмы гипер-графа
- // Учитывая порядок ребер 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++)
+ // Список со всеми автоморфизмами
+ 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++)
{
- // Строковое представление одного автоморфизма
- fullString = "";
- // Для k-й перестановки ребер и для i-й комбинации перестановок вершин
- // Должны перебрать все гипер-ребра
- for (int j = 0; j < combination[i].Count; j++)
+ // Для k-й перестановки ребер перебираем все возможные комбинации перестановок вершин
+ for (int i = 0; i < combination.Count; i++)
{
- // Строковое представление одного гипер-ребра
- 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) + ") ";
+ // Строковое представление одного автоморфизма
+ 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);
}
- // Записываем строковый вид автоморфизма в общий список
- automorphism.Add(fullString);
}
- }
- // Вывод
- for (int i = 0; i < automorphism.Count; i++)
- output.WriteLine(i + 1 + ") : " + automorphism[i]);
- ;
+ // Вывод
+ for (int i = 0; i < automorphism.Count; i++)
+ output.WriteLine(i + 1 + ") : " + automorphism[i]);
+ }
}
}
@@ -322,8 +379,8 @@ namespace HyperGraph
Console.WriteLine("3. Выполнить загрузку гиперграфа из файла.\n");
}
- Console.WriteLine("4. Выполнить расчет числа автоморфизмов согласно теореме 1.");
- Console.WriteLine("5. Выполнить расчет числа автоморфизмов согласно теореме 2.");
+ Console.WriteLine("4. Выполнить расчет числа автоморфизмов согласно теореме 2.");
+ Console.WriteLine("5. Выполнить расчет числа автоморфизмов согласно теореме 3.");
Console.WriteLine("\n0. Выход.\n");
@@ -389,20 +446,11 @@ namespace HyperGraph
{
try
{
- // Если НЕ удовлетворяет условию "в каждом гиперребре одинаковое количество вершин"
- if (!Theorem.isEqualNumberOfVertices(graph))
- {
- LoadStreamWriter(out output, outputPath);
- // Вычислить количество автоморфизмов графа и вывести перестановки
- ExampleTheorema(graph, output);
- output.Close();
- Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
- }
- else
- // Нужно вычислять по другой теореме
- {
- Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 2.");
- }
+ LoadStreamWriter(out output, outputPath);
+ // Вычислить количество автоморфизмов графа и вывести перестановки
+ ExampleTheorema(graph, output);
+ output.Close();
+ Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
}
catch (Exception e)
{
@@ -422,20 +470,11 @@ namespace HyperGraph
{
try
{
- // Если удовлетворяет условию "в каждом гиперребре одинаковое количество вершин"
- if (Theorem.isEqualNumberOfVertices(graph))
- {
- LoadStreamWriter(out output, outputPath);
- // Вычислить количество автоморфизмов графа и вывести их
- ExampleTheoremaThird(graph, output);
- output.Close();
- Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
- }
- else
- // Нужно вычислять по другой теореме
- {
- Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 1.");
- }
+ LoadStreamWriter(out output, outputPath);
+ // Вычислить количество автоморфизмов графа и вывести их
+ ExampleTheoremaThird(graph, output);
+ output.Close();
+ Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
}
catch (Exception e)
{