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.

 

[Dimitre Novatchev]

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

 

[Kasp (2)]

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.

 

[Dimitre Novatchev]

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]

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]

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