import java.util.HashMap; import java.util.Map; /** * Adjancency Map implementation of the Graph interface * Edge labels are stored in nested maps: { v1 -> { v2 -> edge } } * Inspired by and loosely based on Goodrich & Tamassia * * @author Chris Bailey-Kellogg, Dartmouth CS 10, Spring 2015 * @author Tim Pierson, Dartmouth CS10, provided for Winter 2024 */ public class AdjacencyMapGraph implements Graph { protected Map> out; // from v1 to v2: { v1 -> { v2 -> edge } } protected Map> in; // to v1 from v2: { v1 -> { v2 -> edge } } /** * Default constructor, creating an empty graph */ public AdjacencyMapGraph() { in = new HashMap>(); out = new HashMap>(); } public int numVertices() { return out.keySet().size(); } public int numEdges() { // Don't actually keep an edge list around, so compute this on the fly int n = 0; for (V v : vertices()) n += outDegree(v); return n; } public Iterable vertices() { return out.keySet(); } public boolean hasVertex(V v) { return out.keySet().contains(v); } public int outDegree(V v) { return out.get(v).size(); } public int inDegree(V v) { return in.get(v).size(); } public Iterable outNeighbors(V v) { return out.get(v).keySet(); } public Iterable inNeighbors(V v) { return in.get(v).keySet(); } public boolean hasEdge(V u, V v) { return out.get(u).containsKey(v); } public E getLabel(V u, V v) { return out.get(u).get(v); } public void insertVertex(V v) { if (!out.keySet().contains(v)) { out.put(v, new HashMap()); // edges from v in.put(v, new HashMap()); // edges to v } } public void insertDirected(V u, V v, E e) { out.get(u).put(v, e); //out from u to v in.get(v).put(u, e); //reversed for in, from v to u } public void insertUndirected(V u, V v, E e) { // insert in both directions insertDirected(u, v, e); insertDirected(v, u, e); } public void removeVertex(V v) { if (!out.keySet().contains(v)) return; //remove all edges to and from v // remove all in edges to v for (V u : inNeighbors(v)) { // u has an out edge to v out.get(u).remove(v); } //remove all out edges from v for (V w : outNeighbors(v)) { // w has an in edge from v in.get(w).remove(v); } //remove node from outer map in.remove(v); out.remove(v); } public void removeDirected(V u, V v) { //remove edge from u to v in both in and out maps in.get(v).remove(u); //remove from in to v out.get(u).remove(v); //remove from out of u } public void removeUndirected(V u, V v) { // remove in both directions removeDirected(u, v); removeDirected(v, u); } /** * Returns a string representation of the vertex and edge lists. */ public String toString() { return "Vertices: " + out.keySet().toString() + "\nOut edges: " + out.toString(); } }