<jupyter_start><jupyter_text>High performance graph algorithmsA number of high performance algorithms have been implemented in Ensmallen, a considerable portion of which is an implementation of algorithms described in the literature by [<NAME>](https://davidbader.net/), who we thank for his contribution to the field of graph algorithms.See below for the algorithms available in Ensmallen.Note that all of these algorithms are highly parallel implementations, and these benchmarks are being run on COLAB which typically provides virtual machines with a very small number of cores: on a machine with a reasonable number of cores they will execute much faster.To install the GraPE library run:```bashpip install grape```To install exclusively the Ensmallen module, which may be useful when the TensorFlow dependency causes problems, do run:```bashpip install ensmallen```<jupyter_code>! pip install -q ensmallen<jupyter_output><empty_output><jupyter_text>Retrieving a graph to run the sampling onIn this tutorial we will run samples on one of the graph from the ones available from the automatic graph retrieval of Ensmallen, namely the [Homo Sapiens graph from STRING](https://string-db.org/cgi/organisms). If you want to load a graph from an edge list, just follow the examples provided from the [add reference to tutorial].<jupyter_code>from ensmallen.datasets.string import HomoSapiens<jupyter_output><empty_output><jupyter_text>Retrieving and loading the graph<jupyter_code>graph = HomoSapiens()<jupyter_output><empty_output><jupyter_text>We compute the graph report:<jupyter_code>graph<jupyter_output><empty_output><jupyter_text>Enable the speedups<jupyter_code>graph.enable()<jupyter_output><empty_output><jupyter_text>Random Spanning arborescenceThe spanning arborescence algorithm computes a set of edges, an [Arborescence](https://en.wikipedia.org/wiki/Arborescence_(graph_theory)), that is spanning, i.e cover all the nodes in the graph.This is an implementation of [A fast, parallel spanning tree algorithm for symmetric multiprocessors(SMPs)](https://davidbader.net/publication/2005-bc/2005-bc.pdf).<jupyter_code>%%time
spanning_arborescence_edges = graph.spanning_arborescence()<jupyter_output>CPU times: user 132 ms, sys: 211 µs, total: 132 ms
Wall time: 73.5 ms<jupyter_text>Connected componentsThe [connected components](https://en.wikipedia.org/wiki/Component_(graph_theory)) of a graph are the set of nodes connected one another by edges.<jupyter_code>%%time
(
    connected_component_ids,
    number_of_connected_components,
    minimum_component_size,
    maximum_component_size
) = graph.connected_components()<jupyter_output>CPU times: user 240 ms, sys: 123 µs, total: 240 ms
Wall time: 127 ms<jupyter_text>DiameterThe following is an implementation of [On computing the diameter of real-world undirected graphs](https://who.rocq.inria.fr/Laurent.Viennot/road/papers/ifub.pdf).<jupyter_code>%%time
diameter = graph.get_diameter(ignore_infinity=True)<jupyter_output>CPU times: user 7.61 s, sys: 16.2 ms, total: 7.63 s
Wall time: 3.99 s<jupyter_text>Note that most properties that boil down to a single value once computed are stored in a cache structure, so recomputing the diameter once it is done takes a significant smaller time.<jupyter_code>%%time
diameter = graph.get_diameter(ignore_infinity=True)<jupyter_output>CPU times: user 13 µs, sys: 1 µs, total: 14 µs
Wall time: 16.5 µs<jupyter_text>Clustering coefficient and trianglesThis is an implementation of [Faster Clustering Coefficient Using Vertex Covers](https://davidbader.net/publication/2013-g-ba/2013-g-ba.pdf), proving the average clustering coefficient, the total number of triangles and the number of triangles per node.<jupyter_code>%%time
graph.get_number_of_triangles()
%%time
graph.get_number_of_triangles_per_node()
%%time
graph.get_average_clustering_coefficient()
%%time
graph.get_clustering_coefficient_per_node()<jupyter_output>CPU times: user 6min 26s, sys: 1.1 s, total: 6min 27s
Wall time: 3min 16s
{'fraction_non_alphanumeric': 0.07776944236059015, 'fraction_numerical': 0.017754438609652413, 'mean_word_length': 6.751937984496124, 'pattern_counts': {'":': 0, '<': 37, '<?xml version=': 0, '>': 37, 'https://': 7, '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': '10', 'dir': 'jupyter-structured-clean-dedup', 'id': '12261', 'license': 'MIT', 'n_tokens_mistral': 1283, 'n_tokens_neox': 1160, 'n_words': 408, 'path': 'tutorials/High_performance_graph_algorithms.ipynb', 'repo_name': 'caufieldjh/grape', 'size': '4004'}