Printing nodes at a specified distance from a given node in a generic tree matrix

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            string sourceNode = "a";
            int distance = 2;
            string[] digits = { "a", "b", "c", "d", "e", "f", "g" };//nodes
            //node connection matrix
            int[,] connect = {
                                { 1, 1, 1, 0, 0, 0, 0 },
                                { 1, 1, 0, 1, 1, 0, 0 },
                                { 1, 0, 1, 0, 0, 1, 1 },
                                { 0, 1, 0, 1, 0, 0, 0 },
                                { 0, 1, 0, 0, 1, 0, 0 },
                                { 0, 0, 1, 0, 0, 1, 0 },
                                { 0, 0, 1, 0, 0, 0, 1 }
                             };
            Stack<string> sourceNodeStack = new Stack<string>();
            Stack<string> destinationNodeStack = new Stack<string>();
            ArrayList nodeList = new ArrayList();
            sourceNodeStack.Push(sourceNode);
            int level = 0;
            while (level < distance)
            {
                int flag = 0;
                if (sourceNodeStack != null && sourceNodeStack.Count != 0)
                {
                    while (sourceNodeStack.Count != 0)
                    {
                        int currentRow = getIndex(digits, sourceNodeStack.Pop().ToString());
                        nodeList.Add(digits[currentRow]);
                        for (int col = 0; col < connect.GetLength(1); col++)
                        {
                            if (col != currentRow && connect[currentRow, col] == 1 && !nodeList.Contains(digits[col]))
                            {
                                destinationNodeStack.Push(digits[col]);
                                flag = 1;
                            }
                        }
                    }
                    //Copying destinationNodeStack to sourceNodeStack
                    while (destinationNodeStack.Count != 0)
                    {
                        sourceNodeStack.Push(destinationNodeStack.Pop());
                    }
                    if (flag == 1)
                        level++;
                }
                else
                {
                    Console.WriteLine("No nodes found !!!");
                    level = -1;
                    break;
                }
            }
            if (level != -1)
            {
                Console.WriteLine("Nodes at distance " + distance.ToString());
                while (sourceNodeStack.Count != 0)
                {
                    Console.Write(sourceNodeStack.Pop() + " ");
                }
                Console.WriteLine();
            }
        }

        public static int getIndex(string[] strArray, string str)
        {
            int index = -1;
            for (int i = 0; i < strArray.Length; i++)
            {
                if (strArray[i] == str)
                {
                    index = i;
                    break;
                }
            }
            return index;
        }
    }
}

Output
======
Nodes at distance 2
d e f g
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s