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.HashSet;
022 import java.util.List;
023 import java.util.Set;
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.sequence.LinkedSequence;
031
032
033 /**
034 * The class <code>GraphExample1</code> contains one very simple
035 * example of the <code>ch.bfh.algo.Graph</code> interface.
036 *
037 * This example contains the creation of one simple graph containing 6
038 * vertices and 8 edges, which are all <code>Position</code>s in our
039 * framework.
040 *
041 * @author <a href="mailto:">Emmanuel Benoist</a>
042 * @version 1.0
043 */
044 public class GraphExample1{
045
046 /**
047 * The <code>bfsTraversal</code> is an example (very primitive) of
048 * the possible implementation of a Breadth First Search traversal
049 * of a <code>Graph</code>
050 *
051 * @return a <code>Sequence</code> value
052 */
053 public static Sequence<Position<String>> bfsTraversal(Graph<Integer,String> g){
054 Sequence<Position<String>> buffer = new LinkedSequence<Position<String>>();
055 Sequence<Position<String>> result = new LinkedSequence<Position<String>>();
056 Set<Position<String>> bufferedVertices = new HashSet<Position<String>>();
057 List<Position<String>> vertices = g.vertices();
058 for(Position<String> v : vertices){
059 if(! bufferedVertices.contains(v)){
060 buffer.add(v);
061 bufferedVertices.add(v);
062 while(! buffer.isEmpty()){
063 Position<Position<String>> pFirst= buffer.first();
064 v = buffer.element(pFirst);
065 buffer.delete(pFirst);
066 result.add(v);
067
068 for(Position<String> v2 : g.adjacentVertices(v,Direction.ALL)){
069 if(!bufferedVertices.contains(v2) && v2 !=null){
070 bufferedVertices.add(v2);
071 buffer.add(v2);
072 }
073 }
074 }
075 }
076
077 }
078 return result;
079 }
080
081 /**
082 * The <code>constructUndirectedGraph</code> method is used to
083 * initialize a default undirected <code>Graph</code>.
084 *
085 * The returned graph contains 6 vertices and 8 edges.
086 *
087 * @return a <code>Graph</code> value
088 */
089 public static Graph<Integer,String> constructUndirectedGraph(){
090 boolean directed=false;
091 Graph<Integer,String> g = new DefaultGraph<Integer,String>(directed);
092 Position<String> vertA = g.insertVertex("A");
093 Position<String> vertB = g.insertVertex("B");
094 Position<String> vertC = g.insertVertex("C");
095 Position<String> vertD = g.insertVertex("D");
096 Position<String> vertE = g.insertVertex("E");
097 Position<String> vertF = g.insertVertex("F");
098 g.insertEdge(0,vertA,vertE);
099 g.insertEdge(0,vertE,vertD);
100 g.insertEdge(0,vertC,vertE);
101 g.insertEdge(0,vertC,vertD);
102 g.insertEdge(0,vertB,vertC);
103 g.insertEdge(0,vertA,vertB);
104 g.insertEdge(0,vertA,vertF);
105 g.insertEdge(0,vertA,vertF);
106
107 return g;
108 }
109
110
111 public static void ex1(){
112 Graph<Integer,String> g = constructUndirectedGraph();
113 Sequence<Position<String>> bfs = bfsTraversal(g);
114 System.out.print("BFS= [");
115 for(Position<String> v : bfs){
116 System.out.print(v.element()+",");
117 }
118 System.out.println("]");
119
120 }
121
122
123 public static void main(String[] args){
124 System.out.println("***************");
125 System.out.println("Example of use of Graphs");
126 ex1();
127 System.out.println("***************");
128 System.out.println("");
129
130 }
131
132
133 }