You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2015/02/12 14:02:16 UTC
[50/77] [partial] incubator-tinkerpop git commit: moved com/tinkerpop
directories to org/apache/tinkerpop
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java
deleted file mode 100644
index 9dd3684..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java
+++ /dev/null
@@ -1,109 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import com.tinkerpop.gremlin.structure.Edge;
-import com.tinkerpop.gremlin.structure.Graph;
-import com.tinkerpop.gremlin.structure.Vertex;
-
-import java.util.Map;
-import java.util.Optional;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Supplier;
-
-/**
- * Base class for all synthetic network generators.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- * @author Stephen Mallette (http://stephen.genoprime.com)
- */
-public abstract class AbstractGenerator implements Generator {
- protected final Graph g;
- private final String label;
- private final Optional<Consumer<Edge>> edgeProcessor;
- private final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor;
- protected final Supplier<Long> seedSupplier;
-
- /**
- * Constructs a new network generator for edges with the given label and annotator. If a {@code seedGenerator} is
- * not supplied then the system clock is used to generate a seed.
- *
- * @param label Label for the generated edges
- * @param edgeProcessor {@link java.util.function.Consumer} to use for annotating newly generated edges.
- * @param vertexProcessor {@link java.util.function.Consumer} to use for annotating process vertices.
- * @param seedGenerator A {@link java.util.function.Supplier} function to provide seeds to {@link java.util.Random}
- */
- AbstractGenerator(final Graph g, final String label, final Optional<Consumer<Edge>> edgeProcessor,
- final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor,
- final Supplier<Long> seedGenerator) {
- this.g = g;
- this.label = label;
- this.edgeProcessor = edgeProcessor;
- this.vertexProcessor = vertexProcessor;
- this.seedSupplier = seedGenerator;
- }
-
- protected final Edge addEdge(final Vertex out, final Vertex in) {
- final Edge e = out.addEdge(label, in);
- edgeProcessor.ifPresent(c -> c.accept(e));
- return e;
- }
-
- protected final Vertex processVertex(final Vertex vertex, final Map<String, Object> context) {
- vertexProcessor.ifPresent(c -> c.accept(vertex, context));
- return vertex;
- }
-
- public abstract static class AbstractGeneratorBuilder<T extends AbstractGeneratorBuilder> {
- protected String label;
- protected Optional<Consumer<Edge>> edgeProcessor = Optional.empty();
- protected Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor = Optional.empty();
- protected Supplier<Long> seedSupplier = System::currentTimeMillis;
- private final Class<T> extendingClass;
-
- AbstractGeneratorBuilder(final Class<T> extendingClass) {
- this.extendingClass = extendingClass;
- }
-
- public T label(final String label) {
- if (null == label || label.isEmpty()) throw new IllegalArgumentException("Label cannot be empty");
- this.label = label;
- return extendingClass.cast(this);
- }
-
- public T edgeProcessor(final Consumer<Edge> edgeProcessor) {
- this.edgeProcessor = Optional.ofNullable(edgeProcessor);
- return extendingClass.cast(this);
- }
-
- /**
- * The function supplied here may be called more than once per vertex depending on the implementation.
- */
- public T vertexProcessor(final BiConsumer<Vertex, Map<String, Object>> vertexProcessor) {
- this.vertexProcessor = Optional.ofNullable(vertexProcessor);
- return extendingClass.cast(this);
- }
-
- public T seedGenerator(final Supplier<Long> seedGenerator) {
- this.seedSupplier = Optional.ofNullable(seedGenerator).orElse(System::currentTimeMillis);
- return extendingClass.cast(this);
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java
deleted file mode 100644
index cd3f8f9..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java
+++ /dev/null
@@ -1,234 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import com.tinkerpop.gremlin.structure.Edge;
-import com.tinkerpop.gremlin.structure.Graph;
-import com.tinkerpop.gremlin.structure.Vertex;
-import com.tinkerpop.gremlin.util.iterator.IteratorUtils;
-
-import java.util.ArrayList;
-import java.util.HashMap;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.List;
-import java.util.Map;
-import java.util.Optional;
-import java.util.Random;
-import java.util.Set;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Supplier;
-
-/**
- * Generates a synthetic network with a community structure, that is, several densely connected
- * sub-networks that are loosely connected with one another.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- * @author Stephen Mallette (http://stephen.genoprime.com)
- */
-public class CommunityGenerator extends AbstractGenerator {
-
- public static final double DEFAULT_CROSS_COMMUNITY_PERCENTAGE = 0.1;
- public static final int DEFAULT_NUMBER_OF_COMMUNITIES = 2;
-
- private final Distribution communitySize;
- private final Distribution edgeDegree;
- private final double crossCommunityPercentage;
- private final Iterable<Vertex> vertices;
- private final int expectedNumCommunities;
- private final int expectedNumEdges;
-
- private final Random random;
-
- private CommunityGenerator(final Graph g, final String label, final Optional<Consumer<Edge>> edgeProcessor,
- final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor,
- final Supplier<Long> seedGenerator, final Distribution communitySize,
- final Distribution edgeDegree, final double crossCommunityPercentage,
- final Iterable<Vertex> vertices, final int expectedNumCommunities,
- final int expectedNumEdges) {
- super(g, label, edgeProcessor, vertexProcessor, seedGenerator);
- random = new Random(this.seedSupplier.get());
- this.communitySize = communitySize;
- this.edgeDegree = edgeDegree;
- this.crossCommunityPercentage = crossCommunityPercentage;
- this.vertices = vertices;
- this.expectedNumCommunities = expectedNumCommunities;
- this.expectedNumEdges = expectedNumEdges;
- }
-
- /**
- * Generates a synthetic network for provided vertices in the given graph such that the provided expected number
- * of communities are generated with the specified expected number of edges.
- *
- * @return The actual number of edges generated. May be different from the expected number.
- */
- @Override
- public int generate() {
- int numVertices = SizableIterable.sizeOf(vertices);
- final Iterator<Vertex> iter = vertices.iterator();
- final ArrayList<ArrayList<Vertex>> communities = new ArrayList<>(expectedNumCommunities);
- final Distribution communityDist = communitySize.initialize(expectedNumCommunities, numVertices);
- final Map<String, Object> context = new HashMap<>();
- while (iter.hasNext()) {
- final int nextSize = communityDist.nextValue(random);
- context.put("communityIndex", communities.size());
- final ArrayList<Vertex> community = new ArrayList<>(nextSize);
- for (int i = 0; i < nextSize && iter.hasNext(); i++) {
- community.add(processVertex(iter.next(), context));
- }
- if (!community.isEmpty()) communities.add(community);
- }
-
- final double inCommunityPercentage = 1.0 - crossCommunityPercentage;
- final Distribution degreeDist = edgeDegree.initialize(numVertices, expectedNumEdges);
- if (crossCommunityPercentage > 0 && communities.size() < 2)
- throw new IllegalArgumentException("Cannot have cross links with only one community");
- int addedEdges = 0;
-
- //System.out.println("Generating links on communities: "+communities.size());
-
- for (ArrayList<Vertex> community : communities) {
- for (Vertex v : community) {
- final int randomDegree = degreeDist.nextValue(random);
- final int degree = Math.min(randomDegree, (int) Math.ceil((community.size() - 1) / inCommunityPercentage) - 1);
- final Set<Vertex> inlinks = new HashSet<>();
- final Set<Vertex> outlinks = new HashSet<>();
- for (int i = 0; i < degree; i++) {
- Vertex selected = null;
- if (random.nextDouble() < crossCommunityPercentage || (community.size() - 1 <= inlinks.size())) {
- //Cross community
- int tries = 0;
- ArrayList<Vertex> othercomm = null;
-
- // this limit on the number of tries prevents infinite loop where the selected vertex to
- // link to doesn't exist given the nature and structure of the graph.
- while (null == selected && tries < 100) {
- // choose another community to connect to and make sure it's not in the current
- // community of the current vertex
- while (null == othercomm) {
- othercomm = communities.get(random.nextInt(communities.size()));
- if (othercomm.equals(community)) othercomm = null;
- }
- selected = othercomm.get(random.nextInt(othercomm.size()));
- if (outlinks.contains(selected)) selected = null;
-
- tries++;
- }
-
- // if tries expires then the value of selected is null in which case it should not be added.
- if (selected != null) outlinks.add(selected);
- } else {
- //In community
- int tries = 0;
- while (selected == null && tries < 100) {
- selected = community.get(random.nextInt(community.size()));
- if (v.equals(selected) || inlinks.contains(selected)) selected = null;
- tries++;
- }
-
- if (selected != null) inlinks.add(selected);
- }
-
- // only add an edge if the vertex was actually selected.
- if (selected != null) {
- addEdge(v, selected);
- addedEdges++;
- }
- }
- }
- }
- return addedEdges;
- }
-
- public static Builder build(final Graph g) {
- return new Builder(g);
- }
-
- public static class Builder extends AbstractGeneratorBuilder<Builder> {
- private final Graph g;
- private Distribution communitySize = null;
- private Distribution edgeDegree = null;
- private double crossCommunityPercentage = DEFAULT_CROSS_COMMUNITY_PERCENTAGE;
- private Iterable<Vertex> vertices;
- private int expectedNumCommunities = DEFAULT_NUMBER_OF_COMMUNITIES;
- private int expectedNumEdges;
-
- private Builder(final Graph g) {
- super(Builder.class);
- this.g = g;
- final List<Vertex> allVertices = IteratorUtils.list(g.iterators().vertexIterator());
- this.vertices = allVertices;
- this.expectedNumEdges = allVertices.size() * 2;
- }
-
- public Builder verticesToGenerateEdgesFor(final Iterable<Vertex> vertices) {
- this.vertices = vertices;
- return this;
- }
-
- public Builder expectedNumCommunities(final int expectedNumCommunities) {
- this.expectedNumCommunities = expectedNumCommunities;
- return this;
- }
-
- public Builder expectedNumEdges(final int expectedNumEdges) {
- this.expectedNumEdges = expectedNumEdges;
- return this;
- }
-
- /**
- * Sets the distribution to be used to generate the sizes of communities.
- */
- public Builder communityDistribution(final Distribution community) {
- this.communitySize = community;
- return this;
- }
-
- /**
- * Sets the distribution to be used to generate the out-degrees of vertices.
- */
- public Builder degreeDistribution(final Distribution degree) {
- this.edgeDegree = degree;
- return this;
- }
-
- /**
- * Sets the percentage of edges that cross a community, i.e. connect a vertex to a vertex in
- * another community. The lower this value, the higher the modularity of the generated communities.
- *
- * @param percentage Percentage of community crossing edges. Must be in [0,1]
- */
- public Builder crossCommunityPercentage(final double percentage) {
- if (percentage < 0.0 || percentage > 1.0)
- throw new IllegalArgumentException("Percentage must be between 0 and 1");
- this.crossCommunityPercentage = percentage;
- return this;
- }
-
- public CommunityGenerator create() {
- if (null == communitySize)
- throw new IllegalStateException("Need to initialize community size distribution");
- if (null == edgeDegree) throw new IllegalStateException("Need to initialize degree distribution");
- return new CommunityGenerator(this.g, this.label, this.edgeProcessor, this.vertexProcessor, this.seedSupplier,
- this.communitySize, this.edgeDegree, crossCommunityPercentage, vertices,
- expectedNumCommunities, expectedNumEdges);
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java
deleted file mode 100644
index 8a3cdec..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java
+++ /dev/null
@@ -1,47 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import java.util.Random;
-
-/**
- * CopyDistribution returns the conditional value.
- * <p/>
- * Hence, this class can be used as the in-degree distribution to ensure that
- * the in-degree of a vertex is equal to the out-degree.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- */
-public class CopyDistribution implements Distribution {
-
- @Override
- public Distribution initialize(final int invocations, final int expectedTotal) {
- return this;
- }
-
- @Override
- public int nextValue(final Random random) {
- throw new UnsupportedOperationException();
- }
-
- @Override
- public int nextConditionalValue(final Random random, final int otherValue) {
- return otherValue;
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Distribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Distribution.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Distribution.java
deleted file mode 100644
index 46bae25..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Distribution.java
+++ /dev/null
@@ -1,70 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import java.util.Random;
-
-/**
- * Interface for a distribution over discrete values.
- * <p/>
- * Used, for instance, by {@link DistributionGenerator} to define the in- and out-degree distributions and by
- * {@link CommunityGenerator} to define the community size distribution.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- */
-public interface Distribution {
-
- /**
- * Initializes the distribution such that expectedTotal is equal to the expected sum of generated values
- * after the given number of invocatiosn.
- * <p/>
- * Since most distributions have an element of randomness, these values are the expected values.
- *
- * @return A new distribution configured to match the expected total for the number of invocations.
- */
- Distribution initialize(final int invocations, final int expectedTotal);
-
- /**
- * Returns the next value. If this value is randomly generated, the randomness must be drawn from
- * the provided random generator.
- * <p/>
- * DO NOT use your own internal random generator as this makes the generated values non-reproducible and leads
- * to faulty behavior.
- *
- * @param random random generator to use for randomness
- * @return next value
- */
- int nextValue(final Random random);
-
- /**
- * Returns the next value conditional on another given value.
- * <p/>
- * This can be used, for instance, to define conditional degree distributions where the in-degree is conditional on the out-degree.
- * <p/>
- * If this value is randomly generated, the randomness must be drawn from the provided random generator.
- * DO NOT use your own internal random generator as this makes the generated values non-reproducible and leads
- * to faulty behavior.
- *
- * @param random random generator to use for randomness
- * @param otherValue The prior value
- * @return next value
- */
- int nextConditionalValue(final Random random, final int otherValue);
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java
deleted file mode 100644
index 35ae0da..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java
+++ /dev/null
@@ -1,181 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import com.tinkerpop.gremlin.structure.Edge;
-import com.tinkerpop.gremlin.structure.Graph;
-import com.tinkerpop.gremlin.structure.Vertex;
-import com.tinkerpop.gremlin.util.iterator.IteratorUtils;
-
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.List;
-import java.util.Map;
-import java.util.Optional;
-import java.util.Random;
-import java.util.function.BiConsumer;
-import java.util.function.Consumer;
-import java.util.function.Supplier;
-import java.util.stream.IntStream;
-
-/**
- * Generates a synthetic network for a given out- and (optionally) in-degree distribution.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- * @author Stephen Mallette (http://stephen.genoprime.com)
- */
-public class DistributionGenerator extends AbstractGenerator {
-
- private final Distribution outDistribution;
- private final Distribution inDistribution;
- private final Iterable<Vertex> out;
- private final Iterable<Vertex> in;
- private final int expectedNumEdges;
- private final boolean allowLoops;
-
- private DistributionGenerator(final Graph g, final String label, final Optional<Consumer<Edge>> edgeProcessor,
- final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor,
- final Supplier<Long> seedGenerator, final Iterable<Vertex> out,
- final Iterable<Vertex> in, final int expectedNumEdges,
- final Distribution outDistribution, final Distribution inDistribution,
- final boolean allowLoops) {
- super(g, label, edgeProcessor, vertexProcessor, seedGenerator);
- this.out = out;
- this.in = in;
- this.outDistribution = outDistribution;
- this.inDistribution = inDistribution;
- this.expectedNumEdges = expectedNumEdges;
- this.allowLoops = allowLoops;
- }
-
- @Override
- public int generate() {
- final long seed = this.seedSupplier.get();
- Random outRandom = new Random(seed);
- final ArrayList<Vertex> outStubs = new ArrayList<>(expectedNumEdges);
-
- for (Vertex v : out) {
- processVertex(v, Collections.EMPTY_MAP);
- final int degree = this.outDistribution.nextValue(outRandom);
- IntStream.range(0, degree).forEach(i -> outStubs.add(v));
- }
-
- outRandom = new Random(seed);
- Collections.shuffle(outStubs, outRandom);
-
- outRandom = new Random(seed);
- final Random inRandom = new Random(this.seedSupplier.get());
- int addedEdges = 0;
- int position = 0;
- for (Vertex v : in) {
- processVertex(v, Collections.EMPTY_MAP);
- final int degree = this.inDistribution.nextConditionalValue(inRandom, this.outDistribution.nextValue(outRandom));
- for (int i = 0; i < degree; i++) {
- Vertex other = null;
- while (null == other) {
- if (position >= outStubs.size()) return addedEdges; //No more edges to connect
- other = outStubs.get(position);
- position++;
- if (!allowLoops && v.equals(other)) other = null;
- }
- //Connect edge
- addEdge(other, v);
- addedEdges++;
- }
- }
- return addedEdges;
- }
-
- public static Builder build(final Graph g) {
- return new Builder(g);
- }
-
- public static class Builder extends AbstractGeneratorBuilder<Builder> {
- private final Graph g;
- private Distribution outDistribution;
- private Distribution inDistribution;
- private Iterable<Vertex> out;
- private Iterable<Vertex> in;
- private int expectedNumEdges;
- private boolean allowLoops = true;
-
- private Builder(final Graph g) {
- super(Builder.class);
- this.g = g;
- final List<Vertex> allVertices = IteratorUtils.list(g.iterators().vertexIterator());
- this.out = allVertices;
- this.in = allVertices;
- this.expectedNumEdges = allVertices.size() * 2;
- }
-
- public Builder inVertices(final Iterable<Vertex> vertices) {
- this.in = vertices;
- return this;
- }
-
- public Builder outVertices(final Iterable<Vertex> vertices) {
- this.out = vertices;
- return this;
- }
-
- public Builder expectedNumEdges(final int expectedNumEdges) {
- this.expectedNumEdges = expectedNumEdges;
- return this;
- }
-
- /**
- * Sets whether loops, i.e. edges with the same start and end vertex, are allowed to be generated.
- */
- public void allowLoops(final boolean allowLoops) {
- this.allowLoops = allowLoops;
- }
-
- /**
- * Sets the distribution to be used to generate the sizes of communities.
- */
- public Builder outDistribution(final Distribution distribution) {
- this.outDistribution = distribution;
- return this;
- }
-
- /**
- * Sets the distribution to be used to generate the out-degrees of vertices.
- */
- public Builder inDistribution(final Distribution distribution) {
- this.inDistribution = distribution;
- return this;
- }
-
- public DistributionGenerator create() {
- if (null == outDistribution)
- throw new IllegalStateException("Must set out-distribution before generating edges");
- final Distribution outDist = outDistribution.initialize(SizableIterable.sizeOf(out), expectedNumEdges);
- Distribution inDist;
- if (null == inDistribution) {
- if (out != in) throw new IllegalArgumentException("Need to specify in-distribution");
- inDist = new CopyDistribution();
- } else {
- inDist = inDistribution.initialize(SizableIterable.sizeOf(in), expectedNumEdges);
- }
-
- return new DistributionGenerator(this.g, this.label, this.edgeProcessor, this.vertexProcessor, this.seedSupplier,
- this.out, this.in, this.expectedNumEdges, outDist, inDist, allowLoops);
- }
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Generator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Generator.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Generator.java
deleted file mode 100644
index fc2ac41..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/Generator.java
+++ /dev/null
@@ -1,34 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-/**
- * Interface for Graph generators.
- *
- * @author Stephen Mallette (http://stephen.genoprime.com)
- */
-public interface Generator {
- /**
- * Generate the elements in the graph given the nature of the implementation and return the number of
- * edges generated as a result.
- *
- * @return number of edges generated
- */
- public int generate();
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java
deleted file mode 100644
index 3a9f391..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java
+++ /dev/null
@@ -1,76 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import java.util.Random;
-
-/**
- * Generates values according to a normal distribution with the configured standard deviation.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- */
-public class NormalDistribution implements Distribution {
-
- private final double stdDeviation;
- private final double mean;
-
- /**
- * Constructs a NormalDistribution with the given standard deviation.
- * <p/>
- * Setting the standard deviation to 0 makes this a constant distribution.
- *
- * @param stdDeviation Simple deviation of the distribution. Must be non-negative.
- */
- public NormalDistribution(final double stdDeviation) {
- this(stdDeviation, 0.0);
- }
-
- private NormalDistribution(final double stdDeviation, final double mean) {
- if (stdDeviation < 0)
- throw new IllegalArgumentException("Standard deviation must be non-negative: " + stdDeviation);
- if (mean < 0) throw new IllegalArgumentException("Mean must be positive: " + mean);
- this.stdDeviation = stdDeviation;
- this.mean = mean;
- }
-
- @Override
- public Distribution initialize(final int invocations, final int expectedTotal) {
- double mean = (expectedTotal * 1.0) / invocations; //TODO: account for truncated gaussian distribution
- return new NormalDistribution(stdDeviation, mean);
- }
-
- @Override
- public int nextValue(final Random random) {
- if (mean == 0.0) throw new IllegalStateException("Distribution has not been initialized");
- return (int) Math.round(random.nextGaussian() * stdDeviation + mean);
- }
-
- @Override
- public int nextConditionalValue(final Random random, final int otherValue) {
- return nextValue(random);
- }
-
- @Override
- public String toString() {
- return "NormalDistribution{" +
- "stdDeviation=" + stdDeviation +
- ", mean=" + mean +
- '}';
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java
deleted file mode 100644
index d197561..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java
+++ /dev/null
@@ -1,76 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import java.util.Random;
-
-/**
- * Generates values according to a scale-free distribution with the configured gamma value.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- */
-public class PowerLawDistribution implements Distribution {
-
- private final double gamma;
- private final double multiplier;
-
- /**
- * Constructs a new scale-free distribution for the provided gamma value.
- */
- public PowerLawDistribution(final double gamma) {
- this(gamma, 0.0);
- }
-
- private PowerLawDistribution(final double gamma, final double multiplier) {
- if (gamma <= 2.0) throw new IllegalArgumentException("Beta must be bigger than 2: " + gamma);
- if (multiplier < 0) throw new IllegalArgumentException("Invalid multiplier value: " + multiplier);
- this.gamma = gamma;
- this.multiplier = multiplier;
- }
-
- @Override
- public Distribution initialize(final int invocations, final int expectedTotal) {
- double multiplier = expectedTotal / ((gamma - 1) / (gamma - 2) * invocations) * 2; //times two because we are generating stubs
- assert multiplier > 0;
- return new PowerLawDistribution(gamma, multiplier);
- }
-
- @Override
- public int nextValue(final Random random) {
- if (multiplier == 0.0) throw new IllegalStateException("Distribution has not been initialized");
- return getValue(random, multiplier, gamma);
- }
-
- @Override
- public int nextConditionalValue(final Random random, final int otherValue) {
- return nextValue(random);
- }
-
- @Override
- public String toString() {
- return "PowerLawDistribution{" +
- "gamma=" + gamma +
- ", multiplier=" + multiplier +
- '}';
- }
-
- public static int getValue(final Random random, final double multiplier, final double beta) {
- return (int) Math.round(multiplier * (Math.pow(1.0 / (1.0 - random.nextDouble()), 1.0 / (beta - 1.0)) - 1.0));
- }
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/SizableIterable.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/SizableIterable.java b/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/SizableIterable.java
deleted file mode 100644
index 4fed416..0000000
--- a/gremlin-algorithm/src/main/java/com/tinkerpop/gremlin/algorithm/generator/SizableIterable.java
+++ /dev/null
@@ -1,88 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing,
- * software distributed under the License is distributed on an
- * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
- * KIND, either express or implied. See the License for the
- * specific language governing permissions and limitations
- * under the License.
- */
-package com.tinkerpop.gremlin.algorithm.generator;
-
-import java.util.Collection;
-import java.util.Iterator;
-
-/**
- * Utility class to make size determinations for {@link Iterable} for efficient.
- * <p/>
- * If the number of elements in an Iterable is known, then the Iterable can be wrapped in this class to make
- * determining the size a constant time operation rather than an iteration over the whole Iterable.
- * <p/>
- * Some generators need to know the number of vertices prior to generation. Using this class can speed up the generator.
- *
- * @author Matthias Broecheler (me@matthiasb.com)
- */
-public class SizableIterable<T> implements Iterable<T> {
-
- private final Iterable<T> iterable;
- private final int size;
-
- /**
- * Wraps the given Iterable with the given size.
- * <p/>
- * NOTE: the size MUST be the size of the Iterable. This is not verified.
- */
- public SizableIterable(final Iterable<T> iterable, final int size) {
- if (iterable == null)
- throw new NullPointerException();
- if (size < 0)
- throw new IllegalArgumentException("Size must be positive");
- this.iterable = iterable;
- this.size = size;
- }
-
- /**
- * Returns the size of the Iterable
- *
- * @return Size of the Iterable
- */
- public int size() {
- return size;
- }
-
- @Override
- public Iterator<T> iterator() {
- return iterable.iterator();
- }
-
- /**
- * Utility method to determine the number of elements in an Iterable.
- * <p/>
- * Checks if the given Iterable is an instance of a Collection or SizableIterable before iterating to improve performance.
- *
- * @return The size of the given Iterable.
- */
- public static <T> int sizeOf(final Iterable<T> iterable) {
- if (iterable instanceof Collection) {
- return ((Collection<T>) iterable).size();
- } else if (iterable instanceof SizableIterable) {
- return ((SizableIterable<T>) iterable).size();
- } else {
- int size = 0;
- for (Iterator<T> iter = iterable.iterator(); iter.hasNext(); iter.next()) {
- size++;
- }
- return size;
- }
- }
-
-}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java
new file mode 100644
index 0000000..9dd3684
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/AbstractGenerator.java
@@ -0,0 +1,109 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import com.tinkerpop.gremlin.structure.Edge;
+import com.tinkerpop.gremlin.structure.Graph;
+import com.tinkerpop.gremlin.structure.Vertex;
+
+import java.util.Map;
+import java.util.Optional;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+
+/**
+ * Base class for all synthetic network generators.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public abstract class AbstractGenerator implements Generator {
+ protected final Graph g;
+ private final String label;
+ private final Optional<Consumer<Edge>> edgeProcessor;
+ private final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor;
+ protected final Supplier<Long> seedSupplier;
+
+ /**
+ * Constructs a new network generator for edges with the given label and annotator. If a {@code seedGenerator} is
+ * not supplied then the system clock is used to generate a seed.
+ *
+ * @param label Label for the generated edges
+ * @param edgeProcessor {@link java.util.function.Consumer} to use for annotating newly generated edges.
+ * @param vertexProcessor {@link java.util.function.Consumer} to use for annotating process vertices.
+ * @param seedGenerator A {@link java.util.function.Supplier} function to provide seeds to {@link java.util.Random}
+ */
+ AbstractGenerator(final Graph g, final String label, final Optional<Consumer<Edge>> edgeProcessor,
+ final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor,
+ final Supplier<Long> seedGenerator) {
+ this.g = g;
+ this.label = label;
+ this.edgeProcessor = edgeProcessor;
+ this.vertexProcessor = vertexProcessor;
+ this.seedSupplier = seedGenerator;
+ }
+
+ protected final Edge addEdge(final Vertex out, final Vertex in) {
+ final Edge e = out.addEdge(label, in);
+ edgeProcessor.ifPresent(c -> c.accept(e));
+ return e;
+ }
+
+ protected final Vertex processVertex(final Vertex vertex, final Map<String, Object> context) {
+ vertexProcessor.ifPresent(c -> c.accept(vertex, context));
+ return vertex;
+ }
+
+ public abstract static class AbstractGeneratorBuilder<T extends AbstractGeneratorBuilder> {
+ protected String label;
+ protected Optional<Consumer<Edge>> edgeProcessor = Optional.empty();
+ protected Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor = Optional.empty();
+ protected Supplier<Long> seedSupplier = System::currentTimeMillis;
+ private final Class<T> extendingClass;
+
+ AbstractGeneratorBuilder(final Class<T> extendingClass) {
+ this.extendingClass = extendingClass;
+ }
+
+ public T label(final String label) {
+ if (null == label || label.isEmpty()) throw new IllegalArgumentException("Label cannot be empty");
+ this.label = label;
+ return extendingClass.cast(this);
+ }
+
+ public T edgeProcessor(final Consumer<Edge> edgeProcessor) {
+ this.edgeProcessor = Optional.ofNullable(edgeProcessor);
+ return extendingClass.cast(this);
+ }
+
+ /**
+ * The function supplied here may be called more than once per vertex depending on the implementation.
+ */
+ public T vertexProcessor(final BiConsumer<Vertex, Map<String, Object>> vertexProcessor) {
+ this.vertexProcessor = Optional.ofNullable(vertexProcessor);
+ return extendingClass.cast(this);
+ }
+
+ public T seedGenerator(final Supplier<Long> seedGenerator) {
+ this.seedSupplier = Optional.ofNullable(seedGenerator).orElse(System::currentTimeMillis);
+ return extendingClass.cast(this);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java
new file mode 100644
index 0000000..cd3f8f9
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CommunityGenerator.java
@@ -0,0 +1,234 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import com.tinkerpop.gremlin.structure.Edge;
+import com.tinkerpop.gremlin.structure.Graph;
+import com.tinkerpop.gremlin.structure.Vertex;
+import com.tinkerpop.gremlin.util.iterator.IteratorUtils;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Random;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+
+/**
+ * Generates a synthetic network with a community structure, that is, several densely connected
+ * sub-networks that are loosely connected with one another.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public class CommunityGenerator extends AbstractGenerator {
+
+ public static final double DEFAULT_CROSS_COMMUNITY_PERCENTAGE = 0.1;
+ public static final int DEFAULT_NUMBER_OF_COMMUNITIES = 2;
+
+ private final Distribution communitySize;
+ private final Distribution edgeDegree;
+ private final double crossCommunityPercentage;
+ private final Iterable<Vertex> vertices;
+ private final int expectedNumCommunities;
+ private final int expectedNumEdges;
+
+ private final Random random;
+
+ private CommunityGenerator(final Graph g, final String label, final Optional<Consumer<Edge>> edgeProcessor,
+ final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor,
+ final Supplier<Long> seedGenerator, final Distribution communitySize,
+ final Distribution edgeDegree, final double crossCommunityPercentage,
+ final Iterable<Vertex> vertices, final int expectedNumCommunities,
+ final int expectedNumEdges) {
+ super(g, label, edgeProcessor, vertexProcessor, seedGenerator);
+ random = new Random(this.seedSupplier.get());
+ this.communitySize = communitySize;
+ this.edgeDegree = edgeDegree;
+ this.crossCommunityPercentage = crossCommunityPercentage;
+ this.vertices = vertices;
+ this.expectedNumCommunities = expectedNumCommunities;
+ this.expectedNumEdges = expectedNumEdges;
+ }
+
+ /**
+ * Generates a synthetic network for provided vertices in the given graph such that the provided expected number
+ * of communities are generated with the specified expected number of edges.
+ *
+ * @return The actual number of edges generated. May be different from the expected number.
+ */
+ @Override
+ public int generate() {
+ int numVertices = SizableIterable.sizeOf(vertices);
+ final Iterator<Vertex> iter = vertices.iterator();
+ final ArrayList<ArrayList<Vertex>> communities = new ArrayList<>(expectedNumCommunities);
+ final Distribution communityDist = communitySize.initialize(expectedNumCommunities, numVertices);
+ final Map<String, Object> context = new HashMap<>();
+ while (iter.hasNext()) {
+ final int nextSize = communityDist.nextValue(random);
+ context.put("communityIndex", communities.size());
+ final ArrayList<Vertex> community = new ArrayList<>(nextSize);
+ for (int i = 0; i < nextSize && iter.hasNext(); i++) {
+ community.add(processVertex(iter.next(), context));
+ }
+ if (!community.isEmpty()) communities.add(community);
+ }
+
+ final double inCommunityPercentage = 1.0 - crossCommunityPercentage;
+ final Distribution degreeDist = edgeDegree.initialize(numVertices, expectedNumEdges);
+ if (crossCommunityPercentage > 0 && communities.size() < 2)
+ throw new IllegalArgumentException("Cannot have cross links with only one community");
+ int addedEdges = 0;
+
+ //System.out.println("Generating links on communities: "+communities.size());
+
+ for (ArrayList<Vertex> community : communities) {
+ for (Vertex v : community) {
+ final int randomDegree = degreeDist.nextValue(random);
+ final int degree = Math.min(randomDegree, (int) Math.ceil((community.size() - 1) / inCommunityPercentage) - 1);
+ final Set<Vertex> inlinks = new HashSet<>();
+ final Set<Vertex> outlinks = new HashSet<>();
+ for (int i = 0; i < degree; i++) {
+ Vertex selected = null;
+ if (random.nextDouble() < crossCommunityPercentage || (community.size() - 1 <= inlinks.size())) {
+ //Cross community
+ int tries = 0;
+ ArrayList<Vertex> othercomm = null;
+
+ // this limit on the number of tries prevents infinite loop where the selected vertex to
+ // link to doesn't exist given the nature and structure of the graph.
+ while (null == selected && tries < 100) {
+ // choose another community to connect to and make sure it's not in the current
+ // community of the current vertex
+ while (null == othercomm) {
+ othercomm = communities.get(random.nextInt(communities.size()));
+ if (othercomm.equals(community)) othercomm = null;
+ }
+ selected = othercomm.get(random.nextInt(othercomm.size()));
+ if (outlinks.contains(selected)) selected = null;
+
+ tries++;
+ }
+
+ // if tries expires then the value of selected is null in which case it should not be added.
+ if (selected != null) outlinks.add(selected);
+ } else {
+ //In community
+ int tries = 0;
+ while (selected == null && tries < 100) {
+ selected = community.get(random.nextInt(community.size()));
+ if (v.equals(selected) || inlinks.contains(selected)) selected = null;
+ tries++;
+ }
+
+ if (selected != null) inlinks.add(selected);
+ }
+
+ // only add an edge if the vertex was actually selected.
+ if (selected != null) {
+ addEdge(v, selected);
+ addedEdges++;
+ }
+ }
+ }
+ }
+ return addedEdges;
+ }
+
+ public static Builder build(final Graph g) {
+ return new Builder(g);
+ }
+
+ public static class Builder extends AbstractGeneratorBuilder<Builder> {
+ private final Graph g;
+ private Distribution communitySize = null;
+ private Distribution edgeDegree = null;
+ private double crossCommunityPercentage = DEFAULT_CROSS_COMMUNITY_PERCENTAGE;
+ private Iterable<Vertex> vertices;
+ private int expectedNumCommunities = DEFAULT_NUMBER_OF_COMMUNITIES;
+ private int expectedNumEdges;
+
+ private Builder(final Graph g) {
+ super(Builder.class);
+ this.g = g;
+ final List<Vertex> allVertices = IteratorUtils.list(g.iterators().vertexIterator());
+ this.vertices = allVertices;
+ this.expectedNumEdges = allVertices.size() * 2;
+ }
+
+ public Builder verticesToGenerateEdgesFor(final Iterable<Vertex> vertices) {
+ this.vertices = vertices;
+ return this;
+ }
+
+ public Builder expectedNumCommunities(final int expectedNumCommunities) {
+ this.expectedNumCommunities = expectedNumCommunities;
+ return this;
+ }
+
+ public Builder expectedNumEdges(final int expectedNumEdges) {
+ this.expectedNumEdges = expectedNumEdges;
+ return this;
+ }
+
+ /**
+ * Sets the distribution to be used to generate the sizes of communities.
+ */
+ public Builder communityDistribution(final Distribution community) {
+ this.communitySize = community;
+ return this;
+ }
+
+ /**
+ * Sets the distribution to be used to generate the out-degrees of vertices.
+ */
+ public Builder degreeDistribution(final Distribution degree) {
+ this.edgeDegree = degree;
+ return this;
+ }
+
+ /**
+ * Sets the percentage of edges that cross a community, i.e. connect a vertex to a vertex in
+ * another community. The lower this value, the higher the modularity of the generated communities.
+ *
+ * @param percentage Percentage of community crossing edges. Must be in [0,1]
+ */
+ public Builder crossCommunityPercentage(final double percentage) {
+ if (percentage < 0.0 || percentage > 1.0)
+ throw new IllegalArgumentException("Percentage must be between 0 and 1");
+ this.crossCommunityPercentage = percentage;
+ return this;
+ }
+
+ public CommunityGenerator create() {
+ if (null == communitySize)
+ throw new IllegalStateException("Need to initialize community size distribution");
+ if (null == edgeDegree) throw new IllegalStateException("Need to initialize degree distribution");
+ return new CommunityGenerator(this.g, this.label, this.edgeProcessor, this.vertexProcessor, this.seedSupplier,
+ this.communitySize, this.edgeDegree, crossCommunityPercentage, vertices,
+ expectedNumCommunities, expectedNumEdges);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java
new file mode 100644
index 0000000..8a3cdec
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/CopyDistribution.java
@@ -0,0 +1,47 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import java.util.Random;
+
+/**
+ * CopyDistribution returns the conditional value.
+ * <p/>
+ * Hence, this class can be used as the in-degree distribution to ensure that
+ * the in-degree of a vertex is equal to the out-degree.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ */
+public class CopyDistribution implements Distribution {
+
+ @Override
+ public Distribution initialize(final int invocations, final int expectedTotal) {
+ return this;
+ }
+
+ @Override
+ public int nextValue(final Random random) {
+ throw new UnsupportedOperationException();
+ }
+
+ @Override
+ public int nextConditionalValue(final Random random, final int otherValue) {
+ return otherValue;
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Distribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Distribution.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Distribution.java
new file mode 100644
index 0000000..46bae25
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Distribution.java
@@ -0,0 +1,70 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import java.util.Random;
+
+/**
+ * Interface for a distribution over discrete values.
+ * <p/>
+ * Used, for instance, by {@link DistributionGenerator} to define the in- and out-degree distributions and by
+ * {@link CommunityGenerator} to define the community size distribution.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ */
+public interface Distribution {
+
+ /**
+ * Initializes the distribution such that expectedTotal is equal to the expected sum of generated values
+ * after the given number of invocatiosn.
+ * <p/>
+ * Since most distributions have an element of randomness, these values are the expected values.
+ *
+ * @return A new distribution configured to match the expected total for the number of invocations.
+ */
+ Distribution initialize(final int invocations, final int expectedTotal);
+
+ /**
+ * Returns the next value. If this value is randomly generated, the randomness must be drawn from
+ * the provided random generator.
+ * <p/>
+ * DO NOT use your own internal random generator as this makes the generated values non-reproducible and leads
+ * to faulty behavior.
+ *
+ * @param random random generator to use for randomness
+ * @return next value
+ */
+ int nextValue(final Random random);
+
+ /**
+ * Returns the next value conditional on another given value.
+ * <p/>
+ * This can be used, for instance, to define conditional degree distributions where the in-degree is conditional on the out-degree.
+ * <p/>
+ * If this value is randomly generated, the randomness must be drawn from the provided random generator.
+ * DO NOT use your own internal random generator as this makes the generated values non-reproducible and leads
+ * to faulty behavior.
+ *
+ * @param random random generator to use for randomness
+ * @param otherValue The prior value
+ * @return next value
+ */
+ int nextConditionalValue(final Random random, final int otherValue);
+
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java
new file mode 100644
index 0000000..35ae0da
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/DistributionGenerator.java
@@ -0,0 +1,181 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import com.tinkerpop.gremlin.structure.Edge;
+import com.tinkerpop.gremlin.structure.Graph;
+import com.tinkerpop.gremlin.structure.Vertex;
+import com.tinkerpop.gremlin.util.iterator.IteratorUtils;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Random;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Supplier;
+import java.util.stream.IntStream;
+
+/**
+ * Generates a synthetic network for a given out- and (optionally) in-degree distribution.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public class DistributionGenerator extends AbstractGenerator {
+
+ private final Distribution outDistribution;
+ private final Distribution inDistribution;
+ private final Iterable<Vertex> out;
+ private final Iterable<Vertex> in;
+ private final int expectedNumEdges;
+ private final boolean allowLoops;
+
+ private DistributionGenerator(final Graph g, final String label, final Optional<Consumer<Edge>> edgeProcessor,
+ final Optional<BiConsumer<Vertex, Map<String, Object>>> vertexProcessor,
+ final Supplier<Long> seedGenerator, final Iterable<Vertex> out,
+ final Iterable<Vertex> in, final int expectedNumEdges,
+ final Distribution outDistribution, final Distribution inDistribution,
+ final boolean allowLoops) {
+ super(g, label, edgeProcessor, vertexProcessor, seedGenerator);
+ this.out = out;
+ this.in = in;
+ this.outDistribution = outDistribution;
+ this.inDistribution = inDistribution;
+ this.expectedNumEdges = expectedNumEdges;
+ this.allowLoops = allowLoops;
+ }
+
+ @Override
+ public int generate() {
+ final long seed = this.seedSupplier.get();
+ Random outRandom = new Random(seed);
+ final ArrayList<Vertex> outStubs = new ArrayList<>(expectedNumEdges);
+
+ for (Vertex v : out) {
+ processVertex(v, Collections.EMPTY_MAP);
+ final int degree = this.outDistribution.nextValue(outRandom);
+ IntStream.range(0, degree).forEach(i -> outStubs.add(v));
+ }
+
+ outRandom = new Random(seed);
+ Collections.shuffle(outStubs, outRandom);
+
+ outRandom = new Random(seed);
+ final Random inRandom = new Random(this.seedSupplier.get());
+ int addedEdges = 0;
+ int position = 0;
+ for (Vertex v : in) {
+ processVertex(v, Collections.EMPTY_MAP);
+ final int degree = this.inDistribution.nextConditionalValue(inRandom, this.outDistribution.nextValue(outRandom));
+ for (int i = 0; i < degree; i++) {
+ Vertex other = null;
+ while (null == other) {
+ if (position >= outStubs.size()) return addedEdges; //No more edges to connect
+ other = outStubs.get(position);
+ position++;
+ if (!allowLoops && v.equals(other)) other = null;
+ }
+ //Connect edge
+ addEdge(other, v);
+ addedEdges++;
+ }
+ }
+ return addedEdges;
+ }
+
+ public static Builder build(final Graph g) {
+ return new Builder(g);
+ }
+
+ public static class Builder extends AbstractGeneratorBuilder<Builder> {
+ private final Graph g;
+ private Distribution outDistribution;
+ private Distribution inDistribution;
+ private Iterable<Vertex> out;
+ private Iterable<Vertex> in;
+ private int expectedNumEdges;
+ private boolean allowLoops = true;
+
+ private Builder(final Graph g) {
+ super(Builder.class);
+ this.g = g;
+ final List<Vertex> allVertices = IteratorUtils.list(g.iterators().vertexIterator());
+ this.out = allVertices;
+ this.in = allVertices;
+ this.expectedNumEdges = allVertices.size() * 2;
+ }
+
+ public Builder inVertices(final Iterable<Vertex> vertices) {
+ this.in = vertices;
+ return this;
+ }
+
+ public Builder outVertices(final Iterable<Vertex> vertices) {
+ this.out = vertices;
+ return this;
+ }
+
+ public Builder expectedNumEdges(final int expectedNumEdges) {
+ this.expectedNumEdges = expectedNumEdges;
+ return this;
+ }
+
+ /**
+ * Sets whether loops, i.e. edges with the same start and end vertex, are allowed to be generated.
+ */
+ public void allowLoops(final boolean allowLoops) {
+ this.allowLoops = allowLoops;
+ }
+
+ /**
+ * Sets the distribution to be used to generate the sizes of communities.
+ */
+ public Builder outDistribution(final Distribution distribution) {
+ this.outDistribution = distribution;
+ return this;
+ }
+
+ /**
+ * Sets the distribution to be used to generate the out-degrees of vertices.
+ */
+ public Builder inDistribution(final Distribution distribution) {
+ this.inDistribution = distribution;
+ return this;
+ }
+
+ public DistributionGenerator create() {
+ if (null == outDistribution)
+ throw new IllegalStateException("Must set out-distribution before generating edges");
+ final Distribution outDist = outDistribution.initialize(SizableIterable.sizeOf(out), expectedNumEdges);
+ Distribution inDist;
+ if (null == inDistribution) {
+ if (out != in) throw new IllegalArgumentException("Need to specify in-distribution");
+ inDist = new CopyDistribution();
+ } else {
+ inDist = inDistribution.initialize(SizableIterable.sizeOf(in), expectedNumEdges);
+ }
+
+ return new DistributionGenerator(this.g, this.label, this.edgeProcessor, this.vertexProcessor, this.seedSupplier,
+ this.out, this.in, this.expectedNumEdges, outDist, inDist, allowLoops);
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Generator.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Generator.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Generator.java
new file mode 100644
index 0000000..fc2ac41
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/Generator.java
@@ -0,0 +1,34 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+/**
+ * Interface for Graph generators.
+ *
+ * @author Stephen Mallette (http://stephen.genoprime.com)
+ */
+public interface Generator {
+ /**
+ * Generate the elements in the graph given the nature of the implementation and return the number of
+ * edges generated as a result.
+ *
+ * @return number of edges generated
+ */
+ public int generate();
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java
new file mode 100644
index 0000000..3a9f391
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/NormalDistribution.java
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import java.util.Random;
+
+/**
+ * Generates values according to a normal distribution with the configured standard deviation.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ */
+public class NormalDistribution implements Distribution {
+
+ private final double stdDeviation;
+ private final double mean;
+
+ /**
+ * Constructs a NormalDistribution with the given standard deviation.
+ * <p/>
+ * Setting the standard deviation to 0 makes this a constant distribution.
+ *
+ * @param stdDeviation Simple deviation of the distribution. Must be non-negative.
+ */
+ public NormalDistribution(final double stdDeviation) {
+ this(stdDeviation, 0.0);
+ }
+
+ private NormalDistribution(final double stdDeviation, final double mean) {
+ if (stdDeviation < 0)
+ throw new IllegalArgumentException("Standard deviation must be non-negative: " + stdDeviation);
+ if (mean < 0) throw new IllegalArgumentException("Mean must be positive: " + mean);
+ this.stdDeviation = stdDeviation;
+ this.mean = mean;
+ }
+
+ @Override
+ public Distribution initialize(final int invocations, final int expectedTotal) {
+ double mean = (expectedTotal * 1.0) / invocations; //TODO: account for truncated gaussian distribution
+ return new NormalDistribution(stdDeviation, mean);
+ }
+
+ @Override
+ public int nextValue(final Random random) {
+ if (mean == 0.0) throw new IllegalStateException("Distribution has not been initialized");
+ return (int) Math.round(random.nextGaussian() * stdDeviation + mean);
+ }
+
+ @Override
+ public int nextConditionalValue(final Random random, final int otherValue) {
+ return nextValue(random);
+ }
+
+ @Override
+ public String toString() {
+ return "NormalDistribution{" +
+ "stdDeviation=" + stdDeviation +
+ ", mean=" + mean +
+ '}';
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java
new file mode 100644
index 0000000..d197561
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/PowerLawDistribution.java
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import java.util.Random;
+
+/**
+ * Generates values according to a scale-free distribution with the configured gamma value.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ */
+public class PowerLawDistribution implements Distribution {
+
+ private final double gamma;
+ private final double multiplier;
+
+ /**
+ * Constructs a new scale-free distribution for the provided gamma value.
+ */
+ public PowerLawDistribution(final double gamma) {
+ this(gamma, 0.0);
+ }
+
+ private PowerLawDistribution(final double gamma, final double multiplier) {
+ if (gamma <= 2.0) throw new IllegalArgumentException("Beta must be bigger than 2: " + gamma);
+ if (multiplier < 0) throw new IllegalArgumentException("Invalid multiplier value: " + multiplier);
+ this.gamma = gamma;
+ this.multiplier = multiplier;
+ }
+
+ @Override
+ public Distribution initialize(final int invocations, final int expectedTotal) {
+ double multiplier = expectedTotal / ((gamma - 1) / (gamma - 2) * invocations) * 2; //times two because we are generating stubs
+ assert multiplier > 0;
+ return new PowerLawDistribution(gamma, multiplier);
+ }
+
+ @Override
+ public int nextValue(final Random random) {
+ if (multiplier == 0.0) throw new IllegalStateException("Distribution has not been initialized");
+ return getValue(random, multiplier, gamma);
+ }
+
+ @Override
+ public int nextConditionalValue(final Random random, final int otherValue) {
+ return nextValue(random);
+ }
+
+ @Override
+ public String toString() {
+ return "PowerLawDistribution{" +
+ "gamma=" + gamma +
+ ", multiplier=" + multiplier +
+ '}';
+ }
+
+ public static int getValue(final Random random, final double multiplier, final double beta) {
+ return (int) Math.round(multiplier * (Math.pow(1.0 / (1.0 - random.nextDouble()), 1.0 / (beta - 1.0)) - 1.0));
+ }
+}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/1545201f/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/SizableIterable.java
----------------------------------------------------------------------
diff --git a/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/SizableIterable.java b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/SizableIterable.java
new file mode 100644
index 0000000..4fed416
--- /dev/null
+++ b/gremlin-algorithm/src/main/java/org/apache/tinkerpop/gremlin/algorithm/generator/SizableIterable.java
@@ -0,0 +1,88 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package com.tinkerpop.gremlin.algorithm.generator;
+
+import java.util.Collection;
+import java.util.Iterator;
+
+/**
+ * Utility class to make size determinations for {@link Iterable} for efficient.
+ * <p/>
+ * If the number of elements in an Iterable is known, then the Iterable can be wrapped in this class to make
+ * determining the size a constant time operation rather than an iteration over the whole Iterable.
+ * <p/>
+ * Some generators need to know the number of vertices prior to generation. Using this class can speed up the generator.
+ *
+ * @author Matthias Broecheler (me@matthiasb.com)
+ */
+public class SizableIterable<T> implements Iterable<T> {
+
+ private final Iterable<T> iterable;
+ private final int size;
+
+ /**
+ * Wraps the given Iterable with the given size.
+ * <p/>
+ * NOTE: the size MUST be the size of the Iterable. This is not verified.
+ */
+ public SizableIterable(final Iterable<T> iterable, final int size) {
+ if (iterable == null)
+ throw new NullPointerException();
+ if (size < 0)
+ throw new IllegalArgumentException("Size must be positive");
+ this.iterable = iterable;
+ this.size = size;
+ }
+
+ /**
+ * Returns the size of the Iterable
+ *
+ * @return Size of the Iterable
+ */
+ public int size() {
+ return size;
+ }
+
+ @Override
+ public Iterator<T> iterator() {
+ return iterable.iterator();
+ }
+
+ /**
+ * Utility method to determine the number of elements in an Iterable.
+ * <p/>
+ * Checks if the given Iterable is an instance of a Collection or SizableIterable before iterating to improve performance.
+ *
+ * @return The size of the given Iterable.
+ */
+ public static <T> int sizeOf(final Iterable<T> iterable) {
+ if (iterable instanceof Collection) {
+ return ((Collection<T>) iterable).size();
+ } else if (iterable instanceof SizableIterable) {
+ return ((SizableIterable<T>) iterable).size();
+ } else {
+ int size = 0;
+ for (Iterator<T> iter = iterable.iterator(); iter.hasNext(); iter.next()) {
+ size++;
+ }
+ return size;
+ }
+ }
+
+}