Graph Processing

readme

This is some code I did a while back for a job interview.

Problem:  The local commuter railroad services a number of towns in
Kiwiland.  Because of monetary concerns, all of the tracks are 'one-way.'
That is, a route from Kaitaia to Invercargill does not imply the existence
of a route from Invercargill to Kaitaia.  In fact, even if both of these
routes do happen to exist, they are distinct and are not necessarily the
same distance!

The purpose of this problem is to help the railroad provide its customers
with information about the routes.  In particular, you will compute the
distance along a certain route, the number of different routes between two
towns, and the shortest route between two towns.

Input:  A directed graph where a node represents a town and an edge
represents a route between two towns.  The weighting of the edge represents
the distance between the two towns.  A given route will never appear more
than once, and for a given route, the starting and ending town will not be
the same town.

Output: For test input 1 through 5, if no such route exists, output 'NO
SUCH ROUTE'.  Otherwise, follow the route as given; do not make any extra
stops!  For example, the first problem means to start at city A, then
travel directly to city B (a distance of 5), then directly to city C (a
distance of 4).

1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. The number of trips starting at C and ending at C with a maximum of 3
stops.  In the sample data below, there are two such trips: C-D-C (2
stops). and C-E-B-C (3 stops).
7. The number of trips starting at A and ending at C with exactly 4 stops.
In the sample data below, there are three such trips: A to C (via B,C,D); A
to C (via D,C,D); and A to C (via D,E,B).
8. The length of the shortest route (in terms of distance to travel) from A
to C.
9. The length of the shortest route (in terms of distance to travel) from B
to B.
10. The number of different routes from C to C with a distance of less than 30.  

In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC,
CEBCEBC, CEBCEBCEBC.

DirectedWeightedGraph.java

import java.util.*;

/**
 * @author jmenes
 * 
 * DirectedWeightedGraph
 * Uses a variant of an adjacency matrix to represent the graph.
 * The weight itself is used as the edge connection indicator
 * (it's really a cost matrix) 
 *
 */
public class DirectedWeightedGraph {
  
	private ArrayList<String> vertexList;
	private AdjacencyMatrix am;
	
	public DirectedWeightedGraph(String[] v) {
		
		vertexList = new ArrayList<String>(Arrays.asList(v));
		am = this.new AdjacencyMatrix(v);
	}
	
	public void addEdge(String source, String target, double weight) {
		am.setAdjacentNodes(source, target, weight);
	}
	
	public Edge getEdge(String source, String target) {
		if (am.isAdjacentNodes(source, target)) {
			return new Edge(
					source, target, am.getEdgeWeight(source, target));
		}
		return null;	// requested edge does not exist
	}
	
	/**
	 * Get all the edges for the graph
	 * @return
	 */
	public ArrayList<Edge> getEdgeList() {
		
		ArrayList<Edge> edges = new ArrayList<Edge> ();
		for (String v1 : vertexList) {
			for (String v2 : vertexList) {
				if (am.isAdjacentNodes(v1, v2))
					edges.add(getEdge(v1, v2));
			}
		}
		return edges;
	}

	/**
	 * Get all the edges for a given vertex
	 * @param v
	 * @return
	 */
	public ArrayList<Edge> getEdgeList(String v) {
		
		ArrayList<Edge> edges = new ArrayList<Edge> ();
		
		for (String v2 : vertexList) {
			if (am.isAdjacentNodes(v, v2))
				edges.add(getEdge(v, v2));
		}
		
		return edges;
	}

	
	
	public double getEdgeWeight(String source, String target) {
		return am.getEdgeWeight(source, target);
	}

	public ArrayList<String> getVertexList() {
		return vertexList;
	}
	
