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
025 import ch.bfh.algo.Direction;
026 import ch.bfh.algo.Graph;
027 import ch.bfh.algo.Position;
028 import ch.bfh.algo.Sequence;
029 import ch.bfh.algo.graph.DefaultGraph;
030 import ch.bfh.algo.graph.DefaultGraphFactory;
031 import ch.bfh.algo.graph.Vertex;
032 import ch.bfh.algo.sequence.LinkedSequence;
033 import ch.bfh.algo.InvalidAccessorException;
034
035 import java.util.Random;
036
037
038 /**
039 * The class <code>GraphExampleNonGenerics</code> contains an example of use
040 * of graph without any generics.
041 *
042 * @author <a href="mailto:">Emmanuel Benoist</a>
043 * @version 1.0
044 */
045 public class GraphExampleNonGenerics{
046 final static int NUMBER_OF_VERTICES = 30;
047 final static int NUMBER_OF_EDGES = 50;
048
049
050
051 private class DecoratedVertex extends Vertex{
052
053 // We add two properties to this vertex,
054 //
055 // First we have the visited boolean which indicates if this node
056 // has already been inserted in the buffer.
057 boolean visited;
058
059 // The second property is a return property to indicate to which
060 // connected component the vertex belong to.
061 int connectedComponentNumber;
062
063 /**
064 * Get the Visited value.
065 * @return the Visited value.
066 */
067 public boolean isVisited() {
068 return visited;
069 }
070
071 /**
072 * Set the Visited value.
073 * @param newVisited The new Visited value.
074 */
075 public void setVisited(boolean newVisited) {
076 this.visited = newVisited;
077 }
078
079 /**
080 * Get the ConnectedComponentNumber value.
081 * @return the ConnectedComponentNumber value.
082 */
083 public int getConnectedComponentNumber() {
084 return connectedComponentNumber;
085 }
086
087 /**
088 * Set the ConnectedComponentNumber value.
089 * @param newConnectedComponentNumber The new ConnectedComponentNumber value.
090 */
091 public void setConnectedComponentNumber(int newConnectedComponentNumber) {
092 this.connectedComponentNumber = newConnectedComponentNumber;
093 }
094
095 public String toString(){
096 return element().toString()+"("+connectedComponentNumber+")";
097
098 }
099
100 }
101
102 private class DecoratedGraphFactory extends DefaultGraphFactory{
103
104 public Vertex createVertex(){
105 return new DecoratedVertex();
106 }
107
108 public Vertex castVertex(Position p){
109 return (Vertex) p;
110 }
111 }
112
113
114
115
116 /**
117 * The <code>dfsTraversal</code> is an example of the possible
118 * implementation of a Depth First Search traversal of a
119 * <code>Graph</code>. In this case, we use the
120 * <code>DecoratedVertex</code> to store inside each vertex if it
121 * has been visited.
122 *
123 * @return a <code>Sequence</code> value
124 */
125 public static Sequence dfsTraversal(Graph g, List vertices){
126
127 Sequence buffer = new LinkedSequence();
128 Sequence result = new LinkedSequence();
129
130 // ccNumber represents the number of the current Connected Component.
131 int ccNumber = 0;
132 for(Object o1 : vertices){
133 Position v1=(Position)o1;
134 DecoratedVertex v = (DecoratedVertex) v1;
135 if(!v.isVisited()){
136 ccNumber++;
137 buffer.add(v);
138 v.setVisited(true);
139 while(! buffer.isEmpty()){
140 Position pLast= buffer.last();
141 v = (DecoratedVertex)buffer.element(pLast);
142 buffer.delete(pLast);
143 result.add(v);
144 v.setConnectedComponentNumber(ccNumber);
145 for(Object o2 : g.adjacentVertices(v,Direction.OUT)){
146 Position v2 = (Position) o2;
147 DecoratedVertex vv = (DecoratedVertex) v2;
148 if(vv !=null && !vv.isVisited() ){
149 vv.setVisited(true);
150 buffer.add(vv);
151 }
152 }
153 }
154 }
155
156 }
157 return result;
158 }
159
160
161 /**
162 * The <code>constructDirectedGraph</code> method is used to
163 * initialize a default directed <code>Graph</code>.
164 *
165 * The returned graph contains <code>numberOfVertices</code> vertices and
166 * <code>numberOfEdges</code> directed edges.
167 *
168 * @return a <code>Graph</code> value
169 */
170 public Graph constructDirectedGraph(int numberOfVertices,
171 int numberOfEdges){
172 boolean directed=true;
173 Graph g =
174 new DefaultGraph(new DecoratedGraphFactory(),directed);
175
176 // Array containing all the vertices
177 Position<String>[] vertices = new Position[numberOfVertices];
178
179 for(int i=0;i < numberOfVertices;i++){
180 vertices[i]= g.insertVertex(""+i);
181 }
182
183 Random generator = new Random();
184 for(int j=0; j < numberOfEdges;j++){
185 Position v1, v2;
186 int i1 = generator.nextInt(numberOfVertices);
187 int i2= generator.nextInt(numberOfVertices);
188 v1=vertices[i1];
189 v2=vertices[i2];
190 g.insertEdge(0,v1,v2);
191 }
192
193 return g;
194 }
195
196
197 public void run(){
198
199 Graph g = constructDirectedGraph(NUMBER_OF_VERTICES,NUMBER_OF_EDGES);
200 Sequence dfs = dfsTraversal(g,g.vertices());
201 System.out.println("DFS= " + dfs);
202
203 }
204
205
206 public static void main(String[] args){
207 System.out.println("***************");
208 System.out.println("Example of use of a Directed Graphs with edges and vertices non generics.");
209 System.out.println("Computes the DFS of the Graph:");
210 new GraphExampleNonGenerics().run();
211 System.out.println("***************");
212 System.out.println("");
213
214 }
215
216
217 }