Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | package edu.uci.ics.jung.random.generators; | |
11 | import java.util.Random; | |
12 | ||
13 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
14 | import edu.uci.ics.jung.graph.UndirectedGraph; | |
15 | import edu.uci.ics.jung.graph.Vertex; | |
16 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
17 | import edu.uci.ics.jung.graph.impl.SparseVertex; | |
18 | import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge; | |
19 | import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph; | |
20 | /** | |
21 | * Simple graph generator where |V| vertices are generated and |E| random edges | |
22 | * chosen pairwise uniformly | |
23 | * | |
24 | * @author William Giordano, Scott White | |
25 | */ | |
26 | public class SimpleRandomGenerator implements GraphGenerator { | |
27 | private int mNumVertices; | |
28 | private int mNumEdges; | |
29 | ||
30 | protected Vertex newVertex() { | |
31 | 0 | return new SparseVertex(); |
32 | } | |
33 | ||
34 | /** | |
35 | * Constructs the generator | |
36 | * | |
37 | * @param numVertices | |
38 | * number of vertices the graph should have | |
39 | * @param numEdges | |
40 | * number of edges the graph should have | |
41 | */ | |
42 | 0 | public SimpleRandomGenerator(int numVertices, int numEdges) { |
43 | 0 | if (numVertices <= 0) { |
44 | 0 | throw new IllegalArgumentException( |
45 | "A positive # of vertices must be specified."); | |
46 | } | |
47 | 0 | mNumVertices = numVertices; |
48 | 0 | long calcVertices = numVertices; |
49 | 0 | if (numEdges < 0 || numEdges > (calcVertices * (calcVertices - 1) / 2)) { |
50 | 0 | throw new IllegalArgumentException( |
51 | "# of edges [" + numEdges +"] must be between 0 and |V|(|V|-1)/2, v=" + numVertices); | |
52 | } | |
53 | 0 | mNumEdges = numEdges; |
54 | 0 | } |
55 | ||
56 | public void setSeed( long seed ) { | |
57 | 0 | this.seedSet = true; |
58 | 0 | this.seed = seed; |
59 | 0 | } |
60 | ||
61 | 0 | boolean seedSet = false; |
62 | 0 | long seed = 0; |
63 | ||
64 | /** | |
65 | * Generated the graph by creating |V| vertics and then picking |E| random | |
66 | * edges | |
67 | * | |
68 | * @return generated graph | |
69 | */ | |
70 | public ArchetypeGraph generateGraph() { | |
71 | Random rand; | |
72 | 0 | if ( seedSet ) { |
73 | 0 | rand = new Random(seed); |
74 | } else { | |
75 | 0 | rand = new Random(); |
76 | } | |
77 | 0 | UndirectedGraph g = new UndirectedSparseGraph(); |
78 | 0 | for( int i = 0; i < mNumVertices; i ++ ) { |
79 | 0 | g.addVertex( newVertex() ); |
80 | } | |
81 | // GraphUtils.addVertices(g, mNumVertices); | |
82 | 0 | Indexer id = Indexer.getIndexer(g); |
83 | 0 | int ctr = 0; |
84 | 0 | while (ctr < mNumEdges) { |
85 | 0 | Vertex v1 = (Vertex) id.getVertex(rand.nextInt(mNumVertices)); |
86 | 0 | Vertex v2 = (Vertex) id.getVertex(rand.nextInt(mNumVertices)); |
87 | 0 | if ((v1 != v2) && !v1.isNeighborOf(v2)) { |
88 | 0 | g.addEdge(new UndirectedSparseEdge(v1, v2)); |
89 | 0 | ctr++; |
90 | } | |
91 | } | |
92 | 0 | return g; |
93 | } | |
94 | /** | |
95 | * @return Returns the mNumEdges. | |
96 | */ | |
97 | public long getNumEdges() { | |
98 | 0 | return mNumEdges; |
99 | } | |
100 | /** | |
101 | * @return Returns the mNumVertices. | |
102 | */ | |
103 | public long getNumVertices() { | |
104 | 0 | return mNumVertices; |
105 | } | |
106 | } | |
107 |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |