This project has retired. For details please refer to its Attic page.
SyntheticGraphInit 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  package org.apache.giraph.block_app.test_setup.graphs;
19  
20  import java.util.Random;
21  
22  import org.apache.giraph.block_app.test_setup.NumericTestGraph;
23  import org.apache.giraph.block_app.test_setup.TestGraphModifier;
24  import org.apache.giraph.conf.FloatConfOption;
25  import org.apache.giraph.conf.GiraphConfiguration;
26  import org.apache.giraph.conf.IntConfOption;
27  import org.apache.giraph.function.Supplier;
28  import org.apache.hadoop.io.Writable;
29  import org.apache.hadoop.io.WritableComparable;
30  
31  /**
32   * Creates synthetic graphs, that can have community structure.
33   *
34   * @param <I> Vertex id type
35   * @param <V> Vertex value type
36   * @param <E> Edge value type
37   */
38  public class SyntheticGraphInit<I extends WritableComparable,
39      V extends Writable, E extends Writable>
40      implements TestGraphModifier<I, V, E> {
41    public static final IntConfOption NUM_COMMUNITIES = new IntConfOption(
42        "test.SyntheticGraphCreator.NUM_COMMUNITIES", -1, "");
43    public static final IntConfOption NUM_VERTICES = new IntConfOption(
44        "test.SyntheticGraphCreator.NUM_VERTICES", -1, "");
45    public static final IntConfOption NUM_EDGES_PER_VERTEX = new IntConfOption(
46        "test.SyntheticGraphCreator.NUM_EDGES_PER_VERTEX", -1, "");
47    public static final FloatConfOption ACTUAL_LOCALITY_RATIO =
48        new FloatConfOption(
49              "test.SyntheticGraphCreator.ACTUAL_LOCALITY_RATIO", -1, "");
50  
51    protected final Supplier<E> edgeSupplier;
52  
53    public SyntheticGraphInit(Supplier<E> edgeSupplier) {
54      this.edgeSupplier = edgeSupplier;
55    }
56  
57    public SyntheticGraphInit() {
58      this.edgeSupplier = null;
59    }
60  
61    @Override
62    public void modifyGraph(NumericTestGraph<I, V, E> graph) {
63      GiraphConfiguration conf = graph.getConf();
64      int numPartitions = NUM_COMMUNITIES.get(conf);
65      int numVertices = NUM_VERTICES.get(conf);
66      int numEdgesPerVertex = NUM_EDGES_PER_VERTEX.get(conf);
67      int communitySize = numVertices / numPartitions;
68      float actualLocalityRatio = ACTUAL_LOCALITY_RATIO.get(conf);
69      Random random = new Random(42);
70      for (int i = 0; i < numVertices; ++i) {
71        for (int e = 0; e < numEdgesPerVertex / 2; ++e) {
72          boolean localEdge = random.nextFloat() < actualLocalityRatio;
73          int community = i / communitySize;
74          int j;
75          do {
76            if (localEdge) {
77              j = community * communitySize + random.nextInt(communitySize);
78            } else {
79              j = random.nextInt(numVertices);
80            }
81          } while (j == i);
82          graph.addSymmetricEdge(
83              i, j, edgeSupplier != null ? edgeSupplier.get() : null);
84        }
85      }
86    }
87  }