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