third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/MixedRandomGraphGenerator.java

   1 /*
   2  * Copyright (c) 2003, the JUNG Project and the Regents of the University of
   3  * California All rights reserved.
   4  *
   5  * This software is open-source under the BSD license; see either "license.txt"
   6  * or http://jung.sourceforge.net/license.txt for a description.
   7  */
   8 /*
   9  * Created on Jul 2, 2003
  10  *
  11  */
  12 package edu.uci.ics.jung.algorithms.generators.random;
  13
  14 import java.util.Map;
  15 import java.util.Set;
  16
  17 import org.apache.commons.collections15.Factory;
  18
  19 import edu.uci.ics.jung.graph.Graph;
  20 import edu.uci.ics.jung.graph.util.EdgeType;
  21
  22 /**
  23  *
  24  * Generates a mixed-mode random graph based on the output of <code>BarabasiAlbertGenerator</code>.
  25  * Primarily intended for providing a heterogeneous sample graph for visualization testing, etc.
  26  *
  27  */
  28 public class MixedRandomGraphGenerator {
  29
  30         /**
  31          * Equivalent to <code>generateMixedRandomGraph(edge_weight, num_vertices, true)</code>.
  32          */
  33         public static <V,E> Graph<V, E> generateMixedRandomGraph(
  34                         Factory<Graph<V,E>> graphFactory,
  35                         Factory<V> vertexFactory,
  36                 Factory<E> edgeFactory,
  37                 Map<E,Number> edge_weight,
  38                         int num_vertices, Set<V> seedVertices)
  39         {
  40                 return generateMixedRandomGraph(graphFactory, vertexFactory, edgeFactory,
  41                                 edge_weight, num_vertices, true, seedVertices);
  42         }
  43
  44     /**
  45      * Returns a random mixed-mode graph.  Starts with a randomly generated
  46      * Barabasi-Albert (preferential attachment) generator
  47      * (4 initial vertices, 3 edges added at each step, and num_vertices - 4 evolution steps).
  48      * Then takes the resultant graph, replaces random undirected edges with directed
  49      * edges, and assigns random weights to each edge.
  50      */
  51     public static <V,E> Graph<V,E> generateMixedRandomGraph(
  52                 Factory<Graph<V,E>> graphFactory,
  53                 Factory<V> vertexFactory,
  54                 Factory<E> edgeFactory,
  55                 Map<E,Number> edge_weights,
  56             int num_vertices, boolean parallel, Set<V> seedVertices)
  57     {
  58         int seed = (int)(Math.random() * 10000);
  59         BarabasiAlbertGenerator<V,E> bag =
  60             new BarabasiAlbertGenerator<V,E>(graphFactory, vertexFactory, edgeFactory,
  61                         4, 3, //false, parallel,
  62                         seed, seedVertices);
  63         bag.evolveGraph(num_vertices - 4);
  64         Graph<V, E> ug = bag.create();
  65
  66         // create a SparseMultigraph version of g
  67         Graph<V, E> g = graphFactory.create();
  68                 //new SparseMultigraph<V, E>();
  69         for(V v : ug.getVertices()) {
  70                 g.addVertex(v);
  71         }
  72
  73         // randomly replace some of the edges by directed edges to
  74         // get a mixed-mode graph, add random weights
  75
  76         for(E e : ug.getEdges()) {
  77             V v1 = ug.getEndpoints(e).getFirst();
  78             V v2 = ug.getEndpoints(e).getSecond();
  79
  80             E me = edgeFactory.create();
  81             g.addEdge(me, v1, v2, Math.random() < .5 ? EdgeType.DIRECTED : EdgeType.UNDIRECTED);
  82             edge_weights.put(me, Math.random());
  83         }
  84
  85         return g;
  86     }
  87
  88 }