Lets Code Them Up!

Graph Representation: Adjacency Matrix

June 17th, 2017
In our previous post, we stored the graph in Edges List and Vertices List. And we saw that time complexity of performing operations in this representation is very high. So, we need another representation which can perform operations in less time.
Another representation of the graph is a 2D array of size V x V called Adjacency Matrix. Let’s call that matrix adjacencyMatrix. If we have an edge between nodes s and d, then adjacencyMatrix[s][d] is set to 1 or weight, else set to infinity.

Unweighted Undirected Graph

Consider the following graph

Fig 1: Undirected Graph

The adjacency matrix of above graph is

Fig 2: Adjacency Matrix of the graph in Fig 1.

There is an edge between 1 and 2, so we put 1 in adjacencyMatrix[1][2] and also in adjacencyMatrix[2][1] as this is an undirected graph. We give value 1 here because there is no weight for an edge. There is no edge between 1 and 3, so we put infinity in adjacencyMatrix[1][3].

In Java, we initialize a 2D array adjacencyMatrix[size+1][size+1], where size is the total number of vertices in the graph. For the above graph, the matrix will have a size of 7. We assign Integer.MIN_VALUE which is equivalent to negative infinity to adjacencyMatrix.

(Note: We can assign an index from 0 to 6 to all the vertices, but that creates confusion. Here, we use node names as the array index in this implementation. Since there is no node 0, and node start from 1, we increase the matrix size by 1. If you have string nodes, you can give them indices from zero and use size instead of size+1.)
```
public class GraphAdjacencyMatrix{
	
	//2-D array to store adjacency matrix
	private int[][] adjacencyMatrix;
	
	//variable to store size of 2-D array/adjacency matrix
	private int size;
	
	//Constructor to initialize the matrix and size
	public GraphAdjacencyMatrix(int size){
		this.size = size;
		adjacencyMatrix = new int[size][size];
		for(int[] single : adjacencyMatrix)
			Arrays.fill(single, Integer.MIN_VALUE);
	}
}
```
Add an edge

Now we add edges between two nodes using the following method. Since the graph in fig 1 is undirected, we add an edge from source to destination and destination to source by assigning one to adjacencyMatrix[destination] and adjacencyMatrix[destination].
```
public void add(int source, int destination){
		adjacencyMatrix[destination] = 1;
		adjacencyMatrix[destination] = 1;
	}
```
Find Adjacent Vertices

The findAdjacent method takes an index as input and returns anArrayList of vertices adjacent to the index. To find all adjacent vertices of the index, we need to traverseadjacencyMatrix[vertex] and add those vertices to list whose value is 1.

Since we traverse adjacencyMatrix[vertex] linearly, whose size is V (V being the number of vertices in the graph), the time complexity of this operation is O(V).
```
public ArrayList<Integer> findAdjacent(int index){
		ArrayList<Integer> adjacent = new ArrayList<Integer>();
		for(int i=1;i<size;i++){
			if(adjacencyMatrix[index][i] == 1)
				adjacent.add(i);
		}
		return adjacent;
	}
```
Find whether two nodes are connected

To find whether source and destination are connected, we just check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is equal to 1. If any of them is equal to 1, source and destination are connected else they are not connected. The time complexity of this operation is O(1) as we only access a position in a 2D matrix.
```
public boolean isConnected(int source, int destination){
		if(adjacencyMatrix[destination] == 1 || adjacencyMatrix[destination] == 1)
			return true;
		return false;
	}
```
The entire code for a unweighted undirected graph is available here.

Weighted Undirected Graph

Fig 3: Weighted Undirected Graph

If an edge between source and destination has a weight then we assign value of weight to adjacencyMatrix[destination] and adjacencyMatrix[destination].
```
public void add(int source, int destination, int weight){
		adjacencyMatrix[destination] = weight;
		adjacencyMatrix[destination] = weight;
	}
```
To find adjacent nodes of a given node, we add all those nodes to the list whose value is not equal to Integer.MIN_VALUE.
```
public ArrayList<Integer> findAdjacent(int index){
		ArrayList<Integer> adjacent = new ArrayList<Integer>();
		for(int i=1;i<size;i++){
			if(adjacencyMatrix[index][i] != Integer.MIN_VALUE)
				adjacent.add(i);
		}
		return adjacent;
	}
```
Similarly to check whether two nodes are connected or not, we check whether adjacencyMatrix[destination] or adjacencyMatrix[destination] is not equal to Integer.MIN_VALUE.
```
public boolean isConnected(int source, int destination){
		if(adjacencyMatrix[destination] != Integer.MIN_VALUE || adjacencyMatrix[destination] != Integer.MIN_VALUE)
			return true;
		return false;
	}
```
The whole code for the weighted undirected graph can be found here.

