The Graph Data Structure is widely used in programming. 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.
Let’s now see the definition.
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 mathematics is involved.
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 whether two cities are connected 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
We first define the Abstract Data Type (ADT) Graph with the common operations you can use.
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();
}
The previous operations defined in this interface, are enough to get you started in this wonderful topic: Modelling situations using the ADT Graph.
ADT Graph Implementation in C#
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 must 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. You can think of this as a two-way street.
public class UndirectedSimpleGraph<T> : IGraph<T>{
List<T> nodes;
bool [,] adjacencyMatrix;
public UndirectedSimpleGraph(int maxNumberOfNodes){
nodes = new List<T>(maxNumberOfNodes);
adjacencyMatrix = new bool[maxNumberOfNodes,maxNumberOfNodes];
for (int i = 0; i < maxNumberOfNodes; i++){
for (int j = 0; j < maxNumberOfNodes; j++){
adjacencyMatrix[i,j] = false;
}
}
}
public void addEdge(T node1, T node2){
validateNodes(node1, node2);
setEdge(node1, node2, true);
}
public void addNode(T node){
nodes.Add(node);
}
public bool areAdjacents(T node1, T node2){
validateNodes(node1, node2);
int row = nodes.IndexOf(node1);
int col = nodes.IndexOf(node2);
return adjacencyMatrix[row,col];
}
public List<T> getNodes(){
return nodes;
}
public void removeEdge(T node1, T node2)
{
validateNodes(node1, node2);
setEdge(node1, node2, false);
}
public void removeNode(T node)
{
nodes.Remove(node);
}
public List<T> adjacentsTo(T node)
{
if (!nodes.Contains(node)){
throw new Exception("The node is not on the graph");
}
List<T> adjacents = new List<T>();
int row = nodes.IndexOf(node);
for (int i = 0; i < nodes.Count(); i++){
if (adjacencyMatrix[row,i]){
adjacents.Add(nodes[i]);
}
}
return adjacents;
}
private void validateNodes(T node1, T node2){
if (node1.Equals(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, bool value){
int row = nodes.IndexOf(node1);
int col = nodes.IndexOf(node2);
adjacencyMatrix[row,col] = value;
adjacencyMatrix[col,row] = value;
}
}
Now that we have an implementation of the ADT Graph, let’s see an example of how to use it.
Example of usage
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.
UndirectedSimpleGraph <string> graph = new UndirectedSimpleGraph<string>(3);
graph.addNode("city1");
graph.addNode("city2");
graph.addNode("city3");
graph.addEdge("city1", "city2");
Console.WriteLine(graph.areAdjacents("city1", "city2"));
graph.removeEdge("city1", "city2");
Console.WriteLine(graph.areAdjacents("city1", "city2"));
graph.addEdge("city1", "city2");
graph.addEdge("city1", "city3");
List<String> adjacents = graph.adjacentsTo("city1");
Console.WriteLine("city1 adjacents count: " + adjacents.Count);
foreach (string city in adjacents)
{
Console.WriteLine(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.
There are different types of graphs that we can use 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 the connected cities.
- 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: