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 ch.bfh.algo.Direction;
022 import ch.bfh.algo.Graph;
023 import ch.bfh.algo.Position;
024 import ch.bfh.algo.Sequence;
025 import ch.bfh.algo.graph.DefaultGraph;
026 import ch.bfh.algo.graph.DefaultGraphFactory;
027 import ch.bfh.algo.graph.Vertex;
028 import ch.bfh.algo.sequence.LinkedSequence;
029
030
031 /**
032 * The class <code>GraphExample2</code> contains an example of the
033 * <code>ch.bfh.algo.Graph</code> interface, using the Factory Pattern
034 * to have specialized Vertices.
035 *
036 * This example contains the creation of one graph containing 10
037 * vertices and 12 edges. The vertices have two new properties visited
038 * which is used durring the algorithm and
039 * <code>connectedComponentNumber</code> which contains the number of
040 * the connencted component containing this vertex. They are
041 * implemented using another class and the Factory Pattern to create
042 * new instances without changing anything in the graph classes.
043 *
044 * @author <a href="mailto:">Emmanuel Benoist</a>
045 * @version 1.0
046 */
047 public class GraphExample2{
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 (DecoratedVertex) p;
109 }
110 }
111
112
113
114
115
116 /**
117 * The <code>bfsTraversal</code> is an example of the possible
118 * implementation of a Breadth 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<Position<String>> bfsTraversal(Graph<Integer,String> g){
126 Sequence<Position<String>> buffer = new LinkedSequence<Position<String>>();
127 Sequence<Position<String>> result = new LinkedSequence<Position<String>>();
128
129 // ccNumber represents the number of the current Connected Component.
130 int ccNumber = 0;
131 for(Position<String> v1 : g.vertices()){
132 DecoratedVertex v = (DecoratedVertex) v1;
133 if(!v.isVisited()){
134 ccNumber++;
135 buffer.add(v);
136 v.setVisited(true);
137 while(! buffer.isEmpty()){
138 Position<Position<String>> pFirst= buffer.first();
139 v = (DecoratedVertex)buffer.element(pFirst);
140 buffer.delete(pFirst);
141 result.add(v);
142 v.setConnectedComponentNumber(ccNumber);
143 for(Position<String> v2 : g.adjacentVertices(v,Direction.ALL)){
144 DecoratedVertex vv = (DecoratedVertex) v2;
145 if(vv !=null && !vv.isVisited() ){
146 vv.setVisited(true);
147 buffer.add(vv);
148 }
149 }
150 }
151 }
152
153 }
154 return result;
155 }
156
157 /**
158 * The <code>constructUndirectedGraph</code> method is used to
159 * initialize a default undirected <code>Graph</code>.
160 *
161 * The returned graph contains 10 vertices and 12 edges.
162 *
163 * @return a <code>Graph</code> value
164 */
165 public Graph<Integer,String> constructUndirectedGraph(){
166 boolean directed=false;
167 Graph<Integer,String> g =
168 new DefaultGraph<Integer,String>(new DecoratedGraphFactory(),directed);
169 Position<String> vertA = g.insertVertex("A");
170 Position<String> vertB = g.insertVertex("B");
171 Position<String> vertI = g.insertVertex("I");
172 Position<String> vertJ = g.insertVertex("J");
173 Position<String> vertC = g.insertVertex("C");
174 Position<String> vertH = g.insertVertex("H");
175 Position<String> vertD = g.insertVertex("D");
176 Position<String> vertE = g.insertVertex("E");
177 Position<String> vertF = g.insertVertex("F");
178 Position<String> vertG = g.insertVertex("G");
179
180 g.insertEdge(0,vertA,vertE);
181 g.insertEdge(0,vertE,vertD);
182 g.insertEdge(0,vertC,vertE);
183 g.insertEdge(0,vertC,vertD);
184 g.insertEdge(0,vertB,vertC);
185 g.insertEdge(0,vertA,vertB);
186 g.insertEdge(0,vertA,vertF);
187 g.insertEdge(0,vertA,vertF);
188 g.insertEdge(0,vertG,vertH);
189 g.insertEdge(0,vertH,vertI);
190 g.insertEdge(0,vertJ,vertH);
191 g.insertEdge(0,vertI,vertJ);
192
193 return g;
194 }
195
196
197 public void run(){
198 Graph<Integer,String> g = constructUndirectedGraph();
199 Sequence<Position<String>> bfs = bfsTraversal(g);
200 System.out.println("BFS= "+bfs);
201
202 }
203
204
205 public static void main(String[] args){
206 System.out.println("***************");
207 System.out.println("Example of use of Graphs with a decorated vertex.");
208 System.out.println("Computes for each Vertex its Connected Component (CC-number):");
209 new GraphExample2().run();
210 System.out.println("***************");
211 System.out.println("");
212
213 }
214
215
216 }