Return to Answer

Added BFS alternative

Source Link

edited Apr 3, 2017 at 17:05

Alternative: Breadth First Search

As an alternative you could also use a BFS algorithm -- the first part is the same:

def bom_build_bfs(o,p):
    # Create a hash keyed by parts, providing their sub parts as list
    d = dict()
    for [part, subpart] in parts_h:
        if part in d:
            d[part].append(subpart)
        else:
            d[part] = [subpart]

    # add start elements to bom, which later will be removed
    bom = [[serial, None, part, part] for [serial, part] in order]
    i = 0
    # treat it as a queue, adding to it while looping
    while i < len(bom):
        [serial, parent, part, path] = bom[i]
        i += 1
        if part in d:
            for subpart in d[part]:
                bom.append([serial, part, subpart, path + '/' + subpart])
        elif i < len(order): # when there are no sub parts
            bom.append([serial, part, None, path])

    # return the part without the starter elements
    return bom[len(order):]

In my limited tests this ran slower than the DFS solution, but it might depend on how the input data is distributed and how deeply nested it is.

Alternative: Breadth First Search

As an alternative you could also use a BFS algorithm -- the first part is the same:

def bom_build_bfs(o,p):
    # Create a hash keyed by parts, providing their sub parts as list
    d = dict()
    for [part, subpart] in parts_h:
        if part in d:
            d[part].append(subpart)
        else:
            d[part] = [subpart]

    # add start elements to bom, which later will be removed
    bom = [[serial, None, part, part] for [serial, part] in order]
    i = 0
    # treat it as a queue, adding to it while looping
    while i < len(bom):
        [serial, parent, part, path] = bom[i]
        i += 1
        if part in d:
            for subpart in d[part]:
                bom.append([serial, part, subpart, path + '/' + subpart])
        elif i < len(order): # when there are no sub parts
            bom.append([serial, part, None, path])

    # return the part without the starter elements
    return bom[len(order):]

In my limited tests this ran slower than the DFS solution, but it might depend on how the input data is distributed and how deeply nested it is.

Source Link

created Mar 31, 2017 at 21:41

trincot

Some time is lost by having to traverse the p list for each product. For large data, you could preprocess the p list, and create a dict that is keyed by the part, and which provides a list of sub parts for it. Then the lookup for a given product will be faster.

Secondly, the second part of the code will find deeper nested parts, but will fail to find them all when the nesting is deeper.

Here is suggested improvement:

def bom_build(o,p):
    # Create a hash keyed by parts, providing their sub parts as list
    d = dict()
    for [part, subpart] in parts_h:
        if part in d:
            d[part].append(subpart)
        else:
            d[part] = [subpart]

    bom = []
    
    def recurse(bom, d, serial, part, path, required):
        if part in d:
            for subpart in d[part]:
                nextpath = path + '/' + subpart
                bom.append([serial, part, subpart, nextpath])
                recurse(bom, d, serial, subpart, nextpath, False)
        elif required: # when there are no sub parts
            bom.append([serial, part, None, path])
                
    for [serial, part] in order:
        recurse(bom, d, serial, part, part, True)

    return bom

See it run on repl.it