KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > alg > VertexCoversTest


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* ---------------------
26  * VertexCoversTest.java
27  * ---------------------
28  * (C) Copyright 2003-2006, by Linda Buisman and Contributors.
29  *
30  * Original Author: Linda Buisman
31  * Contributor(s): Barak Naveh
32  *
33  * $Id: VertexCoversTest.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 06-Nov-2003 : Initial revision (LB);
38  * 10-Nov-2003 : Adapted to VertexCovers (BN);
39  *
40  */
41 package org.jgrapht.alg;
42
43 import java.util.*;
44
45 import junit.framework.*;
46
47 import org.jgrapht.*;
48 import org.jgrapht.graph.*;
49
50
51 /**
52  * Tests the vertex cover algorithms.
53  *
54  * @author Linda Buisman
55  * @since Nov 6, 2003
56  */
57 public class VertexCoversTest
58     extends TestCase
59 {
60
61     //~ Static fields/initializers --------------------------------------------
62
63     private static final int TEST_GRAPH_SIZE = 200;
64     private static final int TEST_REPEATS = 20;
65
66     //~ Methods ---------------------------------------------------------------
67
68     /**
69      * .
70      */
71     public void testFind2ApproximationCover()
72     {
73         for (int i = 0; i < TEST_REPEATS; i++) {
74             Graph<Integer JavaDoc, DefaultEdge> g = createRandomGraph();
75             assertTrue(
76                 isCover(VertexCovers.find2ApproximationCover(g), g));
77         }
78     }
79
80     /**
81      * .
82      */
83     public void testFindGreedyCover()
84     {
85         for (int i = 0; i < TEST_REPEATS; i++) {
86             Graph<Integer JavaDoc, DefaultEdge> g = createRandomGraph();
87             Set<Integer JavaDoc> c =
88                 VertexCovers.findGreedyCover(
89                     Graphs.undirectedGraph(g));
90             assertTrue(isCover(c, g));
91         }
92     }
93
94     /**
95      * Checks if the specified vertex set covers every edge of the graph. Uses
96      * the definition of Vertex Cover - removes every edge that is incident on a
97      * vertex in vertexSet. If no edges are left, vertexSet is a vertex cover
98      * for the specified graph.
99      *
100      * @param vertexSet the vertices to be tested for covering the graph.
101      * @param g the graph to be covered.
102      *
103      * @return
104      */
105     private boolean isCover(
106         Set<Integer JavaDoc> vertexSet,
107         Graph<Integer JavaDoc, DefaultEdge> g)
108     {
109         Set<DefaultEdge> uncoveredEdges = new HashSet<DefaultEdge>(g.edgeSet());
110
111         for (Iterator<Integer JavaDoc> i = vertexSet.iterator(); i.hasNext();) {
112             uncoveredEdges.removeAll(g.edgesOf(i.next()));
113         }
114
115         return uncoveredEdges.size() == 0;
116     }
117
118     /**
119      * Create a random graph of TEST_GRAPH_SIZE nodes.
120      *
121      * @return
122      */
123     private Graph<Integer JavaDoc, DefaultEdge> createRandomGraph()
124     {
125         // TODO: move random graph generator to be under GraphGenerator
126 // framework.
127 Pseudograph<Integer JavaDoc, DefaultEdge> g =
128             new Pseudograph<Integer JavaDoc, DefaultEdge>(DefaultEdge.class);
129
130         for (int i = 0; i < TEST_GRAPH_SIZE; i++) {
131             g.addVertex(new Integer JavaDoc(i));
132         }
133
134         List<Integer JavaDoc> vertices = new ArrayList<Integer JavaDoc>(g.vertexSet());
135
136         // join every vertex with a random number of other vertices
137 for (int source = 0; source < TEST_GRAPH_SIZE; source++) {
138             int numEdgesToCreate =
139                 ((int) Math.random() * TEST_GRAPH_SIZE / 2) + 1;
140
141             for (int j = 0; j < numEdgesToCreate; j++) {
142                 // find a random vertex to join to
143 int target = (int) Math.floor(Math.random() * TEST_GRAPH_SIZE);
144                 g.addEdge(vertices.get(source), vertices.get(target));
145             }
146         }
147
148         return g;
149     }
150 }
151
Popular Tags