Source of Graph.java

Structures and functions

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
124:     (
125:         Vertex fromVertex,
126:         Vertex toVertex
127:     )
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: }