	public boolean isAdjacentNodes(String n1, String n2) {
		
		return am.isAdjacentNodes(n1, n2);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	
	private class AdjacencyMatrix {
		
		private int nrows;
		private int ncol;
		private double values [] [];
		
		public AdjacencyMatrix(String[] v) {

			this.nrows = v.length;
			this.ncol = v.length;
			/* initialize all values */
			values = new double [nrows] [ncol];
		}

		public void setAdjacentNodes(String n1, String n2, double weight) {
			
			values[vertexList.indexOf(n1)] [vertexList.indexOf(n2)] = weight;
			
		}
		
		public boolean isAdjacentNodes(String n1, String n2) {
			
			if (values[vertexList.indexOf(n1)] [vertexList.indexOf(n2)] > 0.0) {
				return true;
			}
			return false;
		}
		
		public double getEdgeWeight(String n1, String n2) {
			return values[vertexList.indexOf(n1)] [vertexList.indexOf(n2)];
		}
		

	}

}

Edge.java

public class Edge {

  private String source;
	private String target;
	private double weight;
	
	public Edge() {
		super();
		// TODO Auto-generated constructor stub
	}
	
	public Edge(String source, String target, double weight) {
		this.source = source;
		this.target = target;
		this.weight = weight;
	}

	public String getSource() {
		return source;
	}

	public void setSource(String source) {
		this.source = source;
	}

	public String getTarget() {
		return target;
	}

	public void setTarget(String target) {
		this.target = target;
	}

	public double getWeight() {
		return weight;
	}

	public void setWeight(double weight) {
		this.weight = weight;
	}
	
    public String toString()
    {
        return "(" + source + " : " + target + " : " + weight + ")";
    }

	@Override
	public boolean equals(Object obj) {

		if (obj instanceof Edge) {
			if (this.source.equals(((Edge)obj).getSource()) &&
					this.target.equals(((Edge)obj).getTarget()) &&
					this.weight == ((Edge)obj).getWeight()) {
				return true;
			}
		}
		return false;
	}

	@Override
	public int hashCode() {
		// TODO Auto-generated method stub
		return super.hashCode();
	}
}

GraphSearch.java

import java.util.*;

public class GraphSearch {

  private DirectedWeightedGraph graph;
	
	private HashMap<String, ArrayList<String>> adlist;
	private ArrayList<String> vertexList;
	
	private Vector<ArrayList<String>> visited;
	
	public GraphSearch() {
		// default constructor
	}
	
	public GraphSearch(DirectedWeightedGraph graph) {
		this.graph = graph;
		vertexList = graph.getVertexList();
	}
	
	/**
	 * Get total distance for a given node list
	 * @param nodes
	 * @return
	 * @throws NoSuchRouteException
	 */
	public double getDistance(String [] nodes)
		throws NoSuchRouteException
	{
		
		// get edges for given nodes
		String[] part = getEdges(nodes);
		
		double distance = 0.0;
		for (String elem : part) {
			String source = elem.substring(0, 1);
			String target = elem.substring(1, 2);
			if (!graph.isAdjacentNodes(source, target)) {
				throw new NoSuchRouteException();
			} else {
				distance += graph.getEdgeWeight(source, target);
			}
		}
		//stub
		return distance;
	}
	
	/**
	 * Returns edges for a given list of nodes
	 * @param nodes
	 * @return list of edges
	 */
	public String[] getEdges(String [] nodes) {
		
		// generate node partitions - pairs of source/target nodes
		int plen = nodes.length - 1;
		String[] edges = new String[plen];
		for (int i=0; i<plen; i++) {
			edges[i] = nodes[i] + nodes[i+1];
		}
		return edges;
	}
	
	/**
	 *  Generates an adjacency list for the current graph
	 */
	public void getGraphAsAdjacencyList() {
		
		ArrayList<Edge> edges;
		ArrayList<String> endpoints;
		
		// adjacency list
		// - if a list already exists, don't do anything
		if (null != adlist) {
			return;
		}
		
		adlist = 
			new HashMap<String, ArrayList<String>>();
		
		for (String vertex : vertexList) {
			endpoints = new ArrayList<String> ();
			edges = graph.getEdgeList(vertex);
			for (Edge e : edges) {
				endpoints.add(e.getTarget());
			}
			adlist.put(vertex, endpoints);
		}
		
	}

