# Depth of tree

Discussion in 'XML' started by Kasp, Oct 15, 2003.

1. ### KaspGuest

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.

Kasp, Oct 15, 2003

2. ### Dimitre NovatchevGuest

"Kasp" <> wrote in message
news:bmk7dn\$eqe\$...
> 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

Dimitre Novatchev, Oct 15, 2003

3. ### KaspGuest

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

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.

Kasp, Oct 16, 2003
4. ### Dimitre NovatchevGuest

"Kasp" <> wrote in message news:...
> > > 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.
> >

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

Dimitre Novatchev, Oct 16, 2003
5. ### Martin BoehmGuest

"Kasp" <> wrote in message
news:

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

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

Martin Boehm, Oct 16, 2003
6. ### Marek MalowidzkiGuest

> 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

Marek Malowidzki, Oct 20, 2003
7. ### Dimitre NovatchevGuest

"Marek Malowidzki" <> wrote in message news:...
> > 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

Dimitre Novatchev, Oct 20, 2003