Graph Data Structure is an important tool to model real-world situations. In this post, you will learn one of the implementations of the TDA and an example of how to use it.
To use a graph, you first have to understand when and why you can use it. As in other topics, you will find in this blog, the approach is to use these (and other) concepts to model real-life situations.
Table of Contents
- Graph Definition
- ADT Graph
- ADT Graph Data Structure Implementation
- Example of usage of the Graph Data Structure
- Summary
Graph Definition
“A graph G = (V,E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges. Each edge has either one or two vertices associated with it, called its endpoints. An edge is said to connect its endpoints.” Discrete Mathematics and its applications by Rosen.
The above is the mathematical definition of a graph. It is important to know and understand the definitions, especially when you are using mathematical models.
In the case of graphs, like many other topics in programming, you use the mathematical definitions of the model as well as the operations.
Something that you might not get from the definition, but it is very important is that you can use a graph to model relationships among concepts.
The set of vertices are the concepts you want to model. Those concepts can be cities, computers, people, etc.
After that, you can use edges to model the relations between each pair of concepts. For instance, an edge can represent the connection between two cities and the distance between them. Some other examples are as follows:
- To represent if two people are friends or not (social network)
- Are two computers connected? (Computer network)
- Distances from point A to point B in a city (road network)
- and many more
These are just a few examples. Whenever you have concepts (also objects) and relations between them, you can use a graph to model that situation.
ADT Graph
As in the case of the ADT Tree, we first define the ADT Graph with the common operations you can use.
import java.util.List;
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();
}
The previous operations are enough for you to start diving in this wonderful topic: Modelling situations using the ADT Graph.
ADT Graph Data Structure Implementation
You can implement a graph in different ways, two main ways are studied in most Computer Science courses:
- Adjacency matrix
- Adjacency list
In this case, you will see the adjacency matrix implementation.
The adjacency matrix implementation structures the information of the graph in two variables: a list of nodes and a matrix. The values of the matrix are 0s or 1s, or true or false values. These values indicate whether one node is connected (1 or true) or not (0 or false).
We also have to consider that there are different types of graphs: directed, undirected, simple graphs, etc.
In this case, I show the implementation of a simple undirected graph. This type of graph has the following properties:
- There can be only one edge between two nodes.
- If node1 is connected to node2 through an edge, then node 2 is connected to node 1 through the same edge. Think of this as a two-way street.
import java.util.ArrayList;
import java.util.List;
public class UndirectedSimpleGraph<T> implements IGraph<T>{
List<T> nodes;
boolean adjacencyMatrix[][];
UndirectedSimpleGraph(int maxNumberOfNodes){
nodes = new ArrayList<>(maxNumberOfNodes);
adjacencyMatrix = new boolean[maxNumberOfNodes][maxNumberOfNodes];
for (int i=0; i<100; i++){
for (int j=0; j<100; j++){
adjacencyMatrix[i][j]=false;
}
}
}
@Override
public void addNode(T node) {
nodes.add(node);
}
@Override
public void removeNode(T node) {
nodes.remove(node);
}
@Override
public void addEdge(T node1, T node2) throws Exception {
validateNodes(node1, node2);
setEdge(node1, node2, true);
}
@Override
public void removeEdge(T node1, T node2) throws Exception {
validateNodes(node1, node2);
setEdge(node1, node2, false);
}
private void validateNodes(T node1, T node2) throws Exception {
if (node1==node2) throw new Exception("Simple graphs cannot have loops");
if (!nodes.contains(node1) || !nodes.contains(node2)){
throw new Exception("One of the nodes is not on the graph");
}
}
private void setEdge(T node1, T node2, boolean value) {
int row = nodes.indexOf(node1);
int col = nodes.indexOf(node2);
adjacencyMatrix[row][col] = value;
adjacencyMatrix[col][row] = value;
}
@Override
public List<T> adjacentsTo(T node) throws Exception {
if (!nodes.contains(node)){
throw new Exception("The node is not on the graph");
}
List<T> adjacents = new ArrayList<>();
int row = nodes.indexOf(node);
for (int i = 0; i< nodes.size(); i++){
if (adjacencyMatrix[row][i]){
adjacents.add(nodes.get(i));
}
}
return adjacents;
}
@Override
public boolean areAdjacents(T node1, T node2) throws Exception {
validateNodes(node1, node2);
int row = nodes.indexOf(node1);
int col = nodes.indexOf(node2);
return adjacencyMatrix[row][col];
}
@Override
public List<T> getNodes() {
return nodes;
}
}
Now that we have an implementation of the ADT Graph, let’s see an example of how to use it.
Example of usage of the Graph Data Structure
Now, you will see an example of a console application that shows how to represent a graph of three cities, add connections among them, remove connections and see how many cities are connected to a given city.
import java.util.List;
public class GraphExample1 {
public static void main(String[] args) throws Exception {
IGraph<String> graph = new UndirectedSimpleGraph<>(100);
graph.addNode("city1");
graph.addNode("city2");
graph.addNode("city3");
graph.addEdge("city1", "city2");
System.out.println(graph.areAdjacents("city1","city2"));
graph.removeEdge("city1","city2");
System.out.println(graph.areAdjacents("city1","city2"));
graph.addEdge("city1", "city2");
graph.addEdge("city1", "city3");
List<String> adjacents = graph.adjacentsTo("city1");
System.out.println("city1 adjacents count: " + adjacents.size());
for (String city : adjacents){
System.out.println(city);
}
}
}
Summary
The ADT Graph can help us to model situations that involve several concepts and the relations between them.
It is widely used to model different types of networks: road networks, social networks, etc.
You can use different types of graphs to model different situations. How to know which one to use?
You must follow the mathematical definitions of each type of graph and choose the one that is appropriate to model your situation.
Test your knowledge:
- Transform the usage example in this post to represent some of the cities of your country. Use the Console Application to print if the cities are connected.
- Create a graph that models your friendship network. Implement the Console Application and print some data using the operations defined in the ADT Graph.
Leave a comment below about what you did.
H@ppy coding!
Related content: