[145] | 1 | /** |
---|
| 2 | * Graph Class |
---|
| 3 | */ |
---|
| 4 | |
---|
| 5 | import java.util.ArrayList; |
---|
| 6 | import java.util.Map; |
---|
| 7 | import java.util.List; |
---|
| 8 | |
---|
| 9 | public class Graph { |
---|
| 10 | |
---|
| 11 | private List<Vertex> vertices; |
---|
| 12 | private ArrayList<Edge> edges; |
---|
| 13 | |
---|
| 14 | /** |
---|
| 15 | * @param vertices |
---|
| 16 | * @param edges |
---|
| 17 | */ |
---|
| 18 | public Graph(List<Vertex> vertices, ArrayList<Edge> edges) { |
---|
| 19 | this.vertices = vertices; |
---|
| 20 | this.edges = edges; |
---|
| 21 | } |
---|
| 22 | |
---|
| 23 | /** |
---|
| 24 | * @return the vertices |
---|
| 25 | */ |
---|
| 26 | public List<Vertex> getVertices() { |
---|
| 27 | return vertices; |
---|
| 28 | } |
---|
| 29 | |
---|
| 30 | /** |
---|
| 31 | * @param vertices the vertices to set |
---|
| 32 | */ |
---|
| 33 | public void setVertices(List<Vertex> vertices) { |
---|
| 34 | this.vertices = vertices; |
---|
| 35 | } |
---|
| 36 | |
---|
| 37 | /** |
---|
| 38 | * @return the edges |
---|
| 39 | */ |
---|
| 40 | public ArrayList<Edge> getEdges() { |
---|
| 41 | return edges; |
---|
| 42 | } |
---|
| 43 | |
---|
| 44 | /** |
---|
| 45 | * @param edges the edges to set |
---|
| 46 | */ |
---|
| 47 | public void setEdges(ArrayList<Edge> edges) { |
---|
| 48 | this.edges = edges; |
---|
| 49 | } |
---|
| 50 | |
---|
| 51 | /** |
---|
| 52 | * @param v the vertex to search for |
---|
| 53 | * @param unvisitedNodes the set of all unvisited nodes |
---|
| 54 | * @return the edges which contain v |
---|
| 55 | */ |
---|
| 56 | public ArrayList<Edge> getEdgesContaining( Vertex v ) { |
---|
| 57 | ArrayList<Edge> list = new ArrayList<Edge>(); |
---|
| 58 | for( Edge e : edges ) { |
---|
| 59 | if( (e.getStart().equals( v ) || e.getEnd().equals( v )) ) |
---|
| 60 | list.add( e ); |
---|
| 61 | } |
---|
| 62 | return list; |
---|
| 63 | } |
---|
| 64 | |
---|
| 65 | /** |
---|
| 66 | * @param unvisitedNodes the map of vertices and Integer (If a node has been already seen) |
---|
| 67 | * @param distances the map of Vertices to their distances |
---|
| 68 | * @return the vertex which contains the smallest distance |
---|
| 69 | */ |
---|
| 70 | public synchronized Vertex getSmallestNode( Map<Vertex,Integer> unvisitedNodes, Map<Vertex,Integer> distances ) { |
---|
| 71 | Vertex smallest = null; |
---|
| 72 | for( Vertex v : unvisitedNodes.keySet() ) { |
---|
| 73 | if( smallest == null ) |
---|
| 74 | smallest = v; |
---|
| 75 | else { |
---|
| 76 | if( distances.get( v ) < distances.get( smallest ) && unvisitedNodes.get( v ) == null ) |
---|
| 77 | smallest = v; |
---|
| 78 | } |
---|
| 79 | } |
---|
| 80 | return smallest; |
---|
| 81 | } |
---|
| 82 | } |
---|