How to make a spanning tree in C# for a given element in a matrix

Question

0.00/5 (No votes)

See more:

I need to extract the best path in terms of its length from a rectangular array like this array:

Quote:
|1||0||1||0|
|1||0||0||1|
|1||1||0||1|
|0||0||1||1|

The pathfinding rules:

1- Start from the indexes provided in the method signature where the rowIndex and colIndex are the positions of the starting point.

2- The ones must be able to connect with each other either horizontally, vertically, or diagonally.

3- You can not move to the cell that contains zero.

4- You can back by the path but not using the same cells i.e. you can move up the down the up but not using the same cells.

5- The best path from all the extracted paths (possible solutions) is longest one in terms of the connected ones by each other.

6- No problem if the value of the starting cell is 0.

I tried the following recursion algorithm, but it does not work for me and generate wrong output i.e. not as expected!!.

Here are the results: Results

C#

        using System;
        using System.IO;
        using System.Text;
        using System.Drawing;
        using System.Collections;
        using System.ComponentModel;
        using System.Windows.Forms;
        using System.Data;
        using System.Threading;
        using AUV_Topology;
        using System.Collections.Generic;
        using System.Media;
        using System.Linq;

        namespace AUVtopology
        {
            public partial class Form1 : Form
            {        
              static int[,] array;
              static List<int[]> path;

// *******************************************************************************************************************************//
        //This method is used to make sure the coordinate array 
        //is contained in the list. List.contains(new int[] {val1,val2}) was not enough.
        static Boolean containsArray(List<int[]> list, int[] array)
        {
            if (array == null || array.Length == 0)
            {
                return false;
            }
            foreach (var listArray in list)
            {
                if (listArray != null && listArray.Length == array.Length)
                {
                    for (int i = 0; i < listArray.Length; i++)
                    {
                        if (i != listArray.Length - 1)
                        {
                            if (array[i] != listArray[i] && array[i + 1] != listArray[i + 1])
                            {
                                continue;
                            }


                            return true;

                        }

                    }

                }
            }
            return false;
        }    



// *******************************************************************************************************************************//

        //This is the recursive method of the algorithm. It finds the 
        //maximum path of 1 cells in a matrix of 0/1 cells
        static List<int[]> getMaxPath(int[,] array, List<int[]> maxPath, int rowIndex, int colIndex)
        {

            //Add the current cell to the path.
            maxPath.Add(new int[] { rowIndex, colIndex });

            //Get the array limits.
            int rowLength = array.GetLength(0);
            int colLength = array.GetLength(1);

            //If the path contains all the cells in the matrix, stop
            if (maxPath.Count >= rowLength * colLength)
            {
                return maxPath;
            }

            //remove one from lengths to make it the maximum index
            colLength = colLength - 1;
            rowLength = rowLength - 1;

            //We'll use this variable to see which of the 
            //potential 7 paths are the longest.
            List<int[]> futurePath;

            //Go over all 8 possible adjoining cells:
            //If we can go one down, one right, and it's a spot we 
            //have not yet visited
            if (colIndex < colLength && rowIndex < rowLength &&
                array[rowIndex + 1, colIndex + 1] == 1 &&
                !containsArray(maxPath, new int[] { rowIndex + 1, colIndex + 1 }))
            {

                //We use maxPath first, since this is the first 
                //direction and by default is the longest
                maxPath = getMaxPath(array, maxPath, rowIndex + 1, colIndex + 1);
            }

            //If we can go one down, and it's a spot we have not
            //yet visited
            if (colIndex < colLength &&
              array[rowIndex, colIndex + 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex, colIndex + 1 }))
            {

                //We use futurePath now, since this is a second
                //direction and a potential contender
                futurePath = getMaxPath(array, maxPath, rowIndex, colIndex + 1);

                //We only need the maximum path.
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //If we can go one down and one left, and it's a spot
            //we have not yet visited
            if (rowIndex > 0 && colIndex < colLength &&
               array[rowIndex - 1, colIndex + 1] == 1 &&
               !containsArray(maxPath, new int[] { rowIndex - 1, colIndex + 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex + 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //If we can go one left, and it's a spot we have not
            //yet visited
            if (rowIndex > 0 &&
               array[rowIndex - 1, colIndex] == 1 &&
               !containsArray(maxPath, new int[] { rowIndex - 1, colIndex }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one left and one up, and it's a spot we
            //have not yet visited
            if (rowIndex > 0 && colIndex > 0 &&
              array[rowIndex - 1, colIndex - 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex - 1, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex - 1, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one up, and it's a spot we have not yet
            //visited
            if (colIndex > 0 &&
                array[rowIndex, colIndex - 1] == 1 &&
                !containsArray(maxPath, new int[] { rowIndex, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one up and one right, and it's a spot we
            //have not yet visited
            if (colIndex > 0 && rowIndex < rowLength &&
              array[rowIndex + 1, colIndex - 1] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex + 1, colIndex - 1 }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex - 1);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }
            //If we can go one right, and it's a spot we have not
            //yet visited
            if (rowIndex < rowLength &&
              array[rowIndex + 1, colIndex] == 1 &&
              !containsArray(maxPath, new int[] { rowIndex + 1, colIndex }))
            {

                futurePath = getMaxPath(array, maxPath, rowIndex + 1, colIndex);
                if (futurePath.Count > maxPath.Count)
                {
                    maxPath = futurePath;
                }
            }

            //We return the max path. Note: If none of the directions around 
            //us was applicable, we simply return the path we started 
            //with our cell included.
            return maxPath;
        }

So I thought in a different way!!. If we can generate a spanning tree for each node with one more thing; which is that you can back to a lower cell in terms of its indexes, if it is not listed as a previous parent. See the example:

See the image

The branch inside the circle with the blue color represents the longest path in terms of the number of cells with the value 1.
My question is how to implement this. How to create an array for each branch in order to compare them in terms of the length to obtain the longest one as the best solution ?.

What I have tried:

Recursion Function to extract the path as the rules, but I did not work for me as it made wrong results and with large array size it made a stack overflow!!.

Posted 3-Jul-17 21:11pm

Member 11247684

Updated 3-Jul-17 22:51pm

Add a Solution

1 solution

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Member 13291909 · Answer 1 · 2017-07-03T22:51:00

using System; 
using System.Collections.Generic; 
 
namespace Prim 
{ 
    class PriorityQueue 
    { 
        int heapSize; 
        List<Node> nodeList; 
 
        public List<Node> NodeList 
        { 
            get 
            { 
                return nodeList; 
            } 
        } 
 
        public PriorityQueue(List<Node> nl) 
        { 
            heapSize = nl.Count; 
            nodeList = new List<Node>(); 
 
            for (int i = 0; i < nl.Count; i++) 
                nodeList.Add(nl[i]); 
        } 
 
        public void exchange(int i, int j) 
        { 
            Node temp = nodeList[i]; 
 
            nodeList[i] = nodeList[j]; 
            nodeList[j] = temp; 
        } 
 
        public void heapify(int i) 
        { 
            int l = 2 * i + 1; 
            int r = 2 * i + 2; 
            int largest = -1; 
             
            if (l < heapSize && nodeList[l].Key > nodeList[i].Key) 
                largest = l; 
            else 
                largest = i; 
            if (r < heapSize && nodeList[r].Key > nodeList[largest].Key) 
                largest = r; 
            if (largest != i) 
            { 
                exchange(i, largest); 
                heapify(largest); 
            } 
        } 
 
        public void buildHeap() 
        { 
            for (int i = heapSize / 2; i >= 0; i--) 
                heapify(i); 
        } 
 
        int heapSearch(Node node) 
        { 
            for (int i = 0; i < heapSize; i++) 
            { 
                Node aNode = nodeList[i]; 
 
                if (node.Id == aNode.Id) 
                    return i; 
            } 
 
            return -1; 
        } 
 
        public int size() 
        { 
            return heapSize; 
        } 
 
        public Node elementAt(int i) 
        { 
            return nodeList[i]; 
        } 
 
        public void heapSort() 
        { 
            int temp = heapSize; 
 
            buildHeap(); 
            for (int i = heapSize - 1; i >= 1; i--) 
            { 
                exchange(0, i); 
                heapSize--; 
                heapify(0); 
            } 
 
            heapSize = temp; 
        } 
 
        public Node extractMin() 
        { 
            if (heapSize < 1) 
                return null; 
 
            heapSort(); 
 
            exchange(0, heapSize - 1); 
            heapSize--; 
            return nodeList[heapSize]; 
        } 
 
        public int find(Node node) 
        { 
            return heapSearch(node); 
        } 
    } 
}

How to make a spanning tree in C# for a given element in a matrix

1 solution

Solution 1

Add your solution here

Preview 0

How to make a spanning tree in C# for a given element in a matrix

1 solution

Solution 1

Add your solution here

Preview 0

Existing Members

...or Join us