Graph Data Structure applications: solving a real-world problem

/ Data structures, Graph, Java / By

The graph data structure can be used to solve many real-world problems. In this post, you will see one of the graph data structure applications.

To solve the problem I’m showing you here, you can use the implementation for the undirected simple graph data structure.

Table of Contents

Graph ADT operations

When you want to use a data structure to solve problems, it is important to know the available operations.

Find below the general graph ADT operations defined as a Java interface:

public interface  IGraph<T> {
    void addNode(T node);
    void removeNode(T node);
    void addEdge(T node1, T node2) throws Exception;
    void removeEdge(T node1, T node2) throws Exception;
    List<T> adjacentsTo(T node) throws Exception;
    boolean areAdjacents(T node1, T node2) throws Exception;
    List<T> getNodes();
}

Now, using these operations, we will solve the following problem.

Modelling a Students friendship network: one of the graph data structure applications

Imagine a graph is used to model the friendship relations in a group of students. Create an app that:

  • given a name of a specific student, prints on the screen the names of all the friends of that student.
  • Is there a student that does not have any friend?
  • given the name of two students, are they friends?

You can implement the first task by using the method adjacentsTo from the graph data structure. Notice that this method returns all the adjacent nodes to the node used as a parameter.

In the second case, you can just apply the basic algorithm for searching.

Java code for the console app

Find below the implementation of the console app. Notice that there are comments in the code so you can understand better the example.

package com.RP.datastructures.graph;

import java.util.List;
import java.util.Scanner;

public class StudentFriendship {
    public static void main(String[] args) throws Exception {
        IGraph<String> graph = new UndirectedSimpleGraph<>(100);
        graph.addNode("student1");
        graph.addNode("student2");
        graph.addNode("student3");
        graph.addNode("student4");
        graph.addNode("student5");
        //Add the friendship relations
        graph.addEdge("student1", "student2");
        graph.addEdge("student1", "student3");
        graph.addEdge("student1", "student4");
        graph.addEdge("student2", "student3");

        Scanner scanner = new Scanner(System.in);
        //given a name of a specific student,
        // prints on the screen the names of
        // all the friends of that student.
	    System.out.println("Enter the name of the student: ");
        String name = scanner.nextLine();

        List<String> friends = graph.adjacentsTo(name);
        if (friends.size()>0){
            System.out.println("List of friends of the student: " + name);
            for (String friendName:friends) {
                System.out.println(friendName);
            }
        }
        else{
            System.out.println("The student does not have any friends.");
        }

        //Is there a student that does not have any friend?
        for (String student: graph.getNodes()) {
            if (graph.adjacentsTo(student).size()==0){
                System.out.println("The student " + student + " does not have friends");
            }
        }
        // given the name of two student, are they friends?
        System.out.println("Enter the name of the first student: ");
        String name1 = scanner.nextLine();
        System.out.println("Enter the name of the second student: ");
        String name2 = scanner.nextLine();
        if (graph.areAdjacents(name1, name2)){
            System.out.println("The two students are friends");
        }
        else {
            System.out.println("The two students are NOT friends");
        }
    }
}

Sample of output

In the picture below you can find an example of out. Notice this output is relative to the input (green text).

Sample of output for the example of using the graph data structure

Summary

In this post, you used a graph data structure to model a real-life situation: a student friendship network.

As you could see, you can use the methods defined in the Graph ADT to answer questions like, who are the friends of a certain student? which student does not have any friends, and so on. This is one of the many graph data structure applications.

For you to keep practicing, I recommend you extend the implementation provided above to answer the following question:

Related posts:

Undirected Simple Graph Data Structure: Implementation and Usage in Java.

H@ppy coding!