using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Windows.Forms; namespace IST_tow_methods { public partial class Form1 : Form { public Form1() { InitializeComponent(); button_go1.Click += new EventHandler(button_go1_Click); button_go2.Click += new EventHandler(button_go2_Click); button_resettime.Click += button_resettime_Click; } //-------Variable definition-------- System.Diagnostics.Stopwatch sw; //Time object String br = Convert.ToChar(13).ToString() + Convert.ToChar(10).ToString(); String tab = Convert.ToChar(9).ToString(); double R_min = double.MaxValue; double R_max = double.MinValue; double P_min = double.MaxValue; double P_max = double.MinValue; double R_avg; double P_avg; int R_count = 0; int P_count = 0; //-------Shared variables-------- int n; int r; int[] pow_table; int[][] sol_tbl; int[][] sol_tbl2; //-------FPS_ISTs variables-------- int[] C; int[] C_p; int[] Diset; int[] minDiset; int[] Siset; int[] minSiset; int[] Iiset; int[] Next; //-------PMCIST variables-------- int y; int[] S_set; #region PMCIST Graphical interface void button_go1_Click(object sender, EventArgs e) { #region Initialization if (isRandomroot.Checked) text_r.Text = ((int)(new Random().NextDouble() * Math.Pow(2, n))).ToString(); n = int.Parse(text_n.Text); r = int.Parse(text_r.Text); S_set = new int[n]; int[][] Vertex_set = new int[n][]; int[][,] Edge_set = new int[n][,]; string Temp_string = ""; int MQ_type = 0; if (radioButton1.Checked) MQ_type = 0; else MQ_type = 1; pow_table = new int[n + 1]; for (int i = 0; i < n; i++) { pow_table[i] = (int)Math.Pow(2, i); } pow_table[n] = (int)Math.Pow(2, n); if (r > pow_table[n] - 1) { MessageBox.Show("Root is out of range!"); text_r.Text = "0"; r = 0; } sol_tbl2 = new int[n][]; for (int i = 0; i < n; i++) { S_set[i] = (n - 1) - i; sol_tbl2[i] = new int[pow_table[n]]; } #endregion sw = new System.Diagnostics.Stopwatch(); sw.Reset(); // Reset time sw.Start(); // Start up #region PMCIST Algorithms for (int i = 0; i < n; i++) { if (isoutpute.Checked) // Store outpute { sol_tbl2[i][r] = -1; // parent(root) = -1 sol_tbl2[i][MQ_neighbor(r, i, MQ_type)] = r; // parent(c) = r } Vertex_set[i] = new int[pow_table[n]]; Edge_set[i] = new int[pow_table[n], 2]; Vertex_set[i][0] = MQ_neighbor(r, i, MQ_type); for (int level = 0; level < n; level++) { for (int x = 0; x < pow_table[level]; x++) { y = MQ_neighbor(Vertex_set[i][x], S_set[(level - i + n) % n], MQ_type); Edge_set[i][x + pow_table[level], 0] = x; Edge_set[i][x + pow_table[level], 1] = y; Vertex_set[i][x + pow_table[level]] = y; if (isoutpute.Checked && y != r) // Store outpute sol_tbl2[i][y] = Vertex_set[i][x]; // parent(y) = x } } } #endregion sw.Stop(); // Time up #region Print sol_tbl if (isoutpute.Checked) { Temp_string += MQ_type.ToString() + "-MQ" + tab; for (int i = 0; i < sol_tbl2.Length; i++) { Temp_string += "T" + i.ToString() + tab; } Temp_string += br; for (int j = -1; j < sol_tbl2[0].Length; j++) { if (j >= 0) // Output first row for (int i = -1; i < sol_tbl2.Length; i++) { if (i >= 0) // Output first column { if (sol_tbl2[i][j] != -1) if (isShowBinary.Checked) Temp_string += toBinary(sol_tbl2[i][j]).ToString() + " " + sol_tbl2[i][j].ToString() + tab; else Temp_string += sol_tbl2[i][j].ToString() + tab; else Temp_string += "-" + tab; } else { if (isShowBinary.Checked) Temp_string += toBinary(j).ToString() + " " + j.ToString() + tab; else Temp_string += j.ToString() + tab; } } Temp_string += br; } // It is independent if (new IST_tool().isIndependent(sol_tbl2, n, r)) { Temp_string += br + "It is Independent." + br + br; } textBox1.Text = Temp_string; } #endregion #region Output excecution time if (R_min > sw.Elapsed.TotalMilliseconds) R_min = sw.Elapsed.TotalMilliseconds; if (R_max < sw.Elapsed.TotalMilliseconds) R_max = sw.Elapsed.TotalMilliseconds; text_R_time.Text = sw.Elapsed.TotalMilliseconds.ToString("#0.000000") + " ms"; text_R_maxtime.Text = R_max.ToString("#0.000000") + " ms"; text_R_mintime.Text = R_min.ToString("#0.000000") + " ms"; R_avg = (sw.Elapsed.TotalMilliseconds + (R_avg * R_count++)) / R_count; text_R_Averagetime.Text = R_avg.ToString("#0.000000") + " ms (count = " + R_count + ")"; #endregion } #endregion #region FPS_ISTs Graphical interface void button_go2_Click(object sender, EventArgs e) { #region Initialization if (isRandomroot.Checked) text_r.Text = ((int)(new Random().NextDouble() * Math.Pow(2, n))).ToString(); n = int.Parse(text_n.Text); r = int.Parse(text_r.Text); pow_table = new int[n + 1]; for (int i = 0; i < n; i++) { pow_table[i] = (int)Math.Pow(2, i); } pow_table[n] = (int)Math.Pow(2, n); int MQ_type = 0; if (radioButton1.Checked) MQ_type = 0; else MQ_type = 1; string Temp_string = ""; if (r > pow_table[n] - 1) { MessageBox.Show("Root is out of range!"); text_r.Text = "0"; r = 0; } sol_tbl = new int[n][]; for (int i = 0; i < n; i++) sol_tbl[i] = new int[pow_table[n]]; for (int x = 0; x < pow_table[n]; x++) { C = new int[n]; C_p = new int[n]; Diset = new int[n]; minDiset = new int[n]; Siset = new int[n]; minSiset = new int[n]; Iiset = new int[n]; Next = new int[n]; } #endregion sw = new System.Diagnostics.Stopwatch(); sw.Reset(); // Reset time sw.Start(); // Start up #region FPS_ISTs Algorithms for (int x = 0; x < pow_table[n]; x++) // In parallel { for (int i = 0; i < n; i++) { C[i] = MQ_neighbor(r, i, MQ_type); C_p[i] = MQ_neighbor_p(C[i], i, MQ_type); } int temp_d = 0, temp_s = 0; for (int i = n - 1 - 1; i >= 0; i--) { if (minDiset[i + 1] != 0) minDiset[i] = minDiset[i + 1]; if (minSiset[i + 1] != 0) minSiset[i] = minSiset[i + 1]; if ((C[i] & pow_table[i + 1 + 1]) != 0 || (MQ_type == 1 && i == n - 1 - 1)) { if (((x ^ C[i]) & pow_table[i + 1]) != 0) { temp_d += pow_table[i]; minDiset[i] = pow_table[i]; } else { temp_s += pow_table[i]; minSiset[i] = pow_table[i]; } } Diset[i] = temp_d; Siset[i] = temp_s; } for (int i = n - 1; i >= 0; i--) { if (Diset[i] == 0 || (Siset[i] != 0 && minSiset[i] < minDiset[i])) Iiset[i] = x ^ C[i]; else Iiset[i] = x ^ C_p[i]; } for (int i = 0; i < n; i++) { if (Iiset[i] == 0 || (Iiset[i] & pow_table[i]) != 0) Next[i] = i; else Next[i] = -1; } for (int i = n - 1; i >= 0; i--) { int temp_www = i; while (Next[i] == -1) { temp_www = temp_www - 1; if (temp_www < 0) temp_www = (temp_www + n) % n; if ((Iiset[i] & pow_table[temp_www]) != 0) Next[i] = temp_www; } } if (isoutpute.Checked) // Store outpute { for (int i = 0; i < n; i++) { if (x == r) sol_tbl[i][x] = -1; else sol_tbl[i][x] = MQ_neighbor(x, Next[i], MQ_type); } } } #endregion sw.Stop(); // Time up #region Print sol_tbl if (isoutpute.Checked) { Temp_string += MQ_type.ToString() + "-MQ" + tab; for (int i = 0; i < sol_tbl.Length; i++) { Temp_string += "T" + i.ToString() + tab; } Temp_string += br; for (int j = -1; j < sol_tbl[0].Length; j++) { if (j >= 0) // Output first row for (int i = -1; i < sol_tbl.Length; i++) { if (i >= 0) // Output first column { if (sol_tbl[i][j] != -1) if (isShowBinary.Checked) Temp_string += toBinary(sol_tbl[i][j]).ToString() + " " + sol_tbl[i][j].ToString() + tab; else Temp_string += sol_tbl[i][j].ToString() + tab; else Temp_string += "-" + tab; } else { if (isShowBinary.Checked) Temp_string += toBinary(j).ToString() + " " + j.ToString() + tab; else Temp_string += j.ToString() + tab; } } Temp_string += br; } // It is independent if (new IST_tool().isIndependent(sol_tbl, n, r)) { Temp_string += br + "It is Independent." + br + br; } textBox2.Text = Temp_string; } #endregion #region Output excecution time if (P_min > sw.Elapsed.TotalMilliseconds) P_min = sw.Elapsed.TotalMilliseconds; if (P_max < sw.Elapsed.TotalMilliseconds) P_max = sw.Elapsed.TotalMilliseconds; text_P_time.Text = sw.Elapsed.TotalMilliseconds.ToString("#0.000000") + " ms"; text_P_maxtime.Text = P_max.ToString("#0.000000") + " ms"; text_P_mintime.Text = P_min.ToString("#0.000000") + " ms"; P_avg = (sw.Elapsed.TotalMilliseconds + (P_avg * P_count++)) / P_count; text_P_Averagetime.Text = P_avg.ToString("#0.000000") + " ms (count = " + P_count + ")"; #endregion } #endregion #region Clear all contents void button_resettime_Click(object sender, EventArgs e) { R_min = double.MaxValue; R_max = double.MinValue; R_avg = 0; R_count = 0; P_min = double.MaxValue; P_max = double.MinValue; P_avg = 0; P_count = 0; text_R_time.Text = ""; text_R_maxtime.Text = ""; text_R_mintime.Text = ""; text_R_Averagetime.Text = ""; text_P_time.Text = ""; text_P_maxtime.Text = ""; text_P_mintime.Text = ""; text_P_Averagetime.Text = ""; textBox1.Text = ""; textBox2.Text = ""; } #endregion #region Definition of Subroutines #region Definition of Möbius Cube /// /// Find neighbor of x in Möbius Cube /// /// Enter a vertex /// Enter a dimension /// Enter the type 0/1 for Möbius Cube /// public int MQ_neighbor(int x, int indexi, int MQ_type) { if ((indexi == n - 1 && MQ_type == 1) || (x & pow_table[indexi + 1]) != 0) return x ^ (pow_table[indexi + 1] - 1); else return x ^ pow_table[indexi]; } /// /// Find surrenal of Ni(r) /// /// Enter a vertex /// Enter a dimension /// Enter the type 0/1 for Möbius Cube /// public int MQ_neighbor_p(int x, int indexi, int MQ_type) { return x ^ (pow_table[indexi + 1] - 1); } #endregion #region Decimal to Binary /// /// Decimal to Binary /// /// /// public string toBinary(int a) { return Convert.ToString(a, 2).PadLeft(n, '0'); } #endregion #region Binary to Decimal /// /// Binary to Decimal /// /// /// public int toDecimal(string a) { return Convert.ToInt32(a, 2); } #endregion #endregion } }