Weighted Directed Graph

Fig 4:Weighted Directed Graph

In case of directed weighted graph, we assign weight to only adjacencyMatrix[destination] and not to adjacencyMatrix[destination]. Other operations are same as those for the above graphs. The whole code for directed weighted graph is available here.

Problems in this approach

If we have a graph with million nodes, then the space this graph takes is square of million, as adjacency matrix is a 2D array. That’s a lot of space. It is good when we have a large number of vertices and equally large number of edges between them, as then we will have a dense matrix. But If we have a graph with a lot of vertices and very few edges, resulting in a sparse matrix, we store a lot of infinite values which are unnecessary and take a lot of space. The next implementation Adjacency List, which we cover in next post improves upon this.

A large number of vertices and equally large number of edges between them will produce a dense matrix. Here, using adjacency matrix is efficient. But a large number of vertices and very few edges between them will produce a sparse matrix. Here, using adjacency matrix is inefficient as we store a lot of infinite values (taking up large space) which are unnecessary. The next implementation Adjacency List, which we cover in next post improves upon this.
Graph Representation: Edges and Vertices List

June 14th, 2017
In the previous post, we explained what are graphs and how the graph is represented mathematically. In this post, we see how to represent that Graph in computer’s memory (means which data structures to use to implement graphs).
Graphs can be represented in three ways:
1. Edges and Vertices List.
2. Adjacency Matrix
3. Adjacency List
In this post, we start with the first method Edges and Vertices list to represent a graph.

Edges and Vertices List

Here a graph is represented as a vertices list and edges list. The list here means we can use an Array or an ArrayList in Java to store the vertices and edges separately.

Fig 1: Undirected Graph

Consider above graph, the vertices can be stored in a vertices array and the edges can be stored in a separate array.

Fig 2 – Edges and Vertices List of graph in fig 1

Vertices are stored using an array of integers directly. But an edge {u,v} has two values which can’t be stored directly in an array. Therefore we create a class Edge with two instance variables to store the name of the two vertices. Here {1,2,3,4,5,6} are names of our vertices. We could use strings also instead of integers for the names of vertices.
```
/**
* Edge --- class to store an edge between Start vertex and End vertex
*/
class Edge{		
	private int startVertex;
	private int endVertex;
		
	public Edge(int startVertex, int endVertex){
		this.startVertex = startVertex;
		this.endVertex = endVertex;
	}
		
	//Getter method for start vertex
	public int getStartVertex(){
		return startVertex;
	}
		
	//Getter method for end vertex
	public int getEndVertex(){
		return endVertex;
	}
		
}
```
We know that the graph is undirected, so if an edge {u.v} exists, then edge {v,u} exists. But to store edge {v,u} is futile as that will take only extra space. We assume that if we add an edge {u, v} we are also accounting for the edge {v, u}.

Instead of arrays, we are using ArrayList in our implementation as it is more dynamic. So there are two ArrayLists, one of Integer type to store vertices and another of Edge type to store edges.
```
//List verticesList to store vertices
private static ArrayList<Integer> verticesList;
	
//List edgesList to store edges
private static ArrayList<Edge> edgesList;
```
Add an edge

Next, we see how to add an edge from any vertex to another vertex. The following add method does exactly that. First, we check whether the start vertex is present in our verticesList, if not we add it. Then we add an edge object containing both start and end vertex to the edgesList. This way both our verticesList and edgesList are filled simultaneously, ie. stored our entire graph.
```
public void add(int start, int end){
	if(!verticesList.contains(start)){
		verticesList.add(start);
	}
	edgesList.add(new Edge(start, end));
}
```
Find Adjacent Vertices

Now that we have created our graph lets perform some operations on them. The first one is to find adjacent vertices of a given vertex. Adjacent vertices are those vertices to which we have an edge from the given vertex. For example, in the above graph, adjacent vertices of 1 are 2, 4, 5 as there are edges to 2, 4 and 5 respectively from 1.
```
public ArrayList<Integer> findAdjacent(int vertex){
	ArrayList<Integer> adjacent = new ArrayList<Integer>();
	for(Edge edge: edgesList){
	    if(edge.getStartVertex() == vertex)
		adjacent.add(edge.getEndVertex());
	    else if(edge.getEndVertex() == vertex)
		adjacent.add(edge.getStartVertex());
	}
	return adjacent;
}
```
The findAdjacent method takes a vertex as input and returns an ArrayList of vertices adjacent to the vertex. To find all adjacent vertices of vertex, we need to traverse all edges in the edgesList to check which edge contains vertex. If an edge contains vertex, we add the corresponding vertex of that edge to our adjacent list.

