class Graph
1: //Graph.java
3: import java.util.Collection;
4: import java.util.List;
5: import java.util.ArrayList;
6: import java.util.HashMap;
7: import java.util.HashSet;
9: class Graph
10: {
11: // Maps a vertex to an ArrayList of all edges that start from that vertex
12: private HashMap<Vertex, ArrayList<Edge>> fromEdges;
14: // Maps a vertex to an ArrayList of all edges that go to that vertex
15: private HashMap<Vertex, ArrayList<Edge>> toEdges;
17: public Graph()
18: {
19: fromEdges = new HashMap<Vertex, ArrayList<Edge>>();
20: toEdges = new HashMap<Vertex, ArrayList<Edge>>();
21: }
23: public Vertex addVertex(String newVertexLabel)
24: {
25: // Create the new Vertex object
26: Vertex newVertex = new Vertex(newVertexLabel);
28: // Every vertex must exist as a key in both maps
29: fromEdges.put(newVertex, new ArrayList<Edge>());
30: toEdges.put(newVertex, new ArrayList<Edge>());
32: return newVertex;
33: }
35: public Edge addDirectedEdge
36: (
37: Vertex fromVertex,
38: Vertex toVertex
39: )
40: {
41: // Use 1.0 as the default edge weight
42: return addDirectedEdge(fromVertex, toVertex, 1.0);
43: }
45: public Edge addDirectedEdge
46: (
47: Vertex fromVertex,
48: Vertex toVertex,
49: double weight
50: )
51: {
52: // Don't add the same edge twice
53: if (hasEdge(fromVertex, toVertex))
54: {
55: return null;
56: }
58: // Create the Edge object
59: Edge newEdge = new Edge(fromVertex, toVertex, weight);
61: // Add the edge to the appropriate list in both maps
62: fromEdges.get(fromVertex).add(newEdge);
63: toEdges.get(toVertex).add(newEdge);
65: return newEdge;
66: }
68: public Edge[] addUndirectedEdge(Vertex vertexA, Vertex vertexB)
69: {
70: // Use 1.0 as the default edge weight
71: return addUndirectedEdge(vertexA, vertexB, 1.0);
72: }
74: public Edge[] addUndirectedEdge
75: (
76: Vertex vertexA,
77: Vertex vertexB,
78: double weight
79: )
80: {
81: Edge edge1 = addDirectedEdge(vertexA, vertexB, weight);
82: Edge edge2 = addDirectedEdge(vertexB, vertexA, weight);
83: Edge[] result = { edge1, edge2 };
84: return result;
85: }
87: // Returns a collection of all edges in the graph
88: public Collection<Edge> getEdges()
89: {
90: HashSet<Edge> edges = new HashSet<Edge>();
91: for (ArrayList<Edge> edgeList : fromEdges.values())
92: {
93: edges.addAll(edgeList);
94: }
95: return edges;
96: }
98: // Returns the collection of edges with the specified fromVertex
99: public Collection<Edge> getEdgesFrom(Vertex fromVertex)
100: {
101: return fromEdges.get(fromVertex);
102: }
104: // Returns the collection of edges with the specified toVertex
105: public Collection<Edge> getEdgesTo(Vertex toVertex)
106: {
107: return toEdges.get(toVertex);
108: }
110: // Returns a vertex with a matching label, or null if no such vertex exists
111: public Vertex getVertex(String vertexLabel)
112: {
113: // Search the collection of vertices for a vertex with a matching label
114: for (Vertex vertex : getVertices())
115: {
116: if (vertex.label.equals(vertexLabel))
117: {
118: return vertex;
119: }
120: }
121: return null;
122: }
124: // Returns the collection of all of this graph's vertices
125: public Collection<Vertex> getVertices()
126: {
127: return fromEdges.keySet();
128: }
130: // Returns true if this graph has an edge from fromVertex to toVertex
131: public boolean hasEdge(Vertex fromVertex, Vertex toVertex)
132: {
133: if (!fromEdges.containsKey(fromVertex))
134: {
135: // fromVertex is not in this graph
136: return false;
137: }
139: // Search the list of edges for an edge that goes to toVertex
140: ArrayList<Edge> edges = fromEdges.get(fromVertex);
141: for (Edge edge : edges)
142: {
143: if (edge.toVertex == toVertex)
144: {
145: return true;
146: }
147: }
149: return false;
150: }
151: }