Following is the Java code for generating a Random Graph G(n, p) where ‘n’ is the number of nodes/ vertices in the graph and ‘p’ is the probability that any edge will form or not.
The code makes use of JUNG API for graph visualization and creation. More About JUNG…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.awt.Dimension; import javax.swing.JFrame; import edu.uci.ics.jung.algorithms.layout.KKLayout; import edu.uci.ics.jung.algorithms.layout.Layout; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.SparseMultigraph; import edu.uci.ics.jung.visualization.BasicVisualizationServer; public class RandomGraphGenerator { private int n; private double p; public RandomGraphGenerator(int n, double p) { this.n = n; this.p = p; } public Graph<Integer, String> generateRandomGraph() { Graph<Integer, String> g = new SparseMultigraph<Integer, String>(); for (int i = 0; i < n; i++) { g.addVertex(i); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (Math.random() < p) { g.addEdge(i + "-to-" + j, i, j); } } } return g; } public static void main(String[] args) { RandomGraphGenerator rgg = new RandomGraphGenerator(10, 0.5); // int maxEdgeCount = (n*(n-1))>>1; Graph<Integer, String> g = rgg.generateRandomGraph(); // Add some edges. From above we defined these to be of type String // Note that the default is for undirected edges. Layout<Integer, String> layout = new KKLayout<Integer, String>(g); layout.setSize(new Dimension(1200, 600)); // sets the initial size of // the space // The BasicVisualizationServer<V,E> is parameterized by the edge types BasicVisualizationServer<Integer, String> vv = new BasicVisualizationServer<Integer, String>( layout); vv.setPreferredSize(new Dimension(1200, 600)); // Sets the viewing area // size JFrame frame = new JFrame("Simple Graph View"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.getContentPane().add(vv); frame.pack(); frame.setVisible(true); } } |
A sample run for n = 10 and p = 0.5 gives the following result. (Since the graph is random it may generate/ display differently on your machine.)
Random Graph Generated from running above program for n = 10 and p = 0.5
Though the code uses JUNG API for Graph as Object representation, the above code can be extended to have any other graph representation you may wish to choose. Please write a comment if you need help with some other graph representation.
Another code with custom Vertex representation is as listed below:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 |
import java.awt.Color; import java.awt.Dimension; import java.awt.Paint; import java.util.ArrayList; import java.util.List; import javax.swing.JFrame; import org.apache.commons.collections15.Transformer; import edu.uci.ics.jung.algorithms.layout.KKLayout; import edu.uci.ics.jung.algorithms.layout.Layout; import edu.uci.ics.jung.graph.Graph; import edu.uci.ics.jung.graph.SparseMultigraph; import edu.uci.ics.jung.visualization.BasicVisualizationServer; import edu.uci.ics.jung.visualization.decorators.ToStringLabeller; import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position; /** * * @author Team Coddicted * */ public class RandomGraphGeneratorCustomVertex { private int n; private double p; public RandomGraphGeneratorCustomVertex(int n, double p) { this.n = n; this.p = p; } public Graph<Vertex, String> generateRandomGraph() { Graph<Vertex, String> g = new SparseMultigraph<Vertex, String>(); List<Vertex> vertexList = new ArrayList<Vertex>(); for (int i = 0; i < n; i++) { vertexList.add(new Vertex(i)); } for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (Math.random() < p) { g.addEdge(i + "-to-" + j, vertexList.get(i), vertexList.get(j)); } } } return g; } public void displayGraph(Graph<Vertex, String> g) { // Add some edges. From above we defined these to be of type String // Note that the default is for undirected edges. Layout<Vertex, String> layout = new KKLayout<Vertex, String>(g); layout.setSize(new Dimension(1200, 600)); // sets the initial size of // the space // The BasicVisualizationServer<V,E> is parameterized by the edge types BasicVisualizationServer<Vertex, String> vv = new BasicVisualizationServer<Vertex, String>( layout); vv.setPreferredSize(new Dimension(1200, 600)); // Sets the viewing area // size // Create a transformer (optional) // For creating a different colored vertex. Transformer<Vertex, Paint> vertexPaint = new Transformer<Vertex, Paint>() { @Override public Paint transform(Vertex arg0) { return Color.CYAN; } }; // Set the above vertex transformer object to the current graph // renderer. vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint); // Set the labeller for vertex labels // Similar labeller can be applied for edge labeling /* * * If you are specifying any new Vertex/ Edge classes * then do * remember to override and implement the toString method * for this * kind of rendering to work. */ vv.getRenderContext().setVertexLabelTransformer( new ToStringLabeller<Vertex>()); vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR); JFrame frame = new JFrame("Simple Graph View"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.getContentPane().add(vv); frame.pack(); frame.setVisible(true); } public void displayGraph(Graph<Vertex, String> g, final int id) { // Add some edges. From above we defined these to be of type String // Note that the default is for undirected edges. Layout<Vertex, String> layout = new KKLayout<Vertex, String>(g); layout.setSize(new Dimension(1200, 600)); // sets the initial size of // the space // The BasicVisualizationServer<V,E> is parameterized by the edge types BasicVisualizationServer<Vertex, String> vv = new BasicVisualizationServer<Vertex, String>( layout); vv.setPreferredSize(new Dimension(1200, 600)); // Sets the viewing area // size // Create a transformer (optional) // For creating a different colored vertex. Transformer<Vertex, Paint> vertexPaint = new Transformer<Vertex, Paint>() { @Override public Paint transform(Vertex arg0) { if (arg0.getId() == id) return Color.RED; else return Color.CYAN; } }; // Set the above vertex transformer object to the current graph // renderer. vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint); // Set the labeller for vertex labels // Similar labeller can be applied for edge labeling /* * * If you are specifying any new Vertex/ Edge classes * then do * remember to override and implement the toString method * for this * kind of rendering to work. */ vv.getRenderContext().setVertexLabelTransformer( new ToStringLabeller<Vertex>()); vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR); JFrame frame = new JFrame("Simple Graph View"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); frame.getContentPane().add(vv); frame.pack(); frame.setVisible(true); } public static void main(String[] args) { RandomGraphGeneratorCustomVertex rgg = new RandomGraphGeneratorCustomVertex( 10, 0.4); // int maxEdgeCount = (n*(n-1))>>1; Graph<Vertex, String> g = rgg.generateRandomGraph(); rgg.displayGraph(g); } } |
The Vertex class to be used is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
import java.util.List; /** * @author Team Coddicted * */ public class Vertex implements Comparable<Vertex> { /** * Unique ID for every node. */ private int id; /** * Label to be displayed on the vertex (Optional). */ private String label; /** * To hold a previous node in the shortest path. (This would hold a single * node only in one of the possible shortest paths.) */ private Vertex previous; /** * A distance measure for this vertex from source vertex. */ public double sourceDistance = Double.POSITIVE_INFINITY; /** * A List of all previous nodes in all the possible shortest paths. */ private List<Vertex> prev; public Vertex(int id) { this(id, id + ""); } public Vertex(int id, String label) { this.id = id; this.label = label; } @Override public String toString() { return label; } /** * @return the id */ public int getId() { return id; } /** * @return the prev */ public List<Vertex> getPrev() { return prev; } /** * @param prev * the prev to set */ public void setPrev(List<Vertex> prev) { this.prev = prev; } /** * @param id * the id to set */ public void setId(int id) { this.id = id; } /** * @return the label */ public String getLabel() { return label; } /** * @param label * the label to set */ public void setLabel(String label) { this.label = label; } /** * @return the previous */ public Vertex getPrevious() { return previous; } /** * @param previous * the previous to set */ public void setPrevious(Vertex previous) { this.previous = previous; } /** * @return the minDistance */ public double getMinDistance() { return sourceDistance; } /** * @param minDistance * the minDistance to set */ public void setMinDistance(double minDistance) { this.sourceDistance = minDistance; } @Override public int compareTo(Vertex other) { return Double.compare(sourceDistance, other.sourceDistance); } } |
A sample output graph generated from above code is:
there’s an error stop me from running it
”
java.lang.NoClassDefFoundError: org/apache/commons/collections/Predicate
at RandomGraphGenerator.generateRandomGraph(graphjava.java:22)
at RandomGraphGenerator.main(graphjava.java:43)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:272)
?