001 /*
002 * www.ti.bfh.ch
003 *
004 * Copyright 2007, Berne University of Applied Sciences,
005 * School of Engineering and Information Technology
006 * and individual contributors as indicated by the @authors tag.
007 *
008 * This is free software; you can redistribute it and/or modify it under the terms of the
009 * GNU Lesser General Public License as published by the Free Software Foundation;
010 * either version 3 of the License, or (at your option) any later version.
011 *
012 * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
013 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
014 * See the GNU Lesser General Public License for more details.
015 *
016 * You should have received a copy of the GNU Lesser General Public License along with this software;
017 * if not, see <http://www.gnu.org/licenses/>.
018 *
019 */
020 package ch.bfh.algo.example;
021 import java.util.HashMap;
022 import java.util.List;
023 import java.util.Map;
024 import java.util.Random;
025
026 import ch.bfh.algo.Direction;
027 import ch.bfh.algo.Graph;
028 import ch.bfh.algo.Position;
029 import ch.bfh.algo.Sequence;
030 import ch.bfh.algo.graph.DefaultGraph;
031 import ch.bfh.algo.graph.DefaultGraphFactory;
032 import ch.bfh.algo.graph.Vertex;
033 import ch.bfh.algo.sequence.LinkedSequence;
034
035
036 /**
037 * The class <code>GraphStress</code> contains Stess Tests for the Graph
038 *
039 * @author <a href="mailto:">Emmanuel Benoist</a>
040 * @version 1.0
041 */
042 public class GraphStress{
043 final static int MAX_NUMBER_OF_VERTICES = 9000;
044 final static int VERTICES_STEP = 3000;
045 final static int MAX_NUMBER_OF_EDGES = 30000;
046 final static int EDGES_STEP = 10000;
047
048
049
050 private class DecoratedVertex extends Vertex<Integer,String>{
051
052 // We add two properties to this vertex,
053 //
054 // First we have the visited boolean which indicates if this node
055 // has already been inserted in the buffer.
056 boolean visited;
057
058 // The second property is a return property to indicate to which
059 // connected component the vertex belong to.
060 int connectedComponentNumber;
061
062 /**
063 * Get the Visited value.
064 * @return the Visited value.
065 */
066 public boolean isVisited() {
067 return visited;
068 }
069
070 /**
071 * Set the Visited value.
072 * @param newVisited The new Visited value.
073 */
074 public void setVisited(boolean newVisited) {
075 this.visited = newVisited;
076 }
077
078 /**
079 * Get the ConnectedComponentNumber value.
080 * @return the ConnectedComponentNumber value.
081 */
082 public int getConnectedComponentNumber() {
083 return connectedComponentNumber;
084 }
085
086 /**
087 * Set the ConnectedComponentNumber value.
088 * @param newConnectedComponentNumber The new ConnectedComponentNumber value.
089 */
090 public void setConnectedComponentNumber(int newConnectedComponentNumber) {
091 this.connectedComponentNumber = newConnectedComponentNumber;
092 }
093
094 public String toString(){
095 return element().toString()+"("+connectedComponentNumber+")";
096
097 }
098
099 }
100
101 private class DecoratedGraphFactory extends DefaultGraphFactory<Integer,String>{
102
103 public Vertex<Integer,String> createVertex(){
104 return new DecoratedVertex();
105 }
106
107 public Vertex<Integer,String> castVertex(Position<?> p){
108 return (Vertex<Integer,String>) p;
109 }
110 }
111
112
113 private class GraphCopier{
114
115 Map<Position<String>,Position<String>> vertices;
116
117
118 /**
119 * Creates a new <code>GraphCopier</code> instance.
120 *
121 */
122 public GraphCopier(){
123 vertices = new HashMap<Position<String>,Position<String>>();
124 }
125
126 /**
127 * Get the MappingVertices value.
128 * @return the MappingVertices value.
129 */
130 public Map<Position<String>,Position<String>> getVertices() {
131 return vertices;
132 }
133
134 /**
135 * Set the MappingVertices value.
136 * @param newVertices The new MappingVertices value.
137 */
138 public void setVertices(Map<Position<String>,Position<String>> newMappingVertices) {
139 this.vertices = newMappingVertices;
140 }
141
142
143 public Graph<Integer,String> copy(Graph<Integer,String> g){
144 //Graph<E,V> gRes = new DefaultGraph<Integer,String>(g.factory());
145 Graph<Integer,String> gRes = new DefaultGraph<Integer,String>(new DecoratedGraphFactory());
146 for(Position<String> v : g.vertices()){
147 if(v!=null){
148 vertices.put(v , gRes.insertVertex(v.element()));
149 }
150 }
151 for(Position<Integer> e : g.edges(Direction.DIRECTED)){
152 Position<String> origin ,destination;
153 origin = g.origin(e);
154 destination = g.destination(e);
155 Position<Integer> edge = gRes.insertEdge(e.element());
156 gRes.setOrigin(edge,vertices.get(origin));
157 gRes.setDestination(edge,vertices.get(destination));
158 gRes.setDirected(edge);
159 }
160 return gRes;
161 }
162
163 public List<Position<String>> reverseList(List<Position<String>> lVertices){
164 Sequence<Position<String>> seq = new LinkedSequence<Position<String>>();
165 for(Position<String> vertexG1 : lVertices){
166 Position<String> vertexG2 = vertices.get(vertexG1);
167 //seq.insertFirst(vertexG2);
168 if(seq.isEmpty()){
169 seq.add(vertexG2);
170 }
171 else{
172 seq.insertBefore(seq.first(),vertexG2);
173 //seq.insertAfter(seq.last(),vertexG2);
174 }
175 }
176 return seq;
177 }
178
179
180 }
181
182
183
184
185 /**
186 * The <code>dfsTraversal</code> is an example of the possible
187 * implementation of a Depth First Search traversal of a
188 * <code>Graph</code>. In this case, we use the
189 * <code>DecoratedVertex</code> to store inside each vertex if it
190 * has been visited.
191 *
192 * @return a <code>Sequence</code> value
193 */
194 public static Sequence<DecoratedVertex> dfsTraversal(Graph<Integer,String> g, List<Position<String>> vertices){
195 Sequence<DecoratedVertex> buffer = new LinkedSequence<DecoratedVertex>();
196 Sequence<DecoratedVertex> result = new LinkedSequence<DecoratedVertex>();
197
198 // ccNumber represents the number of the current Connected Component.
199 int ccNumber = 0;
200 for(Position<String> v1 : vertices){
201 DecoratedVertex v = (DecoratedVertex) v1;
202 if(!v.isVisited()){
203 ccNumber++;
204 buffer.add(v);
205 v.setVisited(true);
206 while(! buffer.isEmpty()){
207 v = buffer.last().element();
208 buffer.delete(buffer.last());
209 result.add(v);
210 v.setConnectedComponentNumber(ccNumber);
211 for(Position<String> v2 : g.adjacentVertices(v,Direction.OUT)){
212 DecoratedVertex vv = (DecoratedVertex) v2;
213 if(vv !=null && !vv.isVisited() ){
214 vv.setVisited(true);
215 buffer.add(vv);
216 }
217 }
218 }
219 }
220 }
221 return result;
222 }
223
224
225 public static void reverseAllEdges(Graph<Integer,String> g){
226 for(Position<Integer> e : g.edges(Direction.DIRECTED)){
227 g.reverse(e);
228 }
229 }
230
231 /**
232 * The <code>constructDirectedGraph</code> method is used to
233 * initialize a default directed <code>Graph</code>.
234 *
235 * The returned graph contains <code>numberOfVertices</code> vertices and
236 * <code>numberOfEdges</code> directed edges.
237 *
238 * @return a <code>Graph</code> value
239 */
240 public Graph<Integer,String> constructDirectedGraph(int numberOfVertices,
241 int numberOfEdges){
242 boolean directed=true;
243 Graph<Integer,String> g =
244 new DefaultGraph<Integer,String>(new DecoratedGraphFactory(),directed);
245
246 // Array containing all the vertices
247 Position<String>[] vertices = new Position[numberOfVertices];
248
249 for(int i=0;i < numberOfVertices;i++){
250 vertices[i]= g.insertVertex(""+i);
251 }
252
253 Random generator = new Random();
254 for(int j=0; j < numberOfEdges;j++){
255 Position<String> v1, v2;
256 int i1 = generator.nextInt(numberOfVertices);
257 int i2= generator.nextInt(numberOfVertices);
258 // while(i1==i2) i2=generator.nextInt(numberOfVertices);
259 v1=vertices[i1];
260 v2=vertices[i2];
261 g.insertEdge(0,v1,v2);
262 }
263
264 return g;
265 }
266
267
268 public void run(){
269 for(int numbOfVertices = VERTICES_STEP; numbOfVertices <= MAX_NUMBER_OF_VERTICES; numbOfVertices +=VERTICES_STEP){
270 for(int numbOfEdges = EDGES_STEP; numbOfEdges <=MAX_NUMBER_OF_EDGES; numbOfEdges +=EDGES_STEP){
271 try{
272 double[] t=new double[3];
273 t[0]=System.currentTimeMillis();
274 Graph<Integer,String> g = constructDirectedGraph( numbOfVertices,numbOfEdges);
275 t[1]=System.currentTimeMillis();
276 Sequence<DecoratedVertex> dfs = dfsTraversal(g,g.vertices());
277 t[2]=System.currentTimeMillis();
278 System.out.println("Vertices="+numbOfVertices+", \tEdges="+numbOfEdges+
279 ", \tInit="+(t[1]-t[0])/1000+"s, \tDFS="+(t[2]-t[1])/1000+"s"+
280 ", \tComponents=" + dfs.last().element().getConnectedComponentNumber());
281 }
282 catch(Exception e){
283 System.out.println("!!! Exception at Vertices="+numbOfVertices+", Edges="+numbOfEdges);
284 break;
285 }
286 }
287 }
288 }
289
290
291 public static void main(String[] args){
292 System.out.println("***************");
293 System.out.println("Stress Test.");
294 System.out.println("We generate random graphs with up to "+MAX_NUMBER_OF_VERTICES+" Vertices and "+MAX_NUMBER_OF_EDGES+" Edges");
295 System.out.println("incrementing the number of vertices and edges. Visiting each vertex by DFS:");
296 new GraphStress().run();
297 System.out.println("***************");
298 System.out.println("");
299
300 }
301
302
303 }