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