PageRank.java

package com.thealgorithms.others;

import java.util.Scanner;

/**
 * PageRank Algorithm Implementation
 *
 * <p>
 * The PageRank algorithm is used by Google Search to rank web pages in their
 * search engine
 * results. It was named after Larry Page, one of the founders of Google.
 * PageRank is a way of
 * measuring the importance of website pages.
 *
 * <p>
 * Algorithm: 1. Initialize PageRank values for all pages to 1/N (where N is the
 * total number
 * of pages) 2. For each iteration: - For each page, calculate the new PageRank
 * by summing the
 * contributions from all incoming links - Apply the damping factor: PR(page) =
 * (1-d) + d *
 * sum(PR(incoming_page) / outgoing_links(incoming_page)) 3. Repeat until
 * convergence
 *
 * @see <a href="https://en.wikipedia.org/wiki/PageRank">PageRank Algorithm</a>
 */
public final class PageRank {

 private static final int MAX_NODES = 10;
 private static final double DEFAULT_DAMPING_FACTOR = 0.85;
 private static final int DEFAULT_ITERATIONS = 2;

 private int[][] adjacencyMatrix;
 private double[] pageRankValues;
 private int nodeCount;

 /**
 * Constructor to initialize PageRank with specified number of nodes
 *
 * @param numberOfNodes the number of nodes/pages in the graph
 * @throws IllegalArgumentException if numberOfNodes is less than 1 or greater
 * than MAX_NODES
 */
 public PageRank(int numberOfNodes) {
 if (numberOfNodes < 1 || numberOfNodes > MAX_NODES) {
 throw new IllegalArgumentException("Number of nodes must be between 1 and " + MAX_NODES);
 }
 this.nodeCount = numberOfNodes;
 this.adjacencyMatrix = new int[MAX_NODES][MAX_NODES];
 this.pageRankValues = new double[MAX_NODES];
 }

 /**
 * Default constructor for interactive mode
 */
 public PageRank() {
 this.adjacencyMatrix = new int[MAX_NODES][MAX_NODES];
 this.pageRankValues = new double[MAX_NODES];
 }

 /**
 * Main method for interactive PageRank calculation
 *
 * @param args command line arguments (not used)
 */
 public static void main(String[] args) {
 try (Scanner scanner = new Scanner(System.in)) {
 System.out.print("Enter the Number of WebPages: ");
 int nodes = scanner.nextInt();

 PageRank pageRank = new PageRank(nodes);
 System.out.println("Enter the Adjacency Matrix with 1->PATH & 0->NO PATH Between two WebPages: ");

 for (int i = 1; i <= nodes; i++) {
 for (int j = 1; j <= nodes; j++) {
 int value = scanner.nextInt();
 pageRank.setEdge(i, j, value);
 }
 }

 pageRank.calculatePageRank(nodes, DEFAULT_DAMPING_FACTOR, DEFAULT_ITERATIONS, true);
 }
 }

 /**
 * Sets an edge in the adjacency matrix
 *
 * @param from source node (1-indexed)
 * @param to destination node (1-indexed)
 * @param value 1 if edge exists, 0 otherwise
 */
 public void setEdge(int from, int to, int value) {
 if (from == to) {
 adjacencyMatrix[from][to] = 0; // No self-loops
 } else {
 adjacencyMatrix[from][to] = value;
 }
 }

 /**
 * Sets the adjacency matrix for the graph
 *
 * @param matrix the adjacency matrix (1-indexed)
 */
 public void setAdjacencyMatrix(int[][] matrix) {
 for (int i = 1; i <= nodeCount; i++) {
 for (int j = 1; j <= nodeCount; j++) {
 setEdge(i, j, matrix[i][j]);
 }
 }
 }

 /**
 * Gets the PageRank value for a specific node
 *
 * @param node the node index (1-indexed)
 * @return the PageRank value
 */
 public double getPageRank(int node) {
 if (node < 1 || node > nodeCount) {
 throw new IllegalArgumentException("Node index out of bounds");
 }
 return pageRankValues[node];
 }

 /**
 * Gets all PageRank values
 *
 * @return array of PageRank values (1-indexed)
 */
 public double[] getAllPageRanks() {
 return pageRankValues.clone();
 }

 /**
 * Calculates PageRank using the default damping factor and iterations
 *
 * @param totalNodes the total number of nodes
 * @return array of PageRank values
 */
 public double[] calculatePageRank(int totalNodes) {
 return calculatePageRank(totalNodes, DEFAULT_DAMPING_FACTOR, DEFAULT_ITERATIONS, false);
 }

