This is a java program to generate a random graph by generating random number of edges. One important thing to note here is, that we need to decide minimum and maximum number of nodes such that all edges get accommodated. Minimum number of vertices is positive solution to n(n-1) = 2e, where e is number of edges and maximum number of vertices is e+1.
Here is the source code of the Java Program to Create a Random Graph Using Random Edge Generation. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to generate a random graph using random edge generation import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Random; import java.util.Scanner; public class Random_Edges_Graph { private Map<Integer, List<Integer>> adjacencyList; public Random_Edges_Graph(int v) { adjacencyList = new HashMap<Integer, List<Integer>>(); for (int i = 1; i <= v; i++) adjacencyList.put(i, new LinkedList<Integer>()); } public void setEdge(int to, int from) { if (to > adjacencyList.size() || from > adjacencyList.size()) System.out.println("The vertices does not exists"); List<Integer> sls = adjacencyList.get(to); sls.add(from); List<Integer> dls = adjacencyList.get(from); dls.add(to); } public List<Integer> getEdge(int to) { if (to > adjacencyList.size()) { System.out.println("The vertices does not exists"); return null; } return adjacencyList.get(to); } public static void main(String args[]) { System.out.println("Enter the number of edges: "); Scanner sc = new Scanner(System.in); int e = sc.nextInt(); try { int minV = (int) Math.ceil((1 + Math.sqrt(1 + 8 * e)) / 2); int maxV = e + 1; Random random = new Random(); int v = Math.abs(random.nextInt(maxV - minV) + minV); System.out.println("Random graph has "+v+" vertices"); Random_Edges_Graph reg = new Random_Edges_Graph(v); int count = 1, to, from; while (count <= e) { to = Math.abs(random.nextInt(v + 1 - 1) + 1); from = Math.abs(random.nextInt(v + 1 - 1) + 1); reg.setEdge(to, from); count++; } System.out .println("THe Adjacency List Representation of the random graph is: "); for (int i = 1; i <= v; i++) { System.out.print(i + " -> "); List<Integer> edgeList = reg.getEdge(i); if (edgeList.size() == 0) System.out.print("null"); else { for (int j = 1;; j++) { if (j != edgeList.size()) System.out.print(edgeList.get(j - 1) + " -> "); else { System.out.print(edgeList.get(j - 1)); break; } } } System.out.println(); } } catch (Exception E) { System.out.println("Something went wrong"); } sc.close(); } }
Output:
$ javac Random_Edges_Graph.java $ java Random_Edges_Graph Enter the number of edges: 5 Random graph has 4 vertices THe Adjacency List Representation of the random graph is: 1 -> 4 -> 4 2 -> 3 -> 3 3 -> 2 -> 4 -> 2 4 -> 1 -> 1 -> 3
Related posts:
Java Program to Implement Segment Tree
Java Program to Implement Min Heap
Java Program to Use Dynamic Programming to Solve Approximate String Matching
Java Program to Check if a Point d lies Inside or Outside a Circle Defined by Points a, b, c in a Pl...
Java Program to Implement Sieve Of Sundaram
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Converting String to Stream of chars
A Guide to Java 9 Modularity
ClassNotFoundException vs NoClassDefFoundError
Spring MVC Tutorial
JUnit 5 @Test Annotation
Spring RestTemplate Error Handling
Java Program to do a Breadth First Search/Traversal on a graph non-recursively
Java Program to Compute Discrete Fourier Transform Using the Fast Fourier Transform Approach
Java Program to Implement Network Flow Problem
Java – String to Reader
Implementing a Runnable vs Extending a Thread
Java – InputStream to Reader
Jackson Exceptions – Problems and Solutions
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Removing all Nulls from a List in Java
Auditing with JPA, Hibernate, and Spring Data JPA
Java Program to Find the Median of two Sorted Arrays using Binary Search Approach
Tránh lỗi NullPointerException trong Java như thế nào?
Receive email by java client
Java Program to Implement the Schonhage-Strassen Algorithm for Multiplication of Two Numbers
Java Program to Find Strongly Connected Components in Graphs
Partition a List in Java
Guide to Dynamic Tests in Junit 5
Java Program to Emulate N Dice Roller
Java Program to implement Circular Buffer
Java Program to Implement CountMinSketch