Depth of tree

[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.
--
"Accept that some days you are the pigeon and some days the statue."
"A pat on the back is only a few inches from a kick in the butt." - Dilbert.

[Dimitre Novatchev]

"Kasp" <ka*************@epatra.com> wrote in message
news:bm**********@newsreader.mailgate.org...

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.a...20030314165921

=====
Cheers,

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

[Kasp]

> > 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.

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.

[Dimitre Novatchev]

"Kasp" <ka**@epatra.com> wrote in message news:3b**************************@posting.google.c om...

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.

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

[Martin Boehm]

"Kasp" <ka**@epatra.com> wrote in message
news:3b**************************@posting.google.c om

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

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

[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

[Dimitre Novatchev]

"Marek Malowidzki" <ma******@wil.waw.pl> wrote in message news:dd**************************@posting.google.c om...

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