HyperGraph
Changes
ConsoleTest/Program.cs 2(+1 -1)
HyperGraphModel/Combinatorics.cs 42(+41 -1)
HyperGraphModel/HyperGraph.cs 2(+2 -0)
HyperGraphModel/Theorem.cs 128(+128 -0)
WPF/Model/Calculate.cs 97(+83 -14)
WPF/Model/EnumTheorem.cs 2(+2 -0)
WPF/View/MainWindow.xaml 4(+2 -2)
WPF/ViewModel/MainViewModel.cs 106(+101 -5)
WPF/WPF.csproj 3(+1 -2)
Details
ConsoleTest/Program.cs 2(+1 -1)
diff --git a/ConsoleTest/Program.cs b/ConsoleTest/Program.cs
index 355dde7..4633063 100644
--- a/ConsoleTest/Program.cs
+++ b/ConsoleTest/Program.cs
@@ -270,7 +270,7 @@ namespace ConsoleTest
// 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);
+ var combination = Combinatorics<int>.CombinationWithReplays(size, graph.HyperEdge.Count);
// Однако, выше приведенные комбинации работают лишь с перестановками непосредственно вершин, сохраняя позиции ребер
HyperGraphModel/Combinatorics.cs 42(+41 -1)
diff --git a/HyperGraphModel/Combinatorics.cs b/HyperGraphModel/Combinatorics.cs
index fd23cea..e225822 100644
--- a/HyperGraphModel/Combinatorics.cs
+++ b/HyperGraphModel/Combinatorics.cs
@@ -87,7 +87,7 @@ namespace HyperGraphModel
/// <param name="n">Мощность множества элементов</param>
/// <param name="m">По скольку элементов нужно сочетать выборку</param>
/// <returns>Вернет двумерный список размера n^m, где каждый список имеет размер m</returns>
- public static List<List<int>> combinationWithReplays(int n, int m)
+ 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)
@@ -118,5 +118,45 @@ namespace HyperGraphModel
test2.Add(minus(a.Take(m).ToList()));
return test2;
}
+
+ /// <summary>
+ /// Маска, позволяющая перебрать множество сочетаний элементов без повторений
+ /// </summary>
+ /// <param name="n">Мощность множества элементов</param>
+ /// <param name="m">По скольку элементов нужно сочетать выборку</param>
+ /// <returns>Вернет двумерный список размера n^m, где каждый список имеет размер m</returns>
+ public static List<List<int>> СombinationWithoutReplays(int n, int m)
+ {
+ List<List<int>> test2 = new List<List<int>>();
+ bool NextSet(int[] aa, int nn, int mm)
+ {
+ int k = mm;
+ for (int i = k - 1; i >= 0; --i)
+ if (aa[i] < nn - k + i + 1)
+ {
+ aa[i]++;
+ for (int j = i + 1; j < k; j++)
+ aa[j] = aa[j - 1] + 1;
+ return true;
+ }
+ return false;
+ }
+ List<int> minus(List<int> from)
+ {
+ for (int i = 0; i < from.Count; i++)
+ from[i]--;
+ return from;
+ }
+ int[] a = new int[n];
+ for (int i = 0; i < n; i++)
+ a[i] = i + 1;
+ test2.Add(minus(a.Take(m).ToList()));
+ if (n >= m)
+ {
+ while (NextSet(a, n, m))
+ test2.Add(minus(a.Take(m).ToList()));
+ }
+ return test2;
+ }
}
}
diff --git a/HyperGraphModel/Diagram/class diagram.graphml b/HyperGraphModel/Diagram/class diagram.graphml
index 1828127..c21fc5c 100644
--- a/HyperGraphModel/Diagram/class diagram.graphml
+++ b/HyperGraphModel/Diagram/class diagram.graphml
@@ -103,7 +103,7 @@ ______________________________
<y:BorderStyle color="#000000" type="line" width="1.0"/>
<y:NodeLabel alignment="center" autoSizePolicy="content" backgroundColor="#B7C9E3" configuration="com.yworks.entityRelationship.label.name" fontFamily="Dialog" fontSize="16" fontStyle="bold" hasLineColor="false" height="23.6015625" horizontalTextPosition="center" iconTextGap="4" modelName="internal" modelPosition="t" textColor="#000000" verticalTextPosition="bottom" visible="true" width="420.75" x="12.524999999999977" xml:space="preserve" y="4.0">универсальный статичный класс Combinatorics <T></y:NodeLabel>
<y:NodeLabel alignment="left" autoSizePolicy="content" borderDistance="0.0" configuration="com.yworks.entityRelationship.label.attributes" fontFamily="Dialog" fontSize="14" fontStyle="bold" hasBackgroundColor="false" hasLineColor="false" height="106.908203125" horizontalTextPosition="center" iconTextGap="4" modelName="internal" modelPosition="br" textColor="#000000" verticalTextPosition="top" visible="true" width="447.8095703125" x="-2.0095703125000455" xml:space="preserve" y="38.091796875">_________________________________________________________
- + combinationWithReplays(int n, int m) : List<List<int>>
+ + CombinationWithReplays(int n, int m) : List<List<int>>
+ Transposition(List<T> array) : List<List<T>>
- AddInOrderFromList() : List<T>
- Swap() : bool
HyperGraphModel/HyperGraph.cs 2(+2 -0)
diff --git a/HyperGraphModel/HyperGraph.cs b/HyperGraphModel/HyperGraph.cs
index baca752..19e5378 100644
--- a/HyperGraphModel/HyperGraph.cs
+++ b/HyperGraphModel/HyperGraph.cs
@@ -46,6 +46,8 @@ namespace HyperGraphModel
this.Dispose();
}
+ public bool IsEqualNumberOfVertices { get => Theorem.isEqualNumberOfVertices(this); }
+
// Очистка памяти
public void Dispose()
{
HyperGraphModel/Theorem.cs 128(+128 -0)
diff --git a/HyperGraphModel/Theorem.cs b/HyperGraphModel/Theorem.cs
index ee5137e..d89c58b 100644
--- a/HyperGraphModel/Theorem.cs
+++ b/HyperGraphModel/Theorem.cs
@@ -127,6 +127,134 @@ namespace HyperGraphModel
return result;
}
+ public static TheoremAuto TheoremForth(HyperGraph Graph)
+ {
+ if (Theorem.isEqualNumberOfVertices(Graph))
+ {
+ return default;
+ }
+
+ // Список общих вершин : Пара <гиперребро, гиперребро>, каждое из которых содержит общие вершины
+ Dictionary<List<string>, KeyValuePair<List<string>, List<string>>> Pain
+ = new Dictionary<List<string>, KeyValuePair<List<string>, List<string>>>();
+
+ foreach (var edge in Graph.HyperEdge)
+ {
+ var intersectedVerticies = Graph.HyperEdge.Where(x => x != edge && x.Intersect(edge).Any()).Select(x => x.Intersect(edge).ToList()).ToList();
+ foreach (var inter in intersectedVerticies)
+ {
+ // Если комбинация общих вершин еще не была добавлена
+ if (Pain.Keys.FirstOrDefault(key => key.SequenceEqual(inter)) == null)
+ Pain.Add
+ (
+ inter,
+ new KeyValuePair<List<string>, List<string>>
+ (
+ edge,
+ Graph.HyperEdge.FirstOrDefault(x => x != edge && x.Intersect(inter).Count() == inter.Count)
+ )
+ );
+ }
+ }
+
+ // Берем число общих вершин для первой пары смежных ребер
+ int k = Pain.Keys.First().Count;
+ // Если число общих вершин хотя бы для одной пары смежных ребер отличается от первой пары
+ if (Pain.Keys.Any(x => x.Count != k))
+ {
+ // То гиперграф не k-пересекающийся
+ return default;
+ }
+
+ // Копирую гипер-граф, чтобы не изменять исходный
+ HyperGraph graph = new HyperGraph(Graph);
+ // Число автоморфизмов
+ long count = Graph.HyperEdge.Aggregate((long)1, (sum, x) => sum *= Factorial(x.Count - 2 * k)) * Factorial(k);
+
+ TheoremAuto result = new TheoremAuto
+ {
+ isSatisfyTheorem = true,
+ CountAutomorphism = count,
+ AutomorphismNodes = null,
+ GraphWithoutAutoEdges = graph
+ };
+ // Вовращаемое значение в виде структуры
+
+ return result;
+ }
+
+ public static TheoremAuto TheoremFifth(HyperGraph Graph)
+ {
+ if (!Theorem.isEqualNumberOfVertices(Graph))
+ {
+ return default;
+ }
+
+ // Список общих вершин : Пара <гиперребро, гиперребро>, каждое из которых содержит общие вершины
+ Dictionary<List<string>, KeyValuePair<List<string>, List<string>>> Pain
+ = new Dictionary<List<string>, KeyValuePair<List<string>, List<string>>>();
+
+ foreach (var edge in Graph.HyperEdge)
+ {
+ var intersectedVerticies = Graph.HyperEdge.Where(x => x != edge && x.Intersect(edge).Any()).Select(x => x.Intersect(edge).ToList()).ToList();
+ foreach (var inter in intersectedVerticies)
+ {
+ // Если комбинация общих вершин еще не была добавлена
+ if (Pain.Keys.FirstOrDefault(key => key.SequenceEqual(inter)) == null)
+ Pain.Add
+ (
+ inter,
+ new KeyValuePair<List<string>, List<string>>
+ (
+ edge,
+ Graph.HyperEdge.FirstOrDefault(x => x != edge && x.Intersect(inter).Count() == inter.Count)
+ )
+ );
+ }
+ }
+
+ // Берем число общих вершин для первой пары смежных ребер
+ int k = Pain.Keys.First().Count;
+ // Если число общих вершин хотя бы для одной пары смежных ребер отличается от первой пары
+ if (Pain.Keys.Any(x => x.Count != k))
+ {
+ // То гиперграф не k-пересекающийся
+ return default;
+ }
+
+ // Копирую гипер-граф, чтобы не изменять исходный
+ HyperGraph graph = new HyperGraph(Graph);
+ var m = Graph.HyperEdge.Count;
+ var n = Graph.HyperEdge.First().Count;
+ var X = Graph.HyperEdge.Sum(x => x.Count() - k * 2) + k * Graph.HyperEdge.Count;
+
+ // Число автоморфизмов
+ long count = 0;
+ if (n - 2 * k == 1)
+ count = 2 * (X - m * k) * Pow(Factorial(k), m);
+ else
+ {
+ count = 2 * (X - m * k) * Pow((n - 2 * k), m - 1);
+ for (int i = 1; i < n - 2 * k - 1; i++)
+ {
+ count *= Pow((n - 2 * k - i), m) * Pow(Factorial(k), m);
+ }
+ }
+
+
+
+ TheoremAuto result = new TheoremAuto
+ {
+ isSatisfyTheorem = true,//(intersect.Count > 0) ? true : false,
+ CountAutomorphism = count,
+ AutomorphismNodes = null,
+ GraphWithoutAutoEdges = graph
+ };
+ // Вовращаемое значение в виде структуры
+
+ return result;
+ }
+
public static bool isEqualNumberOfVertices(HyperGraph Graph)
{
int count = Graph.HyperEdge[0].Count;
WPF/Model/Calculate.cs 97(+83 -14)
diff --git a/WPF/Model/Calculate.cs b/WPF/Model/Calculate.cs
index a6bc93c..a3e0955 100644
--- a/WPF/Model/Calculate.cs
+++ b/WPF/Model/Calculate.cs
@@ -13,27 +13,57 @@ namespace WPF.Model
{
public static HyperGraph Graph { get; private set; } = new HyperGraph(new Matrix<int>());
- public static void CreateGraph(int Edges, int SameVert, List<int> Verticies)
+ public static void CreateGraph(int Edges, int SameVert, List<int> Verticies, EnumTheorem SelectedTheorem)
{
try
{
- var vert = Verticies.Sum(x => x - SameVert) + SameVert;
- var matrix = new Matrix<int>(vert, Edges);
+ var matrix = new Matrix<int>(0, 0);
- // заполнение ребер отдельными вершинами
- for (int j = 0, i = 0; j < Verticies.Count; j++)
+ if (Verticies.Any())
{
- int k = 0;
- while (Verticies[j] - SameVert > k)
+ if (SelectedTheorem == EnumTheorem.Second || SelectedTheorem == EnumTheorem.Third)
{
- matrix[i++, j] = 1;
- k++;
+ // Общие вершины являются общими для всех ребер
+ // заполнение ребер отдельными вершинами
+ 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++;
+ }
+ //using (System.IO.StreamWriter wr = new StreamWriter(@"D:\test.txt"))
+ //{
+ // for (int o = 0; o < matrix.countRow; o++) { for (int h = 0; h < matrix.countColumn; h++) wr.Write($"{matrix[o, h]} "); wr.WriteLine(); }
+ //}
+ }
}
}
- // заполнение ребер общими вершинами
- for (int i = vert - SameVert; i < vert; i++)
- for (int j = 0; j < matrix.countColumn; j++)
- matrix[i, j] = 1;
Graph = new HyperGraph(matrix);
}
@@ -78,6 +108,40 @@ namespace WPF.Model
}
}
+ public static TheoremAuto TheoremForth()
+ {
+ try
+ {
+ if (Graph == null)
+ throw new Exception("Гипер граф не существует");
+
+ return Theorem.TheoremForth(Graph);
+ }
+ catch (Exception e)
+ {
+ MainViewModel.Current.Status = Common.Status.Error;
+ MainViewModel.Current.StatusMessage = e.Message;
+ return default;
+ }
+ }
+
+ public static TheoremAuto TheoremFifth()
+ {
+ try
+ {
+ if (Graph == null)
+ throw new Exception("Гипер граф не существует");
+
+ return Theorem.TheoremFifth(Graph);
+ }
+ catch (Exception e)
+ {
+ MainViewModel.Current.Status = Common.Status.Error;
+ MainViewModel.Current.StatusMessage = e.Message;
+ return default;
+ }
+ }
+
public static MemoryStream Export(TheoremAuto result, EnumTheorem theorem)
{
MemoryStream memoryStream = new MemoryStream();
@@ -104,6 +168,11 @@ namespace WPF.Model
break;
}
+ case EnumTheorem.Fifth:
+ {
+
+ break;
+ }
}
return memoryStream;
}
@@ -275,7 +344,7 @@ namespace WPF.Model
// 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);
+ var combination = Combinatorics<int>.CombinationWithReplays(size, graph.HyperEdge.Count);
// Однако, выше приведенные комбинации работают лишь с перестановками непосредственно вершин, сохраняя позиции ребер
WPF/Model/EnumTheorem.cs 2(+2 -0)
diff --git a/WPF/Model/EnumTheorem.cs b/WPF/Model/EnumTheorem.cs
index 6f04c4f..aeb29f4 100644
--- a/WPF/Model/EnumTheorem.cs
+++ b/WPF/Model/EnumTheorem.cs
@@ -14,5 +14,7 @@ namespace WPF.Model
Third = 3,
[Description("Четвертая теорема")]
Forth = 4,
+ [Description("Пятая теорема")]
+ Fifth = 5,
}
}
WPF/View/MainWindow.xaml 4(+2 -2)
diff --git a/WPF/View/MainWindow.xaml b/WPF/View/MainWindow.xaml
index 3998e73..40aaeeb 100644
--- a/WPF/View/MainWindow.xaml
+++ b/WPF/View/MainWindow.xaml
@@ -19,8 +19,8 @@
AllowsTransparency="True"
Loaded="Window_Loaded"
Title="{Binding TitleText}"
- Height="235" Width="725"
- MinHeight="235" MinWidth="725"
+ Height="235" Width="790"
+ MinHeight="235" MinWidth="790"
BorderBrush="#FF494957"
BorderThickness="1">
<Window.Resources>
WPF/ViewModel/MainViewModel.cs 106(+101 -5)
diff --git a/WPF/ViewModel/MainViewModel.cs b/WPF/ViewModel/MainViewModel.cs
index 1a7b864..1d3f37e 100644
--- a/WPF/ViewModel/MainViewModel.cs
+++ b/WPF/ViewModel/MainViewModel.cs
@@ -34,7 +34,7 @@ namespace WPF.ViewModel
PathToSave = DefaultPathToSave;
CalculateCommand = new RelayCommand(OnCalculate);
- SaveResultCommand = new RelayCommand(OnSaveResult, () => IsTheoremCorrect);
+ SaveResultCommand = new RelayCommand(OnSaveResult, () => CanSave && IsTheoremCorrect);
//AddItemCommand = new RelayCommand<ItemViewModel>(OnAddItem, item => Items.FirstOrDefault(e => e.Value == item.Value) == null);
//RemoveItemCommand = new RelayCommand<ItemViewModel>(OnRemoveItem, item => !item.Readonly);
@@ -42,11 +42,23 @@ namespace WPF.ViewModel
//SwitchDataVisibleCommand = new RelayCommand(OnSwitchDataVisible);
//ClearSearchCommand = new RelayCommand(OnClearSearch);
- EdgesNum = 3;
+#if DEBUG
+ //EdgesNum = 6;
+ //SameVertNum = 2;
+ //Verticies[0].Value = 4;
+ //Verticies[1].Value = 5;
+ //Verticies[2].Value = 6;
+ //Verticies[3].Value = 6;
+ //Verticies[4].Value = 2;
+ //Verticies[5].Value = 7;
+ EdgesNum = 4;
SameVertNum = 1;
Verticies[0].Value = 4;
Verticies[1].Value = 4;
Verticies[2].Value = 4;
+ Verticies[3].Value = 4;
+ SelectedTheorem = EnumTheorem.Fifth;
+#endif
}
#region Поля и свойства
@@ -68,12 +80,24 @@ namespace WPF.ViewModel
{
_selectedTheorem = value;
SetResultDefault();
+ UpdateText();
OnPropertyChanged(() => SelectedTheorem);
}
get => _selectedTheorem;
}
+ private bool _canSave;
+ public bool CanSave
+ {
+ get => _canSave;
+ set
+ {
+ _canSave = value;
+ OnPropertyChanged(() => CanSave);
+ }
+ }
+
private int _edgesNum;
public int EdgesNum
{
@@ -117,8 +141,26 @@ namespace WPF.ViewModel
public string EdgesText { get => "Количество ребер"; }
public string EdgesTextTooltip { get => "Подсказка. Количество ребер"; }
- public string SameVertText { get => "Количество общих вершин"; }
- public string SameVertTextTooltip { get => "Подсказка. Количество общих вершин"; }
+ private string _sameVertText;
+ public string SameVertText
+ {
+ get => _sameVertText;
+ set
+ {
+ _sameVertText = value;
+ OnPropertyChanged(() => SameVertText);
+ }
+ }
+ private string _sameVertTextTooltip;
+ public string SameVertTextTooltip
+ {
+ get => _sameVertTextTooltip;
+ set
+ {
+ _sameVertTextTooltip = value;
+ OnPropertyChanged(() => SameVertTextTooltip);
+ }
+ }
public string VerticiesText { get => "Номер ребра"; }
public string VerticiesTextTooltip { get => "Подсказка. Номер ребра"; }
@@ -199,6 +241,29 @@ namespace WPF.ViewModel
//LoadDataAsync(App.DataFilePath, true);
}
+ private void UpdateText()
+ {
+ switch(SelectedTheorem)
+ {
+ case EnumTheorem.Second:
+ case EnumTheorem.Third:
+ {
+ CanSave = true;
+ SameVertText = "Количество общих вершин";
+ SameVertTextTooltip = "Подсказка. Количество общих вершин";
+ break;
+ }
+ case EnumTheorem.Forth:
+ case EnumTheorem.Fifth:
+ {
+ CanSave = false;
+ SameVertText = "Количество пересекающихся вершин";
+ SameVertTextTooltip = "Подсказка. Количество вершин, являющихся общими между соседними ребрами";
+ break;
+ }
+ }
+ }
+
private void UpdateVerticies()
{
if (EdgesNum > Verticies.Count)
@@ -229,7 +294,7 @@ namespace WPF.ViewModel
public RelayCommand CalculateCommand { get; }
private void OnCalculate()
{
- CreateGraph(EdgesNum, SameVertNum, Verticies.Select(x => x.Value).ToList());
+ CreateGraph(EdgesNum, SameVertNum, Verticies.Select(x => x.Value).ToList(), SelectedTheorem);
SetResultDefault();
switch (SelectedTheorem)
{
@@ -238,6 +303,12 @@ namespace WPF.ViewModel
Result = TheoremSecond();
Status = Status.OperationSuccess;
StatusMessage = "Расчет успешно выполнен";
+
+ if (!Result.isSatisfyTheorem && Graph.IsEqualNumberOfVertices)
+ {
+ Status = Status.SpecialWarning;
+ StatusMessage = "Расчет успешно выполнен. Используйте теорему три";
+ }
break;
}
case EnumTheorem.Third:
@@ -245,13 +316,38 @@ namespace WPF.ViewModel
Result = TheoremThird();
Status = Status.OperationSuccess;
StatusMessage = "Расчет успешно выполнен";
+
+ if (!Result.isSatisfyTheorem && !Graph.IsEqualNumberOfVertices)
+ {
+ Status = Status.SpecialWarning;
+ StatusMessage = "Расчет успешно выполнен. Используйте теорему два";
+ }
break;
}
case EnumTheorem.Forth:
{
+ Result = TheoremForth();
+ Status = Status.OperationSuccess;
+ StatusMessage = "Расчет успешно выполнен";
+ if (!Result.isSatisfyTheorem && Graph.IsEqualNumberOfVertices)
+ {
+ Status = Status.SpecialWarning;
+ StatusMessage = "Расчет успешно выполнен. Используйте теорему пять";
+ }
+ break;
+ }
+ case EnumTheorem.Fifth:
+ {
+ Result = TheoremFifth();
Status = Status.OperationSuccess;
StatusMessage = "Расчет успешно выполнен";
+
+ if (!Result.isSatisfyTheorem && !Graph.IsEqualNumberOfVertices)
+ {
+ Status = Status.SpecialWarning;
+ StatusMessage = "Расчет успешно выполнен. Используйте теорему четыре";
+ }
break;
}
}
WPF/WPF.csproj 3(+1 -2)
diff --git a/WPF/WPF.csproj b/WPF/WPF.csproj
index 16e9ca4..805b2a4 100644
--- a/WPF/WPF.csproj
+++ b/WPF/WPF.csproj
@@ -37,8 +37,7 @@
<WarningLevel>4</WarningLevel>
</PropertyGroup>
<PropertyGroup>
- <ApplicationIcon>
- </ApplicationIcon>
+ <ApplicationIcon>Icon.ico</ApplicationIcon>
</PropertyGroup>
<ItemGroup>
<Reference Include="Costura, Version=4.1.0.0, Culture=neutral, PublicKeyToken=9919ef960d84173d, processorArchitecture=MSIL">