jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.utils.TestGraphs

LineHitsSource
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.utils;
13  
14 import java.util.HashSet;
15 import java.util.Iterator;
16 import java.util.Set;
17  
18 import edu.uci.ics.jung.exceptions.FatalException;
19 import edu.uci.ics.jung.graph.DirectedGraph;
20 import edu.uci.ics.jung.graph.Edge;
21 import edu.uci.ics.jung.graph.Graph;
22 import edu.uci.ics.jung.graph.Vertex;
23 import edu.uci.ics.jung.graph.decorators.EdgeWeightLabeller;
24 import edu.uci.ics.jung.graph.decorators.Indexer;
25 import edu.uci.ics.jung.graph.decorators.NumberEdgeValue;
26 import edu.uci.ics.jung.graph.decorators.StringLabeller;
27 import edu.uci.ics.jung.graph.impl.AbstractSparseGraph;
28 import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;
29 import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;
30 import edu.uci.ics.jung.graph.impl.SparseGraph;
31 import edu.uci.ics.jung.graph.impl.SparseVertex;
32 import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;
33 import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
34 import edu.uci.ics.jung.graph.impl.UndirectedSparseVertex;
35 import edu.uci.ics.jung.random.generators.BarabasiAlbertGenerator;
36  
37 /**
38  *
39  * Generates a series of potentially useful test graphs.
40  *
41  * @author danyelf
42  *
43  */
440public class TestGraphs {
45  
46     /**
47      * A series of pairs that may be useful for generating graphs. The
48      * miniature graph consists of 8 edges, 10 nodes, and is formed of two
49      * connected components, one of 8 nodes, the other of 2.
50      *
51      */
523    public static String[][] pairs = { { "a", "b", "3" }, {
53             "a", "c", "4" }, {
54             "a", "d", "5" }, {
55             "d", "c", "6" }, {
56             "d", "e", "7" }, {
57             "e", "f", "8" }, {
58             "f", "g", "9" }, {
59             "h", "i", "1" }
60     };
61  
62     /**
63      * Creates a small sample graph that can be used for testing purposes. The
64      * graph is as described in the section on {@link #pairs pairs}. If <tt>isDirected</tt>,
65      * the graph is a {@link DirectedSparseGraph DirectedSparseGraph},
66      * otherwise, it is an {@link UndirectedSparseGraph UndirectedSparseGraph}.
67      *
68      * @param isDirected:
69      * Is the graph directed?
70      * @return a graph consisting of eight edges and ten nodes.
71      */
72     public static AbstractSparseGraph createTestGraph(boolean isDirected) {
73         AbstractSparseGraph g;
7418        if (isDirected) {
7514            g = new DirectedSparseGraph();
76         } else {
774            g = new UndirectedSparseGraph();
78         }
7918        StringLabeller sl = StringLabeller.getLabeller(g);
8018        EdgeWeightLabeller el = EdgeWeightLabeller.getLabeller(g);
81162        for (int i = 0; i < pairs.length; i++) {
82144            String[] pair = pairs[i];
83144            createEdge(g, sl, el, pair[0], pair[1], Integer.parseInt(pair[2]));
84         }
8518        return g;
86  
87     }
88  
89     /**
90      * Returns a graph consisting of a chain of <code>vertex_count - 1</code> vertices
91      * plus one isolated vertex.
92      */
93     public static Graph createChainPlusIsolates(int chain_length, int isolate_count)
94     {
950        Graph g = new UndirectedSparseGraph();
960        if (chain_length > 0)
97         {
980            Vertex[] v = new Vertex[chain_length];
990            v[0] = g.addVertex(new UndirectedSparseVertex());
1000            for (int i = 1; i < chain_length; i++)
101             {
1020                v[i] = g.addVertex(new UndirectedSparseVertex());
1030                g.addEdge(new UndirectedSparseEdge(v[i], v[i-1]));
104             }
105         }
1060        for (int i = 0; i < isolate_count; i++)
1070            g.addVertex(new UndirectedSparseVertex());
108         
1090        return g;
110     }
111     
112     /**
113      * Creates a sample directed acyclic graph by generating several "layers",
114      * and connecting nodes (randomly) to nodes in earlier (but never later)
115      * layers. Each layer has some random number of nodes in it 1 less than n
116      * less than maxNodesPerLayer.
117      *
118      * @return the created graph
119      */
120     public static Graph createDirectedAcyclicGraph(
121         int layers,
122         int maxNodesPerLayer,
123         double linkprob) {
1240        DirectedGraph dag = new DirectedSparseGraph();
1250        StringLabeller sl = StringLabeller.getLabeller(dag);
1260        Set previousLayers = new HashSet();
1270        Set inThisLayer = new HashSet();
1280        for (int i = 0; i < layers; i++) {
129  
1300            int nodesThisLayer = (int) (Math.random() * maxNodesPerLayer) + 1;
1310            for (int j = 0; j < nodesThisLayer; j++) {
1320                Vertex v = dag.addVertex(new SparseVertex());
1330                inThisLayer.add(v);
134                 try {
1350                    sl.setLabel(v, i + ":" + j);
1360                } catch (Exception e) {
1370                }
138                 // for each previous node...
1390                for (Iterator iter = previousLayers.iterator();
1400                    iter.hasNext();
141                     ) {
1420                    Vertex v2 = (Vertex) iter.next();
1430                    if (Math.random() < linkprob) {
1440                        GraphUtils.addEdge(dag, v, v2);
145                     }
146                 }
147             }
148  
1490            previousLayers.addAll(inThisLayer);
1500            inThisLayer.clear();
151         }
1520        return dag;
153     }
154  
155     private static void createEdge(
156         final AbstractSparseGraph g,
157         StringLabeller sl,
158         EdgeWeightLabeller el,
159         String v1Label,
160         String v2Label,
161         int weight) {
162  
163         try {
164144            Vertex v1 = sl.getVertex(v1Label);
165144            if (v1 == null) {
16636                v1 = g.addVertex(new SparseVertex());
16736                sl.setLabel(v1, v1Label);
168             }
169144            Vertex v2 = sl.getVertex(v2Label);
170144            if (v2 == null) {
171126                v2 = g.addVertex(new SparseVertex());
172126                sl.setLabel(v2, v2Label);
173             }
174144            Edge e = GraphUtils.addEdge(g, v1, v2);
175144            el.setWeight(e, weight);
1760        } catch (StringLabeller.UniqueLabelException e) {
1770            throw new FatalException("This should not happen " + e);
178144        }
179144    }
180  
181     /**
182      * Returns a bigger, undirected test graph with a just one component. This
183      * graph consists of a clique of ten edges, a partial clique (randomly
184      * generated, with edges of 0.6 probability), and one series of edges
185      * running from the first node to the last.
186      *
187      * @return the testgraph
188      */
189     public static Graph getOneComponentGraph() {
1900        UndirectedSparseGraph g = new UndirectedSparseGraph();
1910        StringLabeller sl = StringLabeller.getLabeller(g);
1920        EdgeWeightLabeller el = EdgeWeightLabeller.getLabeller(g);
193  
194         // let's throw in a clique, too
1950        for (int i = 1; i <= 10; i++) {
1960            for (int j = i + 1; j <= 10; j++) {
1970                String i1 = "" + i;
1980                String i2 = "" + j;
1990                createEdge(g, sl, el, i1, i2, i + j);
200             }
201         }
202  
203         // and, last, a partial clique
2040        for (int i = 11; i <= 20; i++) {
2050            for (int j = i + 1; j <= 20; j++) {
2060                if (Math.random() > 0.6)
2070                    continue;
2080                String i1 = "" + i;
2090                String i2 = "" + j;
2100                createEdge(g, sl, el, i1, i2, i + j);
211             }
212         }
213  
214         // and one edge to connect them all
2150        Indexer ind = Indexer.getIndexer(g);
2160        for (int i = 0; i < g.numVertices() - 1; i++) {
217             try {
2180                GraphUtils.addEdge(g, (Vertex)ind.getVertex(i), (Vertex) ind.getVertex(i + 1));
2190            } catch (IllegalArgumentException fe) {
2200            }
221         }
222  
2230        return g;
224     }
225  
226     /**
227      * Returns a bigger test graph with a clique, several components, and other
228      * parts.
229      *
230      * @return a demonstration graph of type <tt>UndirectedSparseGraph</tt>
231      * with 28 vertices.
232      */
233     public static Graph getDemoGraph() {
2340        UndirectedSparseGraph g = new UndirectedSparseGraph();
2350        StringLabeller sl = StringLabeller.getLabeller(g);
2360        EdgeWeightLabeller el = EdgeWeightLabeller.getLabeller(g);
237  
2380        for (int i = 0; i < pairs.length; i++) {
2390            String[] pair = pairs[i];
2400            createEdge(g, sl, el, pair[0], pair[1], Integer.parseInt(pair[2]));
241         }
242  
243         // let's throw in a clique, too
2440        for (int i = 1; i <= 10; i++) {
2450            for (int j = i + 1; j <= 10; j++) {
2460                String i1 = "" + i;
2470                String i2 = "" + j;
2480                createEdge(g, sl, el, i1, i2, i + j);
249             }
250         }
251  
252         // and, last, a partial clique
2530        for (int i = 11; i <= 20; i++) {
2540            for (int j = i + 1; j <= 20; j++) {
2550                if (Math.random() > 0.6)
2560                    continue;
2570                String i1 = "" + i;
2580                String i2 = "" + j;
2590                createEdge(g, sl, el, i1, i2, i + j);
260             }
261         }
2620        return g;
263     }
264  
265     /**
266      * Equivalent to <code>generateMixedRandomGraph(edge_weight, num_vertices, true)</code>.
267      */
268     public static Graph generateMixedRandomGraph(NumberEdgeValue edge_weight, int num_vertices)
269     {
2700        return generateMixedRandomGraph(edge_weight, num_vertices, true);
271     }
272  
273     /**
274      * Returns a random mixed-mode graph. Starts with a randomly generated
275      * Barabasi-Albert (preferential attachment) generator
276      * (4 initial vertices, 3 edges added at each step, and num_vertices - 4 evolution steps).
277      * Then takes the resultant graph, replaces random undirected edges with directed
278      * edges, and assigns random weights to each edge.
279      */
280     public static Graph generateMixedRandomGraph(NumberEdgeValue edge_weights, int num_vertices, boolean parallel)
281     {
2820        int seed = (int)(Math.random() * 10000);
2830        BarabasiAlbertGenerator bag = new BarabasiAlbertGenerator(4, 3, false, parallel, seed);
2840        bag.evolveGraph(num_vertices - 4);
2850        Graph ug = (Graph)bag.generateGraph();
2860        SettableVertexMapper svm = new HashSettableVertexMapper();
287  
288         // create a SparseGraph version of g
2890        Graph g = new SparseGraph();
2900        for (Iterator iter = ug.getVertices().iterator(); iter.hasNext(); )
291         {
2920            Vertex v = (Vertex)iter.next();
2930            Vertex w = new SparseVertex();
2940            g.addVertex(w);
2950            if (v.containsUserDatumKey(BarabasiAlbertGenerator.SEED))
2960                w.addUserDatum(BarabasiAlbertGenerator.SEED, BarabasiAlbertGenerator.SEED, UserData.REMOVE);
2970            svm.map(v, w);
298         }
299         
300         // randomly replace some of the edges by directed edges to
301         // get a mixed-mode graph, add random weights
3020        for (Iterator iter = ug.getEdges().iterator(); iter.hasNext(); )
303         {
3040            Edge e = (Edge)iter.next();
3050            Vertex v1 = (Vertex)e.getEndpoints().getFirst();
3060            Vertex v2 = (Vertex)e.getEndpoints().getSecond();
3070            Vertex mv1 = (Vertex)svm.getMappedVertex(v1);
3080            Vertex mv2 = (Vertex)svm.getMappedVertex(v2);
309             Edge me;
3100            if (Math.random() < 0.5)
3110                me = new DirectedSparseEdge(mv1, mv2);
312             else
3130                me = new UndirectedSparseEdge(mv1, mv2);
3140            g.addEdge(me);
3150            edge_weights.setNumber(me, new Double(Math.random()));
316         }
317         
3180        return g;
319     }
320  
321     
322 }

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.