.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "../../docs/source/_gallery/bfs.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code. .. rst-class:: sphx-glr-example-title .. _sphx_glr_.._.._docs_source__gallery_bfs.py: .. _sphx_glr__gallery_bfs.py: Breadth-First Search (BFS) Example ===================================================================================== .. contents:: Table of Contents :local: :depth: 2 :backlinks: top This example demonstrates the Breadth-First Search (BFS) algorithm on a simple :class:`pygraphs.Graph`. The BFS algorithm explores the vertices of a graph in layers, starting from a given source vertex and visiting all its neighbors before moving on to the next layer of vertices. .. GENERATED FROM PYTHON SOURCE LINES 20-40 Define the graphs -------------------------------------------------------------------------------- Create a simple disconnected graph of 7 vertices .. figure:: /_static/graph.png :align: center :width: 50% Disconnected graph with 7 vertices for BFS example. Distance from vertex 0 to vertex 4 is 3 (0 -> 2 -> 3 -> 4). And a directed graph of 7 vertices .. figure:: /_static/graph_directed.png :align: center :width: 50% Directed graph with 7 vertices for BFS example. Distance from vertex 2 to vertex 0 is 2 (2 -> 1 -> 0). .. GENERATED FROM PYTHON SOURCE LINES 40-51 .. code-block:: Python from pygraphs import Graph graph = [[1, 2], [0, 2], [0, 1, 3], [2, 4], [3], [6], [5]] undirected_graph = Graph.from_adjacency(graph) print(undirected_graph.is_directed()) # False graph = [[1, 2], [0, 2], [1, 3], [4], [3], [6], []] directed_graph = Graph.from_adjacency(graph) print(directed_graph.is_directed()) # True .. rst-class:: sphx-glr-script-out .. code-block:: none False True .. GENERATED FROM PYTHON SOURCE LINES 52-61 BFS Examples -------------------------------------------------------------------------------- BFS Distances ^^^^^^^^^^^^^ The BFS distance from a source vertex to all other vertices can be computed using the :func:`pygraphs.bfs_distances` method. The distance is defined as the number of edges in the shortest path from the source vertex to each vertex. If a vertex is unreachable from the source, its distance is -1. .. GENERATED FROM PYTHON SOURCE LINES 61-72 .. code-block:: Python from pygraphs import bfs_distances start_vertex = 0 distances = bfs_distances(undirected_graph, start_vertex) print(distances) # [0, 1, 1, 2, 3, -1, -1] start_vertex = 2 distances = bfs_distances(directed_graph, start_vertex) print(distances) # [2, 1, 0, 1, 2, -1, -1] .. rst-class:: sphx-glr-script-out .. code-block:: none [0, 1, 1, 2, 3, -1, -1] [2, 1, 0, 1, 2, -1, -1] .. GENERATED FROM PYTHON SOURCE LINES 73-77 BFS K annulus, disk, ring ^^^^^^^^^^^^^^^^^^^^^^^^^^^ The BFS k-annulus, k-disk, and k-ring of a source vertex can be computed using the :func:`pygraphs.bfs_k_annulus`, :func:`pygraphs.bfs_k_disk`, and :func:`pygraphs.bfs_k_ring` methods, respectively. The k-annulus includes all vertices that are at a distance greater than or equal to the inner distance and less than or equal to the outer distance from the source vertex. .. GENERATED FROM PYTHON SOURCE LINES 77-96 .. code-block:: Python from pygraphs import bfs_k_annulus start_vertex = 0 inner_distance = 1 outer_distance = 2 neighborhood = bfs_k_annulus( undirected_graph, start_vertex, inner_distance, outer_distance ) print(neighborhood) # [1, 2, 3] start_vertex = 2 inner_distance = 1 outer_distance = 1 neighborhood = bfs_k_annulus( directed_graph, start_vertex, inner_distance, outer_distance ) print(neighborhood) # [1, 3] .. rst-class:: sphx-glr-script-out .. code-block:: none [1, 2, 3] [1, 3] .. GENERATED FROM PYTHON SOURCE LINES 97-101 BFS Shortest Path ^^^^^^^^^^^^^^^^^^^ The BFS shortest path from a source vertex to a target vertex can be computed using the :func:`pygraphs.bfs_shortest_path` method. The shortest path is defined as the path with the fewest edges from the source vertex to the target vertex. If the target vertex is unreachable from the source, the method returns an empty list. .. GENERATED FROM PYTHON SOURCE LINES 101-115 .. code-block:: Python from pygraphs import bfs_shortest_path start_vertex = 0 end_vertex = 4 shortest_path = bfs_shortest_path(undirected_graph, start_vertex, end_vertex) print(shortest_path) # [0, 2, 3, 4] start_vertex = 2 end_vertex = 0 shortest_path = bfs_shortest_path(directed_graph, start_vertex, end_vertex) print(shortest_path) # [2, 1, 0] .. rst-class:: sphx-glr-script-out .. code-block:: none [0, 2, 3, 4] [2, 1, 0] .. GENERATED FROM PYTHON SOURCE LINES 116-122 BFS Shortest Distance ^^^^^^^^^^^^^^^^^^^^^ The BFS shortest distance between a source vertex and a target vertex can be computed using the :func:`pygraphs.bfs_shortest_distance` method. The shortest distance is defined as the number of edges in the shortest path between the source and the target. If the target is unreachable from the source, the method returns -1. .. GENERATED FROM PYTHON SOURCE LINES 122-136 .. code-block:: Python from pygraphs import bfs_shortest_distance start_vertex = 0 end_vertex = 4 distance = bfs_shortest_distance(undirected_graph, start_vertex, end_vertex) print(distance) # 3 start_vertex = 2 end_vertex = 0 distance = bfs_shortest_distance(directed_graph, start_vertex, end_vertex) print(distance) # 2 .. rst-class:: sphx-glr-script-out .. code-block:: none 3 2 .. GENERATED FROM PYTHON SOURCE LINES 137-141 BFS Adjacency Matrix ^^^^^^^^^^^^^^^^^^^^^^^ The BFS adjacency matrix of a graph can be computed using the :func:`pygraphs.bfs_matrix` method. The BFS adjacency matrix is a square matrix where the entry at row i and column j represents the distance from vertex i to vertex j. If vertex j is unreachable from vertex i, the entry is -1. .. GENERATED FROM PYTHON SOURCE LINES 141-173 .. code-block:: Python from pygraphs import bfs_matrix adjacency_matrix = bfs_matrix(undirected_graph) print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):") print(adjacency_matrix) # Expected output: # adjacency_matrix (shape=(7x7)): # [[ 0 1 1 2 3 -1 -1] # [ 1 0 1 2 3 -1 -1] # [ 1 1 0 1 2 -1 -1] # [ 2 2 1 0 1 -1 -1] # [ 3 3 2 1 0 -1 -1] # [-1 -1 -1 -1 -1 0 1] # [-1 -1 -1 -1 -1 1 0]] adjacency_matrix = bfs_matrix(directed_graph) print(f"adjacency_matrix (shape={len(adjacency_matrix)}x{len(adjacency_matrix[0])}):") print(adjacency_matrix) # Expected output: # adjacency_matrix (shape=(7x7)): # [[ 0 1 1 2 3 -1 -1] # [ 1 0 1 2 3 -1 -1] # [ 2 1 0 1 2 -1 -1] # [ 3 2 1 0 1 -1 -1] # [ 4 3 2 1 0 -1 -1] # [-1 -1 -1 -1 -1 0 1] # [-1 -1 -1 -1 -1 -1 0]] .. rst-class:: sphx-glr-script-out .. code-block:: none adjacency_matrix (shape=7x7): [[0, 1, 1, 2, 3, -1, -1], [1, 0, 1, 2, 3, -1, -1], [1, 1, 0, 1, 2, -1, -1], [2, 2, 1, 0, 1, -1, -1], [3, 3, 2, 1, 0, -1, -1], [-1, -1, -1, -1, -1, 0, 1], [-1, -1, -1, -1, -1, 1, 0]] adjacency_matrix (shape=7x7): [[0, 1, 1, 2, 3, -1, -1], [1, 0, 1, 2, 3, -1, -1], [2, 1, 0, 1, 2, -1, -1], [-1, -1, -1, 0, 1, -1, -1], [-1, -1, -1, 1, 0, -1, -1], [-1, -1, -1, -1, -1, 0, 1], [-1, -1, -1, -1, -1, -1, 0]] .. GENERATED FROM PYTHON SOURCE LINES 174-179 BFS Reachability ^^^^^^^^^^^^^^^^ The reachability between two vertices can be checked using the :func:`pygraphs.bfs_is_reachable` method. It returns True if there exists a path from the source vertex to the target vertex in the graph, and False otherwise. .. GENERATED FROM PYTHON SOURCE LINES 179-193 .. code-block:: Python from pygraphs import bfs_is_reachable start_vertex = 0 end_vertex = 4 is_reachable = bfs_is_reachable(undirected_graph, start_vertex, end_vertex) print(is_reachable) # True start_vertex = 6 end_vertex = 5 is_reachable = bfs_is_reachable(directed_graph, start_vertex, end_vertex) print(is_reachable) # False .. rst-class:: sphx-glr-script-out .. code-block:: none True False .. GENERATED FROM PYTHON SOURCE LINES 194-198 BFS Reachable Vertices ^^^^^^^^^^^^^^^^^^^^^^^^^^^ The BFS reachable vertices from a source vertex can be computed using the :func:`pygraphs.bfs_reachable` method. The reachable vertices are defined as the set of vertices that can be reached from the source vertex. .. GENERATED FROM PYTHON SOURCE LINES 198-217 .. code-block:: Python from pygraphs import bfs_reachable start_vertex = 0 max_distance = None reachable_vertices = bfs_reachable( undirected_graph, start_vertex, max_distance=max_distance ) print(reachable_vertices) # [0, 1, 2, 3, 4] start_vertex = 6 max_distance = None reachable_vertices = bfs_reachable( directed_graph, start_vertex, max_distance=max_distance ) print(reachable_vertices) # [6] .. rst-class:: sphx-glr-script-out .. code-block:: none [0, 1, 2, 3, 4] [6] .. GENERATED FROM PYTHON SOURCE LINES 218-230 BFS Connected Components ^^^^^^^^^^^^^^^^^^^^^^^^^^^ The BFS connected components of a graph can be computed using the :func:`pygraphs.bfs_components` method. The connected components are defined as the sets of vertices that are reachable in at least one direction (i.e., there is a path from vertex A to vertex B **OR** from vertex B to vertex A). .. note:: Use ``strongly_connected=True`` to compute the strongly connected components of a directed graph, where both vertices A and B must be reachable from each other (i.e., there is a path from vertex A to vertex B **AND** from vertex B to vertex A). .. GENERATED FROM PYTHON SOURCE LINES 230-241 .. code-block:: Python from pygraphs import bfs_components components = bfs_components(undirected_graph) print(components) # [[0, 1, 2, 3, 4], [5, 6]] components = bfs_components(directed_graph, strongly_connected=False) print(components) # [[0, 1, 2, 3, 4], [5, 6]] components = bfs_components(directed_graph, strongly_connected=True) print(components) # [[0, 1, 2], [3, 4], [5], [6]] .. rst-class:: sphx-glr-script-out .. code-block:: none [[0, 1, 2, 3, 4], [5, 6]] [[0, 1, 2, 3, 4], [5, 6]] [[4, 3], [2, 1, 0], [6], [5]] .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.003 seconds) .. _sphx_glr_download_.._.._docs_source__gallery_bfs.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: bfs.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: bfs.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: bfs.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_