Graphs Using Linked Lists
One may feel that it's really difficult to create a graph in runtime but now this difficult problem is solved . Now a graph can be created in runtime and I have written a Java code to implement Bellman ford algorithm using linked lists . I preferred Java over other programming languages because Java has support for powerful collections framework , Java does not use pointers but written in C , Java program can be converted to C program , let it be any programming language the logic is always the same I hope you got my point , Java comes with power of Hadoop which can process terrabytes of data , Java is platform independent and its more convenient to write complex logic in Java ,Java is used in Billions of devices and if each device pays me minimum 4 dollars for using my algorithm then I would become a Billionaire and reach my destination . I hope this post on Graphs using Linked Lists will clear all the doubts of how to create a Linked List and how to implement any graph algorithm using Linked Lists .
I did lot of hardwork approximately 4 years research work and came up with the solution for the most difficult problem in the field of Graph Theory . With Array based implementation its not possible to add & remove vertices or edges inside Graph but with Linked lists its possible to add and remove vertices or edges and apply Graph algorithm . Here are some of the important Graph Theory applications in day to day life .
To minimize LinkedHashMap & HashMap resizing: Set an appropriate initial capacity if you know the expected number of entries. Adjust the load factor if needed
/* 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.HashMap; import java.util.LinkedHashMap; import java.util.Set; import java.util.Iterator; import java.util.Scanner; import java.util.InputMismatchException; class Edge { String edge; int weight; } class Graph { LinkedHashMap<String, LinkedList<Edge>> H = new LinkedHashMap<>(); HashMap<String, LinkedList<String>> inside = new HashMap<>(); HashMap<String, Integer> D = new HashMap<>(); HashMap<String, String> P = new HashMap<>(); } 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.Bellman ford 10.Delete graph 11.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) Mainbell(graphObject, scan); else System.out.println("Graph is empty"); break; case 10: if (graphObject.H.size() > 0) del(graphObject); else System.out.println("Graph is empty"); break; case 11: break; default: System.out.println("Invalid input received please try again"); break; } } while (input != 11); } 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 + ")=" + edge.weight + " "); 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 iss(String s, Graph obj) { Set<String> vertices = obj.H.keySet(); for (String vertex : vertices) { obj.D.put(vertex, Integer.MAX_VALUE); obj.P.put(vertex, "NIL"); } obj.D.put(s, 0); } static void relax(String u, String v, Graph obj, int weight) { int uValue = obj.D.get(u); int vValue = obj.D.get(v); int total = uValue + weight ; if ( (uValue != Integer.MAX_VALUE ) && (vValue > total)) { obj.D.put(v, total); obj.P.put(v, u); } } static int cycletest(String u, String v, Graph obj, int weight) { if ( (obj.D.get(u) != Integer.MAX_VALUE ) && ( obj.D.get(v) > obj.D.get(u) + weight)) { return 0; } return 1; } static int bell(String s, Graph obj) { int k = 1; iss(s, obj); Set<String> vertices = obj.H.keySet(); if (!obj.H.get(s).isEmpty()) { for (int i = 0; i < vertices.size() - 1; i++) { for (String u : vertices) { LinkedList<Edge> edges = obj.H.get(u); for (Edge edge : edges) { relax(u, edge.edge, obj, edge.weight); } } } for (String vertex : vertices) { if (k != 0) { LinkedList<Edge> edges = obj.H.get(vertex); for (Edge edge : edges) { k = cycletest(vertex, edge.edge, obj, edge.weight); if (k == 0) break; } } } } return k; } static void printpath(String s, String v, Graph obj) { if (s.equals(v)) System.out.print(s); else { if (obj.P.get(v).equals("NIL")) System.out.println("No path exists from " + s + " to " + v); else { printpath(s, obj.P.get(v), obj); System.out.print(" " + v); } } } static void mindis(Graph obj, String s) { Set<String> i = obj.D.keySet(); for (String j : i) { System.out.println("Minimum distance between (" + s + "," + j + ")=" + obj.D.get(j)); } } 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 = new LinkedList<>(); edgelistinsert(obj,currentVertex,vertex,edgeList,scan); obj.H.put(currentVertex, edgeList); } } static void Mainbell(Graph obj, Scanner sc) { String s, d; System.out.println("\n enter source vertex "); s = sc.next(); if(obj.H.keySet().contains(s)) { int k = bell(s, obj); if (k == 0) { System.out.println("-ve weight cycle"); } else { mindis(obj, s); System.out.println("\n enter destination vertex "); d = sc.next(); System.out.println("\nBellman fords shortest path between source and destination is \n"); printpath(s, d, obj); } } else { System.out.println("\n The entered source vertex doesnt exist \n"); } } 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<Edge> edgeList = new LinkedList<>(); LinkedList<String> vertex = new LinkedList<>(obj.H.keySet()); edgelistinsert(obj,currentVertex,vertex,edgeList,sc); obj.H.put(currentVertex , edgeList); vertexCount++; } } static void insertedge(Graph obj, Scanner sc) { String firstVertex, secondVertex; int duplicateFlag, weight=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)) { LinkedList<Edge> edgeList = obj.H.get(firstVertex); duplicateFlag = search(obj, firstVertex, secondVertex); if (duplicateFlag == 1) { System.out.println("edge already present"); } else { System.out.println(" enter the weight of (" + firstVertex + "," + secondVertex + ")"); try { weight = sc.nextInt(); Edge temp2 = new Edge(); temp2.edge = secondVertex; temp2.weight = weight; edgeList.add(temp2); insideinsert(obj,secondVertex,firstVertex); edgeCount++; } catch (InputMismatchException e) { System.out.println("Invalid input! Please enter a valid integer."); sc.nextLine(); } } } 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(); obj.H.remove(vertex); LinkedList<String> vertices = obj.inside.get(vertex); Iterator<String> str = vertices.iterator(); while (str.hasNext()) { LinkedList<Edge> edgeList = obj.H.get(str.next()); iteratoredgedelete(edgeList,vertex); str.remove(); } if(obj.inside.containsKey(vertex)) obj.inside.remove(vertex); if (obj.D.containsKey(vertex)) obj.D.remove(vertex); if (obj.P.containsKey(vertex)) obj.P.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); obj.inside.get(secondVertex).remove(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 void edgelistinsert(Graph obj,String currentVertex, LinkedList<String> vertex, LinkedList<Edge> edgeList , Scanner scan) { int flag = 0,weight=0; String input,secondVertex; 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)) { System.out.println("enter weight of edge(" + currentVertex + "," + secondVertex+ ")"); try { weight = scan.nextInt(); Edge temp2 = new Edge(); temp2.edge = secondVertex; temp2.weight = weight; edgeList.add(temp2); insideinsert(obj,secondVertex,currentVertex); edgeCount++; } catch (InputMismatchException e) { System.out.println("Invalid input! Please enter a valid integer."); scan.nextLine(); } } else { System.out.println("Invalid vertex"); } } else System.out.println("Duplicate vertex not allowed"); } } while (!(input.equals("N"))); } 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.inside.containsKey(secondVertex) ) { obj.inside.get(secondVertex).add(currentVertex); } else { LinkedList<String> inside = new LinkedList<>(); inside.add(currentVertex); obj.inside.put(secondVertex, inside); } } }
