X-Git-Url: https://git.opendaylight.org/gerrit/gitweb?a=blobdiff_plain;ds=inline;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;hb=e1c04c5af263a9604a765f1ab98be51dfc51d8cb;hp=77b419b4a4f3f3b55b081690cba5c2509c2e8b98;hpb=a935ffda7f26be29de879a47b426d0db7a28d588;p=controller.git
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;
- }
-}