	/**
	 * Convenience method for GetTrips that passes a default
	 * of false for the maxeq parameter
	 * @param start
	 * @param end
	 * @param lim
	 * @return
	 */
	public int getTrips(String start, String end, int lim) {
		
		return getTrips(start, end, lim, false);
	}
	
	/**
	 * Count trips that can be made between start/end nodes
	 * within a given stop limit
	 * All the trips up to the limit will be discovered first
	 * so the function will stop when it finds the first trip
	 * over the limit
	 * @param start
	 * @param end
	 * @param stops number of stops
	 * @param maxeq true  - exact stops
	 *              false - max stops
	 * @return
	 */
	public int getTrips(String start, String end, int lim, boolean maxeq) {
		
		int ntrips = 0;
				
		// get graph represented as adjacency list for traversal
		getGraphAsAdjacencyList();
				
		int nstops = 0;
		int tpoint = 0;
		// number of stops for each trip
		int[] trips = new int[10];
		
		Iterator<String> is = adlist.get(start).iterator();
		while (is.hasNext()) {
			
			String target = is.next();
			nstops = 1;	// count this stop
			nstops += traverse(target, end);
			trips[tpoint++] = nstops;
		} 
		
		// get trip count
		for (int i=0; i<trips.length; i++) {
			if (maxeq) {
				if (trips[i] == lim && trips[i] != 0) {
					ntrips++;
				}
			} else {
				if (trips[i] <= lim && trips[i] != 0) {
					ntrips++;
				}
			}
		}
		
		return ntrips;
	}
	
	/**
	 * Calculate number of stops between 2 given nodes
	 * @param n1
	 * @param n2
	 * @return number of stops
	 */
	public int traverse (String n1, String n2) {
		
		int nstops = 0;
		
		Iterator<String> is = adlist.get(n1).iterator();
		while (is.hasNext()) {
		
			String next = is.next();
			nstops++;
			if (next.equalsIgnoreCase(n2)) {
				break;
			}
		}
		
		return nstops;
	}
		
	/**
	 * Get list of vertices between 2 given nodes
	 * @param n1
	 * @param n2
	 * @return
	 */
	public ArrayList<String> getStops (String n1, String n2) {
		
		ArrayList<String> stops = new ArrayList<String>();
		stops.add(n1);
		
		Iterator<String> is = adlist.get(n1).iterator();
		while (is.hasNext()) {
		
			String next = is.next();
			stops.add(next);
			
			while (!next.equalsIgnoreCase(n2)) {
				is = adlist.get(next).iterator();
				while (is.hasNext()) {
					next = is.next();
						stops.add(next);					
				}
			}
			if (next.equalsIgnoreCase(n2)) {
				break;
			}
		}
				
		return stops;
	}
	
