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]

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