internet_graph.py

import math
import numpy as np
from collections import deque


class PageVertex:
    """
    Representation of a single web page and its linked pages.
    """
    def __init__(self, id):
        """Initialize attributes of a new PageVertex instance.
           Parameters:
           id(str): unique identifier of the instance, e.g. 'A'
           Returns: None
        """
        self.page_id = id
        # map each linked page_id --> PageVertex obj
        self.neighbors = dict()
        # each link has the same weight
        self.link_weight = 0

    def __set_link_weight(self, num_links=None):
        """Adjust the weight of any PageVertex linked by this
           instance to be the inverse of its number of
           neighbors.
           Parameter: 
           num_links(int): the number of outlinks of 
                           this instance
           Returns: None
        """
        if num_links is None:
          num_links = len(self.neighbors)
        self.link_weight = (1 / num_links)
        return None

    def add_link(self, page):
        """Link another PageVertex from this instance.
           
           Parameters:
           page(PageVertex): the PageVertex object the
                             outlink leads to
        
        """
        # recalculate the link weight
        num_links = 1 + len(self.neighbors)
        self.__set_link_weight(num_links)
        # add neighbor
        self.neighbors[page.get_id()] = page
        return None

    def __str__(self):
        '''Output the PageVertex and its linked neighbors.'''
        neighbor_ids = list(self.neighbors.keys())
        return f'{self.page_id} adjacent to {neighbor_ids}'

    def __repr__(self):
        '''Output the list of neighbors of this PageVertex.'''
        return self.__str__()

    def get_neighbors(self):
        """Return the PageVertex instances that are linked by 
           this instance.
           
        """
        return list(self.neighbors.values())

    def get_neighbors_with_weights(self):
        """Return the PageVertex instances that are linked by 
           this instance, along with the weight of that link.
           
        """
        neighbors = self.get_neighbors()
        # add each neighbir along with its weights
        neighbor_weights = list()
        for n in neighbors:
            pair = (n, n.link_weight)
            neighbor_weights.append(pair)
        return neighbor_weights

    def get_id(self):
        '''Return the id of this vertex.'''
        return self.page_id

    def has_neighbor(self, page_id):
        '''Return True or False based on if this Page links to the other.'''
        return page_id in self.neighbors


class InternetGraph:
    """
    Represents a composition of all PageVertex instances
    in the network. Is a directed, weighted, and 
    not neccessarily connected graph. 
    """
    def __init__(self):
        '''Construct a new InternetGraph instance.'''
        # map each page_id --> PageVertex obj
        self.pages = dict()

    def add_page_by_id(self, page_id):
        """Instaniate a new PageVertex, then add to
           the InternetGraph.
           Parameters:
           page_id(str): the id of the new PageVertex
                         to be added
           Returns: None
        
        """
        self.pages[page_id] = PageVertex(page_id)
        return None

    def add_page_by_obj(self, page):
        """Add a PageVertex instance into the dictionary
           of all PageVertex instances.
           Parameters:
           page(PageVertex): the PageVertex to be added
           Returns: None
        
        """
        self.pages[page.get_id()] = page
        return None

    def get_pages(self):
        '''Return a list of all PageVertex instances.'''
        return list(self.pages.values())

    def contains_page(self, page_id):
        """Returns True if a PageVertex exists with 'page_id'.
          
           Parameters:
           page_id(str): the id of the PageVertex being queried
           Returns: bool: True only if the id is found in self.pages
        
        """
        return page_id in self.pages

    def get_page(self, page_id):
        """Returns a PageVertex with matching page_id.
           Parameters:
           page_id(str): the id of the PageVertex being queried
           Returns: PageVertex instance, or else raises KeyError.
        
        """
        # raise error, or return object
        if page_id not in self.pages:
            raise KeyError(f'PageVertex {page_id} not found.')
        return self.pages[page_id]

    def link_pages(self, page1_id, page2_id):
        """Adds a link from PageVertex 1 to PageVertex 2.
           Parameters:
           page1_id(str): the id of the PageVertex where the link originates
           page2_id(str): the id of the PageVertex where the link ends
           Returns: None
        
        """
        page1_obj, page2_obj = (
            self.get_page(page1_id),
            self.get_page(page2_id)
        )
        page1_obj.add_link(page2_obj)
        return None

    def __str__(self):
        '''Return the PageVertexs in this instance.'''
        return f'InternetGraph with PageVertices: {self.get_pages()}'


    """What's the PageRank rating of each page?"""

    def compute_inlink_values(self):
        """Return a dict of the total endorsement given
           to each PageVertex.
           Parameters: None
           Returns: 
           list: rankings is an array of the eigenvalues computed from
                 an square matrix of each PageVertex's endorsements
           Complexity Analysis:
           The runtime of this implementation scales quadratically
           with the size of P, the number of PageVertexs in the InternetGraph.
           It also scales with the size of L, the number of links
           in the InternetGraph, because that is the sum total of addition
           operations we will use to calculate the total endorsement 
           received by each PageVertex.
           
           This runtime can be expressed in Big O as O(P^2 + L)
        """
        # compute how much endorsement each PageVertex got
        all_page_ids = list(self.pages.keys())  # O(P)
        inlinks = list()
        for page_id1 in all_page_ids:  # P^2 iterations
            endorsements = list()
            for page_id2 in all_page_ids:
                # get the two Page objects
                pag1, page2 = (
                    self.get_page(page_id1),
                    self.get_page(page_id2)
                )
                # use outlinks to see endorsements from others
                if page2.has_neighbor(page_id1) is True:
                    endorsement_value = page2.link_weight
                # otherwise no endorsement was given
                else:
                    endorsement_value = 0
                # add the single endorsement 
                endorsements.append(endorsement_value)
            # add the PageVertex's total endorsement vector
            inlinks.append(endorsements)
        # Rank the sites by finding the "eigenvalues" after 50 iterations
        rankings = np.array([1/len(self.pages) for page in self.pages]) # O(P)
        for i in range(50): 
            rankings = np.dot(inlinks, rankings)  # O(P^2)
        return rankings

    def bucket_ranked_pages(self, page_eigs):
        """Return a list of tuples for each PageVertex,
           along with its PageRank rating.
           Parameters: 
           page_eigs(dict): hash map between page ids and 
                           their eigenvalues
           
           Returns: 
           dict: each PR rating is mapped to a list
                 of the page ids which have that rating
           Complexity Analysis:
           The runtime of this method scales linearithmically with
           the size of P, the number of PageVertices. Therefore it
           id expressed in Big O as O(P log P).
        """
        # store variables for number of pages to rank 
        num_rankings = len(page_eigs)  # O(P)
        # store possible ratings we can give out (scale 1-10)
        num_possible_ranks = 10
        # compute length of each rating "bucket"
        bucket_len = math.ceil(num_rankings / num_possible_ranks)  # O(1)
        # sort the pages by the greatest eig values
        sorted_pages = list(page_eigs.items())
        sorted_pages.sort(reverse=True, key=lambda p_eig: p_eig[1])  # O(P log P)
        # map each rating to a list of the appropiate pages
        rating_pages = dict()
        for rating in range(1, num_possible_ranks + 1):  # 10 iterations
            # store a list of the page ids 
            pages = list()
            # compute indices of the pages we want
            start = 0 + (bucket_len * (rating - 1))
            end = start + bucket_len
            # add the pages in that bucket
            for page, eig in sorted_pages[start:end]:  # O(P / 10) in total
                pages.append(page)
            # map to the rating - if we haven't already added all pages
            if len(pages) > 0:
                rating_pages[rating] = pages
        return rating_pages

    def rank_pages(self):
        """
        Return the PageRank rating for each page.
        Parameters: None
        Returns:
        List<tuple<str, int>>: tuples in the form (str: page_id, int: rating), 
            where:
                 - page_id is the id of a PageVertex instance
                 - rating is its PageRank value (from 1-10, 1 being highest)
                 - list elements sorted in order of highest ratings,
                   i.e. all PageRanks of 1 come first, then the 2's, and so on 
        Complexity Analysis:
        The runtime of this method grows in relation to P and L
        asymptotically, which represent the number of PageVertexs and the 
        total number of links in the InternetGraph respectively. The Big O
        notation for the combined runtime of the three helper methods
        would be O(P^2 + L).
        """
        # compute eigenvalues of alll pages
        rankings_vector = self.compute_inlink_values()
        # map all pages to their eigenvalues
        page_eigs = dict(zip(list(self.pages), rankings_vector)) 
        # convert to list of PageRank ratings
        rating_pages = self.bucket_ranked_pages(page_eigs)  # O(P log P)
        return rating_pages

    """What pages can I reach N links away from this page?"""

    def find_pages_n_away(self, start_id, link_distance):
        """
        Find and return all pages n links away.
        In this implementation, if a page has multiple
        paths to it from the start that differ in distance,
        then the shortest distance is used to determine if
        should be returned or not. If that shortest distance
        is less than the link_distance argument, the PageVertex
        will not be returned at all.
        For example: 
        Suppose start_id = A, and link_distance = 2, 
        and PageVertex A can reached PageVertex C
        using either 1 link or 2 links - then PageVertex C will not
        be returned, as the function considers C to only to be 1 link
        away from A.
        
        Parmeters:
        start_id (str): The id of the start PageVertex.
        link_distance (int): The distance from the 
                                start vertex we want
        Returns:
        List<str>: All PageVertex ids that are 'link_distance' away
        Complexity Analysis:
        This function attempts to process each PageVertex, by way of 
        each link in the InternetGraph. It scales in linear proportion to 
        P and L as they grow asymptotically larger, therefore
        the Big O notation of this function is O(P + L).
        """
        # check to make sure we have a valid start_id
        if not self.contains_page(start_id):
            raise KeyError(f"PageVertex {start_id}.")
        # Store the starting page in a variable 
        start_page_obj = self.get_page(start_id)
        # Keep a count of steps taken from start so far
        steps = -1
        # Keep a dict of PageVertex ids, mapped to their distance from start
        page_distances = dict()
        # queue of vertices to visit next
        queue = deque() 
        queue.append(start_page_obj)
        # Perform a BFS
        while steps < link_distance:
            # init a list of neighbors to process next
            neighbors = list()
            # Dequeue all the pages in the queue
            while len(queue) > 0:
                current_page_obj = queue.popleft()
                current_page_id = current_page_obj.get_id()
                # add the current PageVertex to the dict
                if current_page_id not in page_distances:
                    page_distances[current_page_id] = steps + 1
                # Keep track of page to process on next iteration
                neighbors.extend(current_page_obj.get_neighbors())
            # enqueue the vertices to visit on the next iteration
            for neighbor in neighbors:
                queue.append(neighbor)
            # Increment the steps taken so far
            steps += 1
        # Return the ids of pages, target distance away
        pages_n_away = list()
        for page_id in page_distances:
            if page_distances[page_id] == link_distance:
                pages_n_away.append(page_id)
        return pages_n_away

    """What's the Shortest Weighted Path Between 2 PageVertexs (by links)?"""

    def find_shortest_path(self, start_id, target_id):
        """
        Use Dijkstra's Algorithm to return the total weight
        of the shortest path from a start page 
        to a destination.
        Parameters:
        start_id(str): the id of the PageVertex where the path begins
        target_id(str): the id of the PageVertex where the path ends
        Returns:
        float: the total weight of the edges along the shortest path
               from the starting to target PageVertex
        Complexity Analysis:
        The runtime of this method asymptotically increases quadratically 
        with respect to P, the number of PageVertexs. The longest step is
        finding the minimum PageVertex to add, since an ordinary array is
        currently used to simulate using a binary min heap.
        Overall, the runtime of this method is O(P^2).
        """
        # Check that both start and target PageVertexs valid
        if self.contains_page(start_id) is False:  # O(P)
            raise KeyError(f'{start_id} not found in InternetGraph!')
        elif self.contains_page(target_id) is False:  # O(P)
            raise KeyError(f'{target_id} not found in InternetGraph!')
        # A: initialize all page distances to INFINITY away
        page_weight = dict()  # O(1)
        for page_obj in self.pages.values():  # P iterations
            page_weight[page_obj] = float('inf')
        # B: Calculate Shortest Paths from Start PageVertex
        start_page = self.pages[start_id]  # O(1)
        page_weight[start_page] = 0
        while len(list(page_weight.items())) > 0:  # P iterations
            # Get the minimum-distance remaining PageVertex
            min_distance = min(list(page_weight.values()))  # O(P)
            min_page = None
            # find the minumum-weighted PageVertex
            for page in page_weight:  # P iterations
                if page_weight[page] == min_distance:
                    min_page = page
            # If target found, return its distance
            if min_page.page_id == target_id:
                return page_weight[min_page]
            # B: List the PageVertex's neighbors
            neighbor_weights = min_page.get_neighbors_with_weights()  # O(L)
            # C: Update the PageVertex's neighbors
            for neighbor, weight in neighbor_weights:
                if neighbor in page_weight:
                    current_distance = page_weight[neighbor]
                    # Update ONLY to reduce the weight of the distance
                    new_dist = weight + page_weight[min_page]
                    if new_dist < current_distance:
                        page_weight[neighbor] = new_dist
            # remove the min weighted page from the dict
            del page_weight[min_page]


if __name__ == "__main__":
    # Runner Script
    # A: instaniate the PageVertexs and Graph
    pageA = PageVertex('A')
    pageB = PageVertex('B')
    pageC = PageVertex('C')
    pageD = PageVertex('D')
    pageA.add_link(pageB)
    pageB.add_link(pageC) 
    pageB.add_link(pageD)
    pageC.add_link(pageA)
    pageC.add_link(pageD)
    pageD.add_link(pageA)
    pageD.add_link(pageB)
    internet = InternetGraph()
    internet.add_page_by_obj(pageA)
    internet.add_page_by_obj(pageB)
    internet.add_page_by_obj(pageC)
    internet.add_page_by_obj(pageD)
    # B: Test PageRank
    rankings = internet.rank_pages()
    print(f'Final rankings: {rankings}')
    # C: Seeing What PageVertexs Can be Reached from 'B'
    neighbors = internet.find_pages_n_away('B', 2)
    print('Shortest distance neighbors 2 links away ' +
          f'from B: {neighbors}')
    # D: Finding Length of Shortest Path
    b_to_d = internet.find_shortest_path('B', 'D')
    print(f'Minimum weight of path from B to D: {b_to_d}')