1/*2 * Licensed to the Apache Software Foundation (ASF) under one3 * or more contributor license agreements. See the NOTICE file4 * distributed with this work for additional information5 * regarding copyright ownership. The ASF licenses this file6 * to you under the Apache License, Version 2.0 (the7 * "License"); you may not use this file except in compliance8 * with the License. You may obtain a copy of the License at9 *10 * http://www.apache.org/licenses/LICENSE-2.011 *12 * Unless required by applicable law or agreed to in writing, software13 * distributed under the License is distributed on an "AS IS" BASIS,14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.15 * See the License for the specific language governing permissions and16 * limitations under the License.17 */1819package org.apache.giraph.io.formats;
2021import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
22import org.apache.giraph.partition.PartitionUtils;
23import org.apache.giraph.partition.SimpleLongRangePartitionerFactory;
24import org.apache.giraph.worker.WorkerInfo;
2526import java.util.Collections;
27import java.util.List;
28import java.util.Random;
2930/**31 * Helper class to generate pseudo-random local edges.32 */33publicclassPseudoRandomLocalEdgesHelper {
34/** Minimum ratio of partition-local edges. */35privatefloat minLocalEdgesRatio;
36/** Whether we're using range-partitioning or hash-partitioning */37privateboolean usingRangePartitioner;
38/** Total number of vertices. */39privatelong numVertices;
40/** Total number of partitions. */41privateint numPartitions;
42/** Average partition size. */43privatelong partitionSize;
4445/**46 * Constructor.47 *48 * @param numVertices Total number of vertices.49 * @param minLocalEdgesRatio Minimum ratio of local edges.50 * @param conf Configuration.51 */52publicPseudoRandomLocalEdgesHelper(long numVertices,
53float minLocalEdgesRatio,
54ImmutableClassesGiraphConfiguration conf)
55 {
56this.minLocalEdgesRatio = minLocalEdgesRatio;
57this.numVertices = numVertices;
58 usingRangePartitioner =
59 SimpleLongRangePartitionerFactory.class.isAssignableFrom(
60 conf.getGraphPartitionerClass());
61int numWorkers = conf.getMaxWorkers();
62 List<WorkerInfo> workerInfos = Collections.nCopies(numWorkers,
63newWorkerInfo());
64 numPartitions =
65 PartitionUtils.computePartitionCount(workerInfos.size(), conf);
66 partitionSize = numVertices / numPartitions;
67 }
6869/**70 * Generate a destination vertex id for the given source vertex,71 * using the desired configuration for edge locality and the provided72 * pseudo-random generator.73 *74 * @param sourceVertexId Source vertex id.75 * @param rand Pseudo-random generator.76 * @return Destination vertex id.77 */78publiclong generateDestVertex(long sourceVertexId, Random rand) {
79long destVertexId;
80if (rand.nextFloat() < minLocalEdgesRatio) {
81if (usingRangePartitioner) {
82int partitionId = Math.min(numPartitions - 1,
83 (int) (sourceVertexId / partitionSize));
84 destVertexId = partitionId * partitionSize +
85 (Math.abs(rand.nextLong()) % partitionSize);
86 } else {
87int partitionId = (int) sourceVertexId % numPartitions;
88 destVertexId = partitionId +
89 numPartitions * (Math.abs(rand.nextLong()) % partitionSize);
90 }
91 } else {
92 destVertexId = Math.abs(rand.nextLong()) % numVertices;
93 }
94return destVertexId;
95 }
96 }