I want to write up a shortest as well as optimal path program for indoor navigation for people with disabilities. For the initial part of the assignment i wish to test my program through graph traversal. My application is supposed to take in a user group then based on that give the appropriate path. The edges are supposed to have 2 values. One for distance and one for quality. I.e distance for path and quality could be set as is it wheelchair accessible or not.
Want program to take in graph with 2 values for edge (weight, quality). Remove all paths going through stairs immediately. Regardless of the distance of going through stairs. Then i want program to check the shortest path among the wheelchair accessible path to see if any is available or not. I want a quality value of 1 for accessible and 2 for inaccessible. So if there is a long path going through an elevator with quality 1 then that path should be taken otherwise the shortest path with quality 1 should be displayed. All edges as W are elevators and S are stairs
What I want in the code is this. A graph which has 2 things defined on its edge (weight, quality) new Graph.Edge("b", "e", 4,1),
Weight could be for the distance but the quality decides the optimal route. I.e. if this is the easiest way to reach there even though it is short. All nodes indicating W indicate elevators. All nodes S are stairs. What I want the code to do is build the map using both defined edges (dist, qual) Then I want all routes going through stairs removed. (The reason they are there is because later on I need this to accommodate abled people too so the program would work in different user groups) Right now I am only bothered with the wheelchair accessibility.
This is how the program should go: Remove all stair nodes from being browsed through. Find shortest path to destination going through elevator (W) only Compare that path to the second value quality- new Graph.Edge("b", "e", 4,1), If the quality is = 1 then that is the optimal path to take is ok. If the quality is = 2 then give the longer path instead. If there are 2 paths with the same weight then obviously give the path with quality =1 If both have quality = 1 then just give the one going through least nodes.'
The below code that i have gives a shortest distance using only the distance value and now i am trying to modify that to suit the above criteria but have no idea how to go about it.
import java.util.HashMap;
import java.util.Map;
import java.util.NavigableSet;
import java.util.TreeSet;
public class Dijkstra {
private static final Graph.Edge[] GRAPH = {
new Graph.Edge("a", "b", 2,1),
new Graph.Edge("a", "w", 5,1),
new Graph.Edge("a", "e", 5,2),
new Graph.Edge("a", "d", 7,1),
new Graph.Edge("a", "s", 6,1),
new Graph.Edge("b", "c", 3,1),
new Graph.Edge("b", "e", 4,1),
new Graph.Edge("b", "w", 3,2),
new Graph.Edge("b", "s", 4,2),
new Graph.Edge("b", "d", 6,1),
new Graph.Edge("c", "e", 4,1),
new Graph.Edge("c", "w", 1,1),
new Graph.Edge("w", "c", 1,1),
new Graph.Edge("c", "s", 2,2),
new Graph.Edge("c", "d", 3,1),
new Graph.Edge("d", "w", 2,2),
new Graph.Edge("d", "s", 1,1),
new Graph.Edge("d", "e", 3,1),
new Graph.Edge("e", "w", 4,2),
new Graph.Edge("e", "s", 5,1),
new Graph.Edge("w", "h", 5,1),
new Graph.Edge("h", "w", 5,2),
new Graph.Edge("s", "h", 1,1),
new Graph.Edge("h", "i", 10,1),
new Graph.Edge("i", "h", 10,1),
new Graph.Edge("i", "g", 5,1),
new Graph.Edge("h", "g", 11,1),
new Graph.Edge("h", "j", 12,1),
new Graph.Edge("i", "j", 3,1),
new Graph.Edge("g", "j", 2,2),
};
private static final String START = "d";
private static final String END = "h";
public static void main(String[] args) {
Graph g = new Graph(GRAPH);
g.dijkstra(START);
g.printPath(END);
//g.printAllPaths();
}
}
class Graph {
private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges
/** One edge of the graph (only used by Graph constructor) */
public static class Edge {
public final String v1, v2;
public final int dist;
private int qual;
public Edge(String v1, String v2, int dist, int qual) {
this.v1 = v1;
this.v2 = v2;
this.dist = dist;
this.qual = qual;
}
}
/** One vertex of the graph, complete with mappings to neighbouring vertices */
public static class Vertex implements Comparable<Vertex> {
public final String name;
public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
private Object qual;
public Vertex previous = null;
public final Map<Vertex, Integer> neighbours = new HashMap<>();
public Vertex(String name) {
this.name = name;
}
private void printPath() {
if (this == this.previous) {
System.out.printf("%s", this.name);
} else if (this.previous == null) {
System.out.printf("%s(unreached)", this.name);
} else {
this.previous.printPath();
System.out.printf(" -> %s(%d)", this.name, this.dist, this.qual);
}
}
@override
public int compareTo(Vertex other) {
return Integer.compare(dist, other.dist);
}
}
/** Builds a graph from a set of edges */
public Graph(Edge[] edges) {
graph = new HashMap<>(edges.length);
//one pass to find all vertices
for (Edge e : edges) {
if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
}
//another pass to set neighbouring vertices
for (Edge e : edges) {
graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
// graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph
}
}
/** Runs dijkstra using a specified source vertex */
public void dijkstra(String startName) {
if (!graph.containsKey(startName)) {
System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
return;
}
final Vertex source = graph.get(startName);
NavigableSet<Vertex> q = new TreeSet<>();
// set-up vertices
for (Vertex v : graph.values()) {
v.previous = v == source ? source : null;
v.dist = v == source ? 0 : Integer.MAX_VALUE;
q.add(v);
}
dijkstra(q);
}
/** Implementation of dijkstra's algorithm using a binary heap. */
private void dijkstra(final NavigableSet<Vertex> q) {
Vertex u, v;
while (!q.isEmpty()) {
u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable
//look at distances to each neighbour
for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
v = a.getKey(); //the neighbour in this iteration
final int alternateDist = u.dist + a.getValue();
if (alternateDist < v.dist ) { // shorter path to neighbour found
q.remove(v);
v.dist = alternateDist;
v.previous = u;
q.add(v);
}
}
}
}
/** Prints a path from the source to the specified vertex */
public void printPath(String endName) {
if (!graph.containsKey(endName)) {
System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
return;
}
graph.get(endName).printPath();
System.out.println();
}
/** Prints the path from the source to every vertex (output order is not guaranteed) */
public void printAllPaths() {
for (Vertex v : graph.values()) {
v.printPath();
System.out.println();
}
}
}
