This article is going to be all about Undirected Graphs. It is in the succession of the previous article Getting Started With The Algorithms that sets you up to learn algorithms. I suggest you read that article to learn about the origin of algorithms, why they are important and needs to be studied.
In this article, I’ll be talking about one of the most interesting topics in algorithms- The Undirected Graphs.
The graphs took my interest at the time when I was pursuing my engineering. And while reading about it I had a realization – It wouldn’t be possible for our generation to evolve if there were no graphs algorithms.
So, in this article, I’m going to talk about a lot of topics related to the
Undirected Graphs. And below are the topics that I have covered in this article:
- Definition
- Why Study Graphs?
- Graph Terminology
- Graph API
- Set-of-edges Graph Representation
- Constructing an Undirected Graph Programmatically
- Adjacency-List Graph Representation
- Adjacency-List Graph Representation- Implementation
Do not worry about the topics. I will make sure you get it right and in the easiest way possible. And at any point, you have any questions just select the part and click on the tweet button.
So let’s start…
Table of Contents
Definition
The definition of Undirected Graphs is pretty simple:
Set of vertices connected pairwise by edges.
Graph definition
Any shape that has 2 or more vertices/nodes connected together with a line/edge/path is called an undirected graph.
Below is the example of an undirected graph:
Vertices are the result of two or more lines intersecting at a point. Edges or Links are the lines that intersect.
These graphs are pretty simple to explain but their application in the real world is immense. You will see that later in this article.
Here’s another example of an Undirected Graph:
You make use of Directed or Undirected Graphs in every day of your life, you just might not be aware of it. It has been engraved in us from the very beginning. And that also makes it important for us to study it.
Why Study Graphs?
As I said, there are thousands of practical applications of Undirected Graphs . And being a Computer Science Engineer, it’s our job to study about these applications and try to make it more efficient.
As of today, there are thousands of graph algorithms that are used for different purposes. For example – Google map uses some of the graph algorithms to find the shortest distance between two points on Google Maps.
Many businesses today such as Ola, Uber, Grab etc… relies on the accuracy of these maps. Their entire business model revolves around it. Smallest miscalculation would cause them thousands of bucks.
All of this is made possible just with the help of Graph Algorithms. Don’t you think we should study more about it? Don’t you want to explore the hidden possibilities?
Well, let me share with you some more real-world applications of Graphs and the algorithms that made it possible.
10 Million Friendships 
Map of Science Clickstreams 
Framingham Heart Study 
Protein-Protein Interaction Network 
The evolution of FCC Lobbying coalition 
The Internet mapped by Opte Project
If you are not amazed to see this then I’m not sure how to impress you 😀
These are some of the live applications made possible by studying graphs. Almost all the maps that you and I use today is the consequence of studying graphs.
Meaning-out-of-chaos is determined with the help of graph. And if you are going to do anything amazing, you must study the graph algorithms.
Mark Zuckerberg is a genius and that’s why he was able to connect everyone around the entire globe. And I’m sure he was also a really good student of algorithms.
Graph Terminology
The graph terminology is pretty simple and easy. It won’t take much time.
- Path
- Cycle
Path
Sequence of vertices connected by edge.
Cycle
Path whose first and last vertices are the same.
You can say that the two vertices are connected if there is a path between them.
Say you want to go to point B from some point A. It is only possible for you to go to that point if there is a path between the two. The path that connects both the point.
Here is the image that depicts the same:
I will not spend much time in terminologies so let’s move to the interesting part- The Graph API.
Graph API
This topic is a bit difficult to understand at first. So in order to make it simpler, I thought of using the Facebook Graph API concept to illustrate it. Because most of you are aware of Facebook and how it works, so I think it would help you to relate with it better. And if you can relate better, you can learn faster.
And just to be clear, facebook graph API is a real thing. The developers built Facebook this way. Graph API records every action that the user makes on the page.
Facebook’s Graph API is composed of:
- Nodes: Individual objects such as a User, a Photo, a Page or a Comment.
- Edges: they represent connections between different objects such as Photos on a Page or Comments on a Photo.
- Fields: Actual data associated with the object, like User’s birthday or Page’s name.
So in order to access any information, typically you use nodes to get data about a specific object, use edges to get collections of objects on a single object and use fields to get data about a single object or each object in a collection.
Implementation Of Graph Using Java
In this section I will show you how to implement a graph using Java language. I chose JAVA because it is familiar to most of the readers. The same could be achieved with any other programming language.
As you know that a Graph consists of vertices and edges. So let’s start by identifying the operations that a graph must perform.
Graph API
Graph
Graph()// initialize a new Graph
Graph init(File inputFile) //create a graph from input file
List addVertex(Vertex vertex)//add new vertex to the graph
boolean addEdge(Vertex v, Vertex w) //add edge from v to w
int getEdgesCount()// number of edges
List getAdjacentVertices(Vertex vertex) //vertices adjacent to v
Great. Now that we have identified all the required methods, let’s write code to make it work.
Graph
Initialize a new data structure that will hold all the vertices and edges to vertices. Below is the code for the same:
@Getter
private final Map<Vertex, List<Vertex>> graph = new HashMap<>();Vertex
Every graph consists of vertices. Create a new class called Vertex in your workspace and paste the below code:
import lombok.Data;
@Data
public class Vertex {
private String label;
private Vertex(String label) {
this.label = label;
}
public static Vertex newLabelInstance(String label) {
return new Vertex(label);
}
}
The Vertex class will represent the vertex of the graph. It takes one value label. Label is a property that holds the name of the vertex.
Add Vertex
I want you to first read the code slowly and try to understand it before moving forward to the description. It would be easy for you to follow up if you have the code in mind.
Below is the code required to add a new Vertex to the graph:
public List<Vertex> addVertex(Vertex vertex) {
graph.putIfAbsent(vertex, new LinkedList<>());
return graph.get(vertex);
}Here you are adding a new vertex to the existing graph. The new LinkedList<>()will hold all the vertices that are connected by an edge to this vertex.
In short, every vertex will have its own bag that will contain all the vertices that is connected to this vertex by an edge.
To visualize the above scenario, see the image below:
This is one way to organize a graph. It is called the Adjacency List. It maintains the Vertex-Indexed array of the list. The information about every vertex of the graph and the edges that connect to it.
After adding the vertices to the graph your Graph will look more like this:
You can add as many vertices you want by calling addVertex(Vertex vertex) method. So far your main method would look like this:
public static void main( String[] args )
{
UndirectedGraph undirectedGraph = UndirectedGraph.newInstance();
undirectedGraph.addVertex(Vertex.newLabelInstance("0"));
undirectedGraph.addVertex(Vertex.newLabelInstance("1"));
undirectedGraph.addVertex(Vertex.newLabelInstance("2"));
undirectedGraph.addVertex(Vertex.newLabelInstance("3"));
undirectedGraph.addVertex(Vertex.newLabelInstance("4"));
undirectedGraph.addVertex(Vertex.newLabelInstance("5"));
undirectedGraph.addVertex(Vertex.newLabelInstance("6"));
}The above code won’t do much but let’s move forward and add another functionality to the graph.
Add Edge
To create an edge that connects two vertices, you need the two vertices. So, let’s add the addEdge(Vertex v, Vertex w) method to the graph:
public boolean addEdge(Vertex v, Vertex w)
{
if (graph.containsKey(v) && graph.containsKey(w)) {
edges++;
return graph.get(v).add(w);
}
return false;
}First, you need to first make sure that the graph contains both the vertex before creating an edge between them.
If the graph contains both the vertices than simple increment the edge count and add the edge to vertex V. So, now vertex will have an edge to W (V-W).
After adding the above code to the Graph class, you can use it in the main method to add edges. Your main method will look like this:
public static void main( String[] args )
{
UndirectedGraph undirectedGraph = UndirectedGraph.newInstance();
undirectedGraph.addVertex(Vertex.newLabelInstance("0"));
undirectedGraph.addVertex(Vertex.newLabelInstance("1"));
undirectedGraph.addVertex(Vertex.newLabelInstance("2"));
undirectedGraph.addVertex(Vertex.newLabelInstance("3"));
undirectedGraph.addVertex(Vertex.newLabelInstance("4"));
undirectedGraph.addVertex(Vertex.newLabelInstance("5"));
undirectedGraph.addVertex(Vertex.newLabelInstance("6"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("1"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("2"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("5"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("6"));
}Now after running above code, your graph contains edges to v1, v2, v5, v6 from v0.
Below is the depiction of the graph after above code:
Adjacent Vertices
Adjacent vertices are the vertices that shares a common edge.
You have a graph in place, but you still need to perform operations on the vertex to find all its adjacent vertices.
Perhaps, you need all the adjacent vertices connected to the given vertex. If there is an edge between two vertices they are called adjacent to each other.
Let’s write the code to print all the adjacent vertices of a given vertex.
public List<Vertex> getAdjacentVertices(Vertex vertex)
{
return graph.get(vertex);
}The above code will return all the adjacent vertices connected to the given vertex.
So, let’s write the code in main method to print all the adjacent vertices:
public static void main( String[] args )
{
UndirectedGraph undirectedGraph = UndirectedGraph.newInstance();
undirectedGraph.addVertex(Vertex.newLabelInstance("0"));
undirectedGraph.addVertex(Vertex.newLabelInstance("1"));
undirectedGraph.addVertex(Vertex.newLabelInstance("2"));
undirectedGraph.addVertex(Vertex.newLabelInstance("3"));
undirectedGraph.addVertex(Vertex.newLabelInstance("4"));
undirectedGraph.addVertex(Vertex.newLabelInstance("5"));
undirectedGraph.addVertex(Vertex.newLabelInstance("6"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("1"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("2"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("5"));
undirectedGraph.addEdge(Vertex.newLabelInstance("0"), Vertex.newLabelInstance("6"));
for (Vertex v: undirectedGraph.getAdjacentVertices(Vertex.newLabelInstance("0")))
System.out.print(v.getLabel() + ", ");
}The output of the above code will be:
Now, you have a code that prints all the adjacent vertices of a given vertex in a graph.
Next you will be creating a graph processor and perform various different operations on the given graph.
Graph Processor
Graph processor is going to be an independent class that will perform common operations on all graphs irrespective of its type.
So, for this article, you will be adding below functionalities to the graph processor:
- Degree of the graph’s vertex
- Maximum degree of the graph
- The average degree of the graph
- Number of self-loops in a graph
To begin with, you need to extract out a Graph Interface. Every graph will implement this interface in order to utilize the common Graph Processor functionalities.
For simplicity, the Graph interface will contain only two methods. Below is the code for the Graph interface.
import java.util.List;
public interface Graph {
int getEdgesCount();
Set<Vertex> getVertices();
List<Vertex> getAdjacentVertices(Vertex vertex);
}You will see why you have to extract the Graph interface shortly.
So now you will create a Graph processor. You can think of a graph processor as the collection of operation that could be performed on the graph. I have talked about that operation above in bullet points.
Graph Processor Class (JAVA)
Create a class and name it GraphProcessor.
This class will contain all the operations that you wish to perform on a graph. You will be creating below operation:
- Degree of the graph’s vertex
- Maximum degree of the graph
- The average degree of the graph
- Number of self-loops in a graph
Below is the snippet of all the methods GraphProcessor will have. Every method represents a functionality that will be performed on the given graph.
Go on try to write the necessary code to realize it. You will soon realize why you had to extract the Graph interface earlier.
Okay, so now I’m going to give you the entire code for the GraphProcessor:
public class GraphProcessor {
public static int degree(Graph graph, Vertex v){
return graph.getAdjacentVertices(v).size();
}
public static int maxDegree(Graph graph) {
int max = 0;
for (Vertex vertex : graph.getVertices()) {
if (max < degree(graph, vertex))
max = degree(graph, vertex);
}
return max;
}
public static double averageDegree(Graph graph) {
// since for each edge, there are two vertexes associated to it.
// so each edge adds 2 degrees to the graph
// hence multiplied by 2.0
return 2.0 * graph.getEdgesCount() / graph.getVertices().size();
}
public static int numberOfSelfLoops(Graph graph) {
int count = 0;
for (Vertex vertex : graph.getVertices())
for (Vertex adjacentVertex : graph.getAdjacentVertices(vertex))
if (vertex.equals(adjacentVertex))
count++;
return count/2; // each edge counted twice
}
}Go on and test each of its method. Pass in the undirected graph object to the method and call each method yourself. You will see how it works.
In case you need to test it using the test cases, then below is the complete test case for the same:
public class GraphProcessorTest {
private File inputFile = Paths.get("src/main/resources/tiny_graph.txt").toFile();
private UndirectedGraph undirectedGraph;
@Before
public void setup() {
undirectedGraph = new UndirectedGraph();
undirectedGraph.init(inputFile);
}
@Test
public void itShouldGiveTheDegreeForTheGivenVertex() {
int degree = GraphProcessor.degree(undirectedGraph, Vertex.newLabelInstance("0"));
Assert.assertEquals(4, degree);
}
@Test
public void itShouldGiveMaxDegreeOfTheGraph() {
int maxDegree = GraphProcessor.maxDegree(undirectedGraph);
Assert.assertEquals(4, maxDegree);
}
@Test
public void itShouldGiveAverageDegreeOfTheEntireGraph() {
double avgDegree = GraphProcessor.averageDegree(undirectedGraph);
System.out.println(undirectedGraph.getEdgesCount());
System.out.println(undirectedGraph.getVertices().size());
Assert.assertEquals(4, avgDegree, 2);
}
@Test
public void itShouldGiveTotalNumberOfSelfLoopsInAGraph() {
int selfLoops = GraphProcessor.numberOfSelfLoops(undirectedGraph);
Assert.assertEquals(0, selfLoops);
}
}Conclusion
So to sum it up:
You have learned the definition of the graph and why should you study it. You have also learned various real-life implementation of the graph.
Not only that you have practically created an Undirected Graphs that reads the input from the file and initializes its edges and vertices. You have also extracted the graph interface out of it so that every undirected graph could leverage the Graph Processor. Then you created an Undirected Graphs Processor that uses the graph interface to perform various operations on the graph.
You have covered a lot of ground here buddy. I think its time you take a little rest and revise it all after some time. And yes don’t forget to subscribe the channel because there’s more coming 🙂
Let me know your blockers, thought, obstacles and everything in the comments below. Looking forward to hear from you.