/** 
 * @author gswong
 */
 
import java.io.*;
import java.util.*;

public class ProbGraph {
    // Assumes a square array, like those generated by ProbModelDriver
    public static void printGraph(int[][] array) {
        int n = array.length;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    
    // Takes an adjacency matrix and makes non-adjacent edges "infinity"
    // Prepares matrix for Floyd-Warshall shortest paths algorithm
    public static void initializeDistance(int[][] array) {
        int n = array.length;
        int maxvalue = 10000;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i != j && array[i][j] == 0)
                    array[i][j] = maxvalue;
            }
        }
    }
    
    // Based on algorithm description and pseudocode on Wikipedia
    public static void findDistance(int[][] array) {
        int n = array.length;
        
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    array[i][j] = 
                        Math.min(array[i][j], array[i][k] + array[k][j]);
                }
            }
        }
    }
    
    // algorithm:
    // take an element out of pending
    // for each friend
        // randomly get whether they adopt the product
            // if they adopt it, add them to pending
    // add element to visited
    public static int[] runSimulation(int[][] adj, int[][] dist,
        double prob, int start, boolean debug) {
        int n = adj.length;
        List<Integer> pending = new ArrayList<Integer>();
        List<Integer> visited = new ArrayList<Integer>();
        int[] adopted = new int[n];
        
        adopted[start] = 1;
        pending.add(start);
        
        while(!pending.isEmpty()) { // some nodes are still waiting to broadcast
            int node = pending.remove(0);
            
            for(int i = 0; i < n; i++) {
                if(adj[node][i] == 1) {  // for each friend
                    if(adoptsWith(prob)) {  // randomly get whether they adopt
                        adopted[i] = 1;
                        if(!visited.contains(i))
                            pending.add(i);
                    }
                }
            }
            visited.add(node);
        }
        
        return adopted;
    }
    
    private static boolean adoptsWith(double prob) {
        Random r = new Random();
        return (r.nextDouble() < prob);
    }
    
    public static void findDegree(int[] degree, int[][] adj) {
        for(int i = 0; i < degree.length; i++) {
            for(int j = 0; j < degree.length; j++) {
                degree[i] += adj[i][j];
            }
        }
    }
}