<jupyter_start><jupyter_text>Graph TheoryPython is an object oriented language. This allows us to create abstract classes, and then instantiate them into objects so that each object has the functionality of the class built into it. One of the best ways to explore graph theory in python is through classes. We will create classes to repreesent the overall graph and then a class to represent a node. The objects created from these classes will have very helpful functions, such as finding the distance between two nodes.<jupyter_code># We are going to need a few libraries for this exercise
import string
class Node(object):
    '''
    This is a class that represents a node. The functions of a class are called methods. Instantiations of this class
    will create objects that have access to the methods. 
    
    Each method begins with an argument of "self" which lets the methos know which object it belongs to.
    
    For the Node object, we care about the name of the node and a dictionary naming the adjacent nodes. The adjacent
    dictionary keys will be the name's of adjacent nodes and the value will be the weight of that edge.
    '''
    def __init__(self, name):
        # The init method is magic python method that get's called when an object is instantiated. 
        self.name = name  # Take the name given at instantiation and assign it to the object
        self.adjacent = {}  # When we create the node, we don't know about any adjacent nodes. Create a placeholder
        
    def __str__(self):
        # When printing a node, format it like this:
        return "Node {}: {}".format(self.name, self.adjacent)
    
    def __repr__(self):
        # When representing this object, use the str method
        return self.__str__()<jupyter_output><empty_output><jupyter_text>Now, we can instantiate two nodes a and b. These two nodes share a weighted edge of 2<jupyter_code>node_a = Node(name='a')
node_b = Node(name='b')

node_a.adjacent['b'] = 2
node_b.adjacent['a'] = 2
print(node_a)

print("Node {} is adjacent to the following nodes {}".format(node_a.name, node_a.adjacent))
print("Node {} is adjacent to the following nodes {}".format(node_b.name, node_b.adjacent))
node_b<jupyter_output>Node a: {'b': 2}
Node a is adjacent to the following nodes {'b': 2}
Node b is adjacent to the following nodes {'a': 2}<jupyter_text>The way that we join these nodes together is through a graph. The graph class will have many of the useful methods we care about.<jupyter_code>class Graph(object):
    '''
    This class represents a graph. The graph is consists of a collection of nodes. 
    '''
    def __init__(self, adjacency_matrix=None):
        '''
        When the graph is instantiated it will not know about any of its member nodes. There is an optional 
        `adjacency_matrix` argument that defaults to None. If an adjacency_matrix is provided, then we can 
        create the member nodes, their relationships, and add them to this graph.
        '''
        self.nodes = {}
        if adjacency_matrix:
            # We were provided an adjacency matrix
            self._create_member_nodes_from_adjacency_matrix(adjacency_matrix)
            
    def __str__(self):
        return '\n'.join([str(n) for n in self.nodes.values()])
    
    def __repr__(self):
        return self.__str__()
    
    def _create_member_nodes_from_adjacency_matrix(self, adjacency_matrix):
        # A preceeding underscore indicates a method that is only called within the class. 
        # Create nodes and weights from an adjacency matrix (list of lists) and assign them to this graph
        letters = list(string.ascii_lowercase)  # Get a list of letters to assign to the nodes we create
        needed_letters = len(adjacency_matrix)
        if needed_letters > len(letters):
            # Give the user an error that the input matrix is too large to have 
            raise ValueError("The matrix is too large to create from 26 letters. Please manually assign names to nodes and then add them to the graph.")
        
        for i, row in enumerate(adjacency_matrix):  # get an index of the row and the contentx of the row
            letter_name = letters[i]
            node = Node(letter_name)
            for j, column_value in enumerate(row):
                if column_value != 0:  # There is an adjacent node here
                    adjacent_letter_name = letters[j]
                    node.adjacent[adjacent_letter_name] = column_value
            self.nodes[letter_name] = node
            
    def get_distance_of_path(self, path):
        # Given a list of node names within the graph, find its distance using the node adjacency measures
        distance = 0
        for i, node_name in enumerate(path[:-1]):
            # Gets the index and node name for each in the path except for the last one
            this_node = self.nodes[node_name]
            next_node = self.nodes[path[i+1]]
            distance += this_node.adjacent[next_node.name]  # Get the distance from this_node to next node
        
        return distance
    
    def find_all_paths_between(self, a, b, path=None):
        if not path:
            # No path list provided, create one
            path = []

        path = path + [a] # Add a to the path

        if a == b:  # This is a path to itself, at the end of a path
            return [path]
        if a not in self.nodes:  # a could not be found in the graph
            return []
        paths = []
        for node in self.nodes[a].adjacent:  # look to adjacent nodes of a
            if node not in path:
                newpaths = self.find_all_paths_between(node, b, path)  # Recursivly go down another level
                for newpath in newpaths:
                    paths.append(newpath)
        return paths
    
    def shortest_path(self, a, b):
        # Get the distance of each weighted path and return the shortest
        all_paths = self.find_all_paths_between(a, b)
        
        if not all_paths:
            return []
        
        # The shortest path will be the first path in the list
        shortest_path = None
        shortest_distance = None
        
        for path in all_paths:
            p_distance = self.get_distance_of_path(path)
            if not shortest_distance or p_distance < shortest_distance:
                # This path is shorter
                shortest_path = path
                shortest_distance = p_distance
                
        return shortest_path
    
    def is_tree(self):
        # returns True if the graph is a tree, otherwise False
        
        node_names = list(self.nodes.keys())
        first = node_names[0]  # Make sure the first node has a path to all other nodes
        
        for node in node_names:
            if node == first:
                continue  # Don't compare it against itself
            if not self.find_all_paths_between(first, node):
                return False  # No path was found between first and node, this must not be a tree
        
        return True<jupyter_output><empty_output><jupyter_text>With the Graph class now, we can instantiate some graphs using adjacency matricies. Here is an unweighted square graph.<jupyter_code>matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]
square_graph = Graph(matrix)<jupyter_output><empty_output><jupyter_text>We can see that the graph is an instance of the Graph class we created and that it has four nodes and the adjacencies of those nodes.<jupyter_code>square_graph
print("The graph is a tree: {}".format(square_graph.is_tree()))<jupyter_output>The graph is a tree: True<jupyter_text>Looking at a weighted square graph we can now look at distances between nodes.<jupyter_code>another_matrix = [
    [0, 5, 0, 1],
    [5, 0, 6, 0],
    [0, 6, 0, -3],
    [1, 0, -3, 0]
]
weighted_graph = Graph(another_matrix)
weighted_graph<jupyter_output><empty_output><jupyter_text>This is another square graph, and we can see multiple paths from points a to c. We can also use the weights to find the shortest path.<jupyter_code>weighted_graph.find_all_paths_between('a', 'c')
weighted_graph.shortest_path('a', 'c')<jupyter_output><empty_output><jupyter_text>We can add another node to this graph, but it is not adjacent to any of the previous nodes<jupyter_code>weighted_graph.nodes['e'] = (Node('e'))
weighted_graph
weighted_graph.is_tree()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.06923168269801687, 'fraction_numerical': 0.005343783398646241, 'mean_word_length': 2.698726394378568, 'pattern_counts': {'":': 0, '<': 32, '<?xml version=': 0, '>': 32, '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': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '135110', 'license': 'MIT', 'n_tokens_mistral': 2405, 'n_tokens_neox': 2295, 'n_words': 988, 'path': 'Fall2019/MSDS400/pythonPractice/Module5/Graph Theory.ipynb', 'repo_name': 'kbridge14/regression_things', 'size': '8421'}