	/**
	 * Find shortest path between 2 given nodes
	 * @param start
	 * @param end
	 * @return
	 */
	public double getShortestPath(String start, String end) {
		
		double pathlength = Double.POSITIVE_INFINITY;
		double tweight = 0.0;
		
		ArrayList<ArrayList<String>> trips =
			new ArrayList<ArrayList<String>>();
		
		getGraphAsAdjacencyList();

		ArrayList<String> stops = new ArrayList<String>();
		
		String n1 = start;
		
		int ncount = adlist.get(start).size();
		if (ncount == 1) {
			// if start node only has one edge we want to iterate
			// on next vertex to build the tree
			// TODO should check if next vertex also has only 1 edge
			stops.add(0, start);
			n1 = adlist.get(start).get(0);
			
		}
		
		Iterator<String> is = adlist.get(n1).iterator();
		while (is.hasNext()) {
			
			String target = is.next();
			
			stops.add(stops.size(), n1);
			stops.addAll(stops.size(), getStops(target, end));
			trips.add((new ArrayList<String>(stops)));
			stops.clear();
			if (ncount == 1) {
				// if start node only has one edge reset
				// with actual start node
				stops.add(0, start);
			}							
		}
		
		for (ArrayList<String> nlist : trips) {
			try {
				tweight = 
					getDistance(nlist.toArray(new String[nlist.size()]));
			} catch (NoSuchRouteException e) {
				tweight = 0.0;
			}
			if (tweight < pathlength) {
				pathlength = tweight;
			}
		}
		
		return pathlength;
	}
	
	
	/**
	 * Count possible routes between two nodes with total distance
	 * less than a given limit
	 * @param start
	 * @param end
	 * @param lim
	 * @return route count
	 */
	public int getRoutes(String start, String end, double lim) {
		
		double pathlength = lim;
		double tweight = 0.0;
		int tcount = 0;
		
		ArrayList<ArrayList<String>> trips =
			new ArrayList<ArrayList<String>>();
				
		getGraphAsAdjacencyList();

		ArrayList<String> stops = new ArrayList<String>();
		visited = new Vector<ArrayList<String>>();
		
		String n1 = start;
		
		int ncount = adlist.get(start).size();
		if (ncount == 1) {
			// if start node only has one edge we want to iterate
			// on next vertex to build the tree
			// TODO should check if the next vertex also only has 1 edge
			stops.add(0, start);
			addVisited(start, stops.size()-1);
			n1 = adlist.get(start).get(0);
		}
		
		stops.add(stops.size(), n1);
		addVisited(n1, stops.size()-1);
		Iterator<String> is = adlist.get(n1).iterator();
		while (is.hasNext()) {
			
			String nnode = is.next();
			
			stops.add(nnode);
			addVisited(nnode, stops.size()-1);
			traverseNodes(nnode, end, stops);
			
			try {
				
				tweight = getDistance(stops.toArray(new String[stops.size()]));
			} catch (NoSuchRouteException e) {
				// if there's an error don't count this trip
				tweight = Double.POSITIVE_INFINITY;
			}
			
			while (tweight < pathlength) {
				trips.add((new ArrayList<String>(stops)));
				tcount++;
				if (nnode.equalsIgnoreCase(end)) {
					stops.remove(stops.size()-1);
				}

				traverseNodes(stops.get(stops.size()-1), end, stops);
				try {
					
					tweight = getDistance(stops.toArray(new String[stops.size()]));
				} catch (NoSuchRouteException e) {
					// if there's an error don't count this trip
					tweight = Double.POSITIVE_INFINITY;
				}
				
			}
			
			
			// get last selected trip and follow next branch from
			// last node with more than one edge
			ArrayList<String> ltrip = trips.get(trips.size()-1);

			// get next node from last stops to determine where
			// to branch next
			String lsnn = stops.get(ltrip.size());
			stops.clear();
			stops.addAll(ltrip);
			stops.add(lsnn);
			
			// if last route exceeded limit, backup 1 edge
			// and go down next branch (if node only has 1 edge
			// continue to back up until next edge is found)
			// -- stops should have at least one edge
			if (stops.size() > 1) {
				boolean nbranch = false;
				while (!nbranch && stops.size()>1) {
					String tv = stops.get(stops.size()-1);		
					stops.remove(stops.size()-1);
					String v1 = stops.get(stops.size()-1);
					ArrayList<String> nodelist = adlist.get(v1);
					while (nodelist.size() == 1 && stops.size() > 1) {
						tv = stops.get(stops.size()-1);;
						stops.remove(stops.size()-1);
						clearVisited(stops.size());
						v1 = stops.get(stops.size()-1);
						nodelist = adlist.get(v1);
					}
					for (String elem : nodelist) {
						// check if all paths were visited for this node
						int i = nodelist.lastIndexOf(tv);
						if (i == nodelist.size()-1) {
							//break;
							continue;
						}
						if (!isVisited(elem, stops.size())) {
							n1 = elem;
							stops.add(n1);
							addVisited(n1, stops.size()-1);
							is = adlist.get(n1).iterator();
							nbranch = true;
							//break;
							continue;
						}
					}
				}
			} else {
					
				stops.clear();
				
				if (ncount == 1) {
					// if start node only has one edge reset
					// with actual start node
					stops.add(0, start);
				}
				stops.add(stops.size(), n1);
			}
							
		}		

		return tcount;
	}
	
