Category Archives: Core Java

Introduction to Graphs

In my previous article, I talked about hashtables. I will discuss one more data structure in this post and it is probably one of the most important data structures of all and that is Graphs.

Clearly, our current web technologies are heavily reliant on graphs. Google, Facebook, or LinkedIn or any social media platform which includes users use graphs as a data structure. So, graphs are the most common data structure to solve problems related to finding the distance between two nodes OR the shortest path from place A to place B.

Therefore, when it comes to the social network, we are accustomed to six degrees of freedom, in such cases, we can use graphs to find how many degrees will it take to connect two nodes on the social network. In networking, most use graphs to find the fastest way to deliver the response.

How do you explain Graphs to 5-year-olds?

The easiest example, one can give to a kid to explain Graphs, is to look at City A and City B on a map. Now use the road that connects to those two cities.

City A – has bananas, and oranges, city B – has apples, and city C – has watermelons.

Now on the map, when we travel from City A to City B, what possible route we can take and what information we can exchange. City A and City B can transfer apples, bananas, oranges to each other. Once City B gets bananas and oranges, it can transfer that to other neighboring cities.

In short, we are connecting nodes (vertices) of cities A and B through a road (edge) while exchanging the products these two cities are known for.

Graphs Data Structure

In this post, we will discuss graphs from the Java perspective. Graphs allow representing real-life relationships between different types of data. There are two important aspects to graph:

Vertices (Nodes) – Nodes represent the points of a graph where the graph is connected. Node store the data or data points.
Edges – Edges represent the relationship between different nodes. Edges can have weight or cost.

However, there is no starting node or ending node in the graph. A graph can be cyclical or acyclical. In conclusion, edges can be directed or undirected which give birth to graphs as directed or undirected.

For instance, edges are generally represented in the form of a set of ordered pairs as in (x,y) – there is an edge from node x to node y. So (x,y) can be different from (y,x), especially in the directed graph.

Representations of Graphs

A. Adjacency Matrix –

This is a 2 dimensional array of size n*n where n is number of nodes in the graph. adj[][] is the usual way of representing this matrix. So if adj[i][j] = 1, it represents an edge between node i and node j. Adjacency matrix for an undirected graph is symmetrical. Now if I have to represent the graph shown above in the figure, I will represent it like below:

	A	B	C	G	E
A	0	1	0	1	0
B	1	0	1	0	1
C	0	1	0	0	1
G	1	0	0	0	1
E	0	1	1	1	0

B. Adjacency List –

Similarly, an array of lists is used. The size of the array is equal to the number of nodes in the graph. So arr[i] will indicate the list of vertices adjacent to node i.

Operations on the Graphs

There are common operations that we will use often. Likewise, graph as a data structure offers the following operations:

Additions

addNode – Add a node in the existing graph

addEdge – Add an edge in the existing graph between two nodes

Removal

removeNode – Remove a node from the existing graph

removeEdge – Remove an edge between two nodes from the graph

Search

contains– find if the graph contains the given node

hasEdge – find if there is an edge between given two nodes

Time and Space Complexity of operations on Graphs

Above all, a post would be incomplete if I didn’t talk about complexity about operations on the graph data structure. Basically, this really depends on what representations you use for the graph. With adjacency matrix, addition and removal operations are O(1) operations. While search operations like contains and hasEdge are also O(1) operations. In addition, the space complexity for the adjacency matrix is O(n*n).

While with adjacency list, additions are O(1) and removal of a node is O(n) operation, removal of an edge is O(1) . Therefore, search operations are equally O(1)

Conclusion

In conclusion, I showed the basics of the graph as a data structure. The graph is a data structure that contains nodes and edges. Also, It has operations like additions, removal, and search. In future posts, I will talk about implementing Depth First Search and Breadth First Search in the graph. After that, we will solve some real problems using this data structure. Above all, Graph is an important data structure.

References

Introduction to Graphs – Graphs
Graph as data structure – Graph as data structure

Hash Tables

What are Hash Tables?

Hash Tables are data structures used to store the data in key/value pair format. It uses a hash function to compute an index which will be used in an array to store the element at that index.

What is key/value pair though?

Alright, I will be digging in fundamentals here. Let’s take an example of database table. To retrieve a particular value from database table, you sometimes need to know a primary key or a unique value from the row of database table. Then you query on database table based on that unique value or primary key to get that entire row or that particular value you are looking for me.

Still complicated?

Let’s take an example of classroom. You are in 2nd grade class and when a teacher does roll call, she doesn’t necessarily call your name, she calls the number assigned to you. So example

1 – John Doe

2 – Jill Doe

3 – Mark Ranson

So the roll number assigned to the student becomes a key to identify that student.

Similarly in programming languages (Java in this case), we use a data structure called Hash Tables.

Hash function takes an input, hashes that input to generate an index which we use as a key to store the value in an array. Why so complexity? Why not we go in sequential order?

