/** 
 * @author YourAndrewIDHere
 * You should fill in the stub for this code file.  The
 * arguments will be given to you 
 */

import java.io.*;
import java.util.*;

public class ProbModelDriver {

	/**
	 * The first argument is the model filename
	 * The second argument should be the value of p, as an ASCII string
	 * The third argument should be the NodeID of the initial product user
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		if(args.length < 3)
		{
			System.out.println("Usage: ProbModelDriver netDefFilename pValue initialNode (-test)");
			return;
		}
		
		String networkFilename = args[0];
		double successProb = Double.parseDouble(args[1]);
		int    startNode = Integer.parseInt(args[2]);
		
		
		// Put any code here that you need to initialize your network model
		
		// Open and read from file
		FileReader input = new FileReader(networkFilename);
		BufferedReader bufRead = new BufferedReader(input);
		String line = bufRead.readLine();

		int nNodes = Integer.parseInt(line);
		Node[] nodes = new Node[nNodes];
		for (int i = 0; i < nNodes; i++)
			nodes[i] = new Node(i);
		
		while ((line = bufRead.readLine()) != null) {
			String[] tokens = line.split(" ");
			if (tokens.length < 2)
				break;
			int u = Integer.parseInt(tokens[0]);
			int v = Integer.parseInt(tokens[1]);
			nodes[u].addNeighbor(v);
			nodes[v].addNeighbor(u);
		}
		
		
		// DO NOT REMOVE THE FOLLOWING CODE.
		if(args.length == 4 && args[3].toLowerCase().equals("-test")) {
			// Put your code to simulate the network
			// here.  You should print out at the end
			// of the simulation all of the nodes which
			// are using the product.  
			
			Random r = new Random();
			ArrayList<Integer> queue = new ArrayList<Integer>();
			queue.add(startNode);
			nodes[startNode].isChanged = true;
			
			while (queue.size() > 0) {
				int currNode = queue.remove(0);
				
				for (int neighbor : nodes[currNode].neighbors) {
					if (nodes[neighbor].isChanged)
						continue;
					if (r.nextDouble() < successProb) {
						nodes[neighbor].isChanged = true;
						queue.add(neighbor);
					}
				}
			}
			
			for (int i = 0; i < nNodes; i++)
				if (nodes[i].isChanged)
					System.out.println(i);
			return; // make sure that this return is called!
		}
		
		// You are free to do whatever you want here...
		// Bren suggests that you create some helper classes
		// to do the simulation and then run your simulations
		// on a variety of parameters in this space.
		
		for (int cs = 0; cs <= 20; cs ++) {
			successProb = cs / 20.0;
			System.out.print(successProb);
			for (startNode = 0; startNode < nNodes; startNode++) {
				int total = 0;
				for (int loop = 0; loop < 100000; loop++) {
					// Initialize 
					for (int i = 0; i < nNodes; i++)
						nodes[i].isChanged = false;
					
					int count = 0;
					Random r = new Random();
					ArrayList<Integer> queue = new ArrayList<Integer>();
					queue.add(startNode);
					nodes[startNode].isChanged = true;
					
					while (queue.size() > 0) {
						int currNode = queue.remove(0);
						count++;
						
						for (int neighbor : nodes[currNode].neighbors) {
							if (nodes[neighbor].isChanged)
								continue;
							if (r.nextDouble() < successProb) {
								nodes[neighbor].isChanged = true;
								queue.add(neighbor);
							}
						}
					}
					total += count;
				}
				System.out.print("\t" + total / nNodes / 1000.);
			}
			System.out.println("");
		}
	}

}