HyperGraph
Changes
HyperGraph/Matrix.cs 37(+29 -8)
HyperGraph/Program.cs 291(+263 -28)
HyperGraph/Theorem.cs 58(+58 -0)
Details
HyperGraph/Matrix.cs 37(+29 -8)
diff --git a/HyperGraph/Matrix.cs b/HyperGraph/Matrix.cs
index 34fd42d..e9901d6 100644
--- a/HyperGraph/Matrix.cs
+++ b/HyperGraph/Matrix.cs
@@ -170,25 +170,46 @@ namespace HyperGraph
return (t)Convert.ChangeType(value, typeof(t));
}
- public static Matrix<T> LoadFromStream(System.IO.StreamReader input, int countR0w, int countCol)
+ public static Matrix<T> LoadFromStream(System.IO.StreamReader input)
{
- Matrix<T> matrix = new Matrix<T>(countR0w, countCol);
+ Matrix<T> matrix = new Matrix<T>(0, 0);
+ int countCol;
string r0w;
try
{
- if (input == null || input.EndOfStream)
+ // Поток существует?
+ if (input == null)
throw new Exception();
+ // Позиция чтения с начала файла
+ input.BaseStream.Position = 0;
+ // Получаем первую строку, чтобы узнать количество столбцов
+ r0w = input.ReadLine();
+ string[] temp = r0w.Split(' ');
+ countCol = temp.Length;
- for (int i = 0; i < countR0w; i++)
+ // Пересоздаем матрицу, т.к. получили количество столбцов
+ matrix = new Matrix<T>(1, countCol);
+
+ // Заполнение первой строки
+ for (int j = 0; j < countCol; j++)
+ {
+ T tmp = ConvertValue<T, string>(temp[j]);
+ matrix[0, j] = tmp;
+ }
+
+ // Перебираем все оставшиеся строки
+ while(!input.EndOfStream)
{
r0w = input.ReadLine();
+ temp = r0w.Split(' ');
+ // Добавление новой строки в матрицу
+ matrix.AddRow();
for (int j = 0; j < countCol; j++)
{
- string temp = r0w.Split(' ')[j];
- T tmp = ConvertValue<T,string>(temp);
- matrix[i,j] = tmp;
+ T tmp = ConvertValue<T, string>(temp[j]);
+ matrix[matrix.countRow - 1, j] = tmp;
}
- }
+ }
}
catch (Exception e)
{
HyperGraph/Program.cs 291(+263 -28)
diff --git a/HyperGraph/Program.cs b/HyperGraph/Program.cs
index 99baa20..809dcf6 100644
--- a/HyperGraph/Program.cs
+++ b/HyperGraph/Program.cs
@@ -31,27 +31,25 @@ namespace HyperGraph
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)
{
- Matrix<int> u = new Matrix<int>(4);
-
- System.IO.StreamReader input = new System.IO.StreamReader("D:\\input.txt");
- System.IO.StreamWriter output = new System.IO.StreamWriter("D:\\output.txt");
-
- // Экземпляр гипер-графа, созданный на основе загружаемой матрицы инцидентности
- // 11 - кол-во строк, 3 - кол-во столбцов
- HyperGraph graph = new HyperGraph(Matrix<int>.LoadFromStream(input, 11, 3));
-
-
- // Все перестановки гипер-графа
- //ExampleAllTranspos(graph, input, output);
-
- // Вычислить количество автоморфизмов графа и вывести перестановки
- ExampleTheorema(graph, output);
-
- input.Close(); output.Close();
- Console.WriteLine("Completed. Press any key");
- Console.ReadKey();
+ Menu();
}
// Все перестановки графа вывести в файл
@@ -78,14 +76,14 @@ namespace HyperGraph
output.Write("1:");
for (int g = 0; g < graph.HyperEdge[i].Count; g++)
output.Write(" {0}", graph.HyperEdge[i][g]);
- output.WriteLine("\n\t-----------");
+ 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("\n\t-----------");
+ output.WriteLine("\r\n\t-----------");
}
output.WriteLine();
}
@@ -97,14 +95,14 @@ namespace HyperGraph
// Получить результат вычислений
var result = Theorem.TheoremAutomorphism(graph);
// Выполняется ли условие согласно теореме 2
- Console.WriteLine("Is Thereom 2: " + result.isSatisfyTheorem);
+ Console.WriteLine("Is Theorem 2: " + result.isSatisfyTheorem);
if (result.isSatisfyTheorem)
{
// Вывод числа автоморфизмов в консоль
Console.WriteLine("Count of automorphism: " + result.CountAutomorphism);
}
// Выполняется ли условие согласно теореме 2
- output.WriteLine("Is Thereom 2: " + result.isSatisfyTheorem);
+ output.WriteLine("Is Theorem 2: " + result.isSatisfyTheorem);
// Если да, то вывести
if (result.isSatisfyTheorem)
{
@@ -119,25 +117,262 @@ namespace HyperGraph
output.Write("1:");
for (int g = 0; g < result.AutomorphismNodes.Count; g++)
output.Write(" {0}", result.AutomorphismNodes[g]);
- output.WriteLine("\n\t-----------");
+ 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("\n\t-----------");
+ output.WriteLine("\r\n\t-----------");
}
- output.WriteLine("\nCount of automorphism: " + result.CountAutomorphism + "\n");
+ output.WriteLine("\r\nCount of automorphism: " + result.CountAutomorphism + "\r\n");
// Вывести перестановки в файл
ExampleAllTranspos(result.GraphWithoutAutoEdges, output);
- output.Write("Automorphism with nodes: ");
-
+ //output.Write("Automorphism with nodes: ");
}
// Уничтожить временный граф
result.GraphWithoutAutoEdges.Dispose();
}
+
+ 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. Вывести все перестановки вершин в ребрах гиперграфа.");
+ Console.WriteLine("5. Выполнить расчет числа автоморфизмов согласно теореме 1.");
+ Console.WriteLine("6. Выполнить расчет числа автоморфизмов согласно теореме 2.");
+
+ 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);
+ // Все перестановки гипер-графа
+ 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
+ {
+ // Если НЕ удовлетворяет условию "в каждом гиперребре одинаковое количество вершин"
+ if (!Theorem.isEqualNumberOfVertices(graph))
+ {
+ LoadStreamWriter(out output, outputPath);
+ // Вычислить количество автоморфизмов графа и вывести перестановки
+ ExampleTheorema(graph, output);
+ output.Close();
+ Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
+ }
+ else
+ // Нужно вычислять по другой теореме
+ {
+ Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 2.");
+ }
+ }
+ catch (Exception e)
+ {
+ PrintError(e.Message);
+ }
+ }
+ else
+ {
+ PrintError("Гиперграф не загружен.");
+ }
+
+ } break;
+ case ConsoleKey.D6:
+ {
+ Console.Clear();
+ if (graph != null)
+ {
+ try
+ {
+ // Если удовлетворяет условию "в каждом гиперребре одинаковое количество вершин"
+ if (Theorem.isEqualNumberOfVertices(graph))
+ {
+ LoadStreamWriter(out output, outputPath);
+ // Вычислить количество автоморфизмов графа
+ var result = Theorem.TheoremAutomorphismForEqualNumberOfVertices(graph);
+ output.WriteLine("\r\nCount of automorphism: " + result + "\r\n");
+ output.Close();
+ Console.WriteLine("\nВывод выполнен в файл: " + outputPath);
+ }
+ else
+ // Нужно вычислять по другой теореме
+ {
+ Console.WriteLine("\nЧисло автоморфизмов графа должно вычисляться по теореме 1.");
+ }
+ }
+ catch (Exception e)
+ {
+ PrintError(e.Message);
+ }
+ }
+ else
+ {
+ PrintError("Гиперграф не загружен.");
+ }
+ } 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();
+ }
}
}
HyperGraph/Theorem.cs 58(+58 -0)
diff --git a/HyperGraph/Theorem.cs b/HyperGraph/Theorem.cs
index e5f731f..791f49e 100644
--- a/HyperGraph/Theorem.cs
+++ b/HyperGraph/Theorem.cs
@@ -64,6 +64,54 @@ namespace HyperGraph
return result;
}
+ public static Int64 TheoremAutomorphismForEqualNumberOfVertices(HyperGraph Graph)
+ {
+ // Копирую гипер-граф, чтобы не изменять исходный
+ HyperGraph graph = new HyperGraph(Graph);
+ // Число автоморфизмов
+ Int64 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)
+ 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);
+
+ return count;
+ }
+
+ 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 Int64 Factorial(int input)
{
@@ -96,5 +144,15 @@ namespace HyperGraph
}
return fact;
}
+
+ private static Int64 Pow(Int64 input, Int64 grade)
+ {
+ if (grade < 0)
+ throw new Exception("error");
+ Int64 result = 1;
+ for (int i = 0; i < grade; i++)
+ result *= input;
+ return result;
+ }
}
}
\ No newline at end of file