Graph Implementation Example in Java

Posted by Marta on March 22, 2022 Viewed 4254 times

This article you will see a graph implementation example in Java from scratch. You will learn how to create and use a graph data structure in Java, practicing with a real exercise that I have seen in many interview processes.

The example is an exciting and challenging problem to solve. Firstly I will introduce the problem itself and a possible way to solve it in Java.

Watch this tutorial in Youtube

In case you are not familiar with the graph data structure, check out this article for a brief introduction.

Table of Contents

The assignment

A delivery service company creates a system that will plan a route for a delivery truck to deliver customer orders. The planner will create a delivery area for each order, which is abstracted as a grid. The challenge is to write an algorithm to determine the distance required for the truck to deliver the order.

The delivery area is represented as a two-dimensional grid of integers where:

1 represents an accessible area
0 represents a non-accessible area
2 represents the order destination

This problem is one of my favorite java assignments to practice. An excellent graph implementation example in Java of how using the correct data structure can turn a seemingly complex problem into something much more straightforward.

Some stuff you should consider before starting. The truck can’t leave the grid and should get to the order destination through the accessible areas. And the truck can move one cell up, down, left, or right at a time.

Here are some examples of different cases with the inputs and the corresponding outputs:

  Example 1
  grid = [[1,1,0],[0,1,2][0,1,1]]
  Output: 5
  
  Example 2
  grid = [[1,1,1,1],[0,1,0,1],[0,1,0,1],[0,1,1,0],[0,1,2,1]]
  Output: 6

I will advise you to pause here and try to solve this problem yourself before checking the solution.

Warning. It is a challenging problem, so don’t worry if it takes you 1 or 2 hours to solve, or even more if you haven’t practiced solving coding problems for a while. That is entirely normal.

To give you a hint, the key to solve this problem is choosing the correct data structure. If you select a data structure, and your code starts becoming complex, that might be a sign; the data structure is not quite right.

Solution

The best solution to this problem is using a java graph implementation. In general, a graph is the right solution for any situation where you need to navigate a grid.

Plus, I will advise you to solve this problem following a test-driven approach, which means defining the function signature to do the calculation without writing the code. Then write some tests. And last, writing the code. Why writing tests? It will be much easier and quicker to check that things are working correctly.

Our solution will have two classes: Cell class representing each matrix cell, and DeliveryArea representing the area the truck should navigate. See the skeleton below, just the class and the method signatures. We will complete the implementation in the next section.

Filename: Cell.java

public class Cell {
    public int row;
    public int col;

    public Cell(int row, int col){
        this.row = row;
        this.col = col;
    }

    public String hashKey(){
        return String.valueOf(this.row)+String.valueOf(this.col);
    }
}

Filename: DeliveryArea.java

import java.util.List;
import java.util.Map;

public class DeliveryArea {

    private final static int ACCESSIBLE_CELL = 1;
    private final static int NON_ACCESSIBLE_CELL = 0;
    private final static int DESTINATION = 2;

    public int[][] matrix;

    public DeliveryArea(int[][] matrix){
        this.matrix = matrix;
    }
    private Map<String, List<Cell>> buildGraph(){
        return null;
    }
    public List<Cell> findRoute(){
        return null;
    }
}

As you can do there are two methods without code. The buildGraph method which will return a graph data structure derived from the matrix. And also we will code the method findRoute, which will contain the algorithm that will work out the path to reach the destination from the starting point (0,0).

Write Graph Implementation in Java

First, we will build a graph like the one below, where each graph node represents a grid cell, and the lists linked to the node represents the connected cells. This representation allows us to navigate the nodes that are connected quickly and ignore the empty cells.

To do so, I will loop through every cell, ignoring the cells containing 0, since they are not accessible. For each, I will check if the cells around are accessible. Those cells will be the adjacent nodes. Then I will create a list containing all adjacent nodes and associate it with the node itself.

