walking a graph: BFS - DFS#
Licence CC BY-NC-ND, Thierry Parmentelat
just a HOWTO
this notebook contains running code, there is no exercise attached
depth-first or breadth-first#
given a non-valued directed graph G, and a start vertex V, there are 2 famous algorithms to walk the graph from V
depth-first (DF) browsing, and
breadth-first (BF) browsing
intuitively, considering for example from the following tree
import graphviz
tree = graphviz.Digraph(engine='dot')
tree.edge('v', 'v1')
tree.edge('v1', 'v11')
tree.edge('v1', 'v12')
tree.edge('v11', 'v111')
tree.edge('v11', 'v112')
tree.edge('v12', 'v121')
tree.edge('v12', 'v122')
tree.edge('v', 'v2')
tree.edge('v2', 'v21')
tree.edge('v2', 'v22')
tree.edge('v21', 'v211')
tree.edge('v21', 'v212')
tree.edge('v22', 'v221')
tree.edge('v22', 'v222')
tree
---------------------------------------------------------------------------
FileNotFoundError Traceback (most recent call last)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/backend/execute.py:76, in run_check(cmd, input_lines, encoding, quiet, **kwargs)
75 kwargs['stdout'] = kwargs['stderr'] = subprocess.PIPE
---> 76 proc = _run_input_lines(cmd, input_lines, kwargs=kwargs)
77 else:
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/backend/execute.py:96, in _run_input_lines(cmd, input_lines, kwargs)
95 def _run_input_lines(cmd, input_lines, *, kwargs):
---> 96 popen = subprocess.Popen(cmd, stdin=subprocess.PIPE, **kwargs)
98 stdin_write = popen.stdin.write
File ~/.asdf/installs/python/3.13.3/lib/python3.13/subprocess.py:1039, in Popen.__init__(self, args, bufsize, executable, stdin, stdout, stderr, preexec_fn, close_fds, shell, cwd, env, universal_newlines, startupinfo, creationflags, restore_signals, start_new_session, pass_fds, user, group, extra_groups, encoding, errors, text, umask, pipesize, process_group)
1036 self.stderr = io.TextIOWrapper(self.stderr,
1037 encoding=encoding, errors=errors)
-> 1039 self._execute_child(args, executable, preexec_fn, close_fds,
1040 pass_fds, cwd, env,
1041 startupinfo, creationflags, shell,
1042 p2cread, p2cwrite,
1043 c2pread, c2pwrite,
1044 errread, errwrite,
1045 restore_signals,
1046 gid, gids, uid, umask,
1047 start_new_session, process_group)
1048 except:
1049 # Cleanup if the child failed starting.
File ~/.asdf/installs/python/3.13.3/lib/python3.13/subprocess.py:1969, in Popen._execute_child(self, args, executable, preexec_fn, close_fds, pass_fds, cwd, env, startupinfo, creationflags, shell, p2cread, p2cwrite, c2pread, c2pwrite, errread, errwrite, restore_signals, gid, gids, uid, umask, start_new_session, process_group)
1968 if err_filename is not None:
-> 1969 raise child_exception_type(errno_num, err_msg, err_filename)
1970 else:
FileNotFoundError: [Errno 2] No such file or directory: PosixPath('dot')
The above exception was the direct cause of the following exception:
ExecutableNotFound Traceback (most recent call last)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/IPython/core/formatters.py:1036, in MimeBundleFormatter.__call__(self, obj, include, exclude)
1033 method = get_real_method(obj, self.print_method)
1035 if method is not None:
-> 1036 return method(include=include, exclude=exclude)
1037 return None
1038 else:
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/jupyter_integration.py:98, in JupyterIntegration._repr_mimebundle_(self, include, exclude, **_)
96 include = set(include) if include is not None else {self._jupyter_mimetype}
97 include -= set(exclude or [])
---> 98 return {mimetype: getattr(self, method_name)()
99 for mimetype, method_name in MIME_TYPES.items()
100 if mimetype in include}
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/jupyter_integration.py:112, in JupyterIntegration._repr_image_svg_xml(self)
110 def _repr_image_svg_xml(self) -> str:
111 """Return the rendered graph as SVG string."""
--> 112 return self.pipe(format='svg', encoding=SVG_ENCODING)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/piping.py:104, in Pipe.pipe(self, format, renderer, formatter, neato_no_op, quiet, engine, encoding)
55 def pipe(self,
56 format: typing.Optional[str] = None,
57 renderer: typing.Optional[str] = None,
(...) 61 engine: typing.Optional[str] = None,
62 encoding: typing.Optional[str] = None) -> typing.Union[bytes, str]:
63 """Return the source piped through the Graphviz layout command.
64
65 Args:
(...) 102 '<?xml version='
103 """
--> 104 return self._pipe_legacy(format,
105 renderer=renderer,
106 formatter=formatter,
107 neato_no_op=neato_no_op,
108 quiet=quiet,
109 engine=engine,
110 encoding=encoding)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/_tools.py:185, in deprecate_positional_args.<locals>.decorator.<locals>.wrapper(*args, **kwargs)
177 wanted = ', '.join(f'{name}={value!r}'
178 for name, value in deprecated.items())
179 warnings.warn(f'The signature of {func_name} will be reduced'
180 f' to {supported_number} positional arg{s_}{qualification}'
181 f' {list(supported)}: pass {wanted} as keyword arg{s_}',
182 stacklevel=stacklevel,
183 category=category)
--> 185 return func(*args, **kwargs)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/piping.py:121, in Pipe._pipe_legacy(self, format, renderer, formatter, neato_no_op, quiet, engine, encoding)
112 @_tools.deprecate_positional_args(supported_number=1, ignore_arg='self')
113 def _pipe_legacy(self,
114 format: typing.Optional[str] = None,
(...) 119 engine: typing.Optional[str] = None,
120 encoding: typing.Optional[str] = None) -> typing.Union[bytes, str]:
--> 121 return self._pipe_future(format,
122 renderer=renderer,
123 formatter=formatter,
124 neato_no_op=neato_no_op,
125 quiet=quiet,
126 engine=engine,
127 encoding=encoding)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/piping.py:149, in Pipe._pipe_future(self, format, renderer, formatter, neato_no_op, quiet, engine, encoding)
146 if encoding is not None:
147 if codecs.lookup(encoding) is codecs.lookup(self.encoding):
148 # common case: both stdin and stdout need the same encoding
--> 149 return self._pipe_lines_string(*args, encoding=encoding, **kwargs)
150 try:
151 raw = self._pipe_lines(*args, input_encoding=self.encoding, **kwargs)
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/backend/piping.py:212, in pipe_lines_string(engine, format, input_lines, encoding, renderer, formatter, neato_no_op, quiet)
206 cmd = dot_command.command(engine, format,
207 renderer=renderer,
208 formatter=formatter,
209 neato_no_op=neato_no_op)
210 kwargs = {'input_lines': input_lines, 'encoding': encoding}
--> 212 proc = execute.run_check(cmd, capture_output=True, quiet=quiet, **kwargs)
213 return proc.stdout
File ~/checkouts/readthedocs.org/user_builds/flotpython-exos-python/envs/main/lib/python3.13/site-packages/graphviz/backend/execute.py:81, in run_check(cmd, input_lines, encoding, quiet, **kwargs)
79 except OSError as e:
80 if e.errno == errno.ENOENT:
---> 81 raise ExecutableNotFound(cmd) from e
82 raise
84 if not quiet and proc.stderr:
ExecutableNotFound: failed to execute PosixPath('dot'), make sure the Graphviz executables are on your systems' PATH
<graphviz.graphs.Digraph at 0x7a4f9b42e270>
these 2 algorithms would yield the nodes in the following orders
DF browsing from v would scan (the newlines are only cosmetic)
v v1 v11 v111 v112
v12 v121 v122
v2 v21 v211 v212
v22 v221 v222
BF browsing from v would scan (ditto)
v
v1 v2
v11 v12 v21 v22
v111 v112 v121 v122 v211 v212 v221 v222
objectives#
we want to write a generator that implements these 2 browsing policies from a graph and vertex.
of course, only the nodes reachable from the entry vertex will be browsed by this method
algorithms#
the 2 algorithms used to perform these scans are, interestingly, very close to one another
in both cases we need a STORAGE object, where we can store() things and retrieve() them later on
FIFO / FILO#
Let us consider the following 2 storage implementations:
Fifoimplements a first-in-first-out policyFilodoes the exact opposite and has a first-in-last-out policy
list or deque
Remember the regular list class is more optimized for a append()/pop() usage
So to work around that, we’re using a deque class, instead of a simple list; it is actually useful only in the Filo case, but this way we have a more homogeneous code
Exercise: you may wish to factorize both into a single class…
But let’s get to it:
from collections import deque
class Fifo:
def __init__(self):
self.line = deque()
def store(self, item):
self.line.append(item)
def retrieve(self):
if self.line:
return self.line.popleft()
def __len__(self):
return len(self.line)
from collections import deque
class Filo:
def __init__(self):
self.line = deque()
def store(self, item):
self.line.append(item)
def retrieve(self):
if self.line:
return self.line.pop()
def __len__(self):
return len(self.line)
# let's check it does what we want
fifo = Fifo()
for i in range(1, 4):
fifo.store(i)
while fifo:
print(f"retrieve → {fifo.retrieve()}")
retrieve → 1
retrieve → 2
retrieve → 3
# same here
filo = Filo()
for i in range(1, 4):
filo.store(i)
while filo:
print(f"retrieve → {filo.retrieve()}")
retrieve → 3
retrieve → 2
retrieve → 1
def scan(start, storage):
"""
performs a scan of all the vertices reachable from start vertex
in an order that is DF or BF, depending on the
storage policy (fifo or filo)
assumptions:
* vertices reachable from a vertex are
stored in a 'neighbours' attribute
* storage should have store() and retrieve() methods
and be testable for emptiness (if storage: ...)
* also it should be empty when entering the scan
"""
storage.store(start)
# keep track of what we've seen
scanned = set()
while storage:
current = storage.retrieve()
# skip vertices already seen
if current in scanned:
continue
yield current
scanned.add(current)
for neighbour in current.neighbours:
storage.store(neighbour)
class Vertex:
def __init__(self, name):
self.name = name
self.neighbours = set()
def __repr__(self):
return self.name
def add_neighbour(self, other):
self.neighbours.add(other)
# rebuild sample graph
def tree_vertex(name, depth):
if depth == 0:
return Vertex(name)
elif depth > 0:
result = Vertex(name)
result.add_neighbour(tree_vertex(name+'1', depth-1))
result.add_neighbour(tree_vertex(name+'2', depth-1))
return result
g = tree_vertex('v', 3)
g
v
FILO = DF - depth first#
FIFO = BF - breadth first#
for vertex in scan(g, Filo()):
print(vertex)
v
v1
v12
v121
v122
v11
v112
v111
v2
v21
v211
v212
v22
v221
v222
for vertex in scan(g, Fifo()):
print(vertex)
v
v2
v1
v22
v21
v11
v12
v222
v221
v212
v211
v111
v112
v122
v121
applications#
being a generator, we can combine it with all the itertools and the like
import itertools
for example, if we need to print every other vertex in a DF scan
df_scan = scan(g, Filo())
for v in itertools.islice(df_scan, 0, None, 2):
print(v)
v
v12
v122
v112
v2
v211
v22
v222
# notice that df_scan is now exhausted !
for v in itertools.islice(df_scan, 0, None, 2):
print(v)
or skip the first 3..
# but we can easily create a new one !
df_scan = scan(g, Filo())
for v in itertools.islice(df_scan, 3, None):
print(v)
v121
v122
v11
v112
v111
v2
v21
v211
v212
v22
v221
v222