<jupyter_start><jupyter_text>Breadth First Search (BFS) In this notebook, we will use cuGraph to compute the Breadth First Search path from a starting vertex to every other vertex in our training dataset.Notebook Credits* Original Authors: <NAME> and <NAME>* Feature available since 0.6* Last Edit: 08/16/2020RAPIDS Versions: 0.14.0    Test Hardware* GV100 32G, CUDA 10.0 IntroductionAs the name implies, BFS traverses the given graph in a breadth first manner. Starting at a specified vertex, the algorithms iteratively searches neighboring vertices.  @see https://en.wikipedia.org/wiki/Breadth-first_searchTo compute BFS in cuGraph use: __bfs(G, start)__* __G__: A cugraph.Graph object* __start_ : the starting vertex IDReturns:* __df__: cudf.DataFrame with three names columns:    * df["vertex"]:   The vertex id.    * df["distance"]: The distance to the starting vertex    * df["predecessor"]: The vertex ID of the vertex that was used to reach this vertex Some notes about vertex IDs...* The current version of cuGraph requires that vertex IDs be representable as 32-bit integers, meaning graphs currently can contain at most 2^32 unique vertex IDs. However, this limitation is being actively addressed and a version of cuGraph that accommodates more than 2^32 vertices will be available in the near future.* cuGraph will automatically renumber graphs to an internal format consisting of a contiguous series of integers starting from 0, and convert back to the original IDs when returning data to the caller. If the vertex IDs of the data are already a contiguous series of integers starting from 0, the auto-renumbering step can be skipped for faster graph creation times.  * To skip auto-renumbering, set the `renumber` boolean arg to `False` when calling the appropriate graph creation API (eg. `G.from_cudf_edgelist(gdf_r, source='src', destination='dst', renumber=False)`).  * For more advanced renumbering support, see the examples in `structure/renumber.ipynb` and `structure/renumber-2.ipynb`  Test DataWe will be using the Zachary Karate club dataset *<NAME>, An information flow model for conflict and fission in small groups, Journal ofAnthropological Research 33, 452-473 (1977).*![Karate Club](../img/zachary_black_lines.png)Our test data is small so that results can be visually verified<jupyter_code># First step is to import the needed libraries
import cugraph
import cudf
from collections import OrderedDict
# define a print path function that take the dataframe and a vertex ID

def print_path(df, id):
    
    p = cugraph.utils.get_traversed_path_list(df, id)
    print(p)<jupyter_output><empty_output><jupyter_text>Read the data using cuDF<jupyter_code># Read the data file
datafile='../data/karate-data.csv'

gdf = cudf.read_csv(datafile, names=["src", "dst"], delimiter='\t', dtype=["int32", "int32"] )
# Look at the first few data records - the output should be two colums src and dst
gdf.head()<jupyter_output><empty_output><jupyter_text>As you can see in the output, the starting vertex ID is 1.  For the BFS algorithm that is okay.   cuGraph will add an isolated vertex with an ID of zero.  It will not be reachable from the test dataset<jupyter_code># create a Graph 
G = cugraph.Graph()
G.from_cudf_edgelist(gdf, source='src', destination='dst', renumber=False)
# Call BFS on the graph starting from vertex 1
df = cugraph.bfs(G,1)
# Let's take a looks at the structure of the returned dataframe
df.dtypes
print_path(df, 22)
print_path(df, 30)<jupyter_output><empty_output><jupyter_text>Picking a starting vertexSince we can see in the graph illustraion above that vertex 17 is at the edge of the graph, let's run BFS with that as the startring vertex<jupyter_code># Call BFS on the graph starting from vertex 17
df2 = cugraph.bfs(G,17)
# Print the max distance
df2["distance"].max()<jupyter_output><empty_output><jupyter_text>Notice that max returned an unexpected value.  That is becouse the isoluated vertex, 0, is unreachable.Whenever a graph contains disjointed components, the distance to the unconnected vertices will always be max_int<jupyter_code>df2["distance"].iloc[0]
# drop all large distances 
exp="distance < 100"
df3 = df2.query(exp)
# Print the max distance
df3["distance"].max()
# Print path to vertex 30
print_path(df2, 30)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07595818815331011, 'fraction_numerical': 0.018118466898954706, 'mean_word_length': 5.26783114992722, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 24, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '124854', 'license': 'Apache-2.0', 'n_tokens_mistral': 1325, 'n_tokens_neox': 1236, 'n_words': 554, 'path': 'notebooks/traversal/BFS.ipynb', 'repo_name': 'hlinsen/cugraph', 'size': '4323'}