How to do a Breadth First Search easily with beautiful soup?

Question

I am trying to do a Breath First Search on a Beautiful soup tree. I know, we can do a Depth First Search with Beautiful soup like this :

html = """SOME HTML FILE"""

soup = BeautifulSoup(html)

for child in soup.recursiveChildGenerator():
    # do some stuff here
    pass

But I have no idea how to do a Breath First Search, anyone having any idea, suggestion ?

Thanks for your help.

Answer 1

Use the .children generator for each element to append to your breadth-first queue:

from bs4 import BeautifulSoup
import requests

html = requests.get("https://stackoverflow.com/questions/44798715/").text
soup = BeautifulSoup(html, "html5lib")
queue = [([], soup)]  # queue of (path, element) pairs
while queue:
    path, element = queue.pop(0)
    if hasattr(element, 'children'):  # check for leaf elements
        for child in element.children:
            queue.append((path + [child.name if child.name is not None else type(child)],
                          child))
    # do stuff
    print(path, repr(element.string[:50]) if element.string else type(element))

Answer 2

To browse HTML document parsed by BeautifulSoup with DFS or BFS do :

solution.py:

import bs4
from bs4 import BeautifulSoup

html = """
<div>root
     <div>child1
          <div>child4
          </div>
          <div>child5
          </div>
     </div>
     <div>child2
     </div>
     <div>child3
          <div>child6
          </div>
     </div>
</div>
"""

Append these lines to solution.py :

def visit(node):
    if isinstance(node, bs4.element.Tag):
        # be careful bs4.element subclass ...
        print(type(node), 'tag:', node.name)
    elif isinstance(node, bs4.element.NavigableString):
        # be careful bs4.CDdata and bs4.element.Comment subclass ...
        print(type(node), repr(node.string))
    else:
        print(type(node), 'UNKNOWN')

And:

def dfs(html):
    bs = BeautifulSoup(html, 'html.parser')
    # <class 'bs4.BeautifulSoup'> [document]
    visit(bs)
    for child in bs.recursiveChildGenerator():
        visit(child)


def bfs(html):
    bs = BeautifulSoup(html, 'html.parser')
    # <class 'bs4.BeautifulSoup'> [document]
    visit(bs)
    for child in recursiveChildGeneratorBfs(bs):
        visit(child)


def recursiveChildGeneratorBfs(bs):
    root = bs
    stack = [root]
    while len(stack) != 0:
        node = stack.pop(0)
        if node is not bs:
            yield node
        if hasattr(node, 'children'):
            for child in node.children:
                stack.append(child)

In ipython console:

In [1]: run solution.py

BFS:

In [2]: bfs(html)
<class 'bs4.BeautifulSoup'> tag: [document]
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> 'root\n     '
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> 'child1\n          '
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> 'child2\n     '
<class 'bs4.element.NavigableString'> 'child3\n          '
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> 'child4\n          '
<class 'bs4.element.NavigableString'> 'child5\n          '
<class 'bs4.element.NavigableString'> 'child6\n          '

DFS:

In [3]: dfs(html)
<class 'bs4.BeautifulSoup'> tag: [document]
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'root\n     '
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'child1\n          '
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'child4\n          '
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'child5\n          '
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'child2\n     '
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'child3\n          '
<class 'bs4.element.Tag'> tag: div
<class 'bs4.element.NavigableString'> 'child6\n          '
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> '\n'
<class 'bs4.element.NavigableString'> '\n'

See :

Documentation