If startVertex is equal to vertex we add the endVertex to the list and if endVertex is equal to vertex we add startVertex to the list. In the end, we return the adjacent list.

If there are E edges then the worst case time complexity of this method will be O(E). Because to find adjacent of any vertex we are traversing through all the edges.

Find whether two nodes are connected

Two nodes are connected when they have an edge between them. Here also we traverse the whole edgesList and check whether vertices of each edge are equal to the given set of nodes or not. If we have a match then the two nodes are connected, otherwise, the two nodes are not connected.
```
public boolean isConnected(int start, int end){
	for(Edge edge: edgesList){
		if((edge.getStartVertex() == start && edge.getEndVertex() == end) ||
		   (edge.getStartVertex() == end && edge.getEndVertex() == start))
			return true;
		}
	return false;
}
```
If there are E edges then the worst case time complexity of this method will also be O(E).

The entire code for this undirected unweighted graph is available here.

Weighted Undirected Graph

If the edges have a weight associated with them then we add another instance variable of integer type to the edge class to store the weight of that edge. And rest operations like adding the edge, finding adjacent vertices of given vertex, etc remain same. The code for a weighted undirected graph is available here.

Fig 3 Weighted Undirected Graph
```
/**
* Edge --- class to store an edge with a weight between Start vertex and End vertex
*/
class Edge{		
		
	private int startVertex;
	private int endVertex;
	private int weight;
		
	public Edge(int startVertex, int endVertex, int weight){
		this.startVertex = startVertex;
		this.endVertex = endVertex;
		this.weight = weight;
	}
	
	//Getter method for start vertex
	public int getStartVertex(){
		return startVertex;
	}
	
	//Getter method for end vertex
	public int getEndVertex(){
		return endVertex;
	}
	
}
```
Weighted Directed Graph

Fig 4: Weighted Directed Graph

The entire representation of graph will be same as the undirected graph. Only the way to access adjacent list and find whether two nodes are connected or not will change. Because now we only have an edge (u,v). The code for the weighted directed graph is available here.

Why this implementation is not effective

For this implementation, we store the graph in an Edges List and a Vertices List. First, consider the space used in this representation. The first Vertices List is a simple integer array of size V (V is a total number of vertices in the graph). If we assume the integer takes constant space ie, O(1), then space to store V vertices will be O(V * 1) ie O(V). The second Edges List is an array of edge objects, and each edge object stores two or three integer variables. Therefore, each edge takes constant space, as we assume both integers takes constant space, ie O(1). If there are E edges then the space for Edges List is O(E). The total space complexity of this representation is O(V + E).

We already know the time complexity of some operations from above, ie O(E). We traverse linearly through all edges to get our desired result. And the number of edges in a graph can be as high as V*V in the worst case. Which makes the time complexity of operations very high.

So, we need an implementation which has operations run in order of vertices instead of edges. In the next post, we study another way to store graph, ie Adjacency Matrix.
Graphs: Introduction

June 13th, 2017

What is a graph?

A graph is a collection of nodes (also called vertices) connected to each other through edges. For example, the below figure is a graph with 6 vertices and 9 edges.

Fig 1: Graph with 6 Vertices and 9 Edges

Mathematically, Graph G is an ordered pair of V vertices and E edges, ie. G = (V,E).

An edge from a vertex a to vertex b is an ordered pair (a,b) if there is a directed edge between the two and an unordered pair {a,b} if there is an undirected edge between the two.

A directed edge between a and b means we can move from a to b only and never from b to a. An undirected edge between a and b means we can go from a to b and also from b to a.

The above graph has only the undirected edges between its vertices.

The vertices set V of above graph will be:

V = { 1, 2, 3, 4, 5, 6}

And the edges set E will be:

E = { {1, 2}, {1, 5}, {1, 4}, {2, 3}, {2, 5}, {2, 6}, {3, 6}, {4, 5}, {5, 6} }

Now, Let’s consider an example of a graph with directed edges and write it’s set V and set E.

Fig 2: Graph with directed edges

The set of vertices will be same:

V = { 1, 2, 3, 4, 5, 6}

But the set of edges will differ:

E = { (1, 2), (1, 5), (1, 4), (1, 6), (2, 3), (3, 6), (4, 5), (5, 6) }

Directed and Undirected Graphs

