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 | ||
12 | import java.util.ArrayList; | |
13 | import java.util.Iterator; | |
14 | import java.util.List; | |
15 | import java.util.Random; | |
16 | ||
17 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
18 | import edu.uci.ics.jung.graph.Edge; | |
19 | import edu.uci.ics.jung.graph.Graph; | |
20 | import edu.uci.ics.jung.graph.Vertex; | |
21 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
22 | import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph; | |
23 | import edu.uci.ics.jung.utils.GraphUtils; | |
24 | ||
25 | /** | |
26 | * Graph generator that generates undirected sparse graphs with power-law distributions. | |
27 | * @author Scott White | |
28 | * @see "A Steady State Model for Graph Power Law by David Eppstein and Joseph Wang" | |
29 | */ | |
30 | public class EppsteinPowerLawGenerator implements GraphGenerator { | |
31 | private int mNumVertices; | |
32 | private int mNumEdges; | |
33 | private int mNumIterations; | |
34 | private double mMaxDegree; | |
35 | private Random mRandom; | |
36 | ||
37 | /** | |
38 | * Constructor which specifies the parameters of the generator | |
39 | * @param numVertices the number of vertices for the generated graph | |
40 | * @param numEdges the number of edges the generated graph will have, should be Theta(numVertices) | |
41 | * @param r the model parameter. The larger the value for this parameter the better the graph's degree | |
42 | * distribution will approximate a power-law. | |
43 | */ | |
44 | 30 | public EppsteinPowerLawGenerator(int numVertices, int numEdges,int r) { |
45 | 30 | mNumVertices = numVertices; |
46 | 30 | mNumEdges = numEdges; |
47 | 30 | mNumIterations = r; |
48 | 30 | mRandom = new Random(); |
49 | 30 | } |
50 | ||
51 | protected Graph initializeGraph() { | |
52 | 30 | Graph graph = null; |
53 | 30 | graph = new UndirectedSparseGraph(); |
54 | 30 | GraphUtils.addVertices(graph,mNumVertices); |
55 | ||
56 | 30 | Indexer id = Indexer.getIndexer(graph); |
57 | ||
58 | 15133 | while (graph.numEdges() < mNumEdges) { |
59 | 15103 | Vertex u = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices)); |
60 | 15103 | Vertex v = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices)); |
61 | 15103 | if (!v.isSuccessorOf(u)) { |
62 | 12400 | GraphUtils.addEdge(graph,u,v); |
63 | } | |
64 | } | |
65 | ||
66 | 30 | double maxDegree = 0; |
67 | 30 | for (Iterator vIt=graph.getVertices().iterator(); vIt.hasNext();) { |
68 | 2000 | Vertex v = (Vertex) vIt.next(); |
69 | 2000 | maxDegree = Math.max(v.degree(),maxDegree); |
70 | } | |
71 | 30 | mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2; |
72 | ||
73 | 30 | return graph; |
74 | } | |
75 | ||
76 | /** | |
77 | * Generates a graph whose degree distribution approximates a power-law. | |
78 | * @return the generated graph | |
79 | */ | |
80 | public ArchetypeGraph generateGraph() { | |
81 | 30 | Graph graph = initializeGraph(); |
82 | ||
83 | 30 | Indexer id = Indexer.getIndexer(graph); |
84 | 118075 | for (int rIdx = 0; rIdx < mNumIterations; rIdx++) { |
85 | ||
86 | 118045 | Vertex v = null; |
87 | 118045 | int degree = 0; |
88 | do { | |
89 | 130793 | v = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices)); |
90 | 130793 | degree = v.degree(); |
91 | ||
92 | 130793 | } while (degree == 0); |
93 | ||
94 | 118045 | List edges = new ArrayList(v.getIncidentEdges()); |
95 | 118045 | Edge randomExistingEdge = (Edge) edges.get((int) (mRandom.nextDouble()*degree)); |
96 | ||
97 | 118045 | Vertex x = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices)); |
98 | 118045 | Vertex y = null; |
99 | do { | |
100 | 233875 | y = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices)); |
101 | ||
102 | 233875 | } while (mRandom.nextDouble() > ((double) (y.degree()+1)/mMaxDegree)); |
103 | ||
104 | 118045 | if (!y.isSuccessorOf(x) && x != y) { |
105 | 108334 | graph.removeEdge(randomExistingEdge); |
106 | 108334 | GraphUtils.addEdge(graph,x,y); |
107 | } | |
108 | } | |
109 | ||
110 | 30 | return graph; |
111 | } | |
112 | ||
113 | public void setSeed(long seed) { | |
114 | 11 | mRandom.setSeed(seed); |
115 | 11 | } |
116 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |