X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?p=controller.git;a=blobdiff_plain;f=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fgenerators%2Frandom%2FBarabasiAlbertGenerator.java;fp=third-party%2Fnet.sf.jung2%2Fsrc%2Fmain%2Fjava%2Fedu%2Fuci%2Fics%2Fjung%2Falgorithms%2Fgenerators%2Frandom%2FBarabasiAlbertGenerator.java;h=0000000000000000000000000000000000000000;hp=77b419b4a4f3f3b55b081690cba5c2509c2e8b98;hb=e1c04c5af263a9604a765f1ab98be51dfc51d8cb;hpb=a935ffda7f26be29de879a47b426d0db7a28d588 diff --git a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java b/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java deleted file mode 100644 index 77b419b4a4..0000000000 --- a/third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/BarabasiAlbertGenerator.java +++ /dev/null @@ -1,227 +0,0 @@ -/* - * Copyright (c) 2003, the JUNG Project and the Regents of the University - * of California - * All rights reserved. - * - * This software is open-source under the BSD license; see either - * "license.txt" or - * http://jung.sourceforge.net/license.txt for a description. - */ -package edu.uci.ics.jung.algorithms.generators.random; - -import java.util.ArrayList; -import java.util.Collection; -import java.util.HashMap; -import java.util.HashSet; -import java.util.List; -import java.util.Map; -import java.util.Random; -import java.util.Set; - -import org.apache.commons.collections15.Factory; - -import edu.uci.ics.jung.algorithms.generators.EvolvingGraphGenerator; -import edu.uci.ics.jung.graph.Graph; -import edu.uci.ics.jung.graph.MultiGraph; -import edu.uci.ics.jung.graph.util.EdgeType; -import edu.uci.ics.jung.graph.util.Pair; - - -/** - *

Simple evolving scale-free random graph generator. At each time - * step, a new vertex is created and is connected to existing vertices - * according to the principle of "preferential attachment", whereby - * vertices with higher degree have a higher probability of being - * selected for attachment.

- * - *

At a given timestep, the probability p of creating an edge - * between an existing vertex v and the newly added vertex is - * 

- * p = (degree(v) + 1) / (|E| + |V|);
- *
- * - *

where |E| and |V| are, respectively, the number - * of edges and vertices currently in the network (counting neither the new - * vertex nor the other edges that are being attached to it).

- * - *

Note that the formula specified in the original paper - * (cited below) was - * 

- * p = degree(v) / |E|
- *
- *

- * - *

However, this would have meant that the probability of attachment for any existing - * isolated vertex would be 0. This version uses Lagrangian smoothing to give - * each existing vertex a positive attachment probability.

- * - *

The graph created may be either directed or undirected (controlled by a constructor - * parameter); the default is undirected. - * If the graph is specified to be directed, then the edges added will be directed - * from the newly added vertex u to the existing vertex v, with probability proportional to the - * indegree of v (number of edges directed towards v). If the graph is specified to be undirected, - * then the (undirected) edges added will connect u to v, with probability proportional to the - * degree of v.

- * - *

The parallel constructor parameter specifies whether parallel edges - * may be created.

- * - * @see "A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999." - * @author Scott White - * @author Joshua O'Madadhain - * @author Tom Nelson - adapted to jung2 - */ -public class BarabasiAlbertGenerator implements EvolvingGraphGenerator { - private Graph mGraph = null; - private int mNumEdgesToAttachPerStep; - private int mElapsedTimeSteps; - private Random mRandom; - protected List vertex_index; - protected int init_vertices; - protected Map index_vertex; - protected Factory> graphFactory; - protected Factory vertexFactory; - protected Factory edgeFactory; - - /** - * Constructs a new instance of the generator. - * @param init_vertices number of unconnected 'seed' vertices that the graph should start with - * @param numEdgesToAttach the number of edges that should be attached from the - * new vertex to pre-existing vertices at each time step - * @param directed specifies whether the graph and edges to be created should be directed or not - * @param parallel specifies whether the algorithm permits parallel edges - * @param seed random number seed - */ - public BarabasiAlbertGenerator(Factory> graphFactory, - Factory vertexFactory, Factory edgeFactory, - int init_vertices, int numEdgesToAttach, - int seed, Set seedVertices) - { - assert init_vertices > 0 : "Number of initial unconnected 'seed' vertices " + - "must be positive"; - assert numEdgesToAttach > 0 : "Number of edges to attach " + - "at each time step must be positive"; - - mNumEdgesToAttachPerStep = numEdgesToAttach; - mRandom = new Random(seed); - this.graphFactory = graphFactory; - this.vertexFactory = vertexFactory; - this.edgeFactory = edgeFactory; - this.init_vertices = init_vertices; - initialize(seedVertices); - } - - - /** - * Constructs a new instance of the generator, whose output will be an undirected graph, - * and which will use the current time as a seed for the random number generation. - * @param init_vertices number of vertices that the graph should start with - * @param numEdgesToAttach the number of edges that should be attached from the - * new vertex to pre-existing vertices at each time step - */ - public BarabasiAlbertGenerator(Factory> graphFactory, - Factory vertexFactory, Factory edgeFactory, - int init_vertices, int numEdgesToAttach, Set seedVertices) { - this(graphFactory, vertexFactory, edgeFactory, init_vertices, numEdgesToAttach, (int) System.currentTimeMillis(), seedVertices); - } - - private void initialize(Set seedVertices) { - - mGraph = graphFactory.create(); - - vertex_index = new ArrayList(2*init_vertices); - index_vertex = new HashMap(2*init_vertices); - for (int i = 0; i < init_vertices; i++) { - V v = vertexFactory.create(); - mGraph.addVertex(v); - vertex_index.add(v); - index_vertex.put(v, i); - seedVertices.add(v); - } - - mElapsedTimeSteps = 0; - } - - private void createRandomEdge(Collection preexistingNodes, - V newVertex, Set> added_pairs) { - V attach_point; - boolean created_edge = false; - Pair endpoints; - do { - attach_point = vertex_index.get(mRandom.nextInt(vertex_index.size())); - - endpoints = new Pair(newVertex, attach_point); - - // if parallel edges are not allowed, skip attach_point if - // already exists; note that because of the way edges are added, we only need to check - // the list of candidate edges for duplicates. - if (!(mGraph instanceof MultiGraph)) - { - if (added_pairs.contains(endpoints)) - continue; - if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED && - added_pairs.contains(new Pair(attach_point, newVertex))) - continue; - } - - double degree = mGraph.inDegree(attach_point); - - // subtract 1 from numVertices because we don't want to count newVertex - // (which has already been added to the graph, but not to vertex_index) - double attach_prob = (degree + 1) / (mGraph.getEdgeCount() + mGraph.getVertexCount() - 1); - if (attach_prob >= mRandom.nextDouble()) - created_edge = true; - } - while (!created_edge); - - added_pairs.add(endpoints); - - if (mGraph.getDefaultEdgeType() == EdgeType.UNDIRECTED) { - added_pairs.add(new Pair(attach_point, newVertex)); - } - } - - public void evolveGraph(int numTimeSteps) { - - for (int i = 0; i < numTimeSteps; i++) { - evolveGraph(); - mElapsedTimeSteps++; - } - } - - private void evolveGraph() { - Collection preexistingNodes = mGraph.getVertices(); - V newVertex = vertexFactory.create(); - - mGraph.addVertex(newVertex); - - // generate and store the new edges; don't add them to the graph - // yet because we don't want to bias the degree calculations - // (all new edges in a timestep should be added in parallel) - Set> added_pairs = new HashSet>(mNumEdgesToAttachPerStep*3); - - for (int i = 0; i < mNumEdgesToAttachPerStep; i++) - createRandomEdge(preexistingNodes, newVertex, added_pairs); - - for (Pair pair : added_pairs) - { - V v1 = pair.getFirst(); - V v2 = pair.getSecond(); - if (mGraph.getDefaultEdgeType() != EdgeType.UNDIRECTED || - !mGraph.isNeighbor(v1, v2)) - mGraph.addEdge(edgeFactory.create(), pair); - } - // now that we're done attaching edges to this new vertex, - // add it to the index - vertex_index.add(newVertex); - index_vertex.put(newVertex, new Integer(vertex_index.size() - 1)); - } - - public int numIterations() { - return mElapsedTimeSteps; - } - - public Graph create() { - return mGraph; - } -}