Unweighted Graphs Using Linked Lists

I hope you liked my post on Bellman ford graph algorithm implementation in Java. With slight changes to my existing code I have recently implemented the Unweighted Graph using linked lists algorithm in Java . You can add additional weight field to the Edge class in case if you want to implement the minimum spanning tree algorithm using linked lists .

/* copyright information 
   Author Name - Raj Gopal Bhallamudi
   Email - flame527@yahoo.com , rajgopal527@gmail.com
   Facebook - facebook.com/r5274
   Instagram - instagram.com/bhrajgopal
   */
   
   
import java.util.LinkedList;
import java.util.LinkedHashMap;
import java.util.Set;
import java.util.Iterator;
import java.util.Scanner;
import java.util.InputMismatchException;


	

class Edge {
	String edge;
}

class Graph {
	LinkedHashMap<String, LinkedList<Edge>> H = new LinkedHashMap<>();
	
}

public class Example {
	
	static int vertexCount=0;
	static int edgeCount=0;

	public static void main(String[] args) {
		
		Runtime runtime = Runtime.getRuntime();

      
        runtime.gc();
        long before = runtime.totalMemory() - runtime.freeMemory();

		Graph graphObject = null;
		bellmanFord(graphObject);
		
		runtime.gc();
        long after = runtime.totalMemory() - runtime.freeMemory();

        System.out.println("\n \n Total Memory used in bytes " + (after - before) );

	}

	static void bellmanFord(Graph graphObject) {
		Scanner scan = new Scanner(System.in);

		if (graphObject == null)
			graphObject = new Graph();

		int input = 0;
		
		

		do {
			System.out.println(
					"\n\n\n\n 1.create graph  2.print graph   3.insert vertex  4.insert edge\n 5.delete vertex   6.delete edge   7.search vertex   8.search edge \n 9.Delete graph 10.completed ");

			try {
			input = scan.nextInt();
			}
			catch (InputMismatchException e) {
	            scan.nextLine(); 
	        }
			
			switch (input) {

			case 1:
				if (graphObject.H.size() > 0)
					System.out.println("Graph already created");
				else
					creategraph(graphObject, scan);
				break;

			case 2:
				if (graphObject.H.size() > 0)
					display(graphObject);
				else
					System.out.println("Graph is empty");
				break;

			case 3:
				if (graphObject.H.size() > 0)
					insertvertex(graphObject, scan);
				else
					System.out.println("Graph is empty");
				break;

			case 4:
				if (graphObject.H.size() > 0)
					insertedge(graphObject, scan);
				else
					System.out.println("Graph is empty");
				break;

			case 5:
				if (graphObject.H.size() > 0)
					deletevertex(graphObject, scan);
				else
					System.out.println("Graph is empty");
				break;

			case 6:
				if (graphObject.H.size() > 0)
					deleteedge(graphObject, scan);
				else
					System.out.println("Graph is empty");
				break;

			case 7:
				if (graphObject.H.size() > 0)
					searchvertex(graphObject, scan);
				else
					System.out.println("Graph is empty");
				break;

			case 8:
				if (graphObject.H.size() > 0)
					searchedge(graphObject, scan);
				else
					System.out.println("Graph is empty");
				break;

			case 9:
				if (graphObject.H.size() > 0)
					del(graphObject);
				else
					System.out.println("Graph is empty");
				break;

			case 10:
				break;

			default:
				System.out.println("Invalid input received please try again");
				break;
			}
		} while (input != 10);
		 
		

	}

	static void display(Graph graphObject) {
		System.out.println("\n CREATED GRAPH IS \n");
		for (String vertex : graphObject.H.keySet()) {
			LinkedList<Edge> edges = graphObject.H.get(vertex);
			if (edges.size() > 0) {
				for (Edge edge : edges)
					System.out.print("(" + vertex + "," + edge.edge + ")"+ " ");
				System.out.println();
			} else {
				System.out.print("(" + vertex + ")");
				System.out.println();
			}	
		}
		System.out.println("\n\n Total number of vertices = "+vertexCount);
		System.out.println(" Total number of edges = "+edgeCount);
	}



	

