user3011517
user3011517

Reputation: 11

Build tree data from dictionary

I have structure as below

{
   "Start": "CDG",
   "AirportsRoutes": 
{
    "BKK" : ["SIN", "DXB", "CDG", "SFO"],
    "CDG" : ["LHR", "SIN"],
    "JFK" : ["CDG", "DXB"],
    "JNB" : ["SIN"],
    "SIN" : ["SFO", "BKK"],
    "SFO" : ["JFK", "BKK", "LHR"],
    "LHR" : ["CDG", "JFK", "DXB"],
    "YYZ" : ["SFO", "JFK"],
    "DXB" : ["JNB", "SIN", "BKK"]
}
}

I created dictionary for AirportsRoutes as Dictionary<string, List<string>>.

I would like to build tree of data from this dictionary by using value to be next node for example if use "CDG" for root node.

Each leaf node will be stop if found the same key of their parent node.

CDG->LHR->CDG
   ->LHR->JFK->CDG
   ->LHR->JFK->DXB->JNB->SIN->SFO->JFK
   ->LHR->JFK->DXB->JNB->SIN->SFO->BKK
   ->LHR->JFK->DXB->JNB->SIN->SFO->LHR
   ->LHR->JFK->DXB->JNB->SIN->BKK...
   ->LHR->JFK->DXB->SIN->SFO...
   ->LHR->JFK->DXB->SIN->BKK..
   ->LHR->JFK->DXB->BKK..
   ->LHR->DXB..

Does everyone know how to make it or do I need to change Dictionary to something else ?

Upvotes: 1

Views: 2983

Answers (1)

Baldrick
Baldrick

Reputation: 11840

This little console app does what you want:

public class Program
{
    public class TreeNode<T>
    {
        public List<TreeNode<T>> children = new List<TreeNode<T>>();
        public T thisItem;
        public TreeNode<T> parent;
    }

    public static void Main(string[] args)
    {
        var dict = new Dictionary<string, List<string>>
        {
            {"BKK", new List<string>{"SIN", "DXB", "CDG", "SFO"}},
            {"CDG" , new List<string>{"LHR", "SIN"}},
            {"JFK" , new List<string>{"CDG", "DXB"}},
            {"JNB" , new List<string>{"SIN"}},
            {"SIN" , new List<string>{"SFO", "BKK"}},
            {"SFO" , new List<string>{"JFK", "BKK", "LHR"}},
            {"LHR" , new List<string>{"CDG", "JFK", "DXB"}},
            {"YYZ" , new List<string>{"SFO", "JFK"}},
            {"DXB", new List<string> {"JNB", "SIN", "BKK"}}
        };

        var tree = BuildTree(dict, "CDG");
    }

    public static TreeNode<T> BuildTree<T>(Dictionary<T, List<T>> dictionary, T root)
    {
        var newTree = new TreeNode<T>
        {
            thisItem = root,
        };

        newTree.children = GetChildNodes(dictionary, newTree);
        
        return newTree;
    }

    public static List<TreeNode<T>> GetChildNodes<T>(Dictionary<T, List<T>> dictionary, TreeNode<T> parent)
    {
        var nodeList = new List<TreeNode<T>>();

        if (dictionary.ContainsKey(parent.thisItem))
        {
            foreach (var item in dictionary[parent.thisItem])
            {
                var nodeToAdd = new TreeNode<T>
                {
                    thisItem = item,
                    parent = parent,
                };

                if (!ContainedInParent(parent, item))
                {
                    nodeToAdd.children = GetChildNodes(dictionary, nodeToAdd);
                }

                // output leaf node for debugging!
                if (nodeToAdd.children.Count == 0)
                {
                    Console.WriteLine(NodeString(nodeToAdd));
                }

                nodeList.Add(nodeToAdd);
            }
        }
        
        return nodeList;
    }

    private static string NodeString<T>(TreeNode<T> node)
    {
        return (node.parent != null ? NodeString(node.parent) + "->" : string.Empty) + node.thisItem;
    }

    private static bool ContainedInParent<T>(TreeNode<T> parent, T item)
    {
        var found = false;

        if (parent != null)
        {
            if (parent.thisItem.Equals(item))
            {
                found = true;
            }
            else
            {
                found = ContainedInParent(parent.parent, item);
            }
        }

        return found;
    }
}

The output is:

CDG->LHR->CDG

CDG->LHR->JFK->CDG

CDG->LHR->JFK->DXB->JNB->SIN->SFO->JFK

CDG->LHR->JFK->DXB->JNB->SIN->SFO->BKK->SIN

CDG->LHR->JFK->DXB->JNB->SIN->SFO->BKK->DXB

CDG->LHR->JFK->DXB->JNB->SIN->SFO->BKK->CDG

.........

Upvotes: 1

Related Questions