6
\$\begingroup\$

The following code performs breadth first search on a mockup tree

# some tree
#             A            - LAYER 0
#         B       C        - LAYER 1 
#      D     E             - LAYER 2
#   F                      - LAYER 3

def get_something(x):
    if x == 'a':
        return ['b', 'c']
    if x == 'b':
        return ['d', 'e']
    if x == 'c':
        return []
    if x == 'd':
        return ['f']
    if x == 'e':
        return []
    if x == 'f':
        return []

and it is traversed by the following not so beautiful code

# I mean it works, but looking at it makes me feel sick

def recursive_get(x, loop_limit, count_limit):

    # stop condition 1: loop limit exceeded and nonzero
    # stop condition 2: count limit exceeded and nonzero
    # stop condition 3: we have reached the bottom

    current = 0
    seen_list = []
    todo_list = [x]

    while ((current < loop_limit or loop_limit == 0) and
           (len(seen_list) < count_limit or count_limit == 0) and
           todo_list):

        result = get_something(todo_list.pop(0))
        seen_list.extend(result)
        todo_list.extend(result)
        current += 1

    return seen_list 

Is there any syntactic sugar to get the second part to look more sexy? (less lines, syntactically nicer looking)?

\$\endgroup\$
4
\$\begingroup\$

get_something is not a good name for the function. Obviously, it specifies your tree by returning the child nodes of an argument node; rename to, say, get_neighbors. Also, your implementation overkills breadth-first search a bit. See what I mean:

def get_neighbors(x):
    if x == 'a':
        return ['b', 'c']
    if x == 'b':
        return ['d', 'e']
    if x == 'c':
        return []
    if x == 'd':
        return ['f']
    if x == 'e':
        return []
    if x == 'f':
        return []

    return [] # Other nodes have no neighbors.

def bfs(start):
    queue = [start]
    visited = set(start)

    while queue:
        node = queue.pop(0)

        for neighbor in get_neighbors(node):
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

    return visited

print(str(bfs('a')))

Also, note that seen_list should be rather a Python set as operating on it is more efficient than on lists.

\$\endgroup\$
  • \$\begingroup\$ I would probably call it getSiblings or getSibling because of the fact there is only 1 neighbor/sibling. But I prefer sibling, especially if you are going to use the terms parent and child for nodes uphill or downhill. \$\endgroup\$ – Malachi Mar 22 '16 at 12:14
  • 2
    \$\begingroup\$ In a tree, yes. As soon as we get to a graph, the colloquial name is neighbors = children + parents (in the case of undirected graph). \$\endgroup\$ – coderodde Mar 22 '16 at 12:17
  • \$\begingroup\$ neighbors is the correct terminology for either a node tree or a graph \$\endgroup\$ – Malachi Mar 22 '16 at 17:26
  • \$\begingroup\$ Not all operations on sets are more efficient. Adding an element should be faster with a normal list. For checks with in your statement is correct though. \$\endgroup\$ – AlexV Mar 23 '16 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.