There are many reasons, first hashing gives security. If somebody exploits sequential order, it is easy to find next element. But hashing allows us to randomly store the data. But the most important, the average time required to search for an element in a hash table is O(1).

Now from the basics, we can say that hash tables have two components – one an array to store the value and a function to calculate the index of the array.

So what is a hash function and how do we write this hash function?

A hash function is a function that takes a data of any size and transforms that data into a fixed size data. In short a hash function will take an input x and transform that into output y. Now, this looks simple, but the question arises what if there are multiple inputs that can be transformed into y. Then we will have a problem. This is known as Collision.

Important characteristics of this hash function

It should avoid collision.
It should easily calculate the keys.
It should uniformly distribute the keys.

How to avoid collision?

There are a couple of techniques.

One technique is open addressing. In Open Addressing, store all elements in hash table itself. At any point, the size of the hash table must be greater than or equal to that of the number of keys. This is useful in the scenario of fixed size tables. During insertion, if you found the occupied slot in the hash table, you go for the next slot. It will continue until it finds an unoccupied slot. Since this is a linear process, open addressing is also linear probing. The disadvantage of open addressing is insertion and search operation becomes linear.

The second technique is Separate Chaining. In this, make each cell of a hash table point to a linked list of records. So if a hash function returns a duplicate key, the value will be placed in a linked list which will be pointed by earlier value stored at that key. The next value will be pointed by earlier linked list element. To make this simpler – let’s assume we have a has function key % 3 and so for 9, it will return 0. For 10, it will return 1. For 16, it will return 1 again. Now when we will store a value (for 10), we will store at index 1 and the next value (for 16), will be in a linked list pointed by the value stored at 1.

When do we use hash tables?

Hash tables offer fast insertion
Hash tables allow fast deletion
Hash tables can help in searching an element

References

Object Oriented Design Principles

A good software developer builds a software using right design principles. If you learn design patterns, object oriented concepts, but don’t learn principles, then you will do a disservice to yourself as a developer. Without design principles, you will build a software with no heart, no functionality to serve. I hope you don’t want to do that.

In this post, I will try to explain some design principles that I have come across or learned through my experience. If you do not understand any of these principles, please comment on the post and I will answer your questions.

Programming for interface and not for implementation

While building design, you can think how you can reuse or design your code in a way where you can extend it in future if needed. OR you have to minimal changes if you have to change. One design principle that can help in such cases is to Program interfaces instead of implementation directly.

For variables, method return types or argument type of methods – use interfaces. This will help to implement interfaces as you want.

Single Responsibility Principle

A class, a method should always implement single responsibility or single functionality. Putting more than one functionality in an object can disturb the functionality in future if there are any changes. To reduce future changes, always create implement your code with single responsibility principle.

Liskov Substitution Principle

This principle states that objects should be replaceable with instances of their subclasses without altering the correctness of the program.

To understand this, let’s look at a simple object and subclasses of that object Bird

public class Bird
{
    void fly()
    {
       // Fly function for bird
    }
}

public class Parrot extends Bird
{
    @Override
    void fly()
    {

    }
}

public class Ostrich extends Bird
{
   // can't implement fly since Ostrich doesn't fly
}

Parrot as a bird can fly, but Ostrich as a bird can’t fly. So if we end up using such an implementation, it will violate the principle of Liskov Substitution.

Open Closed Principle

Open Closed Principle makes that objects,methods should be open for extensions, but closed for modification. Many times, requirements are not clear at the beginning of design and implementation, we must use open closed principle to implement initial design and slowly if requirements change, it becomes easy to add them in design.

Interface Segregation Principle

This principle requires that client should not be forced to implement interface if it doesn’t use that. In another words, make sure your interfaces are concise and implement single functionality only. If interface has more than one functionality, it can be unnecessary for client to implement all the functionalities when it only needs one.

Delegation Principle

Don’t do all the stuff by yourself, but delegate the functionalities to respective classes. Delegation is kind of relationship between objects where an object can forward certain functions to do work to other objects (provided those objects implement those functions).

Dependency Inversion Principle

This principle is type of decoupling behavior for software modules. High level modules should not depend on low level modules. Generally while designing high level classes will depend on low level classes. But if you have to change low level classes after every design revision, it will warrant to be a bad design. To avoid such a problem, we create an abstraction layer. Low level classes will be created based on abstraction layer.

When this principle is used, high level classes use interfaces as an abstraction layer to work with low level classes, instead of working directly with low level classes.

References

Ten object oriented design principles – SOLID Principles
Design Principles – design principles

How to add SOAP headers to Request/Response

Use Case

