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 the collection of all of this graph's vertices
103:     public Collection<Vertex> getVertices()
104:     {
105:         return fromEdges.keySet();
106:     }

108:     // Returns true if this graph has an edge from fromVertex to toVertex
109:     public boolean hasEdge
110:     (
111:         Vertex fromVertex,
112:         Vertex toVertex
113:     )
114:     {
115:         if (!fromEdges.containsKey(fromVertex))
116:         {
117:             // fromVertex is not in this graph
118:             return false;
119:         }

121:         // Search the list of edges for an edge that goes to toVertex
122:         ArrayList<Edge> edges = fromEdges.get(fromVertex);
123:         for (Edge edge : edges)
124:         {
125:             if (edge.toVertex == toVertex)
126:             {
127:                 return true;
128:             }
129:         }

131:         return false;
132:     }
133: }