Comparison of NoSQL databases: Cassandra, Mongodb, CouchDB, Redis, Riak, Couchbase (ex-Membase), Hypertable, ElasticSearch, Accumulo, VoltDB, Kyoto Tycoon, Scalaris, Neo4j and HBase

Please find the below comparison of few No Sql database that might help you arrive on a decision before you go with it. Hope it help you !! happy learning :)


The most popular ones

MongoDB (2.6)
Written in: C++
Main point: Retains some friendly properties of SQL. (Query, index)
License: AGPL (Drivers: Apache)
Protocol: Custom, binary (BSON)
Master/slave replication (auto failover with replica sets)
Sharding built-in
Queries are javascript expressions
Run arbitrary javascript functions server-side
Better update-in-place than CouchDB
Uses memory mapped files for data storage
Performance over features
Journaling (with --journal) is best turned on
On 32bit systems, limited to ~2.5Gb
An empty database takes up 192Mb
GridFS to store big data + metadata (not actually an FS)
Has geospatial indexing
Data center aware
Best used: If you need dynamic queries. If you prefer to define indexes, not map/reduce functions. If you need good performance on a big DB. If you wanted CouchDB, but your data changes too much, filling up disks.

For example: For most things that you would do with MySQL or PostgreSQL, but having predefined columns really holds you back.

Riak (V1.4.8)
Written in: Erlang & C, some JavaScript
Main point: Fault tolerance
License: Apache
Protocol: HTTP/REST or custom binary
Stores blobs
Tunable trade-offs for distribution and replication
Pre- and post-commit hooks in JavaScript or Erlang, for validation and security.
Map/reduce in JavaScript or Erlang
Links & link walking: use it as a graph database
Secondary indices: but only one at once
Large object support (Luwak)
Comes in "open source" and "enterprise" editions
Full-text search, indexing, querying with Riak Search
In the process of migrating the storing backend from "Bitcask" to Google's "LevelDB"
Masterless multi-site replication replication and SNMP monitoring are commercially licensed
Best used: If you want something Dynamo-like data storage, but no way you're gonna deal with the bloat and complexity. If you need very good single-site scalability, availability and fault-tolerance, but you're ready to pay for multi-site replication.

For example: Point-of-sales data collection. Factory control systems. Places where even seconds of downtime hurt. Could be used as a well-update-able web server.

CouchDB (V1.5.1)
Written in: Erlang
Main point: DB consistency, ease of use
License: Apache
Protocol: HTTP/REST
Bi-directional (!) replication,
continuous or ad-hoc,
with conflict detection,
thus, master-master replication. (!)
MVCC - write operations do not block reads
Previous versions of documents are available
Crash-only (reliable) design
Needs compacting from time to time
Views: embedded map/reduce
Formatting views: lists & shows
Server-side document validation possible
Authentication possible
Real-time updates via '_changes' (!)
Attachment handling
thus, CouchApps (standalone js apps)
Best used: For accumulating, occasionally changing data, on which pre-defined queries are to be run. Places where versioning is important.

For example: CRM, CMS systems. Master-master replication is an especially interesting feature, allowing easy multi-site deployments.

Redis (V2.8.9)
Written in: C
Main point: Blazing fast
License: BSD
Protocol: Telnet-like, binary safe
Disk-backed in-memory database,
Dataset size limited to computer RAM (but can span multiple machines' RAM with clustering)
Master-slave replication, automatic failover
Simple values or data structures by keys
but complex operations like ZREVRANGEBYSCORE.
INCR & co (good for rate limiting or statistics)
Bit operations (for example to implement bloom filters)
Has sets (also union/diff/inter)
Has lists (also a queue; blocking pop)
Has hashes (objects of multiple fields)
Sorted sets (high score table, good for range queries)
Lua scripting capabilities (!)
Has transactions (!)
Values can be set to expire (as in a cache)
Pub/Sub lets one implement messaging
Best used: For rapidly changing data with a foreseeable database size (should fit mostly in memory).

For example: Stock prices. Analytics. Real-time data collection. Real-time communication. And wherever you used memcached before.

Clones of Google's Bigtable

HBase (V0.96.0)
Written in: Java
Main point: Billions of rows X millions of columns
License: Apache
Protocol: HTTP/REST (also Thrift)
Modeled after Google's BigTable
Uses Hadoop's HDFS as storage
Map/reduce with Hadoop
Query predicate push down via server side scan and get filters
Optimizations for real time queries
A high performance Thrift gateway
HTTP supports XML, Protobuf, and binary
Jruby-based (JIRB) shell
Rolling restart for configuration changes and minor upgrades
Random access performance is like MySQL
A cluster consists of several different types of nodes
Best used: Hadoop is probably still the best way to run Map/Reduce jobs on huge datasets. Best if you use the Hadoop/HDFS stack already.

For example: Search engines. Analysing log data. Any place where scanning huge, two-dimensional join-less tables are a requirement.

Cassandra (2.0.7)
Written in: Java
Main point: Best of BigTable and Dynamo
License: Apache
Protocol: Thrift & custom binary CQL3
Tunable trade-offs for distribution and replication (N, R, W)
Querying by column, range of keys (Requires indices on anything that you want to search on)
BigTable-like features: columns, column families
Can be used as a distributed hash-table, with an "SQL-like" language, CQL (but no JOIN!)
Data can have expiration (set on INSERT)
Writes can be much faster than reads (when reads are disk-bound)
Map/reduce possible with Apache Hadoop
All nodes are similar, as opposed to Hadoop/HBase
Very good and reliable cross-datacenter replication
Best used: When you write more than you read (logging). If every component of the system must be in Java. ("No one gets fired for choosing Apache's stuff.")

For example: Banking, financial industry (though not necessarily for financial transactions, but these industries are much bigger than that.) Writes are faster than reads, so one natural niche is data analysis.

Hypertable (0.9.7.16)
Written in: C++
Main point: A faster, smaller HBase
License: GPL 2.0
Protocol: Thrift, C++ library, or HQL shell
Implements Google's BigTable design
Run on Hadoop's HDFS
Uses its own, "SQL-like" language, HQL
Can search by key, by cell, or for values in column families.
Search can be limited to key/column ranges.
Sponsored by Baidu
Retains the last N historical values
Tables are in namespaces
Map/reduce with Hadoop
Best used: If you need a better HBase.

For example: Same as HBase, since it's basically a replacement: Search engines. Analysing log data. Any place where scanning huge, two-dimensional join-less tables are a requirement.

Accumulo (1.5.1)
Written in: Java and C++
Main point: A BigTable with Cell-level security
License: Apache
Protocol: Thrift
Another BigTable clone, also runs of top of Hadoop
Originally from the NSA
Cell-level security
Bigger rows than memory are allowed
Keeps a memory map outside Java, in C++ STL
Map/reduce using Hadoop's facitlities (ZooKeeper & co)
Some server-side programming
Best used: If you need to restict access on the cell level.

For example: Same as HBase, since it's basically a replacement: Search engines. Analysing log data. Any place where scanning huge, two-dimensional join-less tables are a requirement.

Special-purpose

Neo4j (2.0.2)
Written in: Java
Main point: Graph database - connected data
License: GPL, some features AGPL/commercial
Protocol: HTTP/REST (or embedding in Java)
Standalone, or embeddable into Java applications
Full ACID conformity (including durable data)
Both nodes and relationships can have metadata
Integrated pattern-matching-based query language ("Cypher")
Also the "Gremlin" graph traversal language can be used
Indexing of nodes and relationships
Nice self-contained web admin
Advanced path-finding with multiple algorithms
Indexing of keys and relationships
Optimized for reads
Has transactions (in the Java API)
Scriptable in Groovy
Online backup, advanced monitoring and High Availability is AGPL/commercial licensed
Best used: For graph-style, rich or complex, interconnected data. Neo4j is quite different from the others in this sense.

For example: For searching routes in social relations, public transport links, road maps, or network topologies.

ElasticSearch (1.1.1)
Written in: Java
Main point: Advanced Search
License: Apache
Protocol: JSON over HTTP (Plugins: Thrift, memcached)
Stores JSON documents
Has versioning
Parent and children documents
Documents can time out
Very versatile and sophisticated querying, scriptable
Write consistency: one, quorum or all
Sorting by score (!)
Geo distance sorting
Fuzzy searches (approximate date, etc) (!)
Asynchronous replication
Atomic, scripted updates (good for counters, etc)
Can maintain automatic "stats groups" (good for debugging)
Still depends very much on only one developer (kimchy).
Best used: When you have objects with (flexible) fields, and you need "advanced search" functionality.

For example: A dating service that handles age difference, geographic location, tastes and dislikes, etc. Or a leaderboard system that depends on many variables.

The "long tail"
(Not widely known, but definitely worthy ones)
Couchbase (ex-Membase) (2.0)
Written in: Erlang & C
Main point: Memcache compatible, but with persistence and clustering
License: Apache
Protocol: memcached + extensions
Very fast (200k+/sec) access of data by key
Persistence to disk
All nodes are identical (master-master replication)
Provides memcached-style in-memory caching buckets, too
Write de-duplication to reduce IO
Friendly cluster-management web GUI
Connection proxy for connection pooling and multiplexing (Moxi)
Incremental map/reduce
Cross-datacenter replication
Best used: Any application where low-latency data access, high concurrency support and high availability is a requirement.

For example: Low-latency use-cases like ad targeting or highly-concurrent web apps like online gaming (e.g. Zynga).

Scalaris (0.5)
Written in: Erlang
Main point: Distributed P2P key-value store
License: Apache
Protocol: Proprietary & JSON-RPC
In-memory (disk when using Tokyo Cabinet as a backend)
Uses YAWS as a web server
Has transactions (an adapted Paxos commit)
Consistent, distributed write operations
From CAP, values Consistency over Availability (in case of network partitioning, only the bigger partition works)
Best used: If you like Erlang and wanted to use Mnesia or DETS or ETS, but you need something that is accessible from more languages (and scales much better than ETS or DETS).

For example: In an Erlang-based system when you want to give access to the DB to Python, Ruby or Java programmers.

VoltDB (2.8.4.1)
Written in: Java
Main point: Fast transactions and rapidly changing data
License: GPL 3
Protocol: Proprietary
In-memory relational database.
Can export data into Hadoop
Supports ANSI SQL
Stored procedures in Java
Cross-datacenter replication
Best used: Where you need to act fast on massive amounts of incoming data.

For example: Point-of-sales data analysis. Factory control systems.

Kyoto Tycoon (0.9.56)
Written in: C++
Main point: A lightweight network DBM
License: GPL
Protocol: HTTP (TSV-RPC or REST)
Based on Kyoto Cabinet, Tokyo Cabinet's successor
Multitudes of storage backends: Hash, Tree, Dir, etc (everything from Kyoto Cabinet)
Kyoto Cabinet can do 1M+ insert/select operations per sec (but Tycoon does less because of overhead)
Lua on the server side
Language bindings for C, Java, Python, Ruby, Perl, Lua, etc
Uses the "visitor" pattern
Hot backup, asynchronous replication
background snapshot of in-memory databases
Auto expiration (can be used as a cache server)
Best used: When you want to choose the backend storage algorithm engine very precisely. When speed is of the essence.

For example: Caching server. Stock prices. Analytics. Real-time data collection. Real-time communication. And wherever you used memcached before.

Of course, all these systems have much more features than what's listed here. I only wanted to list the key points that I base my decisions on. Also, development of all are very fast, so things are bound to change.

Implementing Hash Map using chaining

First what is a hash function?

A hash function is a function which maps keys to indices of an array. So if k is the key and we have an array of size 10, then h(k) will be some integer value ranging between 0 to 9. So this means the hash function h maps the universe u of keys into the slots of array T[ 0 . . . n-1 ]

Now in the above solution there is some issue, what will happen when two keys have the same hash value. i.e.  In other words collision.

To avoid the above situation the easy technique is to do the chaining. Now our data structure will look like as below:

So now the array indices will be maintaining a linked list. Now if we have some key whose h(key) is coming as 1, then we first iterate over the linked list maintained at 1 indices and then add this data at last in the linked list.

Above Data structure is called HashTable/HashMap.

Source Code to implement a HashMap

package test.sachi.dsnalgos.hashmap;

public class HashMap<K extends Integer,V extends String> {

private Entry<K,V>[] bucket;

private int INITIAL_CAPACITY=10;

public HashMap()

{

init();

}

private void init() 

{

bucket=new Entry[INITIAL_CAPACITY];

}

private int hash(K key){

        return key % 10; 

    }

public void add(K key, V value){

int hash=hash(key);

if(bucket[hash]==null){

Entry<K,V> head=new Entry<K,V>(null,null,null);

Entry<K,V> newEntryNode=new Entry<K,V>(key,value,null);

head.next=newEntryNode;

bucket[hash]=head;

}else{

Entry<K,V> temp=bucket[hash];

while(temp.next !=null){

temp=temp.next;

}

Entry<K,V> newEntryNode=new Entry<K,V>(key,value,null);

temp.next=newEntryNode;

}

}

public V get(K key){

int hash=hash(key);

if(bucket[hash]==null){

return null;

}else{

Entry<K,V> temp=bucket[hash];

while(temp!=null){

temp=temp.next;

if(temp.key.equals(key)){

return (V) temp.value;

}

}

}

return null;

}

static class Entry<K,V>

{

K key;

V value;

Entry<K,V> next;

public Entry(K key,V value,Entry<K,V> next){

this.key=key;

this.value=value;

this.next=next;

}

}

}

ArrayList vs LinkedList

ArrayList and LinkedList both implements List interface and their methods and results are almost identical. However there are few differences between them which make one better over another depending on the requirement.

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

Conclusion: LinkedList element deletion is faster compared to ArrayList.

Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.

4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.

There are few similarities between these classes which are as follows:

Both ArrayList and LinkedList are implementation of List interface.
They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).



When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

References:

ArrayList documentation
LinkedList Javadoc

Understanding Trie Datastructure

For starters, let’s consider a simple word puzzle: find all the valid words in a 4x4 letter board, connecting adjacent letters horizontally, vertically, or diagonally. For example, in the following board, we see the letters 'R’, ‘A’, ‘I’, and ‘L’ connecting to form the word “RAIL”.

The naive solution to finding all valids words would be to explore the board starting from the upper-left corner and then moving depth-first to longer sequences, starting again from the second letter in the first row, and so on. In a 4x4 board, allowing vertical, horizontal and diagonal moves, there are 12029640 sequences, ranging in length from one to sixteen characters.

Now, our goal is to find the best data structure to implement this valid-word checker, i.e., our vocabulary. A few points to keep in mind:

1. We only need a single copy of each word, i.e., our vocabulary is a set, from a logical point of view.
2. We need to answer the following questions for any given word:

• Does the current character sequence comprise a valid word?
• Are there longer words that begin with this sequence? If not, we can abandon our depth-first exploration, as going deeper will not yield any valid words.

To illustrate the second point, consider the following board: There’s no point in exploring subsequent moves, since there are no words in the dictionary that start with “ABA”.

We’d love our data structure to answer these questions as quickly as possible. ~O(1) access time would be ideal!


We can define the Vocabulary interface like this

public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Candidate Data Structures

Implementing the contains() method requires a backing data structure that lets you find elements efficiently, while the isPrefix() method requires us to find the “next greater element”, i.e. we need to keep the vocabulary sorted in some way.

We can easily exclude hash-based sets from our list of candidates: while such a structure would give us constant-time checking for contains(), it would perform quite poorly on isPrefix(), in the worst case requiring that we scan the whole set.

For quite the opposite reason, we can also exclude sorted linked-lists, as they require scanning the list at least up to the first element that is greater than or equal to the searched word or prefix.

Two valid options are using a sorted array-backed list or a binary tree.

On the sorted array-backed list we can use binary search to find the current sequence if present or the next greater element at a cost of O(log2(n)), where n is the number of words in the dictionary.

We can implement an array-backed vocabulary that always maintains ordering of like this, using standard java.util.ArrayList and java.util.Collections.binarySeach:

public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }



If we decided to use a binary tree, the implementation could be even shorter and more elegant 

public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

Enter, the Trie 

Logarithmic performance and linear memory isn’t bad. But there are a few more characteristics of our application domain that can lead us to better performance: We can safely assume that all words are lowercase. We accept only a-z letters—no punctuation, no hyphens, no accents, etc. 

The dictionary contains many inflected forms: plurals, conjugated verbs, composite words (e.g., house –> housekeeper). Therefore, many words share the same stem. Words have a limited length. For example, if we are working on a 4x4 board, all words longer than 16 chars can be discarded. This is where the trie (pronounced “try”) comes in. But what exactly is a trie? Tries are neglected data structures, found in books but rarely in standard libraries. 

 For motivation, let’s first consider Computer Science’s poster child: the binary tree. Now, when we analyze the performance of a binary tree and say operation x is O(log(n)), we’re constantly talking log base 2. But what if, instead of a binary tree, we used a ternary tree, where every node has three children (or, a fan-out of three). Then, we’d be talking log base 3. (That’s a performance improvement, albeit only by a constant factor.) Essentially, our trees would become wider but shorter, and we could perform fewer lookups as we don’t need to descend quite so deep. Taking things a step further, what if we had a tree with fan-out equal to the number of possible values of our datatype? This is the motivation behind the trie. And as you may have guessed, a trie is indeed a tree! But, contrary to most binary-trees that you’d use for sorting strings, those that would store entire words in their nodes, each node of a trie holds a single character (and not even that, as we’ll see soon) and has a maximum fan-out equal to the length of the alphabet. In our case, the length of the alphabet is 26; therefore the nodes of the trie have a maximum fan-out of 26. And, while a balanced binary tree has log2(n) depth, the maximum depth of the trie is equal to the maximum length of a word! (Again, wider but shorter.) Within a trie, words with the same stem (prefix) share the memory area that corresponds to the stem. To visualize the difference, let’s consider a small dictionary made of five words. Assume that the Greek letters indicate pointers, and note that in the trie, red characters indicate nodes holding valid words.

The Implementation

As we know, in the tree the pointers to the children elements are usually implemented with a left and right variable, because the maximum fan-out is fixed at two.

In a trie indexing an alphabet of 26 letters, each node has 26 possible children; therefore, 26 possible pointers. Each node thus features an array of 26 (pointers to) sub-trees, where each value could either be either (if there is no such child) or another node.

Then, how do we look up a word in a trie? Here is the method that, given a String s, will identify the node that corresponds to the last letter of the word, if it exists in the tree:

public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }


Analyzing Performance

What makes the trie really perform well in these situations is that the cost of looking up a word or prefix is fixed and dependent only on the number of characters in the word and not on the size of the vocabulary.

In our specific domain, since we have strings that are at most 16 characters, exactly 16 steps are necessary to find a word that is in the vocabulary, while any negative answer, i.e. the word or prefix is not in the trie, can be obtained in at most 16 steps as well! Considering that we have previously ignored the length of the string when calculating running time complexity for both the array-backed sorted list and the tree, which is hidden in the string comparisons, we can as well ignore it here and safely state that lookup is done in O(1) time.

Considering space requirements (and remembering that we have indicated with M the bytesize of the dictionary), the trie could have M nodes in the worst case, if no two strings shared a prefix. But since we have observed that there is high degree of redundancy in the dictionary, there is a lot of compression to be done. The English dictionary that is used in the example code is 935,017 bytes and requires 250,264 nodes, with a compression ratio of about 73%.

However, despite the compression, a trie will usually require more memory than a tree or array. This is because, for each node, at least 26 x sizeof(pointer) bytes are necessary, plus some overhead for the object and additional attributes. On a 64-bit machine, each node requires more than 200 bytes, whereas a string character requires a single byte, or two if we consider UTF strings.

Conclusions

The trie is a very specialized data structure that requires much more memory than trees and lists. However, when specific domain characteristics apply, like a limited alphabet and high redundancy in the first part of the strings, it can be very effective in addressing performance optimization.

References

An extensive explanation of tries and alphabets can be found in chapter 5 of Robert Sedgewick’s book “Algorithms, 4th edition”.

Breadth First Search Implementation in Java

package sachi.test.datastructures;

import java.util.Queue;

import java.util.LinkedList;

import java.util.Scanner;

public class BreadthFirstSearch {

private Queue<Integer> queue;

public BreadthFirstSearch(){

queue= new LinkedList<Integer>();

}

public void breadthFirstSearch(int adjmtrx[][], int source){

int no_of_nodes=adjmtrx[source].length-1;

int visited[]=new int[no_of_nodes +1];

int i, element;

visited[source]=1;

queue.add(source);

while(!queue.isEmpty()){

element=queue.remove();

i=element;

System.out.print(i + "\t");

while(i<=no_of_nodes){

if(adjmtrx[element][i]==1 && visited[i]==0){

queue.add(i);

visited[i]=1;

}

i++;

}

}

}

public static void main(String[] args) {

int no_of_nodes,source;

Scanner scanner = null;

 

try{

System.out.println("Enter the number of nodes in the graph");

scanner = new Scanner(System.in);

no_of_nodes= scanner.nextInt();

int adjmtrx[][]=new int[no_of_nodes+1][no_of_nodes+1];

System.out.println("Enter the adjacency matrix");

    for (int i = 1; i <= no_of_nodes; i++)

        for (int j = 1; j <= no_of_nodes; j++)

        adjmtrx[i][j] = scanner.nextInt();

   

    System.out.println("Enter the source for the graph");

   

            source = scanner.nextInt(); 

            System.out.println("The BFS Traversal for the graph is given by ");

            BreadthFirstSearch bfs = new BreadthFirstSearch();

            bfs.breadthFirstSearch(adjmtrx, source);

 

}catch(Exception e){

 

}

scanner.close();

}

}