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
034
035
036
037 /**
038 * The class <code>GraphExample3</code> contains an example of the
039 * <code>ch.bfh.algo.Graph</code> interface, using the Factory Pattern
040 * to have specialized Vertices.
041 *
042 * This example contains the creation of one graph containing 10
043 * vertices and 12 edges. The vertices have two new properties visited
044 * which is used durring the algorithm and
045 * <code>connectedComponentNumber</code> which contains the number of
046 * the connencted component containing this vertex. They are
047 * implemented using another class and the Factory Pattern to create
048 * new instances without changing anything in the graph classes.
049 *
050 * @author <a href="mailto:">Emmanuel Benoist</a>
051 * @version 1.0
052 */
053 public class GraphExample3{
054
055 private class DecoratedVertex extends Vertex<Integer,String>{
056
057 // We add two properties to this vertex,
058 //
059 // First we have the visited boolean which indicates if this node
060 // has already been inserted in the buffer.
061 boolean visited;
062
063 // The second property is a return property to indicate to which
064 // connected component the vertex belong to.
065 int connectedComponentNumber;
066
067 /**
068 * Get the Visited value.
069 * @return the Visited value.
070 */
071 public boolean isVisited() {
072 return visited;
073 }
074
075 /**
076 * Set the Visited value.
077 * @param newVisited The new Visited value.
078 */
079 public void setVisited(boolean newVisited) {
080 this.visited = newVisited;
081 }
082
083 /**
084 * Get the ConnectedComponentNumber value.
085 * @return the ConnectedComponentNumber value.
086 */
087 public int getConnectedComponentNumber() {
088 return connectedComponentNumber;
089 }
090
091 /**
092 * Set the ConnectedComponentNumber value.
093 * @param newConnectedComponentNumber The new ConnectedComponentNumber value.
094 */
095 public void setConnectedComponentNumber(int newConnectedComponentNumber) {
096 this.connectedComponentNumber = newConnectedComponentNumber;
097 }
098
099 public String toString(){
100 return element().toString()+"("+connectedComponentNumber+")";
101
102 }
103
104 }
105
106 private class DecoratedGraphFactory extends DefaultGraphFactory<Integer,String>{
107
108 public Vertex<Integer,String> createVertex(){
109 return new DecoratedVertex();
110 }
111
112 public Vertex<Integer,String> castVertex(Position<?> p){
113 return (Vertex<Integer,String>) p;
114 }
115 }
116
117
118 private class GraphCopier{
119
120 Map<Position<String>,Position<String>> vertices;
121
122
123 /**
124 * Creates a new <code>GraphCopier</code> instance.
125 *
126 */
127 public GraphCopier(){
128 vertices = new HashMap<Position<String>,Position<String>>();
129 }
130
131 /**
132 * Get the MappingVertices value.
133 * @return the MappingVertices value.
134 */
135 public Map<Position<String>,Position<String>> getVertices() {
136 return vertices;
137 }
138
139 /**
140 * Set the MappingVertices value.
141 * @param newVertices The new MappingVertices value.
142 */
143 public void setVertices(Map<Position<String>,Position<String>> newMappingVertices) {
144 this.vertices = newMappingVertices;
145 }
146
147
148 public Graph<Integer,String> copy(Graph<Integer,String> g){
149 //Graph<E,V> gRes = new DefaultGraph<Integer,String>(g.factory());
150 Graph<Integer,String> gRes = new DefaultGraph<Integer,String>(new DecoratedGraphFactory());
151 for(Position<String> v : g.vertices()){
152 if(v!=null){
153 vertices.put(v , gRes.insertVertex(v.element()));
154 }
155 }
156 for(Position<Integer> e : g.edges(Direction.DIRECTED)){
157 Position<String> origin ,destination;
158 origin = g.origin(e);
159 destination = g.destination(e);
160 Position<Integer> edge = gRes.insertEdge(e.element());
161 gRes.setOrigin(edge,vertices.get(origin));
162 gRes.setDestination(edge,vertices.get(destination));
163 gRes.setDirected(edge);
164 }
165 return gRes;
166 }
167
168 public List<Position<String>> reverseList(List<Position<String>> lVertices){
169 Sequence<Position<String>> seq = new LinkedSequence<Position<String>>();
170 for(Position<String> vertexG1 : lVertices){
171 Position<String> vertexG2 = vertices.get(vertexG1);
172 //seq.insertFirst(vertexG2);
173 if(seq.isEmpty()){
174 seq.add(vertexG2);
175 }
176 else{
177 seq.insertBefore(seq.first(),vertexG2);
178 //seq.insertAfter(seq.last(),vertexG2);
179 }
180 }
181 return seq;
182 }
183
184
185 }
186
187
188
189
190 /**
191 * The <code>dfsTraversal</code> is an example of the possible
192 * implementation of a Depth First Search traversal of a
193 * <code>Graph</code>. In this case, we use the
194 * <code>DecoratedVertex</code> to store inside each vertex if it
195 * has been visited.
196 *
197 * @return a <code>Sequence</code> value
198 */
199 public static Sequence<Position<String>> dfsTraversal(Graph<Integer,String> g, List<Position<String>> vertices){
200 Sequence<Position<String>> buffer = new LinkedSequence<Position<String>>();
201 Sequence<Position<String>> result = new LinkedSequence<Position<String>>();
202
203 // ccNumber represents the number of the current Connected Component.
204 int ccNumber = 0;
205 for(Position<String> v1 : vertices){
206 DecoratedVertex v = (DecoratedVertex) v1;
207 if(!v.isVisited()){
208 ccNumber++;
209 buffer.add(v);
210 v.setVisited(true);
211 while(! buffer.isEmpty()){
212 Position<Position<String>> pLast= buffer.last();
213 v = (DecoratedVertex)buffer.element(pLast);
214 buffer.delete(pLast);
215 result.add(v);
216 v.setConnectedComponentNumber(ccNumber);
217 for(Position<String> v2 : g.adjacentVertices(v,Direction.OUT)){
218 DecoratedVertex vv = (DecoratedVertex) v2;
219 if(vv !=null && !vv.isVisited() ){
220 vv.setVisited(true);
221 buffer.add(vv);
222 }
223 }
224 }
225 }
226
227 }
228 return result;
229 }
230
231
232 public static void reverseAllEdges(Graph<Integer,String> g){
233 for(Position<Integer> e : g.edges(Direction.DIRECTED)){
234 g.reverse(e);
235 }
236 }
237
238 /**
239 * The <code>constructDirectedGraph</code> method is used to
240 * initialize a default directed <code>Graph</code>.
241 *
242 * The returned graph contains 10 vertices and 12 directed edges.
243 *
244 * @return a <code>Graph</code> value
245 */
246 public Graph<Integer,String> constructDirectedGraph(){
247 boolean directed=true;
248 Graph<Integer,String> g =
249 new DefaultGraph<Integer,String>(new DecoratedGraphFactory(),directed);
250 Position<String> vertA = g.insertVertex("A");
251 Position<String> vertB = g.insertVertex("B");
252 Position<String> vertI = g.insertVertex("I");
253 Position<String> vertJ = g.insertVertex("J");
254 Position<String> vertC = g.insertVertex("C");
255 Position<String> vertH = g.insertVertex("H");
256 Position<String> vertD = g.insertVertex("D");
257 Position<String> vertE = g.insertVertex("E");
258 Position<String> vertF = g.insertVertex("F");
259 Position<String> vertG = g.insertVertex("G");
260
261 g.insertEdge(0,vertA,vertE);
262 g.insertEdge(0,vertE,vertD);
263 g.insertEdge(0,vertC,vertE);
264 g.insertEdge(0,vertC,vertD);
265 g.insertEdge(0,vertB,vertC);
266 g.insertEdge(0,vertB,vertA);
267 g.insertEdge(0,vertA,vertF);
268 g.insertEdge(0,vertF,vertB);
269 g.insertEdge(0,vertG,vertH);
270 g.insertEdge(0,vertH,vertI);
271 g.insertEdge(0,vertJ,vertH);
272 g.insertEdge(0,vertI,vertJ);
273
274 return g;
275 }
276
277
278 public void run(){
279 Graph<Integer,String> g = constructDirectedGraph();
280 Sequence<Position<String>> dfs = dfsTraversal(g,g.vertices());
281 System.out.println("DFS= " + dfs);
282 GraphCopier gc = new GraphCopier();
283 Graph<Integer,String> g2 = gc.copy(g);
284 System.out.println("VerticesMap="+gc.getVertices());
285 reverseAllEdges(g2);
286 //Sequence<Position<String>> dfs2 = dfsTraversal(g2,g2.vertices());
287 List<Position<String>> reverseDfs = gc.reverseList(dfs);
288 System.out.println("Reversed DFS= " + reverseDfs);
289
290 Sequence<Position<String>> dfs2 = dfsTraversal(g2,reverseDfs);
291 System.out.println("DFS2= " + dfs2);
292
293 }
294
295
296 public static void main(String[] args){
297 System.out.println("***************");
298 System.out.println("Example of use of a Directed Graphs with a decorated vertex.");
299 System.out.println("Computes for each Vertex its Strongly Connected Component (SCC-number):");
300 new GraphExample3().run();
301 System.out.println("***************");
302 System.out.println("");
303
304 }
305
306
307 }