2
$\begingroup$

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();
      }
   }

}

$\endgroup$

closed as off-topic by Yuval Filmus, David Richerby, Juho, D.W., André Souza Lemos Jun 1 '15 at 1:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – Yuval Filmus, David Richerby, Juho, D.W., André Souza Lemos
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Looks like a programming exercise at this point. $\endgroup$ – Yuval Filmus May 30 '15 at 5:29
  • 2
    $\begingroup$ I think the OP has a formalization problem, but is not very good at explaining it though he is clearly making considerable effort to be as precise as he can. If he were able to do better, he would probably also be able to solve it by himself. His trouble explaining also causes him to get mixed up. I summarize in the next comment what I understand. $\endgroup$ – babou May 30 '15 at 10:32
  • 3
    $\begingroup$ There is a graph of existing paths in a place (building) to be visited. The edges have two labels: distance (numbers that add) and accessibility (booleans that are and-ed). Given two nodes of the graph (2 places in the building), you want the shortest path that is accessible if any, else the shortest of non-accessile one. Does this summarize your question? A more sophisticated version would be to look for the shortest path with minimal number of unaccessible edges. Do I understand your problem correctly? $\endgroup$ – babou May 30 '15 at 10:34
  • 1
    $\begingroup$ If your question is only about the way to program this in Java or another language, that is off topic on this site. We only work on "abstract algorithms", not on programming them ... except if is to study a programming methodology in itself, which is not the case here. $\endgroup$ – babou May 30 '15 at 10:41
  • $\begingroup$ The simplest algorithm is: (1) remove all inaccessible edges and do a shortest-path search (e.g., with Dijkstra's); (2) if that doesn't find a path, put back in all the inaccessible edges and do another shortest-path search (e.g., with Dijkstra's). From here it's just a matter of programming, and as others say, programming/implementation is out of scope for this site. $\endgroup$ – D.W. May 30 '15 at 15:57
3
$\begingroup$

What you may want is the use a "metric" on a pair of values, such that one value always has precedence over the other. In this way, you actually consider any length of stairs to be worse than any path without stairs, but you can discriminate also on the length of stairways.

The way you do this is to mesure a distance as a pair $[w,c]$, where $w$ stands for walk and $c$ stands for climb. The value $w$ can be a distance in meters, and the value of $c$ can be the number of steps to climb, or any other measure of inaccessibility. This is the same as weight and quality suggested by the question, but it seems a terminology closer to the problem at hand.

Then you define:

  • $[w,c] < [w',c']\;\;$ iff $\;\;c<c' \;\vee\; (c=c' \wedge w<w')$, which is just lexicographic order on pairs of values.

  • $[w,c] + [w',c'] = [ w+w', c+c']$

Then you can just use the pairs as measure of distance in Dijkstra's algorithm, to get the most convenient path.

If you do not want to distinguish degrees of inaccessibility, you can take the value of $c$ in the set $\{0,1\}$, with $1+1=1$ for the $c$ component of the pair, which is the same as using a boolean value.

There are other variations, depending on what you want to take into account, and how. For example, you might consider that all stairs are equivalent, independently of the number of steps. Or that some stairs are more difficult for the same number of steps.

There is a coding trick that you can also use, if you know that you will never exceed a given walking distance $D$ on any path that you ever follow. Then you can encode $w,c$ as $w+cD$ and use that as distance. But the computational gain is probably not worth it, and it could lead you to bugging your algorithm as it evolves.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.