Recursively search for parent child combinations and build tree in python and XML

Question

I am trying to traverse this XML data full of parent->child relationships and need a way to build a tree. Any help will be really appreciated. Also, in this case, is it better to have attributes or nodes for the parent-->child relationship?

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<nodes>
    <node name="Car" child="Engine"/>
    <node name="Car" child="Wheel"/>
    <node name="Engine" child="Piston"/>
    <node name="Engine" child="Carb"/>
    <node name="Carb" child="Bolt"/>
    <node name="Spare Wheel"/>
    <node name="Bolt" child="Thread"/>
    <node name="Carb" child="Foat"/>
    <node name="Truck" child="Engine"/>
    <node name="Engine" child="Bolt"/>
    <node name="Wheel" child="Hubcap"/>
</nodes>

On the Python Script, this is what i have. My brain is fried and I cannot get the logic going? please help

import xml.etree.ElementTree as ET
tree = ET.parse('rec.xml')
root = tree.getroot()
def find_node(data,search):
    #str = root.find('.//node[@child="1.2.1"]')
    for node in data.findall('.//node'):
        if node.attrib['name']==search:
            print('Child-->', node)

for nodes in root.findall('node'):
    parent = nodes.attrib.get('name')
    child = nodes.attrib.get('child')
    print (parent,'-->', child)
    find_node(root,child)

A possible output that is expected is something like this (really dont care about the sorting order, As long as all node items are represented somewhere in the tree.

Car --> Engine --> Piston
Car --> Engine --> Carb --> Float
Car --> Engine --> Carb --> Bolt --> Thread
Car --> Wheel --> Hubcaps
Truck --> Engine --> Piston
Truck --> Engine --> Carb --> Bolt --> Thread
Truck --> Loading Bin
Spare Wheel -->

Answer 1

It has been a long time since I did anything with graphs but this should be pretty close it not the most optimal approach:

x = """<?xml version="1.0"?>
<nodes>
    <node name="Car" child="Engine"></node>
    <node name="Engine" child="Piston"></node>
    <node name="Engine" child="Carb"></node>
    <node name="Car" child="Wheel"></node>
    <node name="Wheel" child="Hubcaps"></node>
    <node name="Truck" child="Engine"></node>
    <node name="Truck" child="Loading Bin"></node>
    <nested>
        <node name="Spare Wheel" child="Engine"></node>
    </nested>
    <node name="Spare Wheel" child=""></node>

</nodes>"""

from lxml import etree

xml = etree.fromstring(x)
graph = {}
nodes = set()
for x in xml.xpath("//node"):
    par, child = x.xpath(".//@name")[0], x.xpath(".//@child")[0]
    graph.setdefault(par, set())
    graph[par].add(child)
    nodes.update([child, par])


def find_all_paths(graph, start, end, path=None):
    if path is None:
        path = []
    path = path + [start]
    if start == end:
        yield path
    for node in graph.get(start, []):
        if node not in path:
            for new_path in find_all_paths(graph, node, end, path):
                yield new_path


for n in graph:
    for e in nodes:
        if n != e:
            for path in find_all_paths(graph, n, e):
                if path:
                    print("--> ".join(path))

Which with the updated input would give you:

Engine--> Carb
Engine--> Piston
Car--> Engine
Car--> Wheel
Car--> Wheel--> Hubcaps
Car--> Engine--> Carb
Car--> Engine--> Piston
Spare Wheel--> Engine
Spare Wheel--> 
Spare Wheel--> Engine--> Carb
Spare Wheel--> Engine--> Piston
Wheel--> Hubcaps
Truck--> Engine
Truck--> Engine--> Carb
Truck--> Engine--> Piston
Truck--> Loading Bin

Answer 2

Here is a pure XSLT solution -- efficiently using keys (equivalent to hash-tables) and just 23 lines -- the shortest solution so far.

This is also computationally the simplest one -- compare nesting level 1 to nesting level of 4 - 5 ...

This solution is tail-recursive meaning that any good XSLT processor optimizes it with iteration, thus avoiding the possibility of stack-overflow, as the maximum call-stack depth remains constant (1).

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output method="text"/>

 <xsl:key name="kNodeByChild" match="node" use="@child"/>
 <xsl:key name="kNodeByName" match="node" use="@name"/>

  <xsl:template match="/*">
    <xsl:apply-templates select="node[not(key('kNodeByChild', @name))]"/>
  </xsl:template>

  <xsl:template match="node[not(key('kNodeByName', @child))]">
    <xsl:param name="pParentPath"/>
    <xsl:value-of select="concat($pParentPath, @name, ' ---> ', @child, '&#xA;')"/>
  </xsl:template>

  <xsl:template match="node">
    <xsl:param name="pParentPath"/>

    <xsl:apply-templates select="key('kNodeByName', @child)">
      <xsl:with-param name="pParentPath" select="concat($pParentPath, @name, ' ---> ')"/>
    </xsl:apply-templates>
  </xsl:template>
</xsl:stylesheet>

When this transformation is applied on the provided XML document:

<nodes>
    <node name="Car" child="Engine"/>
    <node name="Car" child="Wheel"/>
    <node name="Engine" child="Piston"/>
    <node name="Engine" child="Carb"/>
    <node name="Carb" child="Bolt"/>
    <node name="Spare Wheel"/>
    <node name="Bolt" child="Thread"/>
    <node name="Carb" child="Foat"/>
    <node name="Truck" child="Engine"/>
    <node name="Engine" child="Bolt"/>
    <node name="Wheel" child="Hubcap"/>
</nodes>

The wanted, correct result is produced:

Car ---> Engine ---> Piston
Car ---> Engine ---> Carb ---> Bolt ---> Thread
Car ---> Engine ---> Carb ---> Foat
Car ---> Engine ---> Bolt ---> Thread
Car ---> Wheel ---> Hubcap
Spare Wheel ---> 
Truck ---> Engine ---> Piston
Truck ---> Engine ---> Carb ---> Bolt ---> Thread
Truck ---> Engine ---> Carb ---> Foat
Truck ---> Engine ---> Bolt ---> Thread