Solved

Building a Tree from DataTable results with the node structure formatted as \Node1\Node2\

Posted on 2008-06-24
11
293 Views
Last Modified: 2011-10-03
Hi,
I've been banging my head against a wall for the past few days with the problem of turning DataTable results into a Tree Structure to populate a TreeView control. The tree path is stored in a field called Path.

[Path]
A\1\A\1
A\1\A\2
A\1\B\1
A\1\B\2
A\1\C\1
A\2\A\1
A\2\A\2
A\2\B\1
B\1\A\1
C\1\A\1

Normally I do a recursive query using parent ID's but this system is different as the Root Parents Childs are all stored in the string.  I've been doing a  For each Row in DataSet and breaking down each Path into a string array using  NodeList = Path.Split(CChar("\"))  but its the building of the nodes that I just cant get my head around.

Idealy I dont want to requery the database again, the results in the datatable from a stored procedure with a fair few params. So I'd have to work with data just in the datatable.


Regards

Daniel
0
Comment
Question by:emub
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 5
11 Comments
 
LVL 18

Expert Comment

by:philipjonathan
ID: 21856632
Probably could do something like:


function TreeNode BuildNode(string path)
{
    TreeNode node = ...  // Build a node for this path
    DataRow[] rows = tbl.Select("LIKE " + path + "\%");
    foreach (DataRow row in rows)
    {
        BuildNode((string) row["path"]);
    }
}

Open in new window

0
 

Author Comment

by:emub
ID: 21857601
Though I think the toughest problem isnt the recursive part its working with the path.

Here is the code I've done so far. it almost works but I cant work out why it gets stuck in a loop.

Tracing through it would make the following nodes

D
D\1
D\1\A
D\1\A\1
D\1\A\2
D\1\A\3
D\1\A\4

then it would start again back at D\1\A point and loop forever.

LocationTreeView.Nodes.Clear()
 
For Each root As String In GetNodeRoots(locationList)
     LocationTreeView.Nodes.Add(BuildNode(root, locationList))
Next
 
    Public Function GetNodeRoots(ByRef list As DataTable) As Collection
        Dim rootNodes As New Collection
        Dim lastRoot As String = String.Empty
 
        For Each row As DataRow In list.Rows
            Dim nodeList() As String = row("LocationName").ToString.Split(CChar("\"))
            If lastRoot <> nodeList(0) Then
                rootNodes.Add(nodeList(0))
                lastRoot = nodeList(0)
            End If
        Next
        Return rootNodes
    End Function
 
    Public Function BuildNode(ByVal path As String, ByRef list As DataTable) As TreeNode
        ' Get the current path where we are upto.
        Dim currentPath() As String = path.Split(CChar("\"))
        ' Create next node.
        Dim node As New TreeNode(currentPath(currentPath.GetUpperBound(0)))
        ' Get a filtered list of all the child nodes for the path passed in.
        For Each row As DataRow In list.Select(String.Concat("LocationName LIKE '", String.Concat(path, "\"), "%'"))
            ' Get the full path of the next node.
            Dim nextNode() As String = row("LocationName").ToString.Split(CChar("\"))
            ' If the next node has any more childs then call the recursive function.
            If nextNode.Count > currentPath.Count Then
                ' Make the next path we pass in just 1 step along from the current path.
                ReDim Preserve nextNode(currentPath.Count)
                ' Call recursive funxtion with the new path, rejoin the path back to its orginal format also.
                node.Nodes.Add(BuildNode(String.Join("\", nextNode), list))
            End If
        Next
        Return node
    End Function

Open in new window

0
 

Author Comment

by:emub
ID: 21864108
Ok while some essential tweeks to the above code for efficency I stumbled accross the probem,

the problem lies with that line

For Each row As DataRow In list.Select(String.Concat("LocationName LIKE '", path, "\", "%'"))

It works fine except for its returning to much,  if the [path] was  

LocationName LIKE 'A\1\%'

it works but its returning multipule entries due to there been no GROUP BY or SELECT DISTINCT clauses.
The problem is I only know how to filter the results in DataTable.Select with parameters. Can you do this in the DataTable or do I have to resort to doing it manually in the code itself?
0
Salesforce Made Easy to Use

On-screen guidance at the moment of need enables you & your employees to focus on the core, you can now boost your adoption rates swiftly and simply with one easy tool.

 
LVL 18

Expert Comment

by:philipjonathan
ID: 21864162
Is it because the select clause returns you all the descendants of a node, whether direct or indirect.

That is when current node is 'A\1'
The select will return you both 'A\1\B', as well as 'A\1\B\2'?

If this is the case your check should be

If nextNode.Count = currentPath.Count + 1 Then

instead of

If nextNode.Count > currentPath.Count Then
0
 

Author Comment

by:emub
ID: 21864193
Yes that is whats happening, the select clause is returning multipule 'A\1\' 's due to child nodes.

however

If nextNode.Count = currentPath.Count + 1 Then

does top the endless looping so I can actually see the results but were missing loads of nodes, we only go max 1 depth in now.
0
 
LVL 18

Expert Comment

by:philipjonathan
ID: 21864220
Hmm, how does your code looks like now after some essential tweaks that you mentioned?
0
 

Author Comment

by:emub
ID: 21864268
tbh pretty much the same I just changed how I was building strings, I had some extra steps in there that wasn't needed, which since this would be looping several 1000's times (alot of records in the DataTable) I didnt want to many overheads.

Looking at whats happening or what we want to stop happening. The Select clause is ment to retrive a list of the Childs ware are to build nodes for then pass those Childpaths into the function again but if them childs have subChilds we have duplicate requests. So we need to remove them duplicates since were not intrested in them.

I can only think of 2 ways atm,  either Create a function that filders the orginal Array of DataRows() removing all duplicates before we start the for next loop. or do an extra check and verify the previously processed node is not = to the next node were about to process. ?? /shrug  :)
0
 

Author Comment

by:emub
ID: 21865618
Tried both methods and the overheads are to high takes 5-6Ssecs pn my PC to generate 1011 nodes.
Which is far to long as the final plan would be much larger.  The problem is working with the DataTable only.  So I'll write it so I can actually query the database for the child nodes and let the database do the filtering.

ty :)
0
 
LVL 18

Accepted Solution

by:
philipjonathan earned 500 total points
ID: 21871394
What about this (pseudo-code):

foreach row in the DataTable
  string() nodes = locationName.ToString().Split("\")
  use the nodes array to traverse down the treeview nodes to find node
    if node is not created yet
      create node (any additional details for the node must be updated later)
    else
      update node information, if anything needs to be updated
  end of treeview traversal
end of foreach

The idea is instead of going by the tree structure and search for its child-node from the DataTable, we loop by the DataTable and create the node immediately (including its ancestor nodes, if they aren't created yet).

I believe the 1st method has O(n^2) complexity, because there are n items in the tree, and each search for a node's children in the DataTable requires us to roughly traverse almost all n items.

While the 2nd method should be a little better O(n log n). Because we only need to traverse the whole table once, that is O(n). And for each item, we search for its location in the tree, which is roughly O(log n). Theoretically, this should be faster, and no duplicates too :) and it does not need recursion ...

Unfortunately, I'm tied down with my office work at the moment, couldn't test it out myself. You can try it out if you want to...
0
 

Author Comment

by:emub
ID: 21873470
Ty, I'd orginally tried to do it that way but failed. After having another go at it I realised I was using the TreeView control incorrectly.

Its all working now and the tree is build pretty much instantly even with all the records in.

I've attached the basic code that gets it working.

Thanks. :)
        For Each row As DataRow In data.Rows
 
            Dim nodePath() As String = row("LocationName").ToString.Split(CChar("\"))
            Dim currentLocation As TreeNode
            Dim nextPath As String = String.Empty
 
            For Each node As String In nodePath
                ' Keep track of our current path, so we can use it as the Node's Key property.
                nextPath = String.Concat(nextPath, node)
 
                If currentLocation Is Nothing AndAlso LocationTreeView.Nodes.Item(nextPath) Is Nothing Then
                    ' Create a new root node.
                    currentLocation = LocationTreeView.Nodes.Add(node, node)
                ElseIf currentLocation IsNot Nothing AndAlso currentLocation.Nodes.Item(nextPath) Is Nothing Then
                    ' Create a new sub node.
                    currentLocation = currentLocation.Nodes.Add(nextPath, nextPath)
                ElseIf currentLocation Is Nothing AndAlso LocationTreeView.Nodes.Item(nextPath) IsNot Nothing Then
                    ' Root node already exists, set our location to root node.
                    currentLocation = LocationTreeView.Nodes.Item(nextPath)
                Else
                    ' Sub node exists, move our current location to subnode.
                    currentLocation = currentLocation.Nodes.Item(nextPath)
                End If
            Next
            ' Reset current location back to root.
            currentLocation = Nothing
            nextPath = String.Empty
        Next

Open in new window

0
 
LVL 18

Expert Comment

by:philipjonathan
ID: 21876593
Wow, thanks for sharing with us, and glad that I can help ... thanks for the points too :)
0

Featured Post

Instantly Create Instructional Tutorials

Contextual Guidance at the moment of need helps your employees adopt to new software or processes instantly. Boost knowledge retention and employee engagement step-by-step with one easy solution.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Article by: Martin
Here are a few simple, working, games that you can use as-is or as the basis for your own games. Tic-Tac-Toe This is one of the simplest of all games.   The game allows for a choice of who goes first and keeps track of the number of wins for…
If you need to start windows update installation remotely or as a scheduled task you will find this very helpful.
Get people started with the process of using Access VBA to control Excel using automation, Microsoft Access can control other applications. An example is the ability to programmatically talk to Excel. Using automation, an Access application can laun…
Show developers how to use a criteria form to limit the data that appears on an Access report. It is a common requirement that users can specify the criteria for a report at runtime. The easiest way to accomplish this is using a criteria form that a…

726 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question