Coverage details for edu.uci.ics.jung.random.permuters.BernoulliEdgePermuter

LineHitsSource
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      */
412    public BernoulliEdgePermuter(int numEdgesToPermute) {
422        mEdgeIndexLookupTable = new HashMap();
432        mNumEdgesToPermute = numEdgesToPermute;
442    }
45  
46     protected void initialize(Graph g) {
472        mPermuteEdgeSample = new long[mNumEdgesToPermute];
48  
492        int numVertices = g.numVertices();
502        Indexer id = Indexer.getIndexer(g);
51  
522        int edgeCtr = 0;
538        for (int i = 0; i < numVertices; i++) {
5424            for (int j = 0; j < numVertices; j++) {
5518                if (i != j) {
5612                    mEdgeIndexLookupTable.put(
57                         new MutableInteger(edgeCtr),
58                         new Pair(id.getVertex(i), id.getVertex(j)));
5912                    edgeCtr++;
60                 }
61             }
62         }
63  
642    }
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) {
722        permuteEdges(graph, 1.0);
732    }
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) {
822        if ((probEdgeFlip < 0) || (probEdgeFlip > 1)) {
830            throw new IllegalArgumentException("Probability must be between 0 and 1.");
84         }
852        int numVertices = graph.numVertices();
862        int numPossibleEdges = numVertices * numVertices - numVertices;
872        if ((mNumEdgesToPermute < 0)
88             || (mNumEdgesToPermute > numPossibleEdges)) {
890            throw new IllegalArgumentException("Number specified for number of edges to flip must be between 0 and n^2-n");
90         }
912        initialize(graph);
92  
932        RandomSampler randomSampler =
94             new RandomSampler(
95                 mNumEdgesToPermute,
96                 numPossibleEdges,
97                 0,
98                 null);
992        randomSampler.nextBlock(mNumEdgesToPermute, mPermuteEdgeSample, 0);
100         //int currentEdgeSample = 0;
1012        Vertex sourceVertex = null;
1022        Vertex destVertex = null;
1032        MutableInteger currentKey = new MutableInteger();
104  
1054        for (int i = 0; i < mNumEdgesToPermute; i++) {
1062            currentKey.setInteger((int) mPermuteEdgeSample[i]);
1072            Pair currentEdge = (Pair) mEdgeIndexLookupTable.get(currentKey);
1082            sourceVertex = (Vertex) currentEdge.getFirst();
1092            destVertex = (Vertex) currentEdge.getSecond();
110  
1112            if (sourceVertex == destVertex) {
1120                continue;
113             }
114  
1152            if (Math.random() <= probEdgeFlip) {
1162                if (!sourceVertex.isPredecessorOf(destVertex)) {
1171                    if (PredicateUtils.enforcesUndirected(graph))
1180                        graph.addEdge(new UndirectedSparseEdge(sourceVertex, destVertex));
119                     else // if either mixed or directed, create a directed edge
1201                        graph.addEdge(new DirectedSparseEdge(sourceVertex, destVertex));
121 // GraphUtils.addEdge(graph, sourceVertex, destVertex);
122                 } else {
1231                    Edge e = sourceVertex.findEdge(destVertex);
1241                    graph.removeEdge(e);
125                 }
126             }
127         }
128  
1292    }
130 }

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.