?using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.IO;
using System.Diagnostics;

namespace HW2_WindowsApplication
{
    public partial class Form1 : Form
    {
        public static StreamReader sr;
        public static TimeSpan tTime;
        public static long memUsage;
        public static Process[] memory;
        public static int Totalnode;
        public static int sum_of_E;
        public static int[] Group1;
        public static int[] Group2;

        public struct Gxy
        {
            public int data;
            public int x;
            public int y;
        }

        public Form1()
        {
            InitializeComponent();

            memory = Process.GetProcessesByName("HW2_WindowsApplication");  //get the memory usage before executing main program 
            memUsage = memory[0].PrivateMemorySize64;
            textBox3.Text = memUsage.ToString() + " bytes";

        }

        private void toolStripMenuItem2_Click(object sender, EventArgs e)  //main program
        {
            if (openFileDialog1.ShowDialog() == DialogResult.OK)
            {
                try
                {
                    memory = Process.GetProcessesByName("HW2_WindowsApplication");

                    file_open();
                    output();

                    progressBar1.Value = 1;
                    textBox4.Text = "";

                    if (checkBox1.Checked == true)
                    {
                        progressBar1.Visible = true;
                        runtime();
                    }
                    else
                    {
                        progressBar1.Visible = false;
                    }
                }
                catch (Exception exception)
                {
                    MessageBox.Show("輸入檔案有誤! (Reason : " + exception.Message + ")");
                }
            }
        }

        private void toolStripMenuItem3_Click(object sender, EventArgs e)
        {
            if (MessageBox.Show("確定離開程式?", "", MessageBoxButtons.YesNo) == DialogResult.Yes)
            {
                Application.Exit();
            }
        }

        private void file_open()
        {
            Totalnode = 0;
            int order = 0;
            int InitialEdge = 0;
            int column = 0;
            char[] delimit = new char[] { ' ' };
            String line;

            sr = new StreamReader(openFileDialog1.FileName);

            //Read the first line of text
            line = sr.ReadLine();

            foreach (string substr in line.Split(delimit)) //save the number of total nodes
            {
                switch (order)
                {
                    case 0:
                        Totalnode = Convert.ToInt16(substr);
                        break;

                    default:
                        break;
                }
                break;
            }

            //Read the second line of text
            line = sr.ReadLine();

            foreach (string substr in line.Split(delimit)) //save the number of initial edges
            {
                switch (order)
                {
                    case 0:
                        InitialEdge = Convert.ToInt16(substr);
                        break;

                    default:
                        break;
                }
                break;
            }
            ;

            int[,] matrix = new int[InitialEdge, 4];
            int[,] matrix2 = new int[Totalnode, Totalnode];
            for (int i = 0; i < Totalnode; i++)
                for (int j = 0; j < Totalnode; j++)
                {
                    matrix2[i, j] = 0;
                }

            //Continue to read until you reach end of file
            while (line != null)
            {
                //Console.WriteLine(line);

                //Read the next line
                line = sr.ReadLine();

                foreach (string substr in line.Split(delimit)) //initial the matrix
                {
                    switch (order)
                    {
                        case 0:
                            matrix[column, 0] = Convert.ToInt16(substr);
                            break;
                        case 1:
                            matrix[column, 1] = Convert.ToInt16(substr);
                            break;
                        case 2:
                            matrix[column, 2] = Convert.ToInt16(substr);
                            break;
                        case 3:
                            matrix[column, 3] = Convert.ToInt16(substr);
                            break;

                        default:
                            break;
                    }
                    order++;
                    if (order == 4)  //judge if the line is ending or not
                    {
                        order = 0;
                        column++;
                    }

                }

                if (column == InitialEdge) //column==InitialEdge  end while
                    break;
            }
            for (int i = 0; i < InitialEdge; i++)
                for (int j = 2; j < 3; j++)
                {
                    int temp1 = matrix[i, j];
                    int temp2 = matrix[i, j + 1];
                    matrix2[temp1 - 1, temp2 - 1] = matrix[i, j - 1];
                    matrix2[temp2 - 1, temp1 - 1] = matrix[i, j - 1];
                }
            /*for (int i = 0; i < Totalnode; i++)
                for (int j = 0; j < Totalnode; j++)
                {
                    Console.WriteLine(matrix2[i,j]);
                }*/
            //close the file
            sr.Close();

            algorithm(matrix2);
        }

        static void algorithm(int[,] matrix2)
        {
            //Console.WriteLine("KL algorithm");
            //Console.WriteLine("Cut Number : {0}", Totalnode);
            //KL algorithm

            int[] Internal = new int[Totalnode];
            int[] External = new int[Totalnode];
            for (int n = 0; n < Totalnode; n++)
            {
                Internal[n] = 0;
                External[n] = 0;
            }
            int[] D = new int[Totalnode];
            for (int i = 0; i < Totalnode; i++)  // calculate I , E
            {
                if (i < Totalnode / 2)
                {
                    for (int j = 0; j < Totalnode / 2; j++)
                    {
                        Internal[i] += matrix2[i, j];
                        External[i] += matrix2[i, j + Totalnode / 2];

                    }
                }
                else
                {
                    for (int j = Totalnode / 2; j < Totalnode; j++)
                    {
                        Internal[i] += matrix2[i, j];
                        External[i] += matrix2[i, j - Totalnode / 2];