	/**
	 * Graph traversal. 
	 * @param n1
	 * @param n2
	 * @param stops
	 */
	public void traverseNodes (String n1, String n2, ArrayList<String> stops) {
				
		getGraphAsAdjacencyList();

		String lnode = stops.get(stops.size()-1);
		if (!n1.equalsIgnoreCase(lnode)) {
			stops.add(stops.size(), n1);
			addVisited(n1, stops.size()-1);
		}

		Iterator<String> in = adlist.get(n1).iterator();
		while (in.hasNext()) {
			String nnode = in.next();
			if (!isVisited(nnode, stops.size())) {
				stops.add(nnode);
				addVisited(nnode, stops.size()-1);
			} else {
				continue;
			}
			while (!nnode.equalsIgnoreCase(n2)) {

				nnode = adlist.get(nnode).get(0);
				stops.add(nnode);

			}
			return;
		}

	}
	
	/**
	 * Mark node as visited
	 * @param node
	 * @param level
	 */
	public void addVisited(String node, int level) {
		
		try {
			visited.get(level).add(node);
		} catch (ArrayIndexOutOfBoundsException e) {
			visited.add(level, (new ArrayList<String>()));
			visited.get(level).add(node);
		}		
	}
	
	/**
	 * Check if node has been visited
	 * @param node
	 * @param level
	 * @return true if node has been visited
	 */
	public boolean isVisited(String node, int level) {
		
		try {
			return visited.get(level).contains(node);
		} catch (ArrayIndexOutOfBoundsException e) {
			// TODO Auto-generated catch block
			//e.printStackTrace();
		}
		return false;
	}
	
	/**
	 * Reset a level
	 * @param level
	 */
	public void clearVisited(int level) {
		
		visited.remove(level);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] edges = 
			{"AB5", "BC4", "CD8", "DC8", "DE6", "AD5", "CE2", "EB3", "AE7"};
				
		DirectedWeightedGraph graph = new DirectedWeightedGraph(
				new String [] {"A", "B", "C", "D", "E"});
				
		for (String elem : edges) {
			String source = elem.substring(0, 1);
			String target = elem.substring(1, 2);
			double weight = Integer.parseInt(elem.substring(2, 3));
			graph.addEdge(source, target, weight);
		}
		
		GraphSearch gs = new GraphSearch(graph);
		
