CODEWITHSUNDEEP
pythonxmltreeelementtree
Nullpoet
Nullpoet

Reputation: 11259

In Python ElementTree how can I get list of all ancestors of an element in tree?

I need "get_ancestors_recursively" function.
A sample run can be

>>> dump(tr)
<anc1>
  <anc2>
    <element> </element>
  </anc2>
</anc1>
>>> input_element = tr.getiterator("element")[0]
>>> get_ancestors_recursively(input_element)
['anc1', 'anc2']

Can somebody help me with this ?

Upvotes: 4

Views: 4322

Answers (4)

Arnold Daniels
Arnold Daniels

Reputation: 16573

You can use a tree traversal algorithm. This does the task in linear time.

def xml_get_ancestors(element: Element, root: Element):
    ancestors = []

    for node in root.iter():
        if node == element:
            return ancestors

        while len(ancestors) > 0 and node not in ancestors[-1]:
            ancestors.pop()
        
        ancestors.append(node)
    
    return None

Upvotes: 0

fantadisco
fantadisco

Reputation: 21

Found this little gem from lots of googling (http://elmpowered.skawaii.net/?p=74)

parent = root.findall(".//{0}/..".format(elem.tag))

root here is your root node of the tree. elem is the actual element object you get from iterating.

This does require you to know the root, which may mean changing how you set up for XML parsing, but it's minor at best.

Upvotes: 0

nearlymonolith
nearlymonolith

Reputation: 946

Another option is LXML, which provides useful extensions to the built in ElementTree api. If you're willing to install an external module, it has a nice Element.getparent() function that you could simply call recursively until reaching ElementTree.getroot(). This will probably be the fastest and most elegant solution (as the lxml.etree module introduces pointer attributes for the Elements that point to their parents, so instead of searching the entire tree for the proper parent/child pairs).

Upvotes: 3

Owen S.
Owen S.

Reputation: 7855

In the latest version of ElementTree (v1.3 or later), you can simply do

input_element.find('..')

recursively. However, the ElementTree that ships with Python doesn't have this functionality, and I don't see anything in the Element class that looks upwards.

I believe this means you have to do it the hard way: via an exhaustive search of the element tree.

def get_ancestors_recursively(e, b):
    "Finds ancestors of b in the element tree e."
    return _get_ancestors_recursively(e.getroot(), b, [])

def _get_ancestors_recursively(s, b, acc):
    "Recursive variant. acc is the built-up list of ancestors so far."
    if s == b:
        return acc
    else:
        for child in s.getchildren():
            newacc = acc[:]
            newacc.append(s)
            res = _get_ancestors_recursively(child, b, newacc)
            if res is not None:
                return res
        return None

This is slow because of the DFS, and cranks out a lot of lists for garbage collection, but if you can deal with that it should be fine.

Upvotes: 2

Related Questions