<jupyter_start><jupyter_text>Spanning Tree with Message Passing<jupyter_code>%matplotlib inline
import networkx as nx<jupyter_output><empty_output><jupyter_text>Spanning tree of an undirected graph is a tree which includes all the vertices of the graph with a minimum number of possible edges.One application of spanning trees is in the [Spanning Tree Protocol (STP)](https://www.wikiwand.com/en/Spanning_Tree_Protocol), where we want to avoid loops in the topology.We want to construct an algorithm that relies on messages passed between nodes and not the knowledge of the overall topology.  Identifying the "root" The idea is to minimize the distance from each node to the "root". The choice of root does not matter. For simplicity we'll designate the node with the lowest ID as the root.This suggests that initially each node can think of itself as the root node and then send the state of its knowledge to neighbors.  Avoiding loops  3 node [clique](https://www.wikiwand.com/en/Clique)<jupyter_code>clique = nx.Graph()
clique.add_nodes_from([1, 2, 3])
clique.add_edges_from([(1, 2), (1, 3), (3, 2)])

nx.draw_networkx(clique)<jupyter_output><empty_output><jupyter_text>In this case we should remove the link between 2 and 3. In that case 3 and 2 have the minimum distance of 1 to the root node 1.  4 node [cycle](https://www.wikiwand.com/en/Cycle_graph)<jupyter_code>cycle = nx.Graph()
cycle.add_nodes_from([1, 2, 3, 4])
cycle.add_edges_from([(1, 2), (1, 3), (3, 4), (2, 4)])

nx.draw_networkx(cycle)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09256844850065189, 'fraction_numerical': 0.018904823989569754, 'mean_word_length': 5.504237288135593, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 13, 'https://': 3, 'lorem ipsum': 0, 'www.': 3, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '519081', 'license': 'MIT', 'n_tokens_mistral': 503, 'n_tokens_neox': 477, 'n_words': 193, 'path': 'algorithms/Spanning-Tree-with-Message-Passing.ipynb', 'repo_name': 'ashishpatel26/learning', 'size': '1534'}