Graph Algorithms – Definitions.

Grapths Algorithms

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.

Graph

  • There are two type of graphs, directed and undirected

directed graph

  •  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.

adjacent

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

different edge

  • 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. 

fifth -Weight

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.  

Path

  • 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)   

simple path

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. 

a cycle

  • 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. 

No cycles in directed graphs

  • A directed graph is acyclic if it has no cycles 

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?

Immutable objects in java

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

 

Tree
Tree

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 :

edge
Tree Edges

Leaves: nodes with no children

.  

Siblings: Nodes with the same root.  

siblings
Siblings

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  

path
Length of a path

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

depth
Depth

 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.  

height
Height

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 .      

Do you play ? Don’t do this mistake !

do you play enough ?

Do you play enough ? I didn’t ! and it was a mistake. Few months ago the company I am working at setup another gaming room on my floor, previously I had to go upstairs to play, but for some reason I didn’t. After setting up the new gaming room, most of the guys started playing video games. The company brought us a brand new Play Station 4. My first thoughts were “Oh my God everyone will start playing, productivity’s will go down and most of our projects will suffer a delay, what a waste of time!” I am a video games fan, I used to play a lot in my school days, especially mmorpg games like Cabal, MU, runescape,and others like Mortal Kombat, Street Fighter, Counter Strike, and many others. The sad story is that I stopped playing at some point, I grew up right ? I had to start studying for high school exams then enroll in University where I had to study hard and build my career there by attending presentations, planning projects, working for some local companies -in other words- always tried not to “waste” my time. Well, it was extremely bad idea ! Not the fact that I cared about my career and self-development but that I didn’t give myself time to play, I was selfish to myself and always considered playing a time wasting !. But what happened ? Ok, the guys at the office got the new Mortal Kombat X game and challenged me. I am that type of guy that if you want me to do something – tell me I can’t do it ! I got into the game and for some reason I allowed myself to dive in and guess what ? I felt fresh again my motivation, productivity and focus factor all went up, currently I am able to concentrate and finish in one hour what I wasn’t able to for two or three hours. It feels like my mind needed its time for pleasure and joy just like my body needs its portion of sugar, protein and carbs everyday !     If you are the type of guy that always wants to keep up, not “wasting” his time, and always strive to be on the top, not bad but give yourself some time to please your mind. Start playing and enjoy your time. Here is a very interesting presentation by Steve Keil talking about play and how important playing is .

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