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]

Re: Depth of tree

"Kasp" <kaspREMOVE_CAP S@epatra.com> wrote in message
news:bmk7dn$eqe $1@newsreader.m ailgate.org...[color=blue]
> Consider an xml like this:[/color]

[color=blue]
> How can I find the max.depth of such a nested-node tree? I am using VB[/color]
with[color=blue]
> MSXML :([/color]


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

In fact, there is a test file called "testMaximum3.x sl" which find exactly
the node with the maximum depth in a tree.
[color=blue]
> 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[/color]
as[color=blue]
> my XML is very huge ~ 50MB!![/color]

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]

Re: Depth of tree

> > How can I find the max.depth of such a nested-node tree? I am using VB[color=blue]
> with[color=green]
> > MSXML :([/color]
>
>
> One can use the "maximum" template from FXSL for this purpose.
>[/color]

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]

Re: Depth of tree

"Kasp" <kasp@epatra.co m> wrote in message news:3b04990d.0 310152038.5aaea 898@posting.goo gle.com...[color=blue][color=green][color=darkred]
> > > How can I find the max.depth of such a nested-node tree? I am using VB[/color]
> > with[color=darkred]
> > > MSXML :([/color]
> >
> >
> > One can use the "maximum" template from FXSL for this purpose.
> >[/color]
>
> Thanks Dimitre for replying.
> However, your solution uses XSL while I need to find the max. depth of
> a tree using DOM (MSXML).[/color]

1. Use:

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

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

currNode.select Nodes(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]

Re: Depth of tree

"Kasp" <kasp@epatra.co m> wrote in message
news:3b04990d.0 310152038.5aaea 898@posting.goo gle.com
[color=blue][color=green][color=darkred]
>>> How can I find the max.depth of such a nested-node tree?
>>> I am using VB with MSXML :([/color][/color][/color]

Where is the problem? This is not a nasty thing. ;-)
[color=blue][color=green]
>> [...Dimitre Novatchev with an XSL solition...][/color]
>
> Any pointer to a solution that uses DOM to find the depth?[/color]

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

xml.Load "test.xml"
RecurseDepth xml.documentEle ment, maxDepth

Debug.Print maxDepth
End Sub
............... ............... ............... ............... .....
Function RecurseDepth(ro ot 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]

Re: Depth of tree

> 1. Use:[color=blue]
>
> selectNodes(//node()[not(node())])[/color]

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]

Re: Depth of tree

"Marek Malowidzki" <malowidz@wil.w aw.pl> wrote in message news:dde66692.0 310200214.18a9a fad@posting.goo gle.com...[color=blue][color=green]
> > 1. Use:
> >
> > selectNodes(//node()[not(node())])[/color]
>
> 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>[/color]

The above is not an empty element -- it has a child text node
(consisting of whitespace-only characters.
[color=blue]
>
> which may be not desired.[/color]

If this is not desired, specify:

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


=====
Cheers,

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