	static void creategraph(Graph obj, Scanner scan) {
		String input, invalid = "END";
		LinkedList<String> vertex = new LinkedList<>();
		do {
			System.out.println("enter a vertex else type END");
			input = scan.next();
			if (!(input.equals(invalid)))
				if (!(vertex.contains(input))) {
					vertex.add(input);
					vertexCount++;
				} else {
					System.out.println("Duplicate vertex not allowed");
				}
		} while (!input.equals(invalid));

		for (int current = 0; current < vertex.size(); current++) {
			String currentVertex = vertex.get(current);
			LinkedList<Edge> edgeList=edgelistinsert(obj,currentVertex,vertex,scan);
			obj.H.put(currentVertex, edgeList);
		}
	}

	

	static void insertvertex(Graph obj, Scanner sc) {
		String currentVertex;
		System.out.println("Enter a vertex");
		currentVertex = sc.next();
		if (obj.H.containsKey(currentVertex))
			System.out.println("vertex already present");
		else {
			LinkedList<String> vertex = new LinkedList<>(obj.H.keySet());
			LinkedList<Edge> edgeList = edgelistinsert(obj,currentVertex,vertex,sc);
			obj.H.put(currentVertex , edgeList);
			vertexCount++;
		}

	}

	static void insertedge(Graph obj, Scanner sc) {
		String firstVertex, secondVertex;
		int duplicateFlag;
		System.out.println("Enter first end vertex");
		firstVertex = sc.next();
		if (obj.H.containsKey(firstVertex)) {
			System.out.println("Enter second end vertex");
			secondVertex = sc.next();
			if (obj.H.containsKey(secondVertex)) {
				LinkedList<Edge> edgeList = obj.H.get(firstVertex);
				duplicateFlag = search(obj, firstVertex, secondVertex);
				if (duplicateFlag == 1) {
					System.out.println("edge already present");
				} else {
						 Edge temp2 = new Edge();
						 temp2.edge = secondVertex;
						 edgeList.add(temp2);
						 insideinsert(obj,secondVertex,firstVertex);
						 edgeCount=edgeCount+2;
				     }
			} else {
				System.out.println("invalid second end vertex");
			}

		} else {
			System.out.println("invalid first end vertex");
		}
	}

	static void searchedge(Graph obj, Scanner sc) {
		String firstVertex, secondVertex;
		int flag = 0;
		System.out.println("Enter first end vertex");
		firstVertex = sc.next();
		if (obj.H.containsKey(firstVertex)) {
			System.out.println("Enter second end vertex");
			secondVertex = sc.next();
			if (obj.H.containsKey(secondVertex)) {
				flag = search(obj, firstVertex, secondVertex);
				if (flag == 1) {
					System.out.println("edge is present");
					return;
				}
			} else {
				System.out.println("Invalid second vertex");
				return;
			}
		} else {
			System.out.println("Invalid first vertex");
			return;
		}
		 if (flag == 0) {
			System.out.println("edge is not present");
		}
	}


	static void searchvertex(Graph obj, Scanner sc) {
		String vertex;
		System.out.println("Enter a vertex");
		vertex = sc.next();
		if (obj.H.containsKey(vertex)) {
			System.out.println("vertex present");
		} else {
			System.out.println("vertex not present");
		}

	}

	static void deletevertex(Graph obj, Scanner sc) {
		String vertex;
		System.out.println("Enter a vertex");
		vertex = sc.next();
		if (obj.H.containsKey(vertex)) {
			
			LinkedList<Edge> edge =obj.H.get(vertex);
			edgeCount = edgeCount - edge.size();
			
			
			Iterator<Edge> str = edge.iterator();
			while (str.hasNext()) {
				LinkedList<Edge> edgeList = obj.H.get(str.next().edge);
				iteratoredgedelete(edgeList,vertex);
				str.remove();
			}
			
			obj.H.remove(vertex);
			
			vertexCount--;

		} else {
			System.out.println("vertex not present");
		}
	}

	static void deleteedge(Graph obj, Scanner sc) {
		String firstVertex, secondVertex;
		System.out.println("Enter first end vertex");
		firstVertex = sc.next();
		if (obj.H.containsKey(firstVertex)) {
			System.out.println("Enter second end vertex");
			secondVertex = sc.next();
			if (obj.H.containsKey(secondVertex)) {

				int flag = search(obj, firstVertex, secondVertex);
				if (flag == 1) {
					LinkedList<Edge> edgeList = obj.H.get(firstVertex);
					iteratoredgedelete(edgeList,secondVertex);
					edgeList = obj.H.get(secondVertex);
					iteratoredgedelete(edgeList,firstVertex);
					
				} else {
					System.out.println("edge not present");
				}
			} else {
				System.out.println("invalid second vertex");
			}
		} else {
			System.out.println("invalid first vertex");
		}

	}

	static void del(Graph obj) {
		Set<String> vertices = obj.H.keySet();
		for (String vertex : vertices)
			obj.H.remove(vertex);
	}


	static int search(Graph obj, String firstVertex, String secondVertex) {
		int flag = 0;
		LinkedList<Edge> edgeList = obj.H.get(firstVertex);
		for (Edge edge : edgeList) {
			if (edge.edge.equals(secondVertex)) {
				flag = 1;
				break;
			}
		}
		return flag;
	}
	
	static LinkedList<Edge> edgelistinsert(Graph obj,String  currentVertex, LinkedList<String> vertex,   Scanner scan)
	{
		int flag = 0;
		String input,secondVertex;
		LinkedList<Edge> edgeList;
		
		if(obj.H.get(currentVertex)  !=null)
		{
			edgeList=obj.H.get(currentVertex);
		}
		else {
			edgeList=new LinkedList<>();
		}
		
		
		do {
			System.out.println("Is There any vertex coming out from vertex " + currentVertex + " press Y or N");
			input = scan.next();
			if (input.equals("Y")) {
				System.out.println("enter the other end vertex coming out from " + currentVertex);
				secondVertex = scan.next();
				flag=checkduplicate(edgeList,secondVertex);
				if (flag != 1) {
					if (vertex.contains(secondVertex)) {
							Edge temp2 = new Edge();
							temp2.edge = secondVertex;
							edgeList.add(temp2);
							insideinsert(obj,secondVertex,currentVertex);
							edgeCount=edgeCount+2;
					} else {
						System.out.println("Invalid vertex");
					}
				} else
					System.out.println("Duplicate vertex not allowed");
			}

		} while (!(input.equals("N")));
		
		return edgeList;
	}
	
	static int checkduplicate(LinkedList<Edge> edgeList, String edge)
	{
		for (Edge temp : edgeList) {
			if (temp.edge.equals(edge)) {
				return 1;
			}
		}		
		return 0;
	}
	
	static void iteratoredgedelete(LinkedList<Edge> edgeList,String vertex)
	{
		
		Iterator<Edge> iterator = edgeList.iterator();
		while (iterator.hasNext()) {
			if (iterator.next().edge.equals(vertex)) {
				iterator.remove();
				edgeCount--;
				break;
			}
		}
		
	}
	
	static void insideinsert(Graph obj,String secondVertex ,String currentVertex ) {
		if(obj.H.containsKey(secondVertex) ) {
			
			Edge edge = new Edge();
			edge.edge= currentVertex;
			obj.H.get(secondVertex).add(edge);
		}
		else {
			
			LinkedList<Edge> insideEdge = new LinkedList<>();
			Edge edge = new Edge();
			edge.edge= currentVertex;
			insideEdge.add(edge);
			obj.H.put(secondVertex, insideEdge);
			
		}
		
		
	}

}