| 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. |