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.permuters; | |
11 | ||
12 | import java.util.HashMap; | |
13 | import java.util.Map; | |
14 | ||
15 | import cern.jet.random.sampling.RandomSampler; | |
16 | import edu.uci.ics.jung.graph.Edge; | |
17 | import edu.uci.ics.jung.graph.Graph; | |
18 | import edu.uci.ics.jung.graph.Vertex; | |
19 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
20 | import edu.uci.ics.jung.graph.impl.DirectedSparseEdge; | |
21 | import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge; | |
22 | import edu.uci.ics.jung.utils.MutableInteger; | |
23 | import edu.uci.ics.jung.utils.Pair; | |
24 | import edu.uci.ics.jung.utils.PredicateUtils; | |
25 | ||
26 | /** | |
27 | * An edge permuter that permutes edges by sampling uniformly at random a given number of possible edges and for each | |
28 | * that exists that edge is removed and for each that doesn't exist that edge is added. The user can specify | |
29 | * with what probability this should removal/addition process should happen. | |
30 | * @author Scott White | |
31 | */ | |
32 | public class BernoulliEdgePermuter implements EdgePermuter { | |
33 | Map mEdgeIndexLookupTable; | |
34 | private long[] mPermuteEdgeSample; | |
35 | private int mNumEdgesToPermute; | |
36 | ||
37 | /** | |
38 | * Constructs the edge permuter. | |
39 | * @param numEdgesToPermute the number of edges to permute | |
40 | */ | |
41 | 2 | public BernoulliEdgePermuter(int numEdgesToPermute) { |
42 | 2 | mEdgeIndexLookupTable = new HashMap(); |
43 | 2 | mNumEdgesToPermute = numEdgesToPermute; |
44 | 2 | } |
45 | ||
46 | protected void initialize(Graph g) { | |
47 | 2 | mPermuteEdgeSample = new long[mNumEdgesToPermute]; |
48 | ||
49 | 2 | int numVertices = g.numVertices(); |
50 | 2 | Indexer id = Indexer.getIndexer(g); |
51 | ||
52 | 2 | int edgeCtr = 0; |
53 | 8 | for (int i = 0; i < numVertices; i++) { |
54 | 24 | for (int j = 0; j < numVertices; j++) { |
55 | 18 | if (i != j) { |
56 | 12 | mEdgeIndexLookupTable.put( |
57 | new MutableInteger(edgeCtr), | |
58 | new Pair(id.getVertex(i), id.getVertex(j))); | |
59 | 12 | edgeCtr++; |
60 | } | |
61 | } | |
62 | } | |
63 | ||
64 | 2 | } |
65 | ||
66 | /** | |
67 | * Permutes the edges with default probability 1, meaning that if an edge is sample it will either be removed | |
68 | * or added depending on whether it exists already | |
69 | * @param graph the graph whose edges are to be permuted | |
70 | */ | |
71 | public void permuteEdges(Graph graph) { | |
72 | 2 | permuteEdges(graph, 1.0); |
73 | 2 | } |
74 | ||
75 | /** | |
76 | * Permutes the edges using a user-specified probability that an edge is removed or added. | |
77 | * @param graph the graph whose edges are to be permuted | |
78 | * @param probEdgeFlip the probability that if a possible edge is sample it is removed, if it already exists | |
79 | * or added if it doesn't | |
80 | */ | |
81 | public void permuteEdges(Graph graph, double probEdgeFlip) { | |
82 | 2 | if ((probEdgeFlip < 0) || (probEdgeFlip > 1)) { |
83 | 0 | throw new IllegalArgumentException("Probability must be between 0 and 1."); |
84 | } | |
85 | 2 | int numVertices = graph.numVertices(); |
86 | 2 | int numPossibleEdges = numVertices * numVertices - numVertices; |
87 | 2 | if ((mNumEdgesToPermute < 0) |
88 | || (mNumEdgesToPermute > numPossibleEdges)) { | |
89 | 0 | throw new IllegalArgumentException("Number specified for number of edges to flip must be between 0 and n^2-n"); |
90 | } | |
91 | 2 | initialize(graph); |
92 | ||
93 | 2 | RandomSampler randomSampler = |
94 | new RandomSampler( | |
95 | mNumEdgesToPermute, | |
96 | numPossibleEdges, | |
97 | 0, | |
98 | null); | |
99 | 2 | randomSampler.nextBlock(mNumEdgesToPermute, mPermuteEdgeSample, 0); |
100 | //int currentEdgeSample = 0; | |
101 | 2 | Vertex sourceVertex = null; |
102 | 2 | Vertex destVertex = null; |
103 | 2 | MutableInteger currentKey = new MutableInteger(); |
104 | ||
105 | 4 | for (int i = 0; i < mNumEdgesToPermute; i++) { |
106 | 2 | currentKey.setInteger((int) mPermuteEdgeSample[i]); |
107 | 2 | Pair currentEdge = (Pair) mEdgeIndexLookupTable.get(currentKey); |
108 | 2 | sourceVertex = (Vertex) currentEdge.getFirst(); |
109 | 2 | destVertex = (Vertex) currentEdge.getSecond(); |
110 | ||
111 | 2 | if (sourceVertex == destVertex) { |
112 | 0 | continue; |
113 | } | |
114 | ||
115 | 2 | if (Math.random() <= probEdgeFlip) { |
116 | 2 | if (!sourceVertex.isPredecessorOf(destVertex)) { |
117 | 1 | if (PredicateUtils.enforcesUndirected(graph)) |
118 | 0 | graph.addEdge(new UndirectedSparseEdge(sourceVertex, destVertex)); |
119 | else // if either mixed or directed, create a directed edge | |
120 | 1 | graph.addEdge(new DirectedSparseEdge(sourceVertex, destVertex)); |
121 | // GraphUtils.addEdge(graph, sourceVertex, destVertex); | |
122 | } else { | |
123 | 1 | Edge e = sourceVertex.findEdge(destVertex); |
124 | 1 | graph.removeEdge(e); |
125 | } | |
126 | } | |
127 | } | |
128 | ||
129 | 2 | } |
130 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |