/*

  * 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.

  */

 /*

  * Created on Jul 2, 2003

  *  

  */

 package edu.uci.ics.jung.graph.util;

 import java.util.ArrayList;

 import java.util.HashSet;

 import java.util.List;

 import java.util.Set;

 import edu.uci.ics.jung.graph.DirectedGraph;

 import edu.uci.ics.jung.graph.DirectedSparseMultigraph;

 import edu.uci.ics.jung.graph.Graph;

 import edu.uci.ics.jung.graph.SparseMultigraph;

 import edu.uci.ics.jung.graph.UndirectedGraph;

 import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;

 /**

  * Provides generators for several different test graphs.

  */

 public class TestGraphs {

         /**

          * A series of pairs that may be useful for generating graphs. The

          * miniature graph consists of 8 edges, 10 nodes, and is formed of two

          * connected components, one of 8 nodes, the other of 2.

          *  

          */

         public static String[][] pairs = { { "a", "b", "3" }, {

                         "a", "c", "4" }, {

                         "a", "d", "5" }, {

                         "d", "c", "6" }, {

                         "d", "e", "7" }, {

                         "e", "f", "8" }, {

                         "f", "g", "9" }, {

                         "h", "i", "1" }

         };

         /**

          * Creates a small sample graph that can be used for testing purposes. The

          * graph is as described in the section on {@link #pairs pairs}. If <code>isDirected</code>,

          * the graph is a {@link DirectedSparseMultigraph DirectedSparseMultigraph},

          * otherwise, it is an {@link UndirectedSparseMultigraph UndirectedSparseMultigraph}.

          * 

          * @return a graph consisting of eight edges and ten nodes.

          */

         public static Graph<String, Number> createTestGraph(boolean directed) {

                 Graph<String, Number> graph = null;

                 if(directed) {

                         graph = new DirectedSparseMultigraph<String,Number>();

                 } else {

                         graph = new UndirectedSparseMultigraph<String,Number>();

                 }

                 for (int i = 0; i < pairs.length; i++) {

                         String[] pair = pairs[i];

                         graph.addEdge(Integer.parseInt(pair[2]), pair[0], pair[1]);

                 }

                 return graph;

         }

     /**

      * Returns a graph consisting of a chain of <code>vertex_count - 1</code> vertices

      * plus one isolated vertex.

      */

     public static Graph<String,Number> createChainPlusIsolates(int chain_length, int isolate_count)

     {

             Graph<String,Number> g = new UndirectedSparseMultigraph<String,Number>();

         if (chain_length > 0)

         {

             String[] v = new String[chain_length];

             v[0] = "v"+0;

             g.addVertex(v[0]);

             for (int i = 1; i < chain_length; i++)

             {

                 v[i] = "v"+i;

                 g.addVertex(v[i]);

                 g.addEdge(new Double(Math.random()), v[i], v[i-1]);

             }

         }

         for (int i = 0; i < isolate_count; i++) {

             String v = "v"+(chain_length+i);

             g.addVertex(v);

         }

         return g;

     }

         /**

          * Creates a sample directed acyclic graph by generating several "layers",

          * and connecting nodes (randomly) to nodes in earlier (but never later)

          * layers. Each layer has some random number of nodes in it 1 less than n

          * less than maxNodesPerLayer.

          * 

          * @return the created graph

          */

         public static Graph<String,Number> createDirectedAcyclicGraph(

                 int layers,

                 int maxNodesPerLayer,

                 double linkprob) {

                 DirectedGraph<String,Number> dag = new DirectedSparseMultigraph<String,Number>();

                 Set<String> previousLayers = new HashSet<String>();

                 Set<String> inThisLayer = new HashSet<String>();

                 for (int i = 0; i < layers; i++) {

                         int nodesThisLayer = (int) (Math.random() * maxNodesPerLayer) + 1;

                         for (int j = 0; j < nodesThisLayer; j++) {

                 String v = i+":"+j;

                                 dag.addVertex(v);

                                 inThisLayer.add(v);

                                 // for each previous node...

                 for(String v2 : previousLayers) {

                                         if (Math.random() < linkprob) {

                         Double de = new Double(Math.random());

                                                 dag.addEdge(de, v, v2);

                                         }

                                 }

                         }

                         previousLayers.addAll(inThisLayer);

                         inThisLayer.clear();

                 }

                 return dag;

         }

         private static void createEdge(

                         Graph<String, Number> g,

                         String v1Label,

                         String v2Label,

                         int weight) {

                         g.addEdge(new Double(Math.random()), v1Label, v2Label);

         }

         /**

          * Returns a bigger, undirected test graph with a just one component. This

          * graph consists of a clique of ten edges, a partial clique (randomly

          * generated, with edges of 0.6 probability), and one series of edges

          * running from the first node to the last.

          * 

          * @return the testgraph

          */

         public static Graph<String,Number> getOneComponentGraph() {

                 UndirectedGraph<String,Number> g = new UndirectedSparseMultigraph<String,Number>();

                 // let's throw in a clique, too

                 for (int i = 1; i <= 10; i++) {

                         for (int j = i + 1; j <= 10; j++) {

                                 String i1 = "" + i;

                                 String i2 = "" + j;

                                 g.addEdge(Math.pow(i+2,j), i1, i2);

                         }

                 }

                 // and, last, a partial clique

                 for (int i = 11; i <= 20; i++) {

                         for (int j = i + 1; j <= 20; j++) {

                                 if (Math.random() > 0.6)

                                         continue;

                                 String i1 = "" + i;

                                 String i2 = "" + j;

                                 g.addEdge(Math.pow(i+2,j), i1, i2);

                         }

                 }

                 List<String> index = new ArrayList<String>();

                 index.addAll(g.getVertices());

                 // and one edge to connect them all

                 for (int i = 0; i < index.size() - 1; i++) 

                     g.addEdge(new Integer(i), index.get(i), index.get(i+1));

                 return g;

         }

         /**

          * Returns a bigger test graph with a clique, several components, and other

          * parts.

          * 

          * @return a demonstration graph of type <tt>UndirectedSparseMultigraph</tt>

          *         with 28 vertices.

          */

         public static Graph<String, Number> getDemoGraph() {

                 UndirectedGraph<String, Number> g = 

             new UndirectedSparseMultigraph<String, Number>();

                 for (int i = 0; i < pairs.length; i++) {

                         String[] pair = pairs[i];

                         createEdge(g, pair[0], pair[1], Integer.parseInt(pair[2]));

                 }

                 // let's throw in a clique, too

                 for (int i = 1; i <= 10; i++) {

                         for (int j = i + 1; j <= 10; j++) {

                                 String i1 = "c" + i;

                                 String i2 = "c" + j;

                 g.addEdge(Math.pow(i+2,j), i1, i2);

                         }

                 }

                 // and, last, a partial clique

                 for (int i = 11; i <= 20; i++) {

                         for (int j = i + 1; j <= 20; j++) {

                                 if (Math.random() > 0.6)

                                         continue;

                                 String i1 = "p" + i;

                                 String i2 = "p" + j;

                 g.addEdge(Math.pow(i+2,j), i1, i2);

                         }

                 }

                 return g;

         }

     /**

      * Returns a small graph with directed and undirected edges, and parallel edges.

      */

     public static Graph<String, Number> getSmallGraph() {

         Graph<String, Number> graph = 

             new SparseMultigraph<String, Number>();

         String[] v = new String[3];

         for (int i = 0; i < 3; i++) {

             v[i] = String.valueOf(i);

             graph.addVertex(v[i]);

         }

         graph.addEdge(new Double(0), v[0], v[1], EdgeType.DIRECTED);

         graph.addEdge(new Double(.1), v[0], v[1], EdgeType.DIRECTED);

         graph.addEdge(new Double(.2), v[0], v[1], EdgeType.DIRECTED);

         graph.addEdge(new Double(.3), v[1], v[0], EdgeType.DIRECTED);

         graph.addEdge(new Double(.4), v[1], v[0], EdgeType.DIRECTED);

         graph.addEdge(new Double(.5), v[1], v[2]);

         graph.addEdge(new Double(.6), v[1], v[2]);

         return graph;

     }

 }