This is a java program to generate a random graph using number of edges provided by user. 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 Generate a Random UnDirected Graph for a Given Number of Edges. 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 randomly generate a undirected graph where numbers of edges is given by user 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_Undirected_Graph { private Map<Integer, List<Integer>> adjacencyList; public Random_Undirected_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_Undirected_Graph rug = new Random_Undirected_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); rug.setEdge(to, from); count++; } System.out .println("The Adjacency List Representation of the graph is: "); for (int i = 1; i <= v; i++) { System.out.print(i + " -> "); List<Integer> edgeList = rug.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_Undirected_Graph.java $ java Random_Undirected_Graph Enter the number of edges: 15 Random graph has 6 vertices The Adjacency List Representation of the graph is: 1 -> 4 -> 2 -> 3 -> 5 2 -> 2 -> 2 -> 1 -> 5 3 -> 5 -> 6 -> 4 -> 6 -> 1 -> 5 -> 4 4 -> 6 -> 4 -> 4 -> 1 -> 3 -> 3 5 -> 3 -> 6 -> 3 -> 1 -> 2 6 -> 4 -> 3 -> 5 -> 3
Related posts:
A Custom Data Binder in Spring MVC
Initialize a HashMap in Java
Java Program to Implement Find all Forward Edges in a Graph
Hướng dẫn Java Design Pattern – Chain of Responsibility
Spring Cloud AWS – S3
Uploading MultipartFile with Spring RestTemplate
Spring Boot - Internationalization
Java Program to Perform Insertion in a 2 Dimension K-D Tree
Chương trình Java đầu tiên
Java Program to Check Cycle in a Graph using Topological Sort
Explain about URL and HTTPS protocol
Java Program to Implement a Binary Search Tree using Linked Lists
Một số từ khóa trong Java
Queue và PriorityQueue trong Java
Immutable Map Implementations in Java
Java Program to Implement Quick sort
Changing Annotation Parameters At Runtime
Guide to Apache Commons CircularFifoQueue
Guide to the ConcurrentSkipListMap
Java 9 Stream API Improvements
Spring Boot - Enabling Swagger2
Java Program to Perform Search in a BST
Java Program to Implement Ternary Search Tree
Find the Registered Spring Security Filters
Sort a HashMap in Java
Examine the internal DNS cache
Java Program to Compute Discrete Fourier Transform Using Naive Approach
Getting Started with Custom Deserialization in Jackson
Java Program to Implement Fermat Factorization Algorithm
Java Program to Perform Naive String Matching
Java Program to Use rand and srand Functions
Mix plain text and HTML content in a mail