Derek Elder: +Program

2009-11-02T23:07:03Z

+Program

New page

<pre>
//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));
}
}
</pre>

Directory:Derek Elder/Programs/Reachable - Revision history

Derek Elder: +Program