This project has retired. For details please refer to its Attic page.
PseudoRandomLocalEdgesHelper xref
View Javadoc

1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   *     http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing, software
13   * 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 and
16   * limitations under the License.
17   */
18  
19  package org.apache.giraph.io.formats;
20  
21  import org.apache.giraph.conf.ImmutableClassesGiraphConfiguration;
22  import org.apache.giraph.partition.PartitionUtils;
23  import org.apache.giraph.partition.SimpleLongRangePartitionerFactory;
24  import org.apache.giraph.worker.WorkerInfo;
25  
26  import java.util.Collections;
27  import java.util.List;
28  import java.util.Random;
29  
30  /**
31   * Helper class to generate pseudo-random local edges.
32   */
33  public class PseudoRandomLocalEdgesHelper {
34    /** Minimum ratio of partition-local edges. */
35    private float minLocalEdgesRatio;
36    /** Whether we're using range-partitioning or hash-partitioning */
37    private boolean usingRangePartitioner;
38    /** Total number of vertices. */
39    private long numVertices;
40    /** Total number of partitions. */
41    private int numPartitions;
42    /** Average partition size. */
43    private long partitionSize;
44  
45    /**
46     * Constructor.
47     *
48     * @param numVertices Total number of vertices.
49     * @param minLocalEdgesRatio Minimum ratio of local edges.
50     * @param conf Configuration.
51     */
52    public PseudoRandomLocalEdgesHelper(long numVertices,
53                                        float minLocalEdgesRatio,
54                                        ImmutableClassesGiraphConfiguration conf)
55    {
56      this.minLocalEdgesRatio = minLocalEdgesRatio;
57      this.numVertices = numVertices;
58      usingRangePartitioner =
59          SimpleLongRangePartitionerFactory.class.isAssignableFrom(
60              conf.getGraphPartitionerClass());
61      int numWorkers = conf.getMaxWorkers();
62      List<WorkerInfo> workerInfos = Collections.nCopies(numWorkers,
63          new WorkerInfo());
64      numPartitions =
65          PartitionUtils.computePartitionCount(workerInfos.size(), conf);
66      partitionSize = numVertices / numPartitions;
67    }
68  
69    /**
70     * Generate a destination vertex id for the given source vertex,
71     * using the desired configuration for edge locality and the provided
72     * pseudo-random generator.
73     *
74     * @param sourceVertexId Source vertex id.
75     * @param rand Pseudo-random generator.
76     * @return Destination vertex id.
77     */
78    public long generateDestVertex(long sourceVertexId, Random rand) {
79      long destVertexId;
80      if (rand.nextFloat() < minLocalEdgesRatio) {
81        if (usingRangePartitioner) {
82          int partitionId = Math.min(numPartitions - 1,
83              (int) (sourceVertexId / partitionSize));
84          destVertexId = partitionId * partitionSize +
85              (Math.abs(rand.nextLong()) % partitionSize);
86        } else {
87          int 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      }
94      return destVertexId;
95    }
96  }