Hi all,
I'm looking for a fast algorithm to do the following:
A DataTable has the following columns: ID, ParentID, Title, Body, etc. It
represents webforum conversation threads. ParentID points to the ID of the
parent post.
I'm trying to convert this into a tree structure in memory (e.g. XML).
I understand this can be done with recursion but my algorithm seems to be
too slow, i.e. there are too many loops. Does anyone have an example of a
better algorithm?
Thanks.
Mine is (pseudocode):
For each row in table
{
if parent == 0 // top element
{
row.visited = true;
AttachToTree()
RecursivelySear chForChildRen(r ow)
}
}
method RecursivelySear chForChildRen(p arent)
{
Foreach row in table // TODO need to eliminate this extra loop, too
much iterating
{
if row.visited == false && row.parent == parent
{
row.visited = true;
AttachToParent( )
RecursivelySear chForChildRen(r ow) // call itself again
}
}
}
-Oleg. 2 3758
This probably has small chance of working without me implementing and
testing it, but it's a welcome break from writing specs for me, and I hope
it helps. :) It should perform better than O(n^2). By the way, if your
data is already in a friendly order (parents before children or vice versa)
you could write something very simple that would be wicked fast.
// "map" is an object that maps from an int id to a node object
// "node" is a class holds a row object and a parent node object
foreach row in table
{
if (!map.Exists(ro w.id))
{
// create parent placeholder node if necessary
if (!map.Exists(ro w.parentid))
map[row.parentid] = new node(null, null);
// create new node with row and link to parent node
map[row.id] = new node(row, map[row.parentid]);
}
else if (map[row.id].row is null) // node was created as mere
placeholder earlier?
{
// create parent placeholder node if necessary
if (!map.Exists(ro w.parentid))
map[row.parentid] = new node(null, null);
// fill in this node now with row and link to parent node
map[row.id].row = row;
map[row.id].parentnode = map[row.parentid]
}
}
Brad Williams
This is not bad at all. I've tested it.
However, in my scenario, I need to convert ID-ParentID rows of a DataTable
into a Row-ChildrenCollect ion.
In other words, here's the class structure:
class Node
{
int id;
string name;
NodeCollection subnodes;
}
Your code produces a list of leaves with the ability of walking up to the
top element.
I'm trying to write the opposite, e.g. to get a list of top nodes. Each node
has a pointer to all its children.
Thanks,
-Oleg.
"Brad Williams" <sp**@spam.co m> wrote in message
news:c8******** **@news01.intel .com... This probably has small chance of working without me implementing and testing it, but it's a welcome break from writing specs for me, and I hope it helps. :) It should perform better than O(n^2). By the way, if your data is already in a friendly order (parents before children or vice
versa) you could write something very simple that would be wicked fast.
// "map" is an object that maps from an int id to a node object // "node" is a class holds a row object and a parent node object foreach row in table { if (!map.Exists(ro w.id)) { // create parent placeholder node if necessary if (!map.Exists(ro w.parentid)) map[row.parentid] = new node(null, null);
// create new node with row and link to parent node map[row.id] = new node(row, map[row.parentid]); } else if (map[row.id].row is null) // node was created as mere placeholder earlier? { // create parent placeholder node if necessary if (!map.Exists(ro w.parentid)) map[row.parentid] = new node(null, null);
// fill in this node now with row and link to parent node map[row.id].row = row; map[row.id].parentnode = map[row.parentid] } }
Brad Williams
This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Lars Tengnagel |
last post by:
I'm trying to use the matrix variable to collect a matrix in the file
MatrixInfo which contains a lot of different matrices. Yhe commented line is
the problem.
HOW ???????
import re
import MatrixInfo
class Diff:
def __init__(self,filobj,matrix='pam250',begin=0,end='none'):
|
by: SallyBenjamin |
last post by:
Hello..
Can anyone help me with this coding. Basically, it needs to have add
node, remove node, add edges , remove edges and display the graph
But.I have only succedded to add node, add and remove edge and also
display graph...
Can anyone plz help me to change this and add the nodes..
Thank u
|
by: Zoran Stipanicev |
last post by:
Hi!
The question is product of laziness. I want to write generic operators for
matrix computation which would adapt to different types of matrices i.e.
when
adding square matrix and lower triangle matrix it would add only elements on
and
under main diagonal and copy the rest from square matrix. Basically it would
allow adding new matrix type (shape) without writing new operators (I'm to
lazy
|
by: Stipanicev |
last post by:
I want to write generic operators for
matrix computation which would adapt to different types (shapes) of matrices
i.e. when
adding square matrix and lower triangle matrix it would add only elements on
and
under main diagonal and copy the rest from square matrix. Basically it would
allow adding new matrix type (shape) without writing new operators. Here is
the
code I hope could do that:
|
by: Steve |
last post by:
I have been studying the Adjacency List Model as a means of achieving
a folder structure in a project I am working on. Started with the
excellent article by Gijs Van Tulder
http://www.sitepoint.com/article/hierarchical-data-database
My database has this basic structure:
Id
FolderName
| |
by: sanjeevron |
last post by:
Define a class for an adjacency matrix representation of weighted, directed graphs in C++.
2. Implement the following essential methods in your class. Any input validation or exceptions
must be handled within the methods.
• addNode - adds a new node (vertex) to the graph
• deleteNode(i) - deletes a given node, i from the graph
• addEdge(i,j,w) - adds an edge from node i to node j with weight w
• deleteEdge(i,j) - deletes the edge from node...
|
by: madhuparna |
last post by:
Plzz give the code for implementing adjacency matrix in C
|
by: mark |
last post by:
I have a 5x5 Matrix. Each cell consists a string value(ex:URL of a
website)
I want to find out which string value occurs( i.e. repeats ) maximum
no. of times in the matrix.
I have a hint that BINARY SEARCH TREE will be used here and that NODE
class in c# may be used to implement trees.
|
by: kantai |
last post by:
Need help in solving the problem below. Any help would be highly
appreciated
Implement the adt graph as a C++ class first by using an adjacency
matrix to represent the graph then by using an adjacency list to
represent the graph. Extend the programming problem by adding adt
operations such as Isconnected and HasCycle. also include operations
that perform a topological sort for a directed graph without cycles.
Determine the dfs...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| |
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |