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
}
}