A directed graph is a graph which has directed edges while an undirected graph is a graph which has only undirected or bi-directional edges. For example, Fig 1 is an undirected graph and Fig 2 is a directed graph.

Weighted and Un-Weighted graph

If there is a cost/weight associated with all edges in a graph, then that graph is a weighted graph. If there is no weight associated with the edges like in Fig 1 and Fig 2, then it is an un-weighted graph. Fig 3 is a weighted graph where edges have a weight of 5, 10 or 15 associated with them.

Fig 3: Weighted Graph

In the next post, we will implement graphs in Java and perform operations on them.
Learning Swift – Enumerations

May 25th, 2017
In this post, we will implement enumerations in swift.
What’s an enumeration?

According to the official documentation of Swift:

“An enumeration defines a common type for a group of related values.”

In simple words, an enumeration is a user defined data type which stores a set of values. Examples of such sets can be days of the week, days of the month, etc.

How to define enums in swift?

In swift, the enumeration is defined using the following syntax:
```
enum EnumerationName {
    // cases
}
```
Here enum is the keyword, and enumerationName is the name for the enumeration. The following example code creates an enum which stores days of the week.
```
enum DaysOfWeek{
    case monday 
    case tuesday 
    case wednesday
    case thursday
    case friday 
    case saturday 
    case sunday 
}
```
Once the enums are created, we define a variable of this enum type as the following code shows:
```
var today = DaysOfWeek.tuesday
```
When we assign DaysOfWeek.tuesday to variable today, type of today becomes an enumeration. Switch statements which we studied in this post, can be used to match individual enumeration values.
```
today = .thursday
switch today{
case .monday, .tuesday, .wednesday, .thursday, .friday:
    print("Working Days")
case .saturday, .sunday:
    print("Holidays")
}
```
After first initialization, we can assign values to the enum variables only using “.casename”, as done in the above example through “.thursday“.

The output of above program is “Working Days” as “.thursday” falls into the first switch case.

Raw Values

In swift, enumerations can be initialized with raw values. In this example, we assign “Int” to the enumeration, making sure all the cases in this enumeration will have an integer raw value by default on initialization.
```
enum DaysOfWeek: Int{
    case monday
    case tuesday
    case wednesday
    case thursday
    case friday
    case saturday
    case sunday
}

var today = DaysOfWeek.thursday

print("\(today.rawValue)")
```
When we fetch the raw value using “today.rawValue“, we get an output of three. Because by default, if we don’t assign values to all the cases, swift assigns “0” to the first case and the remaining cases are incremented by “1“, i.e. monday is 0, tuesday is 1, wednesday is 2, thursday is 3 and so on.

Similarly, if we assign monday with 61, the output of thursday will be 64. Here, Swift assigns 61 to monday and all other values are incremented by 1.

Last, we assign separate and different values to all the enumeration cases.

The type of raw values in the enumerations could be float or double or string also.

Associated Values

The raw values are of the same type, so all cases store values of the same type. But in swift, enumeration cases can also store values of different data types. These values associated with each enumeration case are called associated values. For example the below enumeration:
```
enum EmployeeRecord{
    case name(String, String)
    case age(Int)
    case weight(Float)
}
```
Here we have an enumeration EmployeeRecord with three cases(values): name which can store two string values, age which can store one integer value and weight which can store a float value.

The next question that arises is how to initialize a variable of this enumeration type?
```
var employee = EmployeeRecord.name("John", "Doe")
```
Consider the name case which stores two strings. While initializing the variable employee with the enumeration EmployeeRecord, we fill in the values of the associated strings with “John” and “Doe“.
```
switch employee {
case .name(let first, let last):
    print("First Name: \(first)")
    print("Last Name: \(last)")
case .age(var age):
    print("Age: \(age)")
case .weight(let weight):
    print("Weight: \(weight)")
default:
    print("Invalid value")
}
```
Similarly, when we check these cases in the switch, we have to add the associated values as constants or variables to be able to use them. For the name, there are “let first” and “let second“.

With this, we complete enumeration in swift. If any questions, leave them in comments below. You can find the code for this post here.
Learning Swift: Functions [Argument labels]

March 31st, 2017
From last three posts, we have been working on functions in swift. So far we learned
In this post, we will learn about function argument labels.

Recall this syntax we discussed in the first post on functions.
```
func functionName (paramName: paramType  ) -> returnType{
 
 //block of code
 return object
 
 }
```
Here we have not used argument labels. First, let’s add the argument labels to this syntax.
```
func functionName (argumentLabel paramName: paramType  ) -> returnType{
 
 //block of code
 return object
 
 }
```
What is this argument label? Why do we use it? How’s it different from the parameter names.

