Advertisement
Guest User

Untitled

a guest
Dec 6th, 2019
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.49 KB | None | 0 0
  1. /**
  2.      * A method that returns a Java Iterator that contains the list of Node objects that
  3.      * states a path from the starting Node to the destination Node if such path exists.
  4.      * The method also considers the amount of money the traveling car initial has and will
  5.      * have during its travels. If such path doesn't exist, it will simply return null
  6.      *
  7.      * @param start                     the integer value that is the name of the Node object the car will
  8.      *                                  start at
  9.      * @param destination               the integer value that is the name of the Node object the car will
  10.      *                                  end at
  11.      * @param initialMoney              the integer value that is the initial amount of money the car will
  12.      *                                  start with
  13.      * @return finalPath.iterator()     the Java Iterator that holds the pathway of Nodes to get from the
  14.      *                                  starting Node to the destination Node
  15.      * @throws GraphException           when a specific Node is not in the Graph
  16.      */
  17.     public Iterator findPath(int start, int destination, int initialMoney) throws GraphException {
  18.         // Sets the currentNode as the starting Node and sets the money the car current has
  19.         Node currentNode = roadGraph.getNode(start);
  20.         int money = initialMoney;
  21.  
  22.         // marks the currentNode to true to avoid going into an infinite loop
  23.         currentNode.setMark(true);
  24.         // adds the currentNode into the arrayList variable called finalPath
  25.         finalPath.add(currentNode);
  26.        
  27.         // Checks if the name of the Node the method is currently on is the same as the name of the
  28.         // destination Node. If true, ends the recursion, sets the boolean variable to state that the
  29.         // a path has been detected and is ready to empty the execution stack
  30.         if (start == destination) {
  31.             pathFinish = true;
  32.             return finalPath.iterator();
  33.         }
  34.         // Otherwise, continue
  35.         else {
  36.             // Retreive a Java Iterator that holds any available edges with the current node the method
  37.             // is on
  38.             Iterator availPath = roadGraph.incidentEdges(currentNode);
  39.            
  40.             // A while loop that continues until there aren't any Edge objects to look through
  41.             while (availPath.hasNext()) {
  42.                 // Sets up a temporary Edge object to check to do a recursive call and see if it leads to
  43.                 // the destination Node
  44.                 Edge tempEdge = (Edge) availPath.next();
  45.                 Node nextNode = tempEdge.secondEndpoint();
  46.                
  47.                 // Checks if the Node on the other end of the Edge it is temporarily checking is marked or
  48.                 // not. If it isn't, it continues to go and check what kind of Edge it is to adjust the money
  49.                 // the car will subsequently hold
  50.                 if (nextNode.getMark() == false) {
  51.                     if (tempEdge.getType() == 1 && money - this.toll >= 0)
  52.                         findPath(nextNode.getName(), destination, money - this.toll);
  53.                     else if (tempEdge.getType() == -1)
  54.                         findPath(nextNode.getName(), destination, money + this.gain);
  55.                     else if (tempEdge.getType() == 0)
  56.                         findPath(nextNode.getName(), destination, money);
  57.  
  58.                     // Checks if a path has been made, and if true, simply return and empty the execution stack
  59.                     if (pathFinish == true)
  60.                         return finalPath.iterator();
  61.                 }
  62.             }
  63.             // From here, it indicates that a path was not found in the currentNode it was on and must be
  64.             // removed from the finalPath arrayList and is ready to be unmarked for future use
  65.             finalPath.remove(currentNode);
  66.             currentNode.setMark(false);
  67.            
  68.             // Checks if the finalPath arrayList is empty and if so, return null
  69.             if (finalPath.isEmpty())
  70.                 return null;
  71.             // Otherwise return the Java Iterator
  72.             return finalPath.iterator();
  73.         }
  74.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement