Sunday 13 December 2015

Iterator Pattern in Java | Simple Genric implementation

Hello Friends,

Today I wish to share with you the Iterator pattern. It is very powerful way to iterate over any collection. It is fast and also helpful in hiding the complicated way to traverse the underlying data structure of the collection.

Suppose we have a Collection of String Objects stored in a class. Today I hold the items in simple array, tomorrow I may choose to use LinkedList to hold the items, and may be later I decide to use Tree or any other efficient data structure to hold my data. I want the users of my collection class not to get troubled by my decision of changing the underlying data structure. I want to provide them a uniform way to access the items in the collection.

The Iterator pattern solves this problem nicely. I can provide an Iterator to my collection and it can be used by the users of my collection class to iterate over the items in the collection. The internal traversing can be handled internally in the Iterator class but the iteration methods contract never changes. Lets see below as how we can implement this.

An interface iterator can be defined with hasNext() returning boolean [ true if collection has more items to iterate, else false ], and next() to get the next item in the collection. Collection class has a private concrete class implementing the Iterator and the object of concrete class(implementing the Iterator) can be exposed using a public method.


Suppose we have a collection class named Lib.java It can hold items and I want a uniform way using which outside world (LibManager.java) can iterate my collection class.

Lets see the UML class diagram for this.



To keep the implementation simple, I have just kept add method in ICollection. Also the exceptional conditions such as array index out of bounds are not handled. We can do all that once we get the understanding of the Iterator pattern.
Actual java.util classes Like ArrayList, LinkedList etc uses this pattern. They implement java.util.Iterable and hence enhanced for loop ( for each loop ) can be used with them.
Enhanced for loop uses iterator to iterate and hence is faster. Usually in our code we get List of object, List can be actually be implemented by LinekdList or ArrayList but using Iterator to iterate is always faster as to iterate any element using Iterator  only one step ahead needs to be taken whereas in case of traditional for loop, if the concrete implementation is LinekedList then again and again items will be traversed starting from the start of the linkedList.
The Underlying data structure can change anytime, (say from ArrayList to LinekdList) hence using Iterator ( or enhanced for loop ) to iterate is always preferable.



public interface ICollection<E> {
	public void add(E element);
}
 
public interface SIterable<P> {
	public CIterator<P> iterator();
}
 
public interface CIterator<L> {
	public boolean hasNext();

	public L next();
}
 
public class Lib<T> implements SIterable<T>,ICollection<T>{
	private Object[] items;
	private int maxSize;
	private int size;
	public Lib(int size){
		maxSize = size;
		items = new Object[maxSize];
	}
	@Override
	public void add(T element) {
		items[size++] = element;
	}
	
	@Override
	public CIterator<T> iterator() {
		return new LibIterator();
	}
	
	private class LibIterator implements CIterator<T>{
		int iteratingIndex = 0;
		@Override
		public boolean hasNext() {
			return iteratingIndex < size;
		}

		@Override
		public T next() {
			Object nextItem = items[iteratingIndex];
			iteratingIndex++;
			return ((T)nextItem);
		}
		
	}
}
 
public class LibManager {
	public static void main(String[] args) {
		Lib<String> lib = new Lib<String>(5);
		lib.add("Bread");
		lib.add("Butter");
		lib.add("Apple");
		lib.add("Orange");
		lib.add("Pineapple");
		CIterator<String> itr = lib.iterator();
		while(itr.hasNext()){
			System.out.println(itr.next());
		}
	}
}

Saturday 28 November 2015

Breadth-first search in java | using Adjacency list and Adjacency Matrix.

Dear Friends,

I am here with a famous traversal method for Graph : Breadth first search [BFS]

This method is based on the idea of visiting a graph by taking breadth wise approach. The method will become more clear as we see the diagram below and then go through the code for BFS.

We need three basic entities for implementation of BFS

1. Graph
2. Queue
3. State  : {NEW, IN_Q, VISITED} This represents the Graph-node's state, initially all the nodes are in NEW state and as it is added in the queue, its state is changed to IN_Q and as it is removed from the queue, its state is changed to VISITED.




State : {NEW,IN_Q,VISITED}
Queue : size = 0
Graph:
vertices = {1,2,3,4,5,6,7}
node1 : 
neighbourList = 2->3->4->null    
state : State.NEW
node2 : 

neighbourList = 1->5->null                                
state : State.NEW
node3 : 

neighbourList = 1->6->7->null                          
state : State.NEW
node4 : 

neighbourList = 1->null                                     
state : State.NEW
node5 : 

neighbourList = 2->null                                     
state : State.NEW
node6 :

neighbourList = 3->null                                     
state : State.NEW
node7 : 

neighbourList = 3->null                                     
state : State.NEW
node8 : 
neighbourList = null                                          
state : State.NEW
node9 : 
neighbourList = 10->11->12->13->null            
state : State.NEW
node10 : 
neighbourList = 9->11->null                           
state : State.NEW
node11 : 
neighbourList = 9->10->14->null                   
state : State.NEW
node12 : 
neighbourList = 9->14->null
state : State.NEW
node13 : 
neighbourList = 9->null
state : State.NEW
node14 : 
neighbourList = 11->12->null
state : State.NEW


Basic BFS Algorithm
1. Execute a loop for 'node-size' number of iterations.
2. for each node with state != State.VISITED call the bfs(Node currentNode)
3. queue.add(currentNode) and set the state of the current node :  currentNode.state = State.IN_Q
4. run a while loop until queue.isEmpty() != true
   Node visitedNode = queue.remove()
   visitedNode.state = State.VISITED
   print(visitedNode)
   queue.add(all the nodes with state = State.NEW from visitedNode.neighbourList and mark each node's state as State.IN_Q)

Lets Apply BFS to above graph

Adding in the queue,  the node1 , marked it as In_Q
Removing from queue, the node1 , marked it as VISITED and Printing it
Printing the Visited node1
Adding in the queue,  the node2 , marked it as In_Q
Adding in the queue,  the node3 , marked it as In_Q
Adding in the queue,  the node4 , marked it as In_Q
Removing from queue, the node2 , marked it as VISITED and Printing it
Printing the Visited node2
Adding in the queue,  the node5 , marked it as In_Q
Removing from queue, the node3 , marked it as VISITED and Printing it
Printing the Visited node3
Adding in the queue,  the node6 , marked it as In_Q
Adding in the queue,  the node7 , marked it as In_Q
Removing from queue, the node4 , marked it as VISITED and Printing it
Printing the Visited node4
Removing from queue, the node5 , marked it as VISITED and Printing it
Printing the Visited node5
Removing from queue, the node6 , marked it as VISITED and Printing it
Printing the Visited node6
Removing from queue, the node7 , marked it as VISITED and Printing it
Printing the Visited node7
Adding in the queue,  the node8 , marked it as In_Q
Removing from queue, the node8 , marked it as VISITED and Printing it
Printing the Visited node8
Adding in the queue,  the node9 , marked it as In_Q
Removing from queue, the node9 , marked it as VISITED and Printing it
Printing the Visited node9
Adding in the queue,  the node10 , marked it as In_Q
Adding in the queue,  the node11 , marked it as In_Q
Adding in the queue,  the node12 , marked it as In_Q
Adding in the queue,  the node13 , marked it as In_Q
Removing from queue, the node10 , marked it as VISITED and Printing it
Printing the Visited node10
Removing from queue, the node11 , marked it as VISITED and Printing it
Printing the Visited node11
Adding in the queue, the node14 , marked it as In_Q
Removing from queue, the node12 , marked it as VISITED and Printing it
Printing the Visited node12
Removing from queue, the node13 , marked it as VISITED and Printing it
Printing the Visited node13
Removing from queue, the node14 , marked it as VISITED and Printing it
Printing the Visited node14

Now Lets see as how we can implement it : Lets use Adjacency List. Friends Please find the code in java below:

/**
 * 
 * @author krishna kumar
 * 
 *         This is a basic implementation of BFS for Graph using Adjacency list.
 *
 */
public class Graph {

    private Node[] vertices; // stores the nodes of the graph
    private int size; // number of nodes in the graph
    private Queue queue;
    public Graph(int size) {
        this.size = size;
        vertices = new Node[size];
        addNodes();
        queue = new Queue(size);
    }

    public class Node {
        int name;
        Neighbour neighbourList;
        State state; 
        Node(int name) {
            this.name = name;
            state = State.NEW;
        }
    }

    public class Neighbour {
        int index;
        Neighbour next;

        public Neighbour(int index, Neighbour next) {
            this.index = index;
            this.next = next;
        }
    }
    private void addNodes(){
        for(int i = 1; i <= size ; i++){
            addNode(i);
        }
    }
    public void addNode(int name) {
        vertices[name - 1] = new Node(name);
    }

    public void addEdge(int sourceName, int destiName) {
        int srcIndex = sourceName - 1;
        int destiIndex = destiName - 1;
        Node srcNode = vertices[srcIndex];
        Node destiNode = vertices[destiIndex];
        srcNode.neighbourList = new Neighbour(destiIndex, srcNode.neighbourList);
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        destiNode.neighbourList = new Neighbour(srcIndex, destiNode.neighbourList);
    }



    public void traverseGraph() {
        System.out.println("Using BFS Traversing the graph");

        for (int i = 0; i < size; i++) {
            if (vertices[i].state != State.VISITED) {
                bfs(vertices[i]);
            }
        }
    }

    private void bfs(Node currentNode) {
        queue.add(currentNode);
        currentNode.state = State.IN_Q;
        while(!queue.isEmpty()){
            Node visitedNode = queue.remove();
            visitedNode.state = State.VISITED;
            System.out.println(visitedNode.name);
            Neighbour temp = visitedNode.neighbourList;
            while(temp != null){
                Node neighbour = vertices[temp.index];
                if(neighbour.state == State.NEW){
                    queue.add(neighbour);
                    neighbour.state = State.IN_Q;
                }
                temp = temp.next;
            }
        }
    }

    public enum State {
        NEW, IN_Q, VISITED
    };

    /**
     * 
     * This is a simple queue implemented using array. Although ideally queue
     * should be implemented in circular style so as to use the empty area when
     * items are deleted from the front but for BFS implementation we each item
     * is added only once so if the size of the queue is taken as the size of
     * the items then there is no need for circular styled implementation.
     *
     */
    public class Queue {
        Node[] queue;
        int maxSize;
        int front = -1,rear = -1;

        Queue(int maxSize) {
            this.maxSize = maxSize;
            queue = new Node[maxSize];
        }

        public void add(Node node) {
            queue[++rear] = node;
        }

        public Node remove() {
            Node node = queue[++front];
            queue[front] = null;
            return node;
        }

        public boolean isEmpty() {
            return front == rear;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(14);
        graph.addEdge(1, 4);
        graph.addEdge(1, 3);
        graph.addEdge(1, 2);
        graph.addEdge(2, 5);
        graph.addEdge(3, 7);
        graph.addEdge(3, 6);
        graph.addEdge(9, 13);
        graph.addEdge(9, 12);
        graph.addEdge(9, 11);
        graph.addEdge(9, 10);
        graph.addEdge(10, 11);
        graph.addEdge(11, 14);
        graph.addEdge(12, 14);
        graph.traverseGraph();
    }
}






Below friends, please find the code for Implementation of BFS using Adjacency Matrix


/**
 * 
 * @author krishna kumar
 * 
 *         Below code shows basic implementation of DFS in a graph. Graph has
 *         been implemented using adjacency matrix
 *
 */
public class Graph {
    private int[][] adjacencyMatrix;
    private int size; // number of nodes in the graph
    private State[] states;
    private Queue queue;
    public Graph(int size) {
        this.size = size;
        adjacencyMatrix = new int[size][size];// Initialized with all 0s
        states = new State[size];
        for (int i = 0; i < size; i++) {
            states[i] = State.NEW;
        }
        queue = new Queue(size);
    }

    public void addEdge(int sourceName, int destinationName) {
        int sourceIndex = sourceName - 1;
        int destinationIndex = destinationName - 1;
        adjacencyMatrix[sourceIndex][destinationIndex] = 1;
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        adjacencyMatrix[destinationIndex][sourceIndex] = 1;
    }

    public void traverseGraph() {
        System.out.println("Using BFS Traversing the graph");

        for (int i = 0; i < size; i++) {
            if (states[i] != State.VISITED) {
                bfs(i+1);
            }
        }
    }

    private void bfs(int currentNodeName) {
        queue.add(currentNodeName);
        states[currentNodeName-1] = State.IN_Q;
        while(!queue.isEmpty()){
            int visitedNodeName = queue.remove();
            states[visitedNodeName-1] = State.VISITED;
            System.out.println(visitedNodeName);
            for(int i = 0; i < size; i++){
                if(adjacencyMatrix[visitedNodeName-1][i] != 0){
                    if(states[i] == State.NEW){
                        queue.add((i+1));
                        states[i] = State.IN_Q;
                    }
                }
            }
        }
    }

    public enum State {
        NEW, IN_Q, VISITED
    };

    /**
     * 
     * This is a simple queue implemented using array. Although ideally queue
     * should be implemented in circular style so as to use the empty area when
     * items are deleted from the front but for BFS implementation we each item
     * is added only once so if the size of the queue is taken as the size of
     * the items then there is no need for circular styled implementation.
     *
     */
    public class Queue {
        Integer[] queue;
        int maxSize;
        int front = -1,rear = -1;

        Queue(int maxSize) {
            this.maxSize = maxSize;
            queue = new Integer[maxSize];
        }

        public void add(int node) {
            queue[++rear] = node;
        }

        public int remove() {
            int node = queue[++front];
            queue[front] = null;
            return node;
        }

        public boolean isEmpty() {
            return front == rear;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(14);
        
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(3, 6);
        graph.addEdge(3, 7);
        graph.addEdge(9, 10);
        graph.addEdge(9, 11);
        graph.addEdge(9, 12);
        graph.addEdge(9, 13);
        graph.addEdge(10, 11);
        graph.addEdge(11, 14);
        graph.addEdge(12, 14);
        graph.traverseGraph();
    }

}


Tuesday 24 November 2015

Understanding Depth first Search DFS using Java (for trees and Graphs)

Hello Friends,

DFS is one of the algorithm that we can use to traverse the elements of a Graph.

Lets try to build the algorithm for DFS below. For simplicity lets use tree with multiple children (tree is also a special type of graph).





Lets try to follow below steps and see how we traverse the above tree.


Lets have 3 basic entities to implement DFS algorithm:
1. currentNode
2. currentConnectedList (List to contain connected nodes)
3. visited[]  (Array of type boolean and  size = number of nodes in the graph and all cells initialized with false, let us have node with name 'i' be mapped with cell with index as 'i-1')

 

Algorithm :
1. Pick a node and mark it as currentNode
2. For the currentNode, find the connected nodes and add them in its currentConnectedList
3. Set the cell value in array visited as true for the cell corresponding to the currentNode
4. print the visited node name print(nodeName)
5. pick the first Non visited node from the current node's currentConnectedList and mark it as currentNode
In case currentConnectedList has no nodes in it or all the nodes have been visited then go to parent Node of the currentNode and pick next non visited node. In case the parent node is null then break the loop.
[we have put the condition to pick the non visited ones, when working with Graphs with cycles then it is this condition that prevents the algorithm from running infinitely by being stuck in the cycle.]
6. Go to step 2.



currentNode = 1
visited = [true][false][false][false][false][false][false][false][false][false][false][false][false][false]
print(1) 
currentConnectedList = 2->7->14 [1st non visited node is 2 so
2 will be picked next and we will come back for 7 and 14 later]

currentNode = 2
visited = [true][true][false][false][false][false][false][false][false][false][false][false][false][false]
print(2)
currentConnectedList= 3->5

currentNode = 3
visited = [true][true][true][false][false][false][false][false][false][false][false][false][false][false]
print(3)
currentConnectedList= 4

currentNode = 4
visited = [true][true][true][true][false][false][false][false][false][false][false][false][false][false]
print(4)
currentConnectedList= NULL

As currentConnectedList has no nodes so we go to parent of 4, i.e. 3. Lets go to 3 and see who is left unvisited. At currentNode = 3 we find only one element in
connectedList = 4, and 4 already has been visited (we see in the Visited array) so nothing left to pick from here

Lets go to parent of 3, i.e. 2 and see who is left unvisited. for 2 we see connectedList = 3->5, from visited array we find 3 already have been visited so now we pick 5

currentNode = 5
visited = [true][true][true][true][true][false][false][false][false][false][false][false][false][false]
print(5)
currentConnectedList= 6

currentNode
= 6
visited = [true][true][true][true][true][true][false][false][false][false][false][false][false][false]
print(6)
currentConnectedList= NULL

Similar to above again we have a situation when connectedList do not have any element.
Lets go to parent of 6 i.e. 5 and there we see only connected element was 6 which has already
been visited so we go to parent of 5 i.e. 2 and again we find connectedList = 3->5 and these
both elements have been visited. So now lets see parent of 2 i.e 1, for 1 we see connectedList = 2->7->14.
As per our rule, lets pick first non visited node from the connected List i.e. 7

currentNode = 7
visited = [true][true][true][true][true][true][true][false][false][false][false][false][false][false]
print(7)
currentConnectedList= 8->10->13

currentNode = 8
visited = [true][true][true][true][true][true][true][true][false][false][false][false][false][false]
print(8)
currentConnectedList= 9

currentNode = 9
visited = [true][true][true][true][true][true][true][true][true][false][false][false][false][false]
print(9)
currentConnectedList= NULL

going to 8 we see no more node left unvisited so lefts go to 7 and there we see connectedList = 8->10
and 8 has already been visited so next unvisited node is 10

currentNode = 10
visited = [true][true][true][true][true][true][true][true][true][true][false][false][false][false]
print(10)
currentConnectedList= 11->12

currentNode = 11
visited = [true][true][true][true][true][true][true][true][true][true][true][false][false][false]
print(11)
currentConnectedList= null

Going to 10 , we find connectedList = 11->12 and as 11 has already been visited so next unvisited node is 12

currentNode = 12
visited = [true][true][true][true][true][true][true][true][true][true][true][true][false][false]
print(12)
currentConnectedList= NULL

Going to parent of 12 i.e. 10 we find all the nodes in its connectedList have been visited
so going to parent of 10 i.e. 7 we find connectedList = 8->10->13, 8 and 10 have already been visited so next we have 13 to pick

currentNode = 13
visited = [true][true][true][true][true][true][true][true][true][true][true][true][true][false]
print(13)
currentConnectedList= NULL

Going back to 7 we find no more unvisited node in the connectedList, so going to parent of 7 i.e. 1 we see its connectedList = 2->7->14.
As 2 and 7 have already been visited, we are left with 14.

currentNode = 14
visited = [true][true][true][true][true][true][true][true][true][true][true][true][true][true]
print(14)
currentConnectedList= NULL

As no element in the connectedList, we go to the parent of 14, i.e. 1 and 1 has all its nodes in the connectedList 2->7->14 as visited.
Parent of 1 is Null hence we have reached the starting Node, so we are done with visiting all the nodes.

Now having understood a basic idea about the DFS, lets see a graph below and do some analysis.








Here we see the graph contains 3 sub graphs, 1,2,3,4,5,6,7 are connected then 9,10,11 are connected and then 8 is alone. These 3 sub graph make up our complete graph. Suppose this graphs represents good baseball players from 3 different teams (say Team A, Team B and Team C) who are coming to some separate city be part of some super team. Now suppose we wish to pass some information to all these players then it is enough if we pass that information to any 1 player from each team (so at-least  we need to pass information to 3 players).

Here DFS can come handy. We can start a for loop set for 11 iterations and then run the DFS for the node (representing a player) if it is not visited. DFS will visit all the connected nodes (players). Then coming back to the next iterations of the loop, as another non visited node is encountered (meaning we have a node from another sub graph) we need to  execute DFS  again  to visit the nodes of that sub graph.

In above case 3 times DFS will run 1st for Node-1, 2nd for Node 8 and 3rd for Node-9.

Now lets see the implementation of DFS below:


Below lets see the code for DFS in graph implemented using Adjacency matrix and then using Adjacency list

Code using Adjacency Matrix :

/**
 * 
 * @author krishna kumar
 * 
 *         Below code shows basic implementation of DFS in a graph. Graph has
 *         been implemented using adjacency matrix
 *
 */
public class Graph {
    private int[][] adjacencyMatrix;
    private int size; // number of nodes in the graph
    private boolean[] visited;

    public Graph(int size) {
        this.size = size;
        adjacencyMatrix = new int[size][size];// Initialized with all 0s
        visited = new boolean[size];
    }

    public void addEdge(int sourceName, int destinationName) {
        int sourceIndex = sourceName - 1;
        int destinationIndex = destinationName - 1;
        adjacencyMatrix[sourceIndex][destinationIndex] = 1;

        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        adjacencyMatrix[destinationIndex][sourceIndex] = 1;
    }

    public void traverseGraph() {
        System.out.println("Using DFS Traversing the graph");
        /*
         * If graph contains disconnected nodes or sub graphs then below loops
         * makes sure that all such nodes or sub graphs are also visited
         * 
         * In a single connected graph below loop is not needed and simply
         * dfs(1); can be called and the graph will be visited.
         */
        for (int i = 1; i <= size; i++) {
            if (!visited[i - 1]) {
                dfs(i);
            }
        }
    }

    private void dfs(int currentNodeName) {
        visited[currentNodeName - 1] = true;
        System.out.println(currentNodeName);
        for (int i = 0; i < size; i++) {
            if (adjacencyMatrix[currentNodeName - 1][i] != 0) {
                if (!visited[i]) {
                    dfs(i + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(11);

        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 3);
        graph.addEdge(3, 5);
        graph.addEdge(3, 6);
        graph.addEdge(4, 5);
        graph.addEdge(4, 7);
        graph.addEdge(9, 11);
        graph.addEdge(10, 11);
        graph.traverseGraph();
    }

}


Below lets use adjacency List and see the implementation. For Linked List implementation of Stack styled Linked list have been used [ holding the reference of the last added element in the graph]
We will use class Node to represent the graph-node so  instead of separate array 'visited', we can simply declare a boolean field : 'visited' in class Node itself.

package com.graph.adjacencylist;

/**
 * 
 * @author krishna kumar
 * 
 *         This is a basic implementation of Graph using Adjacency list.
 *
 */
public class Graph {

    private Node[] vertices; // stores the nodes of the graph
    private int size; // number of nodes in the graph

    public Graph(int size) {
        this.size = size;
        vertices = new Node[size];
    }

    public class Node {
        int name;
        boolean visited = false;
        Neighbour neighbourList;

        Node(int name) {
            this.name = name;
        }
    }

    public class Neighbour {
        int index;
        Neighbour next;

        public Neighbour(int index, Neighbour next) {
            this.index = index;
            this.next = next;
        }
    }

    public void addNode(int name) {
        vertices[name - 1] = new Node(name);
    }

    public void addEdge(int sourceName, int destiName) {
        int srcIndex = sourceName - 1;
        int destiIndex = destiName - 1;
        Node srcNode = vertices[srcIndex];
        Node destiNode = vertices[destiIndex];
        srcNode.neighbourList = new Neighbour(destiIndex, srcNode.neighbourList);
        // the graph is non directional so if from S, D is reachable then vice
        // versa is also true
        destiNode.neighbourList = new Neighbour(srcIndex, destiNode.neighbourList);
    }

    public void traverseGraph() {
        /*
         * If graph contains disconnected nodes or sub graphs then below loops
         * makes sure that all such nodes or sub graphs are also visited
         * 
         * In a single connected graph below loop is not needed and simply
         * dfs(vertices[0]); can be called and the graph will be visited.
         */
        for (int i = 0; i < size; i++) {
            if (!vertices[i].visited) {
                dfs(vertices[i]);
            }
        }
    }

    private void dfs(Node currentNode) {
        currentNode.visited = true;
        System.out.println(currentNode.name);
        Neighbour temp = currentNode.neighbourList;
        while (temp != null) {
            if (!vertices[temp.index].visited) {
                dfs(vertices[temp.index]);
            }
            temp = temp.next;
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(11);
        graph.addNode(1);
        graph.addNode(2);
        graph.addNode(3);
        graph.addNode(4);
        graph.addNode(5);
        graph.addNode(6);
        graph.addNode(7);
        graph.addNode(8);
        graph.addNode(9);
        graph.addNode(10);
        graph.addNode(11);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2,3);
        graph.addEdge(3,5);
        graph.addEdge(3, 6);
        graph.addEdge(4, 5);
        graph.addEdge(4,7);
        graph.addEdge(9,11);
        graph.addEdge(10,11);
        graph.traverseGraph();
    }
}