DADDiJkstra Qualification Review

[drewreed2005]

DADDiJkstra Review

KEY FEATURES

You can try them out on your own right now! Fully working demos linked below.

• Sign-up page
• Sign-in page
• Dijkstra Application
• Home Page
• About Page

All backend features are implemented through a deployed Springboot site.

HOW IT WORKS

We go over it in our About Page, but we'll go over it here, too.

Dijkstra Algorithm

Once a node map has been built on the frontend, its information on all nodes and edges (which is constantly updated) is converted to JSON to act as the body of a POST request. The JSON data is converted to an object in Java. It is referenced below as a GraphRequest object in the POST request code.

@PostMapping("/")
    @ResponseBody
    public ResponseEntity<Object> findShortestPath(@RequestBody GraphRequest request) { // HERE
        int[][] adjacencyList = request.getAdjacencyList();
        int source = request.getSource();
        int target = request.getTarget();
        HashMap<Integer,int[]> coordinates= request.getCoordinates();

        WeightedGraph weightedGraph = new WeightedGraph();
        weightedGraph.setGraphFromAdjacencyList(adjacencyList);
        Dijkstra.dijkstra(weightedGraph, source);
        ArrayList<Integer> shortestPath = Dijkstra.ReverseIteratePath(source, target);

        //TODO: implement storing the coordinates of the graph in the backend.
        // Usr usr = new Usr(email, password, name); //highScore, totalOfAllScores, numberOfScores);
        // repository.save(usr);
        return new ResponseEntity<>(shortestPath, HttpStatus.OK);
    }

You can see the full content for GraphRequest here.

public class GraphRequest {
    private int source;
    private int target;
    private int[][] adjacencyList;
    private HashMap<Integer,int[]> coordinates;

The Dijkstra algorithm itself is complicated, and it call all be seen on this page. Put simply, it parses through the weights of the connections between every node and calculates what path would be the fastest to get from one node to a target node.

Saved Graph Data

When a request to the Dijkstra algorithm is made, information including the adjacency list of all nodes and the coordinates of each node are sent to the backend in a separate request, which stores the graph's information on the signed-in user's database entry (see sign-up below). Shown below is the section of the Usr API Controller that handles this request. See code comments for more details.

@PutMapping("/update")
  public ResponseEntity<Object> updateUsr(@RequestBody CanvasUpdate canvasUpdate) {
    try {
        logger.debug("Received PUT request for updating user data: {}", canvasUpdate);
  
        // finding the user by email
        Usr usr = repository.findByEmail(canvasUpdate.getEmail());
        logger.debug("Found user: {}", usr);
  
        if (usr != null) {
            // creating a new hashmap to be added
            HashMap<String, Object> history = new HashMap<String, Object>();
            // adding data from the request body to the hashmap
            history.put("adjacencyList", canvasUpdate.getAdj());
            history.put("coords", canvasUpdate.getCoords());
            // add the canvas history with the built in user method
            usr.addCanvasHistory(history);
  
            // saving the updated user
            repository.save(usr);
  
            return new ResponseEntity<>("User updated successfully", HttpStatus.OK);
        } else {
            return new ResponseEntity<>("User not found", HttpStatus.NOT_FOUND);
        }
    } catch (Exception e) {
        e.printStackTrace();
        logger.error("Failed to update user", e);
        return new ResponseEntity<>("Failed to update user", HttpStatus.INTERNAL_SERVER_ERROR);
    }
  }

Like the Dijkstra algorithm, this method makes reference to a class that transforms the JSON body called CanvasUpdate. You can see its code here.

Sign-up Page

Using string data inputted by the user into input elements, we make a POST request to the backend that ensures that no duplicate/garbage data is being sent (including repeat emails or invalid emails/passwords). This request uses URL queries to be made.

// info taken from URL queries
@PostMapping( "/post")
public ResponseEntity<Object> postUsr(@RequestParam("email") String email,
                                        @RequestParam("password") String password,
                                        @RequestParam("name") String name) {
    // A person object WITHOUT ID will create a new record with default roles as student
    Usr usr = new Usr(email, password, name);
    usr.setPassword(passwordEncoder.encode(usr.getPassword())); // PASSWORD ENCRYPTION
    repository.save(usr);
    return new ResponseEntity<>(email +" is created successfully", HttpStatus.CREATED);
}

During this process, the user's password is encrypted. This was a necessary addition to the incomplete base Springboot Person class. Try the fetch for yourself to confirm it works!

Sign-in Page

The user puts in data again, and a POST request is made to /authenticate, which determines if there is a user in the database with the provided information. This is part of the JWT API Controller.

@PostMapping("/authenticate")
public ResponseEntity<?> createAuthenticationToken(@RequestBody Usr authenticationRequest) throws Exception {
    authenticate(authenticationRequest.getEmail(), authenticationRequest.getPassword());
    final UserDetails userDetails = usrDetailsService
    .loadUserByUsername(authenticationRequest.getEmail());
    final String token = jwtTokenUtil.generateToken(userDetails);
    final ResponseCookie tokenCookie = ResponseCookie.from("jwt", token)
    .httpOnly(true)
    .secure(true)
    .path("/")
    .maxAge(3600)
    .sameSite("None; Secure")
    // .domain("example.com") // Set to backend domain
    .build();
    return ResponseEntity.ok().header(HttpHeaders.SET_COOKIE, tokenCookie.toString()).build();
}

The jwt cookie that is sent carries over to the application page, which then accesses the data to browse past node maps. This allows the results of previous algorithm uses to be seen again.

WHY IT MATTERS

DADDiJkstra's purpose is to teach about graph theory and algorithms. We felt it imperative, given the prevalence of algorithms in computer science, that we provide a resource to visualize the process of algorithmic pathfinding. We chose Dijkstra because it acts as the basis for other, more common pathfinding algorithms like the A* algorithm.

By providing an easy-to-use resource that implements the algorithm in action, we allows fellow students and others with some interest in computer science to see a window into the more complicated applications possible with algorithmic pathfinding.

Peer Reviews

Grader	Score
Tay Kim	8.8/9
Tirth Thakkar	8.8/9
Emaad Mir	8.73/9
Luna Iwazaki	9/9
Vivian Ni	8.82/9
Vardaan Sinha	8.9/9
John Mortensen	8.37/9
Vakkala Sai Pranavi	8.55/9
Ellie Rozenkrantz	8.46/9
Average	8.743

Overall Feedback:

We were somewhat scrambling towards the end, which affected our presentation at N@TM. We could've prevented this but doing more work in the feature week to have a more solid foundation for the direction of our project. Doing this would eliminate most of the variables that would confound our team's development.

Mostly three people carried, but we needed more attention on our project. We want to maintain focus and attention on the project. We definitely need to fix this in preparation for the next two trimesters. We want to develop habits to remain engaged in coding.

---

Each Team provides an ISSUE for scoring their Project and makes a link to it on their N@tM Sign Up page. Make sure you start with a self grading summary.Criteria/Key Features/Technicals: Frontend, APIs, Backend, Database
3.6 to 4 pts. HOOK! Key features achieved (shown in running demo to graders), 1 minute show
3.6 to 4 pts. KNOWLEGE, HOW IT IS MADE! Key features blogged (shown in demo time to graders), 2 minute show
0.6 to 1 pt. VALUE. Most useful or valuable aspect of project.SELF and CROSS OVER GRADERS PROVIDE TOTAL, 9 of 10 is highest.