#include

#include

#include "AdjacencyList.h$"$

using namespace std;

$//$ prints the PageRank of all pages after p powerIterations in ascending

$//$ alphabetical order of webpages and rounding rank to two decimal places

void AdjacencyList::PageRank$($int n$)\{$

$//$ optionally, store your output in a string$/$stringstream and then return it from this function after printing so that it is easier to test with Catch

for $($auto& page: In$\_$Degree$)$

Ranking$[$page$.$first$]=(1\mathrm{.}0$f $/($float$)$In$\_$Degree.size$())$;

$//$ Creates a new map to hold old page ranks

mapNew$\_$Ranking;

$//$find the page rank for the iterations

for$($int i $=1$; isecond$)*$ Ranking$[$connection$]$;

New$\_$Ranking$[$page$.$first$]=$ result;

$\}$

Ranking $=$ New$\_$Ranking;

$\}$

map::iterator Rank$\_$Iterator;

for$($Rank$\_$Iterator $=$ Ranking.begin$()$; Rank$\_$Iterator $!=$ Ranking.end$()$; Rank$\_$Iterator$++)\{$

cout $<<$ setprecision$(2)<<$ fixed $<<$ Rank$\_$Iterator$->$first $<<""<<$ Rank$\_$Iterator$->$second;

cout $<<"$

$"$;

$\}$

$\}$

void AdjacencyList::Edges$($string from, string to$)\{$

Out$\_$Degree$[$from$]+=1$;

In$\_$Degree$[$to$].$push$\_$back$($from$)$;

if$($Out$\_$Degree.find$($to$)==$ Out$\_$Degree.end$())$

Out$\_$Degree$[$to$]=0$;

if$($In$\_$Degree.find$($from$)==$ In$\_$Degree.end$())$

In$\_$Degree$[$from$]=\{\}$;

$\}$ ;

$--------------------------------------------$

#pragma once

#include

#include

#include

#include

using namespace std;

class AdjacencyList $\{$

private:

$//$ To store sites based on rank

map Ranking;

$//$ To store Out Degree

map Out$\_$Degree;

$//$ To store In Degree

map$>$ In$\_$Degree;

public:

$//$Think about what helper functions you will need in the algorithm

void PageRank$($int n$)$;

void Edges$($string from, string to$)$;

$\}$;

$---------------------------------------------------------$

Main.c

#include

#include "AdjacencyList.h$"$

using namespace std;

int main$()\{$

AdjacencyList Created$\_$Graph;

int no$\_$of$\_$lines, power$\_$iterations;

string from, to;

cin $>>$ no$\_$of$\_$lines;

cin $>>$ power$\_$iterations;

for $($int i $=0$; i $<$ no$\_$of$\_$lines; i$++)\{$

cin $>>$ from;

cin $>>$ to;

Created$\_$Graph.Edges$($from$,$ to$)$;

$\}$

$//$Create a graph object

Created$\_$Graph.PageRank$($power$\_$iterations$)$;

$-----------------------------------------------------------$

$\}$Describe the data structure you used to implement the graph and why.

What is the computational complexity of each method in your implementation in the worst case in terms of Big O notation?

What is the computational complexity of your main method in your implementation in the worst case in terms of Big O notation?

What did you learn from this assignment, and what would you do differently if you had to start over?