Depth of tree

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

  1. Kasp

    Kasp Guest

    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
    #1
    1. Advertising

  2. "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
    #2
    1. Advertising

  3. Kasp

    Kasp Guest

    > > 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.
     
    Kasp, Oct 16, 2003
    #3
  4. "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.
    > >

    >
    > 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
     
    Dimitre Novatchev, Oct 16, 2003
    #4
  5. Kasp

    Martin Boehm Guest

    "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

    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
     
    Martin Boehm, Oct 16, 2003
    #5
  6. > 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
    #6
  7. "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
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Wynan James

    Depth of n-ary tree

    Wynan James, Sep 29, 2003, in forum: Java
    Replies:
    10
    Views:
    11,392
    Stefan Poehn
    Sep 30, 2003
  2. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,240
  3. howa
    Replies:
    1
    Views:
    3,570
    mlimber
    Oct 26, 2006
  4. jono

    depth-first search of a tree

    jono, Oct 1, 2008, in forum: Python
    Replies:
    0
    Views:
    639
  5. RAKHE

    Depth of Binary Tree

    RAKHE, Mar 11, 2010, in forum: C Programming
    Replies:
    18
    Views:
    4,866
    Phred Phungus
    Mar 15, 2010
Loading...

Share This Page