		/* test cases */
		// 1. find distance of ABC
		try {						
			System.out.println("Distance of ABC: "
					+ (gs.getDistance(new String[] { "A", "B", "C" })));
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
			
		// 2. find distance of AD
		try {						
			System.out.println("Distance of AD: "
				+ (gs.getDistance(new String[] { "A", "D"})));
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		
		// 3. find distance of ADC
		try {						
			System.out.println("Distance of ADC: "
				+ (gs.getDistance(new String[] { "A", "D", "C"})));
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		
		// 4. find distance of AEBCD
		try {						
			System.out.println("Distance of AEBCD: "
				+ (gs.getDistance(new String[] { "A", "E", "B", "C", "D"})));
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}

		// 5. find distance of AED
		try {						
			System.out.println("Distance of AED: "
				+ (gs.getDistance(new String[] { "A", "E", "D"})));
		} catch (NoSuchRouteException e) {
			System.out.println("AED: No such route");
		}
		
		// 6. Number of trips C -> C <= 3 stops
		System.out.println("No. of trips C-C <= 3 stops: " + gs.getTrips("C", "C", 3));

		// 7. Number of trips A -> C = 4 stops
		System.out.println("No. of trips A-C = 4 stops: " + gs.getTrips("A", "C", 4));
		
		// 8. Length of shortest route A -> C
		System.out.println("Length of shortest route A-C: " +
				gs.getShortestPath("A", "C"));
		
		// 9. Length of shortest route B -> B
		System.out.println("Length of shortest route B-B: " +
				gs.getShortestPath("B", "B"));
		
		// 10. Number of routes C -> C
		System.out.println("No. of routes C-C: " + gs.getRoutes("C", "C", 30));
		
	}

}

ListNode.java

public class ListNode<V> {
  
	/**
	 * Linked list node
	 * - not used
	 */
	V item;
	ListNode<V> next;
	
	ListNode (V v) {
		item = v;
		next = null;
	}
}

NoSuchRouteException.java

public class NoSuchRouteException extends Exception {

  /**
	 * 
	 */
	private static final long serialVersionUID = -29906922965253681L;

}

TestGraphSearch.java

import junit.framework.TestCase;
import junit.framework.TestResult;


public class TestGraphSearch extends TestCase {

  private GraphSearch gs;
	private DirectedWeightedGraph graph;
	
	private static String[] edges = 
		{"AB5", "BC4", "CD8", "DC8", "DE6", "AD5", "CE2", "EB3", "AE7"};
	private static String[] vertex =
		{"A", "B", "C", "D", "E"};
	
	
	
	@Override
	public TestResult run() {
		// TODO Auto-generated method stub
		return super.run();
	}

	@Override
	protected void setUp() throws Exception {
		
		graph = new DirectedWeightedGraph(vertex);
				
		for (String elem : edges) {
			String source = elem.substring(0, 1);
			String target = elem.substring(1, 2);
			double weight = Integer.parseInt(elem.substring(2, 3));
			graph.addEdge(source, target, weight);
		}
		
		gs = new GraphSearch(graph);
	}

	@Override
	protected void tearDown() throws Exception {
		// TODO Auto-generated method stub
		super.tearDown();
	}
	
	public void testGraphSearch() {
		// 1. find distance of ABC
		double dexpected = 9.0;
		double dactual = 0.0;
		try {						
			dactual = gs.getDistance(new String[] { "A", "B", "C" });
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		assertEquals("1. Distance of ABC", dexpected, dactual);
			
		// 2. find distance of AD
		dexpected = 5.0;
		dactual = 0.0;
		try {						
			dactual = gs.getDistance(new String[] { "A", "D"});
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		assertEquals("2. Distance of AD", dexpected, dactual);
		
		// 3. find distance of ADC
		dexpected = 13.0;
		dactual = 0.0;
		try {						
			dactual = gs.getDistance(new String[] { "A", "D", "C"});
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		assertEquals("3. Distance of ADC", dexpected, dactual);

		
		// 4. find distance of AEBCD
		dexpected = 22.0;
		dactual = 0.0;
		try {						
			dactual = gs.getDistance(new String[] { "A", "E", "B", "C", "D"});
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		assertEquals("4. Distance of AEBCD", dexpected, dactual);

		// 5. find distance of AED
		dexpected = 0.0;
		dactual = 0.0;
		try {						
			dactual = gs.getDistance(new String[] { "A", "E", "D"});
		} catch (NoSuchRouteException e) {
			System.out.println("No such route");
		}
		assertEquals("5. Distance of AED (No such route)", dexpected, dactual);
		
		// 6. Number of trips C -> C
		int iexpected = 2;
		int iactual = gs.getTrips("C", "C", 3);
		assertEquals("6. Number of trips C -> C", iexpected, iactual);

		// 7. Number of trips A -> C
		iexpected = 3;
		iactual = gs.getTrips("A", "C", 4);
		assertEquals("7. Number of trips A -> C", iexpected, iactual);
		
		// 8. Length of shortest route A -> C
		dexpected = 9.0;
		dactual = gs.getShortestPath("A", "C");
		assertEquals("8. Length of shortest route A -> C", dexpected, dactual);
		
		// 9. Length of shortest route B -> B
		dexpected = 9.0;
		dactual = gs.getShortestPath("B", "B");
		assertEquals("9. Length of shortest route B -> B", dexpected, dactual);
		
		// 10. Number of routes C -> C
		iexpected = 7;
		iactual = gs.getRoutes("C", "C", 30);
		assertEquals("10. Number of routes C -> C", iexpected, iactual);
		
	}

}