HyperGraph
Changes
HyperGraph/Combinatorics.cs 37(+37 -0)
HyperGraph/HyperGraph.cs 14(+13 -1)
HyperGraph/Program.cs 205(+172 -33)
HyperGraph/Theorem.cs 44(+30 -14)
Details
HyperGraph/Combinatorics.cs 37(+37 -0)
diff --git a/HyperGraph/Combinatorics.cs b/HyperGraph/Combinatorics.cs
index a0f5fb7..47787ee 100644
--- a/HyperGraph/Combinatorics.cs
+++ b/HyperGraph/Combinatorics.cs
@@ -81,5 +81,42 @@ namespace HyperGraph
return true;
}
+ /// <summary>
+ /// Маска, позволяющая перебрать множество сочетаний элементов с повторениями
+ /// </summary>
+ /// <param name="n">Мощность множества элементов</param>
+ /// <param name="m">По скольку элементов нужно сочетать выборку</param>
+ /// <returns>Вернет двумерный список размера n^m, где каждый список имеет размер m</returns>
+ public static List<List<int>> combinationWithReplays(int n, int m)
+ {
+ List<List<int>> test2 = new List<List<int>>();
+ bool NextSet(int[] aa, int nn, int mm)
+ {
+ int j = mm - 1;
+ while (j >= 0 && aa[j] == nn) j--;
+ if (j < 0) return false;
+ if (aa[j] >= nn)
+ j--;
+ aa[j]++;
+ if (j == mm - 1) return true;
+ for (int k = j + 1; k < mm; k++)
+ aa[k] = 1;
+ return true;
+ }
+ List<int> minus(List<int> from)
+ {
+ for (int i = 0; i < from.Count; i++)
+ from[i]--;
+ return from;
+ }
+ int h = n > m ? n : m; // размер массива а выбирается как max(n,m)
+ int[] a = new int[h];
+ for (int i = 0; i < h; i++)
+ a[i] = 1;
+ test2.Add(minus(a.Take(m).ToList()));
+ while (NextSet(a, n, m))
+ test2.Add(minus(a.Take(m).ToList()));
+ return test2;
+ }
}
}
HyperGraph/HyperGraph.cs 14(+13 -1)
diff --git a/HyperGraph/HyperGraph.cs b/HyperGraph/HyperGraph.cs
index 7b8f552..e02235a 100644
--- a/HyperGraph/HyperGraph.cs
+++ b/HyperGraph/HyperGraph.cs
@@ -38,7 +38,6 @@ namespace HyperGraph
foreach (var elem in edge)
HyperEdge.Last().Add(elem);
}
- Console.WriteLine();
}
// При уничтожении
@@ -62,5 +61,18 @@ namespace HyperGraph
GC.Collect();
GC.WaitForPendingFinalizers();
}
+
+ public override string ToString()
+ {
+ string fullString = "", edgeString;
+ foreach (var edge in this.HyperEdge)
+ {
+ edgeString = "(";
+ foreach (var vert in edge)
+ edgeString += vert + '-';
+ fullString += edgeString.Remove(edgeString.Length - 1, 1) + ") ";
+ }
+ return fullString;
+ }
}
}
HyperGraph/Program.cs 205(+172 -33)
diff --git a/HyperGraph/Program.cs b/HyperGraph/Program.cs
index 809dcf6..e7c31a2 100644
--- a/HyperGraph/Program.cs
+++ b/HyperGraph/Program.cs
@@ -67,7 +67,9 @@ namespace HyperGraph
// Вывод всех вершин текущего гипер-ребра
output.Write("Current edge include:");
for (int g = 0; g < graph.HyperEdge[i].Count; g++)
+ {
output.Write(" {0}", graph.HyperEdge[i][g]);
+ }
// Вывод всех перестановок текущего гипер-ребра
output.WriteLine();
@@ -75,14 +77,20 @@ namespace HyperGraph
// Вывод начальной перестановки
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();
@@ -109,34 +117,177 @@ namespace HyperGraph
// Вывод вершин и числа автоморфизмов в файл
output.WriteLine("Automorphism with nodes: ");
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\nCount of automorphism: " + result.CountAutomorphism + "\r\n");
// Вывести перестановки в файл
- ExampleAllTranspos(result.GraphWithoutAutoEdges, output);
- //output.Write("Automorphism with nodes: ");
+ 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)
+ {
+ output.WriteLine("\r\nCount of automorphism: " + 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";
@@ -167,10 +318,12 @@ namespace HyperGraph
Console.ResetColor();
}
else
+ {
Console.WriteLine("3. Выполнить загрузку гиперграфа из файла.\n");
- Console.WriteLine("4. Вывести все перестановки вершин в ребрах гиперграфа.");
- Console.WriteLine("5. Выполнить расчет числа автоморфизмов согласно теореме 1.");
- Console.WriteLine("6. Выполнить расчет числа автоморфизмов согласно теореме 2.");
+ }
+
+ Console.WriteLine("4. Выполнить расчет числа автоморфизмов согласно теореме 1.");
+ Console.WriteLine("5. Выполнить расчет числа автоморфизмов согласно теореме 2.");
Console.WriteLine("\n0. Выход.\n");
@@ -206,7 +359,9 @@ namespace HyperGraph
Console.WriteLine("Введите полный путь к файлу результатов:");
var path = Console.ReadLine();
if (LoadStreamWriter(out output, path))
+ {
outputPath = path;
+ }
} break;
case ConsoleKey.D3:
{
@@ -231,29 +386,6 @@ namespace HyperGraph
{
Console.Clear();
if (graph != null)
- {
- try
- {
- LoadStreamWriter(out output, outputPath);
- // Все перестановки гипер-графа
- ExampleAllTranspos(graph, output);
- Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
- }
- catch (Exception e)
- {
- PrintError(e.Message);
- }
- }
- else
- {
- PrintError("Гиперграф не загружен.");
- }
- }
- break;
- case ConsoleKey.D5:
- {
- Console.Clear();
- if (graph != null)
{
try
{
@@ -283,7 +415,7 @@ namespace HyperGraph
}
} break;
- case ConsoleKey.D6:
+ case ConsoleKey.D5:
{
Console.Clear();
if (graph != null)
@@ -294,9 +426,8 @@ namespace HyperGraph
if (Theorem.isEqualNumberOfVertices(graph))
{
LoadStreamWriter(out output, outputPath);
- // Вычислить количество автоморфизмов графа
- var result = Theorem.TheoremAutomorphismForEqualNumberOfVertices(graph);
- output.WriteLine("\r\nCount of automorphism: " + result + "\r\n");
+ // Вычислить количество автоморфизмов графа и вывести их
+ ExampleTheoremaThird(graph, output);
output.Close();
Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
}
@@ -316,13 +447,18 @@ namespace HyperGraph
PrintError("Гиперграф не загружен.");
}
} break;
- case ConsoleKey.D0: { if (input != null) input.Close(); if (output != null) output.Close(); Environment.Exit(0); } 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();
@@ -371,7 +507,10 @@ namespace HyperGraph
{
Console.ForegroundColor = ConsoleColor.Red;
foreach (var message in messages)
+ {
Console.WriteLine(message);
+ }
+
Console.ResetColor();
}
}
HyperGraph/Theorem.cs 44(+30 -14)
diff --git a/HyperGraph/Theorem.cs b/HyperGraph/Theorem.cs
index 791f49e..68e2d4e 100644
--- a/HyperGraph/Theorem.cs
+++ b/HyperGraph/Theorem.cs
@@ -64,7 +64,7 @@ namespace HyperGraph
return result;
}
- public static Int64 TheoremAutomorphismForEqualNumberOfVertices(HyperGraph Graph)
+ public static TheoremAuto TheoremAutomorphismForEqualNumberOfVertices(HyperGraph Graph)
{
// Копирую гипер-граф, чтобы не изменять исходный
HyperGraph graph = new HyperGraph(Graph);
@@ -85,20 +85,36 @@ namespace HyperGraph
}
// В списке intersect расположены общие для всех гипер-ребер вершины
- if (intersect.Count == 0)
- return 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);
+ 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 count;
+ return result;
}
public static bool isEqualNumberOfVertices(HyperGraph Graph)