Depth of tree

K

Kasp

Consider an xml like this:
<root>
<node>
<node>
<node>
</node>
</node>
<node>
</node>

<node>
</node>

<node>
<node>
<node>
<node>
</node>
</node>
</node>
</node>
</root>

How can I find the max.depth of such a nested-node tree? I am using VB with
MSXML :(
I am pretty novice with XML and XPath and need some help how to do this? I
am hoping someone would be able to point me to a "non-recursive" solution as
my XML is very huge ~ 50MB!!
Thanks.
 
D

Dimitre Novatchev

Kasp said:
Consider an xml like this:

How can I find the max.depth of such a nested-node tree? I am using VB with
MSXML :(


One can use the "maximum" template from FXSL for this purpose.

In fact, there is a test file called "testMaximum3.xsl" which find exactly
the node with the maximum depth in a tree.
I am pretty novice with XML and XPath and need some help how to do this? I
am hoping someone would be able to point me to a "non-recursive" solution as
my XML is very huge ~ 50MB!!

There are recursive solutions, which find the maximum in a linear time,
regardless of the size of the source.xml. The "maximum" template from FXSL
uses exactly such algorithm (DVC or "divide and conquer").

You can find a simpler implementation of maximum(), which also implements
DVC here:

http://www.topxml.com/code/default.asp?p=3&id=v20030314165921



=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL
 
K

Kasp

How can I find the max.depth of such a nested-node tree? I am using VB
with


One can use the "maximum" template from FXSL for this purpose.

Thanks Dimitre for replying.
However, your solution uses XSL while I need to find the max. depth of
a tree using DOM (MSXML).

Any pointer to a solution that uses DOM to find the depth?
Thanks.
 
D

Dimitre Novatchev

Kasp said:
Thanks Dimitre for replying.
However, your solution uses XSL while I need to find the max. depth of
a tree using DOM (MSXML).

1. Use:

selectNodes(//node()[not(node())])

2. Then for each of the returned (leaf) nodes get:

currNode.selectNodes(ancestor::node()).length

3. Put each such (number of a leaf node's ancestors) value in an array.

4. Find the maximum of the elements of the array computed in 3.



=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL
 
M

Martin Boehm

Where is the problem? This is not a nasty thing. ;-)
[...Dimitre Novatchev with an XSL solition...]

Any pointer to a solution that uses DOM to find the depth?

Use a recursive function like this one:
.................................................................
Sub test()
Dim xml As New DOMDocument40
Dim maxDepth As Long

xml.Load "test.xml"
RecurseDepth xml.documentElement, maxDepth

Debug.Print maxDepth
End Sub
.................................................................
Function RecurseDepth(root As IXMLDOMNode, _
maxDepth As Long, _
Optional currDepth As Long) As Long

Dim node As IXMLDOMNode

For Each node In root.childNodes
If node.nodeType = NODE_ELEMENT Then
RecurseDepth node, maxDepth, currDepth + 1
End If
Next node

If currDepth > maxDepth Then maxDepth = currDepth
End Function

.................................................................

This relies on the VB default of handing arguments over by reference, so
I can change the "outside" maxDepth from within RecurseDepth.

HTH

Martin
 
M

Marek Malowidzki

1. Use:
selectNodes(//node()[not(node())])

There is one subtle issue: with this form of XPath, XSL transformation seems
to count additional empty element, created when XML specifies empty content
for an element, e.g.

<node>
</node>

which may be not desired. Perhaps a way to avoid it would be to use
//node()[name() != '' and not(node())]. In this case, the depth will be the
same in both cases - when you specify

<node>
</node>

or

<node/>

(In fact, I was a bit surprised myself).

Marek
 
D

Dimitre Novatchev

Marek Malowidzki said:
1. Use:

selectNodes(//node()[not(node())])

There is one subtle issue: with this form of XPath, XSL transformation seems
to count additional empty element, created when XML specifies empty content
for an element, e.g.

<node>
</node>

The above is not an empty element -- it has a child text node
(consisting of whitespace-only characters.
which may be not desired.

If this is not desired, specify:

<xsl:strip-space element="*"/>


=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top