BFS Spanning Tree#
This notebook illustrates how to create a spanning tree of a graph with vertex labels consistent with breadth-first search traversal.
%%capture
%run receptor_tools.ipynb
P = graphs.PetersenGraph()
P.show(edge_labels=False)
(BFSVertexList,BFSTree) = P.lex_BFS(tree=True,initial_vertex=0)
BFSTree.show(edge_labels=False)
show(BFSVertexList)
A module that was compiled using NumPy 1.x cannot be run in
NumPy 2.2.6 as it may crash. To support both 1.x and 2.x
versions of NumPy, modules must be compiled with NumPy 2.0.
Some module may need to rebuild instead e.g. with 'pybind11>=2.12'.
If you are a user of the module, the easiest solution will be to
downgrade to 'numpy<2' or try to upgrade the affected module.
We expect that some modules will need time to support NumPy 2.
Traceback (most recent call last): File "/usr/lib/python3.10/runpy.py", line 196, in _run_module_as_main
return _run_code(code, main_globals, None,
File "/usr/lib/python3.10/runpy.py", line 86, in _run_code
exec(code, run_globals)
File "/usr/lib/python3/dist-packages/sage/repl/ipython_kernel/__main__.py", line 3, in <module>
IPKernelApp.launch_instance(kernel_class=SageKernel)
File "/usr/lib/python3/dist-packages/traitlets/config/application.py", line 846, in launch_instance
app.start()
File "/usr/lib/python3/dist-packages/ipykernel/kernelapp.py", line 677, in start
self.io_loop.start()
File "/usr/lib/python3/dist-packages/tornado/platform/asyncio.py", line 199, in start
self.asyncio_loop.run_forever()
File "/usr/lib/python3.10/asyncio/base_events.py", line 603, in run_forever
self._run_once()
File "/usr/lib/python3.10/asyncio/base_events.py", line 1909, in _run_once
handle._run()
File "/usr/lib/python3.10/asyncio/events.py", line 80, in _run
self._context.run(self._callback, *self._args)
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 461, in dispatch_queue
await self.process_one()
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 450, in process_one
await dispatch(*args)
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 357, in dispatch_shell
await result
File "/usr/lib/python3/dist-packages/ipykernel/kernelbase.py", line 652, in execute_request
reply_content = await reply_content
File "/usr/lib/python3/dist-packages/ipykernel/ipkernel.py", line 353, in do_execute
res = shell.run_cell(code, store_history=store_history, silent=silent)
File "/usr/lib/python3/dist-packages/ipykernel/zmqshell.py", line 532, in run_cell
return super().run_cell(*args, **kwargs)
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 2914, in run_cell
result = self._run_cell(
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 2960, in _run_cell
return runner(coro)
File "/usr/lib/python3/dist-packages/IPython/core/async_helpers.py", line 78, in _pseudo_sync_runner
coro.send(None)
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3185, in run_cell_async
has_raised = await self.run_ast_nodes(code_ast.body, cell_name,
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3377, in run_ast_nodes
if (await self.run_code(code, result, async_=asy)):
File "/usr/lib/python3/dist-packages/IPython/core/interactiveshell.py", line 3457, in run_code
exec(code_obj, self.user_global_ns, self.user_ns)
File "/tmp/ipykernel_10975/791223156.py", line 2, in <module>
P.show(edge_labels=False)
File "/usr/lib/python3/dist-packages/sage/graphs/generic_graph.py", line 20195, in show
return self.graphplot(**plot_kwds).show(**kwds)
File "/usr/lib/python3/dist-packages/sage/graphs/graph_plot.py", line 1026, in show
self.plot().show(**kwds)
File "/usr/lib/python3/dist-packages/sage/misc/decorators.py", line 410, in wrapper
return func(*args, **kwds)
File "/usr/lib/python3/dist-packages/sage/plot/graphics.py", line 2133, in show
dm.display_immediately(self, **kwds)
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 851, in display_immediately
plain_text, rich_output = self._rich_output_formatter(obj, rich_repr_kwds)
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 643, in _rich_output_formatter
rich_output = self._call_rich_repr(obj, rich_repr_kwds)
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 601, in _call_rich_repr
return obj._rich_repr_(self, **rich_repr_kwds)
File "/usr/lib/python3/dist-packages/sage/plot/graphics.py", line 1000, in _rich_repr_
return display_manager.graphics_from_save(
File "/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py", line 731, in graphics_from_save
save_function(filename, **kwds)
File "/usr/lib/python3/dist-packages/sage/misc/decorators.py", line 410, in wrapper
return func(*args, **kwds)
File "/usr/lib/python3/dist-packages/sage/plot/graphics.py", line 3296, in save
from matplotlib import rcParams
File "/usr/lib/python3/dist-packages/matplotlib/__init__.py", line 109, in <module>
from . import _api, _version, cbook, docstring, rcsetup
File "/usr/lib/python3/dist-packages/matplotlib/rcsetup.py", line 27, in <module>
from matplotlib.colors import Colormap, is_color_like
File "/usr/lib/python3/dist-packages/matplotlib/colors.py", line 56, in <module>
from matplotlib import _api, cbook, scale
File "/usr/lib/python3/dist-packages/matplotlib/scale.py", line 23, in <module>
from matplotlib.ticker import (
File "/usr/lib/python3/dist-packages/matplotlib/ticker.py", line 136, in <module>
from matplotlib import transforms as mtransforms
File "/usr/lib/python3/dist-packages/matplotlib/transforms.py", line 46, in <module>
from matplotlib._path import (
---------------------------------------------------------------------------
AttributeError Traceback (most recent call last)
AttributeError: _ARRAY_API not found
---------------------------------------------------------------------------
ImportError Traceback (most recent call last)
/tmp/ipykernel_10975/791223156.py in <module>
1 P = graphs.PetersenGraph()
----> 2 P.show(edge_labels=False)
3 (BFSVertexList,BFSTree) = P.lex_BFS(tree=True,initial_vertex=Integer(0))
4 BFSTree.show(edge_labels=False)
5 show(BFSVertexList)
/usr/lib/python3/dist-packages/sage/graphs/generic_graph.py in show(self, method, **kwds)
20193 plot_kwds = {k: kwds.pop(k) for k in graphplot_options if k in kwds}
20194
> 20195 return self.graphplot(**plot_kwds).show(**kwds)
20196
20197 def plot3d(self, bgcolor=(1,1,1),
/usr/lib/python3/dist-packages/sage/graphs/graph_plot.py in show(self, **kwds)
1024 kwds[k] = value
1025
-> 1026 self.plot().show(**kwds)
1027
1028 def plot(self, **kwds):
/usr/lib/python3/dist-packages/sage/misc/decorators.py in wrapper(*args, **kwds)
408 kwds[self.name + "options"] = suboptions
409
--> 410 return func(*args, **kwds)
411
412 # Add the options specified by @options to the signature of the wrapped
/usr/lib/python3/dist-packages/sage/plot/graphics.py in show(self, **kwds)
2131 from sage.repl.rich_output import get_display_manager
2132 dm = get_display_manager()
-> 2133 dm.display_immediately(self, **kwds)
2134
2135 def xmin(self, xmin=None):
/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py in display_immediately(self, obj, **rich_repr_kwds)
849 1/2
850 """
--> 851 plain_text, rich_output = self._rich_output_formatter(obj, rich_repr_kwds)
852 self._backend.display_immediately(plain_text, rich_output)
853
/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py in _rich_output_formatter(self, obj, rich_repr_kwds)
641 has_rich_repr = isinstance(obj, SageObject) and hasattr(obj, '_rich_repr_')
642 if has_rich_repr:
--> 643 rich_output = self._call_rich_repr(obj, rich_repr_kwds)
644 if isinstance(rich_output, OutputPlainText):
645 plain_text = rich_output
/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py in _call_rich_repr(self, obj, rich_repr_kwds)
599 if rich_repr_kwds:
600 # do not ignore errors from invalid options
--> 601 return obj._rich_repr_(self, **rich_repr_kwds)
602 try:
603 return obj._rich_repr_(self)
/usr/lib/python3/dist-packages/sage/plot/graphics.py in _rich_repr_(self, display_manager, **kwds)
998 for file_ext, output_container in preferred:
999 if output_container in display_manager.supported_output():
-> 1000 return display_manager.graphics_from_save(
1001 self.save, kwds, file_ext, output_container)
1002
/usr/lib/python3/dist-packages/sage/repl/rich_output/display_manager.py in graphics_from_save(self, save_function, save_kwds, file_extension, output_container, figsize, dpi)
729 if dpi is not None:
730 kwds['dpi'] = dpi
--> 731 save_function(filename, **kwds)
732 from sage.repl.rich_output.buffer import OutputBuffer
733 buf = OutputBuffer.from_file(filename)
/usr/lib/python3/dist-packages/sage/misc/decorators.py in wrapper(*args, **kwds)
408 kwds[self.name + "options"] = suboptions
409
--> 410 return func(*args, **kwds)
411
412 # Add the options specified by @options to the signature of the wrapped
/usr/lib/python3/dist-packages/sage/plot/graphics.py in save(self, filename, **kwds)
3294 "', '".join(ALLOWED_EXTENSIONS) + "'!")
3295 else:
-> 3296 from matplotlib import rcParams
3297 rc_backup = (rcParams['ps.useafm'], rcParams['pdf.use14corefonts'],
3298 rcParams['text.usetex']) # save the rcParams
/usr/lib/python3/dist-packages/matplotlib/__init__.py in <module>
107 # cbook must import matplotlib only within function
108 # definitions, so it is safe to import from it here.
--> 109 from . import _api, _version, cbook, docstring, rcsetup
110 from matplotlib.cbook import MatplotlibDeprecationWarning, sanitize_sequence
111 from matplotlib.cbook import mplDeprecation # deprecated
/usr/lib/python3/dist-packages/matplotlib/rcsetup.py in <module>
25 from matplotlib import _api, cbook
26 from matplotlib.cbook import ls_mapper
---> 27 from matplotlib.colors import Colormap, is_color_like
28 from matplotlib.fontconfig_pattern import parse_fontconfig_pattern
29 from matplotlib._enums import JoinStyle, CapStyle
/usr/lib/python3/dist-packages/matplotlib/colors.py in <module>
54 import matplotlib as mpl
55 import numpy as np
---> 56 from matplotlib import _api, cbook, scale
57 from ._color_data import BASE_COLORS, TABLEAU_COLORS, CSS4_COLORS, XKCD_COLORS
58
/usr/lib/python3/dist-packages/matplotlib/scale.py in <module>
21 import matplotlib as mpl
22 from matplotlib import _api, docstring
---> 23 from matplotlib.ticker import (
24 NullFormatter, ScalarFormatter, LogFormatterSciNotation, LogitFormatter,
25 NullLocator, LogLocator, AutoLocator, AutoMinorLocator,
/usr/lib/python3/dist-packages/matplotlib/ticker.py in <module>
134 import matplotlib as mpl
135 from matplotlib import _api, cbook
--> 136 from matplotlib import transforms as mtransforms
137
138 _log = logging.getLogger(__name__)
/usr/lib/python3/dist-packages/matplotlib/transforms.py in <module>
44
45 from matplotlib import _api
---> 46 from matplotlib._path import (
47 affine_transform, count_bboxes_overlapping_bbox, update_path_extents)
48 from .path import Path
ImportError: numpy.core.multiarray failed to import
d = dict((v,i) for i, v in enumerate(BFSVertexList))
print(d)
{0: 0, 1: 1, 4: 2, 5: 3, 2: 4, 6: 5, 3: 6, 9: 7, 7: 8, 8: 9}
P2 = P.copy()
P2.relabel(d)
P2 = add_edge_monomials(P2)
P2.show(figsize=6,edge_labels=True)
T2=BFSTree.copy()
T2.relabel(d)
T2 = add_edge_monomials(T2,short_name=True)
T2.show(figsize=6,edge_labels=True)