Let’s find out.

Remember this factorial function from last few posts?
```
func factorial (number: Int) -> Int{
    var factorial = 1
    var temp = number
    while(temp>1){
        factorial =  factorial * temp
        temp = temp - 1
    }
    return factorial
}
```
We will add an argument label “of” to the parameter name number.
```
func factorial (of number: Int) -> Int{
    var factorial = 1
    var temp = number
    while(temp>1){
        factorial =  factorial * temp
        temp = temp - 1
    }
    return factorial
}
```
Immediately we have an error here, where we are calling this function factorial.

The error says “Incorrect argument label in call(have number:”, expected “of:”

When we replace the number with of, the error vanishes.

This “of’ here is an argument label. The argument labels are like external parameter name. These are used when calling a function. The other parameter name “number” is the internal parameter name and is used inside the function.

Earlier when there was no “of” ie argument label, the parameter name became the default argument label and we used “number:” instead of “of:”.

So when we explicitly write an argument label we have to use that in the function call. Else we use the parameter name as argument label.

The use of argument label makes a function more expressive, sort of like a sentence. Like this factorial function call above, now, can be read as the factorial of 7.

With this we complete functions. If you have any questions leave them in the comment section below.
Learning Swift: Functions [Return Values]

March 21st, 2017
From last two posts, we have been working on functions in swift. In the first post we learned how to define and call the functions and in the second we focused on the parameters.

In this post, we will look into the values a function can return.

If you recall the last two posts, we have used an example of a factorial function. For this post also, we will be using the same factorial function as an example.
```
func factorial (number: Int) -> Int{
    var factorial = 1
    var temp = number
    while(temp>1){
        factorial =  factorial * temp
        temp = temp - 1
    }
    return factorial
}
```
Functions with One Return Value

When we take a closer look at the function, we see that this function returns factorial variable. What is this factorial variable?

This factorial variable stores the factorial of the number which we pass as the parameter. And this factorial is of the type integer.

Plus the main point to note here is that we have used Int as the return type in the function definition which you can see in the first line.

When we call this function for a factorial of 7, we get the output as 5040 which is an integer.

So this function has a return value. It returns just one value ie factorial.

But returning a value is not mandatory for a function. We will also have functions which are having no return values.

Functions with No Return Value

For the example of a function with no return value, we will be removing the return type of this factorial function.

Let’s delete this int from the first line. But as soon as we remove this int, we get an error which says, “Unexpected non-void return value in void function”

This actually means that we are returning a value in a function which has no return value. Void means that the function is not going to have a return value.

And when we delete this return statement the error vanishes.

Now factorial function is complete and we are calling this factorial function here in the print statement. The output is just the empty parenthesis and not 5040. why?

Well, coming back to the function, we see it does not return a value and also have no print statement to print the value of factorial.

What we can do is copy this print statement inside and replace the function call with the factorial variable. And call this function separately.

Now we can again see the output 5070.
```
//Example
//Factorial of a Number

func factorial (number : Int) {
    var factorial = 1
    var temp = number
    while(temp>1){
        factorial =  factorial * temp
        temp = temp - 1
    }
    print("Factorial is \(factorial)")

}

//functionName(paramName: paramValue)
factorial(number: 7)
```
Hmm, this was a function with no return value. And before this one, we saw the function with one return value.

Functions with Multiple Return Values

But what should we do if we want to return more than one value?

In swift, we can do that by using tuples as return values. And in these tuples, specify the multiple return types.

Not clear? I know. It will be through this example. We will first write a function to return the quotient and remainder of dividing number A by number B and then understand it.
```
//divide function with two return values quotient and remainder

func divide(numA: Int, numB: Int) -> (quotient: Int, remainder: Int){
    return (numA/numB, numA%numB)
}

let result = divide(numA: 9, numB: 2)

print("Quotient is \(result.quotient) and Remainder is \(result.remainder)")
```
We get the output as 4 and 1.

Any guess what’s going on here. We have a function divide with two input parameters: numA and numB. And the return values quotient and remainder which are enclosed in parenthesis to form a tuple.

Next, we return numA/numB to get the quotient and numA%numB to get the remainder.

We can directly print the result by calling the function in a print statement. But if want to access both the results separately, we store them in a constant and then call them by their names as we did in this print statement using the result.quotient and result.remainder.

Now we know how to make functions with no parameter, one parameter and also multiple parameters.

You can find the source code for this post here.

In the next post, we will move on to argument labels.