In this post, I show how to add SOAP headers to SOAP request/response. If you have Code First Webservice OR WSDL Contract based WebService, you will be responding to your client requests with a SOAP response. In my case, it was a WS-Trust Security Token Web Service and the endpoint was correctly responding with a WS-Trust Response. This SOAP response will include SAMLv1.1 OR SAMLv2.0 token. Now consumer of this web service can either trust the server response or also validate the response for few things like time validity, signature validity, and even security header validity.

If you are supporting Transport Binding on this Web Service endpoint, it will be straight forward. Web Service response will have security headers

But as per my use case, if you are merely using UsernameToken Binding , Web Service response will not include security headers, especially if you are using Apache CXF libraries, these libraries will not always add security headers.

Likewise, if a consumer needs security headers for validation purposes, how do you add these security headers in response from your server endpoint?

Solution

In this particular case, the Web Service response needed Security header with timestamp only.

What is the security header and why Timestamp is required?

In a SOAP request or response, you will need Security header element based on security policy that Web Service will be using. This header in a request will look like below:


<wsse:Security soapenv:mustUnderstand="true" xmlns:wsse="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd" xmlns:wsu="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
     <wsu:Timestamp wsu:Id="TS-D3788B6EB508E3A553155173495342917">
         <wsu:Created>2019-03-04T21:29:13.429Z</wsu:Created>
         <wsu:Expires>2019-03-04T21:30:13.429Z</wsu:Expires>
     </wsu:Timestamp>
     <wsse:UsernameToken wsu:Id="UsernameToken-6CBAAFA3A8815F71FC15511581437664">
        <wsse:Username>john.doe@betterjavacode.com</wsse:Username>
        <wsse:Password Type="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-username-token-profile-1.0#PasswordText">********</wsse:Password>
     </wsse:UsernameToken>
</wsse:Security>

Once a Web Service endpoint receives this request, it will validate the username and password and will verify if timestamp validity is accurate. On successful validation, Web Service will generate a response that will also include Security header with Timestamp. Consumer will validate that timestamp. Having a timestamp in SOAP header minimizes the risk of Replay attack as in an attacker can’t either use the SOAP response after Expiration time or even can’t send the same request after Expiration time.

How do you add this security header of timestamp if using Apache CXF libraries?

Apache CXF libraries offer few ways to achieve this:

JAX-WS standard way is to write a SOAP handler that will add headers to the SOAP message. To simplify this, you will have to register the SOAP handler on the client or server-side.
JAX-WS offers another way through annotation @WebParam(header = true, mode = Mode.OUT).
wsdl first way wherein your WSDL operation you specify SOAPHeader as part of your SOAP binding.
CXF offers its own way to add these headers. In this post, I will show how you can leverage CXF libraries to add these headers.

How to add Security headers using CXF libraries?

Assumption is that you have used apache CXF libraries to build Web Service endpoint. JAX-WS offers a WebServiceContext which makes a Web Service endpoint to access message context. This message context can help to retrieve details for username, password, and other security headers from the request.

Same way, this message context can be used to grab a list of headers List<org.apache.cxf.headers.Header> . We will create our Soap header for security element and then add this header in the list of headers. The code for this will look like below:


SOAPFactory soapFactory = SOAPFactory.newInstance(SOAPConstants.SOAP_1_2_PROTOCOL);

SOAPElement securityElement = soapFactory.createElement("Security",
        "wsse", "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd");
SOAPElement timestampElement = soapFactory.createElement("Timestamp",
        "wsu", "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd");
timestampElement.setAttribute(WSTrustConstants.WSU_ID, "_0");

String created = getCurrentDateTime();
String expires = getCurrentDateTimePlusDelay(300L);
SOAPElement createdSOAPElement = soapFactory.createElement("Created",
        "wsu", "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd");
createdSOAPElement.addTextNode(created);
SOAPElement expiresSOAPElement = soapFactory.createElement("Expires",
        "wsu", "http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd");
expiresSOAPElement.addTextNode(expires);

timestampElement.addChildElement(createdSOAPElement);
timestampElement.addChildElement(expiresSOAPElement);
securityElement.addChildElement(timestampElement);
SoapHeader soapHeader = new SoapHeader(securityElement.getElementQName(), securityElement);

List<Header> headers = new ArrayList<>();
headers.add(soapHeader);
webServiceContext.getMessageContext().put(Header.HEADER_LIST, headers);

Conclusion

In this post, I showed how we can leverage Apache CXF libraries to add SOAP headers in a web service response. Similarly, the same libraries can be used to add these headers to the request.

References

Apache CXF Libraries – Apache CXF
Adding SOAP header – Adding SOAP header
Interceptors – interceptors

Social KPI Application Progress

In this post, I will be showing the progress of Social KPI Application so far through a screencast. This is my first screencast, so learning about OBS (Open Broadcast Software) along the way.

Future Sprint Stories

Add Jasper Reports
Integrate with Instagram and Twitter APIs
User Management for administrators
Role Management for users and reports according to roles
Report Management according to account type