The graph data structure has many applications. This post will teach you how to use it to solve a real-world problem.
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 an interface in C#:
public interface IGraph<T>{
void addNode(T node);
void removeNode(T node);
void addEdge(T node1, T node2);
void removeEdge(T node1, T node2);
List<T> adjacentsTo(T node);
bool areAdjacents(T node1, T node2);
List<T> getNodes();
}
Now, using these operations, we will solve the following problem.
Problem 1: Friendship relations in a group of students
Imagine that a graph is used to model friendship relations in a group of students. Create a console application 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 friends?
- 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.
C# 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.
class Person {
private string name;
public String Name{
get => name;
set => name = value;
}
public Person(string name) {
this.name = name;
}
}
class Program
{
static void Main(string[] args){
IGraph<Person> graph = new UndirectedSimpleGraph<Person>(10);
Person p1 = new Person("John");
Person p2 = new Person("Jane");
Person p3 = new Person("Smith");
Person p4 = new Person("Rose");
//Adding nodes that represent each student in the network
graph.addNode(p1);
graph.addNode(p2);
graph.addNode(p3);
graph.addNode(p4);
//Adding the relations between the students
graph.addEdge(p1, p2);
graph.addEdge(p1, p3);
graph.addEdge(p1, p4);
graph.addEdge(p2, p3);
//ussing adjacentsTo method to find out who
//are the friends of john
Console.WriteLine("John friends:");
List<Person> pList = graph.adjacentsTo(p1);
foreach (Person p in pList) {
Console.WriteLine(p.Name);
}
//ussing areAdjacents method to find out if
//Jane and Smith are friends
Console.WriteLine("Are Jane and Smith friends?");
if (graph.areAdjacents(p2, p3))
Console.WriteLine("Jane and Smith are friends");
else
Console.WriteLine("Jane and Smith are not friends");
//ussing areAdjacents method to find out if
//Jane and Rose are friends
Console.WriteLine("Are Jane and Rose friends?");
if (graph.areAdjacents(p2, p4))
Console.WriteLine("Jane and Rose are friends");
else
Console.WriteLine("Jane and Rose 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.
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 ADT Graph to answer questions like, who are the friends of a certain student? Which student does not have any friends, and so on.
For you to keep practicing, I recommend you extend the implementation provided above to answer the following question:
- Print the name of the student that has more friends. Hint: use the maximum basic algorithm.
H@ppy coding!
Related posts:
