Directory:Derek Elder/Programs/Reachable
MyWikiBiz, Author Your Legacy — Wednesday December 25, 2024
Jump to navigationJump to search//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)); } }