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;
8: class Graph
9: {
10: // Maps a vertex to an ArrayList of all edges that start from that vertex
11: private HashMap<Vertex, ArrayList<Edge>> fromEdges;
13: // Maps a vertex to an ArrayList of all edges that go to that vertex
14: private HashMap<Vertex, ArrayList<Edge>> toEdges;
16: public Graph()
17: {
18: fromEdges = new HashMap<Vertex, ArrayList<Edge>>();
19: toEdges = new HashMap<Vertex, ArrayList<Edge>>();
20: }
22: public Vertex addVertex(String newVertexLabel)
23: {
24: // Create the new Vertex object
25: Vertex newVertex = new Vertex(newVertexLabel);
27: // Every vertex must exist as a key in both maps
28: fromEdges.put(newVertex, new ArrayList<Edge>());
29: toEdges.put(newVertex, new ArrayList<Edge>());
31: return newVertex;
32: }
34: public Edge addDirectedEdge
35: (
36: Vertex fromVertex,
37: Vertex toVertex
38: )
39: {
40: // Use 1.0 as the default edge weight
41: return addDirectedEdge(fromVertex, toVertex, 1.0);
42: }
44: public Edge addDirectedEdge
45: (
46: Vertex fromVertex,
47: Vertex toVertex,
48: double weight
49: )
50: {
51: // Don't add the same edge twice
52: if (hasEdge(fromVertex, toVertex))
53: {
54: return null;
55: }
57: // Create the Edge object
58: Edge newEdge = new Edge(fromVertex, toVertex, weight);
60: // Add the edge to the appropriate list in both maps
61: fromEdges.get(fromVertex).add(newEdge);
62: toEdges.get(toVertex).add(newEdge);
64: return newEdge;
65: }
67: public Edge[] addUndirectedEdge
68: (
69: Vertex vertexA,
70: Vertex vertexB
71: )
72: {
73: // Use 1.0 as the default edge weight
74: return addUndirectedEdge(vertexA, vertexB, 1.0);
75: }
77: public Edge[] addUndirectedEdge
78: (
79: Vertex vertexA,
80: Vertex vertexB,
81: double weight
82: )
83: {
84: Edge edge1 = addDirectedEdge(vertexA, vertexB, weight);
85: Edge edge2 = addDirectedEdge(vertexB, vertexA, weight);
86: Edge[] result = { edge1, edge2 };
87: return result;
88: }
90: // Returns the collection of edges with the specified fromVertex
91: public Collection<Edge> getEdgesFrom(Vertex fromVertex)
92: {
93: return fromEdges.get(fromVertex);
94: }
96: // Returns the collection of edges with the specified toVertex
97: public Collection<Edge> getEdgesTo(Vertex toVertex)
98: {
99: return toEdges.get(toVertex);
100: }
102: // Returns a vertex with a matching label, or null if no such vertex exists
103: public Vertex getVertex(String vertexLabel)
104: {
105: // Search the collection of vertices for a vertex with a matching label
106: for (Vertex vertex : getVertices())
107: {
108: if (vertex.label.equals(vertexLabel))
109: {
110: return vertex;
111: }
112: }
113: return null;
114: }
116: // Returns the collection of all of this graph's vertices
117: public Collection<Vertex> getVertices()
118: {
119: return fromEdges.keySet();
120: }
122: // Returns true if this graph has an edge from fromVertex to toVertex
123: public boolean hasEdge(Vertex fromVertex, Vertex toVertex)
124: {
125: if (!fromEdges.containsKey(fromVertex))
126: {
127: // fromVertex is not in this graph
128: return false;
129: }
131: // Search the list of edges for an edge that goes to toVertex
132: ArrayList<Edge> edges = fromEdges.get(fromVertex);
133: for (Edge edge : edges)
134: {
135: if (edge.toVertex == toVertex)
136: {
137: return true;
138: }
139: }
141: return false;
142: }
143: }