Roxaq

C# Kruskal Implementation - Vddicted

Jul 25th, 2018
42
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace Kruskal
  8. {
  9.    
  10.     class Room
  11.     {
  12.         private int xPos, yPos;
  13.         private int group;
  14.  
  15.         private bool isOn;
  16.         private bool[] isConnected = new bool[4];
  17.  
  18.         public Room(int Y, int X, int nGroup)
  19.         {
  20.             xPos = X;
  21.             yPos = Y;
  22.             group = nGroup;
  23.  
  24.             isOn = true;
  25.             isConnected[0] = false;
  26.             isConnected[1] = false;
  27.             isConnected[2] = false;
  28.             isConnected[3] = false;
  29.         }
  30.  
  31.         public int getXPos()
  32.         {
  33.             return xPos;
  34.         }
  35.  
  36.         public void setXPos(int value)
  37.         {
  38.             xPos = value;
  39.         }
  40.  
  41.         public int getYPos()
  42.         {
  43.             return yPos;
  44.         }
  45.  
  46.         public void setYPos(int value)
  47.         {
  48.             yPos = value;
  49.         }
  50.  
  51.         public int getGroup()
  52.         {
  53.             return group;
  54.         }
  55.  
  56.         public void setGroup(int value)
  57.         {
  58.             group = value;
  59.         }
  60.  
  61.         public bool getIsOn()
  62.         {
  63.             return isOn;
  64.         }
  65.  
  66.         public void setIsOn(bool value)
  67.         {
  68.             isOn = value;
  69.         }
  70.  
  71.         public bool getIsConnected(int index)
  72.         {
  73.             try
  74.             {
  75.                 return isConnected[index];
  76.             }
  77.             catch
  78.             {
  79.                 Console.Write("Connection Array Out of Range");
  80.                 return true;
  81.             }
  82.         }
  83.  
  84.         public void setIsConnected(int index, bool value)
  85.         {
  86.             try
  87.             {
  88.                 isConnected[index] = value;
  89.             }
  90.             catch
  91.             {
  92.                 Console.SetCursorPosition(0, 20);
  93.                 Console.Write("Connection Array out of Range");
  94.             }
  95.         }
  96.     }
  97.  
  98.     class Program
  99.     {
  100.         static void Main(string[] args)
  101.         {
  102.             List<Room> mazeToCheck = new List<Room>();
  103.             List<Room> mazeChecked = new List<Room>();
  104.  
  105.  
  106.  
  107.             int sizeX, sizeY;
  108.             sizeY = Convert.ToInt32(Console.ReadLine());
  109.             sizeX = Convert.ToInt32(Console.ReadLine());
  110.  
  111.             Console.Clear();    
  112.  
  113.  
  114.             Room[] maze = new Room[sizeX * sizeY];
  115.             HashSet<Room>[] vertexSets = new HashSet<Room>[sizeX * sizeY];
  116.  
  117.             /*
  118.              *
  119.              *Inicialização dos nodes do labirinto
  120.              *    e inserção dos nodes em grupos isolados
  121.              *
  122.              */
  123.             for (int i = 0; i < sizeY; i++){
  124.                 for(int j = 0; j < sizeX; j++){
  125.                     int curIndex = i * sizeX + j;
  126.                     maze[curIndex] = new Room(i, j, curIndex);
  127.                     mazeToCheck.Add(maze[curIndex]);
  128.                     vertexSets[curIndex] = new HashSet<Room>();
  129.                     vertexSets[curIndex].Add(maze[curIndex]);
  130.                    
  131.                 }
  132.             }
  133.  
  134.             Random random = new Random();
  135.             int randNode;
  136.  
  137.  
  138.             /*
  139.              * Enquanto houver nodes para serem checados
  140.              * escolher um node aleatorio na lista de nodes
  141.              * descobrir sua coordenada, e procurar nodes vizinhos
  142.              */
  143.  
  144.             int nodes = 0;
  145.             while(mazeToCheck.Count > 0)
  146.             {
  147.                 nodes++;
  148.                 randNode = random.Next(0, mazeToCheck.Count);
  149.                 Room currentNode = mazeToCheck[randNode];
  150.                 Room destNode;
  151.                 List<int> connectionsToCheck = new List<int>();
  152.  
  153.  
  154.                 //Condições de checagem
  155.                 ///Se o node estiver no extremo esquerdo:   nao procurar no X- (West-0)
  156.                 ///Se o node estiver no extremo direito:    nao procurar no X+ (East-2)
  157.                 ///se o node estiver no extremo topo:       nao procurar no Y- (North-1)
  158.                 ///Se o node estiver no extremo baixo:      nao procurar no Y+ (South-3)
  159.                                
  160.                 //Extrema esquerda (west)
  161.                 if(currentNode.getXPos() > 0)
  162.                 {
  163.                     connectionsToCheck.Add(0);
  164.                 }
  165.                 //Extrema direita (east)
  166.                 if(currentNode.getXPos() < sizeX - 1)
  167.                 {
  168.                     connectionsToCheck.Add(2);
  169.                 }
  170.                 //Extremo topo (north)
  171.                 if(currentNode.getYPos() > 0)
  172.                 {
  173.                     connectionsToCheck.Add(1);
  174.                 }
  175.                 //Extremo baixo (south)
  176.                 if(currentNode.getYPos() < sizeY - 1)
  177.                 {
  178.                     connectionsToCheck.Add(3);
  179.                 }
  180.  
  181.                 //Placeholder
  182.                
  183.                
  184.                 //Placeholder
  185.  
  186.                 //Checar o vertice escolhido
  187.                 //Se o node linkado ao vertice for do mesmo grupo do node atual, descartar vertice e tentar novamente (tentar ate a lista de vertices esvaziar)
  188.                 //Se a lista de vertices esvaziar e nenhum vertice for escolhido, desconsiderar node (para nao criar loops) e continuar para o proximo
  189.  
  190.                 //Aqui o node tera uma lista de possiveis conexões
  191.                 //Deve agora comparar o node da conexão escolhida aleatoriamente para saber se esta no mesmo grupo
  192.                 bool foundConnection = false;
  193.                 while (connectionsToCheck.Count > 0 && foundConnection == false)
  194.                 {
  195.                     int randomConnection = connectionsToCheck[random.Next(0, connectionsToCheck.Count)];
  196.                     //Console.WriteLine("Current Node: {2} Connection Count: {0} RandomConnection: {1}", connectionsToCheck.Count, randomConnection, nodes);
  197.  
  198.                     int destGroup;
  199.                     switch (randomConnection)
  200.                     {
  201.                         //West Check (X - 1)
  202.                         case 0:
  203.                             //armazena o node ligado ao vertice escolhido
  204.                             destNode = maze[currentNode.getYPos() * sizeX + currentNode.getXPos() - 1];
  205.  
  206.                             /*
  207.                             * se os nodes pertencem ao mesmo grupo
  208.                             * remover o vertice atual da checagem, e continuar tentando se houver mais vertices
  209.                             *
  210.                             * se os nodes forem de grupos diferentes, transferir o node destino ao grupo do node atual
  211.                             */
  212.  
  213.                             if (CheckRoomsGroup(currentNode, destNode))
  214.                             {
  215.                                 connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(0));
  216.                             }
  217.                             else
  218.                             {
  219.                                 //armazena o indice do node destino
  220.                                 destGroup = maze[currentNode.getYPos() * sizeX + currentNode.getXPos() - 1].getGroup();
  221.  
  222.                                 //faz a união do conjunto de sets
  223.                                 vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
  224.                                 foreach(Room r in vertexSets[destGroup])
  225.                                 {
  226.                                     maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
  227.                                 }
  228.                                 maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
  229.  
  230.                                 //indica que uma conexão foi feita
  231.                                 foundConnection = true;
  232.                             }
  233.                             break;
  234.                         //North Check (Y - 1)
  235.                         case 1:
  236.  
  237.                             destNode = maze[(currentNode.getYPos() - 1) * sizeX + currentNode.getXPos()];
  238.  
  239.                             if (CheckRoomsGroup(currentNode, destNode)){
  240.                                 connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(1));
  241.                             }else
  242.                             {
  243.                                 destGroup = maze[(currentNode.getYPos() - 1) * sizeX + currentNode.getXPos()].getGroup();
  244.  
  245.                                 vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
  246.                                 foreach (Room r in vertexSets[destGroup])
  247.                                 {
  248.                                     maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
  249.                                 }
  250.  
  251.                                 maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
  252.                                 foundConnection = true;
  253.                             }
  254.                             break;
  255.                         //East Check (X + 1)
  256.                         case 2:
  257.  
  258.                             destNode = maze[(currentNode.getYPos() * sizeX + currentNode.getXPos() + 1)];
  259.  
  260.                             if (CheckRoomsGroup(currentNode, destNode))
  261.                             {
  262.                                 connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(2));
  263.                             }
  264.                             else
  265.                             {
  266.                                 destGroup = maze[(currentNode.getYPos() * sizeX + currentNode.getXPos() + 1)].getGroup();
  267.  
  268.                                 vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
  269.                                 foreach (Room r in vertexSets[destGroup])
  270.                                 {
  271.                                     maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
  272.                                 }
  273.  
  274.                                 maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
  275.                                 foundConnection = true;
  276.                             }
  277.                             break;
  278.                         //South Check (Y + 1)
  279.                         case 3:
  280.  
  281.                             destNode = maze[((currentNode.getYPos() + 1) * sizeX + currentNode.getXPos())];
  282.  
  283.                             if (CheckRoomsGroup(currentNode, destNode))
  284.                             {
  285.                                 connectionsToCheck.RemoveAt(connectionsToCheck.IndexOf(3));
  286.                             }
  287.                             else
  288.                             {
  289.                                 destGroup = maze[((currentNode.getYPos() + 1) * sizeX + currentNode.getXPos())].getGroup();
  290.  
  291.                                 vertexSets[currentNode.getGroup()].UnionWith(vertexSets[destGroup]);
  292.                                 foreach (Room r in vertexSets[destGroup])
  293.                                 {
  294.                                     maze[r.getYPos() * sizeX + r.getXPos()].setGroup(currentNode.getGroup());
  295.                                 }
  296.                                 foundConnection = true;
  297.                                 maze[currentNode.getYPos() * sizeX + currentNode.getXPos()].setIsConnected(randomConnection, true);
  298.                             }
  299.                             break;
  300.                     }
  301.                     PrintMaze(maze, sizeY, sizeX);
  302.                     Console.ReadLine();
  303.  
  304.                 }
  305.                 mazeChecked.Add(mazeToCheck[randNode]);
  306.                 mazeToCheck.RemoveAt(randNode);
  307.                
  308.                 connectionsToCheck.Clear();
  309.             }
  310.            
  311.                     //InitMaze(maze, sizeY, sizeX);
  312.                     PrintMaze(maze, sizeY, sizeX);
  313.             Console.Read();
  314.  
  315.         }
  316.  
  317.         ///<summary>Check if two rooms are in the same group</summary>
  318.         static bool CheckRoomsGroup(Room room1, Room room2)
  319.         {
  320.             if(room1.getGroup() == room2.getGroup())
  321.             {
  322.                 return true;
  323.             }else
  324.             {
  325.                 return false;
  326.             }
  327.  
  328.         }
  329.  
  330.         static void PrintMaze(Room[] maze, int sizeY, int sizeX)
  331.         {
  332.             for (int i = 0; i < sizeY; i++)
  333.             {
  334.                 for (int j = 0; j < sizeX; j++)
  335.                 {
  336.                     int curIndex = i * sizeX + j;
  337.                     Console.SetCursorPosition(maze[curIndex].getXPos() * 2, maze[curIndex].getYPos() * 2);
  338.                     if (maze[curIndex].getIsOn())
  339.                     {
  340.                         Console.Write("{0}",maze[curIndex].getGroup());
  341.                     }
  342.                     //West Check
  343.                     if (maze[curIndex].getIsConnected(0) == true && maze[curIndex].getXPos() * 2 - 1 > 0)
  344.                     {
  345.                         Console.SetCursorPosition(maze[curIndex].getXPos() * 2 - 1, maze[curIndex].getYPos() * 2 + 0);
  346.                         Console.Write("─");
  347.                     }
  348.  
  349.                     //North Check
  350.                     if (maze[curIndex].getIsConnected(1) == true && maze[curIndex].getYPos() * 2 - 1 > 0)
  351.                     {
  352.                         Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 0, maze[curIndex].getYPos() * 2 - 1);
  353.                         Console.Write("│");
  354.                     }
  355.  
  356.                     //East Check
  357.                     if (maze[curIndex].getIsConnected(2) == true && maze[curIndex].getXPos() * 2 + 1 < sizeX * 2 - 2)
  358.                     {
  359.                         Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 1, maze[curIndex].getYPos() * 2 + 0);
  360.                         Console.Write("─");
  361.                     }
  362.  
  363.                     //South Check
  364.                     if (maze[curIndex].getIsConnected(3) == true && maze[curIndex].getYPos() * 2 + 1 < sizeY * 2 - 2)
  365.                     {
  366.                         Console.SetCursorPosition(maze[curIndex].getXPos() * 2 + 0, maze[curIndex].getYPos() * 2 + 1);
  367.                         Console.Write("│");
  368.                     }
  369.                 }
  370.             }
  371.         }
  372.     }
  373. }
Add Comment
Please, Sign In to add comment