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(Vertex vertexA, Vertex vertexB,
75: double weight)
76: {
77: Edge edge1 = addDirectedEdge(vertexA, vertexB, weight);
78: Edge edge2 = addDirectedEdge(vertexB, vertexA, weight);
79: Edge[] result = { edge1, edge2 };
80: return result;
81: }
83: // Returns a collection of all edges in the graph
84: public Collection<Edge> getEdges()
85: {
86: HashSet<Edge> edges = new HashSet<Edge>();
87: for (ArrayList<Edge> edgeList : fromEdges.values())
88: {
89: edges.addAll(edgeList);
90: }
91: return edges;
92: }
94: // Returns the collection of edges with the specified fromVertex
95: public Collection<Edge> getEdgesFrom(Vertex fromVertex)
96: {
97: return fromEdges.get(fromVertex);
98: }
100: // Returns the collection of edges with the specified toVertex
101: public Collection<Edge> getEdgesTo(Vertex toVertex)
102: {
103: return toEdges.get(toVertex);
104: }
106: // Returns a vertex with a matching label, or null if no such vertex exists
107: public Vertex getVertex(String vertexLabel)
108: {
109: // Search the collection of vertices for a vertex with a matching label
110: for (Vertex vertex : getVertices())
111: {
112: if (vertex.label.equals(vertexLabel))
113: {
114: return vertex;
115: }
116: }
117: return null;
118: }
120: // Returns the collection of all of this graph's vertices
121: public Collection<Vertex> getVertices()
122: {
123: return fromEdges.keySet();
124: }
126: // Returns true if this graph has an edge from fromVertex to toVertex
127: public boolean hasEdge(Vertex fromVertex, Vertex toVertex)
128: {
129: if (!fromEdges.containsKey(fromVertex))
130: {
131: // fromVertex is not in this graph
132: return false;
133: }
135: // Search the list of edges for an edge that goes to toVertex
136: ArrayList<Edge> edges = fromEdges.get(fromVertex);
137: for (Edge edge : edges)
138: {
139: if (edge.toVertex == toVertex)
140: {
141: return true;
142: }
143: }
145: return false;
146: }
147: }