Simple Java Graph and DFS with explanation


  • 0
    J

    Simple Directed Graph and DFS
    based on equations and value, we need to construct directed graph along with weight.
    E.g a/b=2 then we a-->b with weight 2 and b--->a with weight 1/2. the same for b/c=3 and the rest. when we need to query a/c we need do a/c=a/b * b/c. use regular DFS ways to do it.

    Note: a/a and x/x are special cases.

    welcome for any suggestions.

    
    // this is directional graph, use dfs to calculate them.
    	public static double[] calcEquation(String[][] equations, double[] values, String[][] query) {
    //construct directed graph
    		HashMap<String, List<DirectedEdge>> graph = new HashMap<String, List<DirectedEdge>>();
    		List<String> onStack = new ArrayList<String>();
    		int index = 0;
    		for (String[] pair : equations) {
    			List<DirectedEdge> list1 = graph.getOrDefault(pair[0], new ArrayList<DirectedEdge>());
    			list1.add(new DirectedEdge(pair[0], pair[1], values[index]));
    			graph.put(pair[0], list1);
    			List<DirectedEdge> list2 = graph.getOrDefault(pair[1], new ArrayList<DirectedEdge>());
    			list2.add(new DirectedEdge(pair[1], pair[0], 1 / values[index]));
    			graph.put(pair[1], list2);
    			index++;
    		}
    		double[] result = new double[query.length];
    		index = 0;
    		for (String[] qry : query) {
    			double temp = -1;
    			// calculate the result
    			onStack.clear();
    			onStack.add(qry[0]);
    			if (canReach(qry[0], qry[1], graph, onStack)) {
    				temp = 1;
    				for (int i = 0; i < onStack.size() - 1; i++) {
    					List<DirectedEdge> list = graph.get(onStack.get(i));
    					for (DirectedEdge de : list) {
    						if (de.w.equals(onStack.get(i + 1))) {
    							temp = temp * de.weight;
    							break;
    						}
    					}
    				}
    
    			}
    			result[index++] = temp;
    
    		}
    		return result;
    
    	}
    
    	public static boolean canReach(String var1, String var2, HashMap<String, List<DirectedEdge>> graph,
    			List<String> onStack) {
    		boolean found = false;
    		if (graph.containsKey(var1)) {
    			if (var1.equals(var2)) {
    				found = true;
    			} else {
    				for (DirectedEdge de : graph.get(var1)) {
    					if (de.v.equals(var2)) {
    						found = true;
    						break;
    					} else if (de.w.equals(var2)) {
    						onStack.add(de.w);
    						found = true;
    						break;
    					}
    					if (!onStack.contains(de.w)) {
    						onStack.add(de.w);
    						if (canReach(de.w, var2, graph, onStack)) {
    							return true;
    						}
    						onStack.remove(onStack.size() - 1);
    					}
    				}
    			}
    		}
    		return found;
    
    	}
    
    	public static class DirectedEdge {
    		private final String v; // edge source
    		private final String w; // edge target
    		private final double weight; // edge weight
    
    		public DirectedEdge(String v, String w, double weight) {
    			this.v = v;
    			this.w = w;
    			this.weight = weight;
    		}
    
    		public double weight() {
    			return weight;
    		}
    
    		public String from() {
    			return v;
    		}
    
    		public String to() {
    			return w;
    		}
    
    		@Override
    		public boolean equals(Object obj) {
    			// TODO Auto-generated method stub
    			DirectedEdge de2 = (DirectedEdge) obj;
    			return this.v.equals(de2.v);
    		}
    
    	}
    
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.