## Graph Algorithms – Definitions.

This post represents a brief introduction to graph algorithms. When study I usually use to use paper and write a summary for what I read to better understand, analyze, and memorize what I am studying.

Instead of using paper, this time, I decided to use my nice little blog as someone else can benefit from it. Reference of the definitions and books are provided at the end of this post.

My mind, on the other hand, better works by visualizing things so I’ve done my best to draw pictures of the definitions mentioned in this post.

1- Graph: graph G = (V, E) consists of a set of vertices, V, and a set of edges, E.

•  Each edge is a pair (v, w), where v, w ∈ V. Edges are sometimes referred to as arcs.

• There are two type of graphs, directed and undirected

•  Directed graphs are called digraphs.
• Vertex w is adjacent to v if and only if (v, w) ∈ E. In other words if the w and v are connected with only one edge. The edge E is consisted of w and v.

• In an undirected graph E is represented either by (v,w) or (w,v), the direction is both ways, it is undirected right ?

• In a directed graph (v,w) is a different edge than (w,v).
• An edge can have a weight or sometimes called cost. In a geographical  map this can represent the distance between two points, for example.

2- Path: A path in a graph is a sequence of vertices w 1 , w 2 , w 3 , . . . , w N such that (w i , w i+1 ) ∈ E for 1 ≤ i < N.

• The length of such a path is the number of edges on the path, which is equal to N − 1
• There is always a path from every vertex to itself and its length is 0, this is intuitive.
• loop, this represents an edge (v, v) i.e a path from a vertex to itself.

• A simple path is a path such that all vertices are distinct, except that the first and last could be the same. (wiki definition: a simple path is a path in a graph which does not have repeating vertices)

3- Cycle: A cycle in a directed graph is a path of length at least 1 such that w 1 = w N ; this cycle is simple if the path is simple. In other, more intuitive words a cycle is a path that ends at the same vertex that it started from.

• The is no cycles in an undirected graph, why is that? well because very edge is considered as a a cycle as it has both way from v -> w and from w->v.

• A directed graph is acyclic if it has no cycles

• A directed acyclic graph is sometimes referred to by its abbreviation, DAG

4- Some more points :

• An undirected graph is connected if there is a path from every vertex to every other vertex.
• A directed graph which is connected (there is a path from every vertex to every other vertex) is called strongly connected.
• If a directed graph is not strongly connected (there is NO a path from every vertex to every other vertex), but the underlying graph the one without direction to the arcs or in other words the same graph after removing directions of edges is connected, then the graph is said to be weakly connected. In other words, a directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
• A complete graph is a graph in which there is an edge between every pair of vertices

5- References:

## Immutable objects in Java,are they really immutable?

In this article I emphasize on using immutable objects in java and show how objects, even being immutable, can still be changed.

## What are java immutable objects ?

Immutable objects are objects those state (value) cannot be changed after their creation (construction), here is an example.

#### How to make an object immutable ?

As we can see from the object above:

• Define object’s class as final so it can’t be extended and changed;
• Define object’s properties as final
• Provide only one constructor that sets all properties
• No setters !
• Every instance property must be immutable too !

To give an example of the last point check the following:

If some properties of the object in case are not immutable then the object itself is not too. However there is a work-around to solve this problem which it is to make defensive copies.

## Why immutable objects are so cool ?

There are not one or two reasons to make objects immutable and here are some, can you think of others ?

• Immutable objects are automatically thread-safe and have no synchronization issues:

Nearly all the atomicity and visibility hazards we’ve described sofar, such as seeing stale values, losing updates, or observing an object to be inan inconsistent state, have to do with the vagaries of multiple threads trying toaccess the same mutable state at the same time. Java concurrency in practice.

• Allow hashCode to use lazy initialization, and to cache its return value:   Calculating hash code could be an expensive operation. There are some cases where hashCode() is frequently called – like when using some objects as key of map entries – calculating the hash code once and only when needed can gain performance especially when the operation is performed frequently BUT this applies only when objects are IMMUTABLE. Consider however that object can changes its state, calculating hash code once and then change the objects state will result in errors when dealing with the object.
• Always have “failure atomicity” (a term used by Joshua Bloch): if an immutable object throws an exception, it’s never left in an undesirable or indeterminate state
• Don’t need to be copied defensively when used as a field
• To see how set can be abused by mutable objects check this link
• Their state validation is checked once upon construction, and it never needs to be checked again
• Make good Map keys and Set elements (these objects must not change state while in the collection)

Everything said is wonderful but check this out :
Even if your class is 100% immutable designed its state still can be change – with reflection – and here is how.

Output: User{name=’asd’, age=18}

Do you know how to solve this, I don’t !

## Trees – definitions with pictures

This article depicts fundamental definitions of trees. It is an introduction to a series of articles dedicated to trees and their definitions in a simple and understood approach. Some people, like me, understand better with picture, they tend to draw a lot when explaining to others or themselves. Also, they tend to do a lot of hand motions when explaining something. The following summarized definitions are fundamental to understand trees.

A Tree is a collection of nodes

One is called root, and zero or more nonempty children.

Each child or group of children can be considered a tree or a sub-tree of the main tree, thus each child of the main tree can be seen as a root.

A link between a root and its child is called edge If a tree has N nodes then it has N-1 edges, the red numbers on the images show edges nodes :

Leaves: nodes with no children

.

Siblings: Nodes with the same root.

A path from node n 1 to n k is defined as a sequence of nodes n 1 , n 2 , . . . , n k such that n (i) is the parent of n (i+1) for 1 ≤ i < k The length of this path is the number of edges on the path, namely k − 1

The depth of n i is the length of the unique path from the root to n i . Thus, the root is at depth 0

The height of n i is the length of the longest path from n i to a leaf. The height of a tree is equal to the height of the root.

If there is a path from n 1 to n 2 , then n 1 is an ancestor of n 2 and n 2 is a descendant of n 1 . If n 1 = n 2 , then n 1 is a proper ancestor of n 2 and n 2 is a proper descendant of n 1 .

## Just another synchronization tricky fail made by me.

This post is not another Java synchronization tutorial in this post I will discuss an error code that a colleague of mine commented during a code review – which is extremely important and useful for clean and minimum bugs provided code.

## IDEA Intellij JDBC Driver support for IBM Informix

#### IDEA Intellij

Probably the best IDE on the market so far that boosts your productivity to its maximum. The first time I was introduced to IDEA Intellij I felt in love with it.  I do not understand some developers that has like 3 to 4 separate programs and ten opened command line terminals (CLT) when develop. It goes something like this one IDE for source code one Database viewer, one CLT for building the project, one for deployment and another for starting local dev server and god knows what else. IDEA Intellij has them all in one windows maybe two at most.

#### IBM informix

Read moreIDEA Intellij JDBC Driver support for IBM Informix

## Spring MVC HTTP Status 405 – Request method ‘POST’ not supported

Recently I’ve started developing a new website utilizing Spring Technologies, Spring MVC and Spring Security. This is best way to learn something new, rather than reading and reading I decided to implement a website with SpringMVC, Spring Security.
As I haven’t done any website with Spring MVC before I struggled a little bit with it.
One of the problems I’ve faced was, the title of this post, Spring MVC HTTP Status 405 – Request method ‘POST’ not supported.

Read moreSpring MVC HTTP Status 405 – Request method ‘POST’ not supported