<jupyter_start><jupyter_text>Introduction to data science and programmingClass 26: Graph algorithmsIT University of Copenhagen, Fall 2019Instructor: <NAME>  Setup<jupyter_code>from Graph import *
G = Graph()

edge_list = [
    ('A', 'B'),
    ('A', 'D'),
    ('B', 'C'),
    ('B', 'D'),
    ('B', 'E'),
    ('C', 'E'),
    ('D', 'E'),
    ('D', 'F'),
    ('E', 'F'),
    ('E', 'G'),
    ('F', 'G')]

G.add_edges_from(edge_list)

G._edges['A']['B']['weight'] = 7
G._edges['A']['D']['weight'] = 5
G._edges['B']['C']['weight'] = 8
G._edges['B']['D']['weight'] = 9
G._edges['B']['E']['weight'] = 7
G._edges['C']['E']['weight'] = 5
G._edges['D']['E']['weight'] = 15
G._edges['D']['F']['weight'] = 6
G._edges['E']['F']['weight'] = 8
G._edges['E']['G']['weight'] = 9
G._edges['F']['G']['weight'] = 11

G.weights()<jupyter_output><empty_output><jupyter_text>Prim's algorithm<jupyter_code>@add_method(Graph)
def mst_prim(self):
    """ Calculates the minimum spanning tree using Prim's algorithm.
    Focus is to be human-readable; the code was not optimized for efficiency.
    """
    
    demo = True # Set this to true to print how the algorithm works step by step
    
    # initialize the MST nodes, links, and weights
    MST_nodes = set()
    MST_links = {} # Will look like this: {('A', 'B'): 5}

    # select an arbitrary node to begin with
    MST_nodes.add(list(self._nodes.keys())[0])
    
    while len(MST_nodes) != self.number_of_nodes():
        frontierlinks = set() # This is the frontier: All link candidates to grow the MST
        
        # for each node m in MST_nodes, consider the link (m, k) if
        # k is not already in MST_links
        for m in MST_nodes:
            for k in self._nodes.keys():
                if k not in MST_nodes and (m, k) in self.weights(): 
                    frontierlinks.add((m, k))
        
        # find the candidate link with the smallest weight
        newlink = sorted(frontierlinks, key=lambda e:self.weights()[e[0], e[1]])[0]
        # add this link and its weight to MST_links
        MST_links[newlink] = self.weights()[newlink[0], newlink[1]]
        # add the new node to MST_nodes
        MST_nodes.add(newlink[1])
        if demo: 
            print("Frontier:",frontierlinks)
            print("Adding the link",newlink,":",self.weights()[newlink[0], newlink[1]])
            print("MST progress:",MST_links, '\n')
        #if demo: print(newlink, self.weights()[newlink[0], newlink[1]])
        
    MST = Graph()
    MST.add_nodes_from(MST_nodes)
    MST.add_edges_from(MST_links.keys())
    for link, w in MST_links.items(): # update weights
        MST._edges[link[0]][link[1]]['weight'] = w
    
    return MST
MST = G.mst_prim()
MST.weights()<jupyter_output><empty_output><jupyter_text>Kruskal's algorithm<jupyter_code>@add_method(Graph)
class _UF:
    """Union-find data structure for the Kruskal algorithm.
    Focus is to be human-readable; the code was not optimized for efficiency.
    """

    def __init__(self, G):
        """Initialize: Every node is its own parent and has rank 0"""
        self.parent = {key:key for key in list(G._nodes.keys())}
        self.rank = {key:0 for key in list(G._nodes.keys())}

    def are_connected(self, u, v):
        """Check if two nodes are in the same component"""
        return self._find(u) == self._find(v)

    def _find(self, u):
        """Find the root of node u"""
        while u != self.parent[u]:
            u = self.parent[u]
        return u
    
    def union(self, u, v):
        """Create the union of two components"""
        u_root = self._find(u)
        v_root = self._find(v)
        if u_root == v_root:
            # nothing to do if they are already in the same component
            return
        if self.rank[u_root] > self.rank[v_root]:
            # If u is higher ranked, we can connect v to u
            self.parent[v_root] = u_root
        else:
            # If not, we connect u to v and increase v's rank if needed
            self.parent[u_root] = v_root
            if self.rank[u_root] == self.rank[v_root]:
                self.rank[v_root] += 1
@add_method(Graph)
def mst_kruskal(self):
    """ Calculates the minimum spanning tree using Kruskal's algorithm.
    Focus is to be human-readable; the code was not optimized for efficiency.
    """
    
    demo = True # Set this to true to print how the algorithm works step by step
    
    # Initialize the MST nodes, links, and weights
    MST_nodes = set()
    MST_links = {} # Will look like this: {('A', 'B'): 5}

    # Sort all links by weights from smallest to largest. Skip every other due to symmetry.
    sorted_links = sorted(self.weights(), key=self.weights().__getitem__)[0::2]
    
    uf = _UF(self)
    for e in sorted_links:
        u, v = e
        if demo: print("Consider adding:",e,":",self.weights()[e])
        # if u, v already connected, abort this edge
        if uf.are_connected(u, v):
            if demo: print("NOT adding the link.\n")
            continue
        # if not, connect them and add this edge and its nodes to the MST
        uf.union(u, v)
        MST_links[e] = self.weights()[e[0], e[1]]
        MST_nodes.add(u)
        MST_nodes.add(v)
        if demo: 
            print("Adding the link.")
            print("MST progress:",MST_links)
            print("Components:", uf.parent)
            print("Ranks:", uf.rank, "\n")
        if len(MST_nodes) == self.number_of_nodes(): 
            break # We can stop once we cover all nodes
        
    MST = Graph()
    MST.add_nodes_from(MST_nodes)
    MST.add_edges_from(MST_links.keys())
    for link, w in MST_links.items(): # update weights
        MST._edges[link[0]][link[1]]['weight'] = w
    
    return MST
MST = G.mst_kruskal()
MST.weights()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1472212633759061, 'fraction_numerical': 0.00742147048671039, 'mean_word_length': 2.599378881987578, 'pattern_counts': {'":': 2, '<': 14, '<?xml version=': 0, '>': 15, 'https://': 0, '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': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '465027', 'license': 'CNRI-Python', 'n_tokens_mistral': 1953, 'n_tokens_neox': 1901, 'n_words': 561, 'path': 'class26_graphalgorithmsandviz/class26_graphalgorithmsandviz.ipynb', 'repo_name': 'mszell/introdatasci', 'size': '5801'}