This is a java program to generate a random graph by selecting 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 Construct a Random Graph by the Method of Random Edge Selection. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
import java.util.HashMap; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Random; public class Random_Edges_Graph2 { private Map<Integer, List<Integer>> adjacencyList; public Random_Edges_Graph2(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("Random Graph Generation"); Random random = new Random(); int e = Math.abs(random.nextInt(21 - 1) + 1); try { int minV = (int) Math.ceil((1 + Math.sqrt(1 + 8 * e)) / 2); int maxV = e + 1; int v = Math.abs(random.nextInt(maxV - minV) + minV); System.out.println("Random graph has "+v+" vertices"); System.out.println("Random graph has "+e+" edges"); Random_Edges_Graph2 reg = new Random_Edges_Graph2(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"); } } }
Output:
$ javac Random_Edges_Graph2.java $ java Random_Edges_Graph2 Random Graph Generation Random graph has 4 vertices Random graph has 5 edges The Adjacency List Representation of the random graph is: 1 -> 4 2 -> 3 -> 3 -> 4 3 -> 3 -> 3 -> 2 -> 2 4 -> 1 -> 2
Related posts:
Converting String to Stream of chars
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Java Program to Implement JobStateReasons API
Java Program to Create a Random Graph Using Random Edge Generation
Returning Custom Status Codes from Spring Controllers
Java Program to Implement Binomial Heap
A Quick Guide to Using Keycloak with Spring Boot
Concatenating Strings In Java
Add Multiple Items to an Java ArrayList
Các chương trình minh họa sử dụng Cấu trúc điều khiển trong Java
Setting Up Swagger 2 with a Spring REST API
Java Program to Implement LinkedHashMap API
OAuth2 for a Spring REST API – Handle the Refresh Token in Angular
Java Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree
Java Program to Check the Connectivity of Graph Using BFS
Java Program to Implement Counting Sort
Introduction to the Java ArrayDeque
Spring Boot - Logging
Java Program for Topological Sorting in Graphs
Lớp HashMap trong Java
New Features in Java 8
Convert a Map to an Array, List or Set in Java
Java Program to Perform Arithmetic Operations on Numbers of Size
Comparing Objects in Java
Java Program to Implement AA Tree
Java Program to Implement Adjacency Matrix
Lấy ngày giờ hiện tại trong Java
Quản lý bộ nhớ trong Java với Heap Space vs Stack
Vòng lặp for, while, do-while trong Java
Java Program to Implement Double Order Traversal of a Binary Tree
An Introduction to ThreadLocal in Java
Java Web Services – JAX-WS – SOAP