 /**
 * Calculates PageRank with custom parameters
 *
 * @param totalNodes the total number of nodes
 * @param dampingFactor the damping factor (typically 0.85)
 * @param iterations number of iterations to perform
 * @param verbose whether to print detailed output
 * @return array of PageRank values
 */
 public double[] calculatePageRank(int totalNodes, double dampingFactor, int iterations, boolean verbose) {
 validateInputParameters(totalNodes, dampingFactor, iterations);

 this.nodeCount = totalNodes;
 double initialPageRank = 1.0 / totalNodes;

 if (verbose) {
 System.out.printf("Total Number of Nodes: %d\tInitial PageRank of All Nodes: %.6f%n", totalNodes, initialPageRank);
 }

 initializePageRanks(totalNodes, initialPageRank, verbose);
 performIterations(totalNodes, dampingFactor, iterations, verbose);

 if (verbose) {
 System.out.println("\nFinal PageRank:");
 printPageRanks(totalNodes);
 }

 return pageRankValues.clone();
 }

 /**
 * Validates input parameters for PageRank calculation
 *
 * @param totalNodes the total number of nodes
 * @param dampingFactor the damping factor
 * @param iterations number of iterations
 * @throws IllegalArgumentException if parameters are invalid
 */
 private void validateInputParameters(int totalNodes, double dampingFactor, int iterations) {
 if (totalNodes < 1 || totalNodes > MAX_NODES) {
 throw new IllegalArgumentException("Total nodes must be between 1 and " + MAX_NODES);
 }
 if (dampingFactor < 0 || dampingFactor > 1) {
 throw new IllegalArgumentException("Damping factor must be between 0 and 1");
 }
 if (iterations < 1) {
 throw new IllegalArgumentException("Iterations must be at least 1");
 }
 }

 /**
 * Initializes PageRank values for all nodes
 *
 * @param totalNodes the total number of nodes
 * @param initialPageRank the initial PageRank value
 * @param verbose whether to print output
 */
 private void initializePageRanks(int totalNodes, double initialPageRank, boolean verbose) {
 for (int i = 1; i <= totalNodes; i++) {
 pageRankValues[i] = initialPageRank;
 }

 if (verbose) {
 System.out.println("\nInitial PageRank Values, 0th Step");
 printPageRanks(totalNodes);
 }
 }

 /**
 * Performs the iterative PageRank calculation
 *
 * @param totalNodes the total number of nodes
 * @param dampingFactor the damping factor
 * @param iterations number of iterations
 * @param verbose whether to print output
 */
 private void performIterations(int totalNodes, double dampingFactor, int iterations, boolean verbose) {
 for (int iteration = 1; iteration <= iterations; iteration++) {
 double[] tempPageRank = storeCurrentPageRanks(totalNodes);
 calculateNewPageRanks(totalNodes, tempPageRank);
 applyDampingFactor(totalNodes, dampingFactor);

 if (verbose) {
 System.out.printf("%nAfter %d iteration(s)%n", iteration);
 printPageRanks(totalNodes);
 }
 }
 }

 /**
 * Stores current PageRank values in a temporary array
 *
 * @param totalNodes the total number of nodes
 * @return temporary array with current PageRank values
 */
 private double[] storeCurrentPageRanks(int totalNodes) {
 double[] tempPageRank = new double[MAX_NODES];
 for (int i = 1; i <= totalNodes; i++) {
 tempPageRank[i] = pageRankValues[i];
 pageRankValues[i] = 0;
 }
 return tempPageRank;
 }

 /**
 * Calculates new PageRank values based on incoming links
 *
 * @param totalNodes the total number of nodes
 * @param tempPageRank temporary array with previous PageRank values
 */
 private void calculateNewPageRanks(int totalNodes, double[] tempPageRank) {
 for (int targetNode = 1; targetNode <= totalNodes; targetNode++) {
 for (int sourceNode = 1; sourceNode <= totalNodes; sourceNode++) {
 if (adjacencyMatrix[sourceNode][targetNode] == 1) {
 int outgoingLinks = countOutgoingLinks(sourceNode, totalNodes);
 if (outgoingLinks > 0) {
 pageRankValues[targetNode] += tempPageRank[sourceNode] / outgoingLinks;
 }
 }
 }
 }
 }

 /**
 * Applies the damping factor to all PageRank values
 *
 * @param totalNodes the total number of nodes
 * @param dampingFactor the damping factor
 */
 private void applyDampingFactor(int totalNodes, double dampingFactor) {
 for (int i = 1; i <= totalNodes; i++) {
 pageRankValues[i] = (1 - dampingFactor) + dampingFactor * pageRankValues[i];
 }
 }

 /**
 * Counts the number of outgoing links from a node
 *
 * @param node the source node (1-indexed)
 * @param totalNodes total number of nodes
 * @return the count of outgoing links
 */
 private int countOutgoingLinks(int node, int totalNodes) {
 int count = 0;
 for (int i = 1; i <= totalNodes; i++) {
 if (adjacencyMatrix[node][i] == 1) {
 count++;
 }
 }
 return count;
 }

 /**
 * Prints the PageRank values for all nodes
 *
 * @param totalNodes the total number of nodes
 */
 private void printPageRanks(int totalNodes) {
 for (int i = 1; i <= totalNodes; i++) {
 System.out.printf("PageRank of %d: %.6f%n", i, pageRankValues[i]);
 }
 }
}