You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
77 lines
2.9 KiB
77 lines
2.9 KiB
|
|
|
|
import java.util.List;
|
|
import java.util.LinkedList;
|
|
import java.util.HashMap;
|
|
import java.util.Queue;
|
|
import java.util.Stack;
|
|
import java.util.Set;
|
|
import java.util.HashSet;
|
|
|
|
/*
|
|
* SD2x Homework #6
|
|
* Implement the methods below according to the specification in the assignment description.
|
|
* Please be sure not to change the signature of any of the methods!
|
|
*/
|
|
|
|
public class GraphUtils {
|
|
|
|
public static int minDistance(Graph graph, String src, String dest) {
|
|
if(graph == null || src == null || dest == null) return -1;
|
|
if(!graph.containsElement(src) || !graph.containsElement(dest)) return -1;
|
|
if(src.equals(dest)) return 0;
|
|
|
|
Queue<Node> toExplore = new LinkedList<Node>();
|
|
HashMap<Node,Integer> explored = new HashMap<Node, Integer>();
|
|
toExplore.add(graph.getNode(src));
|
|
explored.put(graph.getNode(src),0);
|
|
while(!toExplore.isEmpty()){
|
|
for(Edge e : graph.getNodeEdges(toExplore.poll())){
|
|
if(e.getDestination().getElement().equals(dest)) return explored.get(e.getSource()) + 1;
|
|
if(explored.containsKey(e.getDestination())) continue;
|
|
toExplore.add(e.getDestination());
|
|
explored.put(e.getDestination(), explored.get(e.getSource()) + 1);
|
|
}
|
|
}
|
|
return -1;
|
|
}
|
|
|
|
|
|
public static Set<String> nodesWithinDistance(Graph graph, String src, int distance) {
|
|
HashMap<String, Integer> nodes = new HashMap<String, Integer>();
|
|
Queue<Node> toExplore = new LinkedList<Node>();
|
|
|
|
if(graph == null || src == null) return null;
|
|
if(!graph.containsElement(src)) return null;
|
|
if(distance < 1) return null;
|
|
nodes.put(src, 0);
|
|
toExplore.add(graph.getNode(src));
|
|
|
|
while(!toExplore.isEmpty()){
|
|
for(Edge e : graph.getNodeEdges(toExplore.poll())){
|
|
if(nodes.containsKey(e.getDestination().getElement())) continue;
|
|
if(nodes.get(e.getSource().getElement()) == distance) continue;
|
|
nodes.put(e.getDestination().getElement(), nodes.get(e.getSource().getElement()) + 1);
|
|
toExplore.add(e.getDestination());
|
|
}
|
|
}
|
|
nodes.remove(src);
|
|
return nodes.keySet();
|
|
}
|
|
|
|
|
|
public static boolean isHamiltonianPath(Graph g, List<String> values) {
|
|
if(g == null || values == null) return false;
|
|
if(values.isEmpty()) return false;
|
|
if(!values.get(0).equals(values.get(values.size() - 1))) return false;
|
|
if(g.getNumNodes() != values.size() - 1) return false;
|
|
HashSet<String> visited = new HashSet<String>();
|
|
visited.add(values.get(0));
|
|
for(int i = 1; i < values.size() - 1; i++){
|
|
if(visited.contains(values.get(i))) return false;
|
|
if(!g.getNodeNeighbors(g.getNode(values.get(i))).contains(g.getNode(values.get(i + 1)))) return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
}
|