Directory:Derek Elder/Programs/Reachable

//Program 1c
//Professor Pattis, ICS-23 Lab 1
//Programmers: Cameron Ruatta, Derek Elder

import edu.uci.ics.pattis.introlib.Prompt;
import edu.uci.ics.pattis.introlib.TypedBufferReader;
import edu.uci.ics.pattis.ics23.collections.*;

import java.util.Iterator;
import java.util.StringTokenizer;
import java.io.EOFException;

//Example of how this code works:
//Say we have a node a that points to node b and c
//Add a to searchNodes queue, pass it to reachable(), reachable() removes a from the queue and adds it's destination nodes to a set
//Destination nodes b and c are passed to reachable() and their destination nodes are added to searchNodes and destination nodes.

public class Reachable
{
	public static Set<String> reachableNodes = new ArraySet<String>();
	public static Queue<String> searchNodes = new ArrayQueue<String>();
	
	public static void printGraph(Map<String,Set<String>> graphMap, String output)
	{
		System.out.println(output);
		List<String>sourceNodesList = new ArrayList<String>(graphMap.keys());
		for(String sourceNode : sourceNodesList)
		{
			Set<String> destinationNodes = graphMap.get(sourceNode);
			System.out.println(sourceNode + " -> " + destinationNodes);
		}
	}
	public static boolean existsIn(String s, Iterable<String> v)
	{
		//This method allows us to see if an Iterable data type (ArrayQueue & ArraySet) has string s in it already.
		//It returns boolean true if the string is already present.
		Iterator<String> it = v.iterator();
		Boolean toAdd = false;
		while(toAdd == false && it.hasNext())
		{
			if(it.next().equals(s))
				toAdd = true;
		}
		return toAdd;
	}
	public static Set<String> reachable(Map<String,Set<String>> graphMap, String startNode)
	{
		if(existsIn(startNode, reachableNodes) == false) //Check and see if startNode is already in reachableNodes
		{
			reachableNodes.add(startNode);
		}
		
		while(!searchNodes.isEmpty()) //While there are nodes in searchNodes
		{
			for(String e : searchNodes) 
			{
				try
				{
					searchNodes.remove(); //Remove the current node to prevent repeat searches
					Set<String> destinationNodes = new ArraySet<String>(graphMap.get(e));
					for(String i : destinationNodes) //Go through destinations of node e
					{
						if(existsIn(i, searchNodes)==false) //Check to see if a destination node already is going to be searched later
							searchNodes.add(i); //Add in all the new destination nodes of e into searchNodes to be searched next
					}
					reachable(graphMap,searchNodes.peek()); //Pass the top node of SearchNodes back into reachable to be searched. The process is repeated
				}
				catch(NullPointerException f) //When we reach the final node we break out of the loop and return our Set of destination nodes
				{
					if(searchNodes.size() == 0) //We're done searching
						break;
					else
						reachable(graphMap,searchNodes.peek());
				}
				break;
			}
			break;
		}
		return reachableNodes;
	}
	public static void main(String[] args)
	{
		Map<String,Set<String>> graphMap = new ArrayMap<String,Set<String>>();
		TypedBufferReader tbr = new TypedBufferReader("Enter name of file with graph");
		//Repeatedly read lines from a file until the EOFException is thrown.
		for (;;)
		{
			try
			{
				String line = tbr.readLine();
				StringTokenizer st = new StringTokenizer(line, ";");
				String sourceNode = st.nextToken();

				while (st.hasMoreTokens())
				{
					String token = st.nextToken();

					//Update map for the current node
					Set<String> nodes = graphMap.get(sourceNode);
					if (nodes == null)
					{
						nodes = new ArraySet<String>();
						graphMap.put(sourceNode,nodes);
					}
					nodes.add(token);
				}
			} catch (EOFException e) {break;}
		}
		printGraph(graphMap, "Graph: source -> {destination} edges");
		String start = Prompt.forString("\nEnter node to start from");
		searchNodes.add(start); //Pass the start node to searchNodes queue
		System.out.println("Node reachable from " + start + " = " + reachable(graphMap,start));
	}
}