See how to implement this in Java below. You should paste the code below inside the DeliveryArea.java file:

   public Map<String, List<Cell>> buildGraph(){
        // loop through every cell and
        //      if it s accessible:
        //          - add entry in the graph
        //          - check the cell around to see if they are connected
        //                  ( don't check the cells beyond the matrix limits)
        Map<String, List<Cell>> graph = new HashMap<>();
        for( int row=0;row<matrix.length;row++) {
            for(int col=0;col<matrix[0].length;col++){
                if(matrix[row][col]!= NON_ACCESSIBLE_CELL){
                    Cell currentCell = new Cell(row,col);
                    String currentCellHash = currentCell.hashKey();

                    if(graph.get(currentCellHash)==null)
                        graph.put(currentCell.hashKey(),new ArrayList<>());

                    List<Cell> existingAdjacentCells = graph.get(currentCellHash);

                    if(row -1 >= 0){ // this means the cell above is inside the matrix
                        if(matrix[row-1][col]!=NON_ACCESSIBLE_CELL){
                            existingAdjacentCells.add(new Cell(row-1,col));
                        }
                    }

                    if(col-1 >= 0) { // this means the cell on the left col is inside the matrix
                        if(matrix[row][col-1]!=NON_ACCESSIBLE_CELL){
                            existingAdjacentCells.add(new Cell(row, col-1));
                        }
                    }

                    if(row+1<matrix.length){ // the cell below is inside the matrix
                        if(matrix[row+1][col]!=NON_ACCESSIBLE_CELL){
                            existingAdjacentCells.add(new Cell(row+1,col));
                        }
                    }

                    if(col+1 < matrix[0].length) { //the cell to the right is within the matrix
                        if(matrix[row][col+1]!=NON_ACCESSIBLE_CELL){
                            existingAdjacentCells.add(new Cell(row,col+1));
                        }
                    }

                }
            }
        }
        return graph;
    }

Keep moving to your destination

Now that we built the graph, the truck can start moving to the destination!

The code will need to check if we got to our destination; in other words, check if the cell where the truck is positioned is equal to 2. If not, we will move to the next accessible cells, meaning any of the connected nodes. To avoid moving in circles or move to cells that we already visited, we will create a list to track the visited cells.

You should paster the code below inside the DeliveryArea.java, inside the findRoute method:

 public List<Cell> findRoute(){

        Map<String, List<Cell>> graph = buildGraph();

        Cell currentCell = new Cell(0,0);
        List<Cell> alreadyVisitedCells = new LinkedList<>();
        alreadyVisitedCells.add(currentCell);
        List<Cell> finalPath = new LinkedList<>();
        finalPath.add(currentCell);

        while(matrix[currentCell.row][currentCell.col]!=DESTINATION){ // if the truck is not ar the destination
            Cell nextCellToMove = findNextAccesibbleCell(graph, currentCell, alreadyVisitedCells);

            if(nextCellToMove==null){
                // the route is blocked so, go back
                currentCell = alreadyVisitedCells.get(alreadyVisitedCells.size()-2);
                finalPath.remove(finalPath.size()-1);
            }else{
                alreadyVisitedCells.add(nextCellToMove);
                finalPath.add(nextCellToMove);
                currentCell = nextCellToMove;
            }
        }


        return finalPath;
    }

And here is the method to get the next accessible cell. In the case of no accessible cell, it will return null.

 private Cell findNextAccesibbleCell(Map<String,List<Cell>> graph,Cell currentCell, List<Cell> alreadyVisitedCells){
        for (Cell adjacentCell: graph.get(currentCell.hashKey())){
            if(!alreadyVisitedCells.contains(adjacentCell)){
                return adjacentCell;
            }
        }
        return null;
    }

Conclusion

To summarise, in this article we have seen step by step a graph implementation example in Java. Specifically we have seen how to navigate a matrix from point A to point B.

I hope this short article was useful and clarifies how to navigate a graph. Keep in mind the graph structure fits well for any problem where there are entities and relationships between those entities. I encourage you to keep doing java assignments for practicing and developing your programming skills.

I hope you enjoy this tutorial, and thank you so much for reading and supporting this blog! Happy coding!