Graphs/Java/Adjacency Map

For a more lightweight implementation, see Graphs/Java/Adjacency Map Lite

Adjacency Map Graph class implementation: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures

• The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.
• The AdjMapGraph2.java class implements a validate method, gracefully switches between the interface types IVertex/IEdge and the classes Vertex/Edge, and is a demonstration of good API implementation. Use it.

Link to code: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/

Overview

Before going through the details of the implementation, let's give an overview of the inheritance/interface/class logistics. Unfortunately, this step is a Catch-22: making a wrong decision at this step will cause lots of headaches and extra work, even for a small and simple class, but you really have to implement everything to have a good sense of how it should be done. Practice makes perfect.

Abstract Vertex and Edge Classes

We implement abstract vertex and edge classes via interfaces.

There are three interfaces defined: IGraph, IVertex, and IEdge. We'll just focus on the latter two.

• Link to IVertex: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/IVertex.java
• Link to IEdge: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/IEdge.java

These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.

Concrete Vertex and Edge Classes

Complementing this are two classes, Vertex and Edge, implemented inside of the Adjacency Map Graph class. These implement specific functionality that is neglected by the interfaces.

• Link to Vertex class: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L21
• Link to Edge class: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L59

The only catch is, any time we need to use the specific functionality of the Vertex and Edge classes implemented inside of the Adjacency Map Graph class, we need a validate() method to perform a safe cast from the generic interface type to the specific internal class type. Here is an example of such a method that converts a pointer of type IVertex (the generic interface type) to a pointer of type Vertex (the internal implementation of the Vertex class inside the Adjacency Map Graph class), and same with an IEdge to Edge validate method:

• Link to validate vertex method: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L104
• Link to validate edge method: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L118

  	@SuppressWarnings({"unchecked"})
  	private Vertex<V> validate(IVertex<V> v) {
  	  	if (!(v instanceof Vertex)) {
			throw new IllegalArgumentException("Invalid vertex");
		}

		// Safe cast:
  	  	Vertex<V> vert = (Vertex<V>) v;

		return vert;
	}

  	@SuppressWarnings({"unchecked"})
  	private Edge<E> validate(IEdge<E> e) {
  	  	if (!(e instanceof Edge)) {
			throw new IllegalArgumentException("Invalid edge");
		}

		// Safe cast:
  	  	Edge<E> edge = (Edge<E>) e;

		return edge;
	}

Implementation

Vertex Class

We alluded to the need for implementing a separate vertex interface and a concrete vertex class. Below is the concrete Vertex class. It defines the methods:

• constructor
• getElement - return the data associated with this vertex
• getIncoming - get a list of incoming edges and the vertices where they originate
• getOutgoing - get a list of outgoing edges and the vertices where they terminate

	/**
	 * Adjacency Map Vertex.
	 */
	public class Vertex<V> implements IVertex<V> {
	
		// Not storing a position pointer
		private V element;
		private boolean isDirected;
		private Map<IVertex<V>, IEdge<E>> outgoing, incoming;
	
		public Vertex(V element, boolean isDirected) { 
			this.element = element;
			outgoing = new HashMap<IVertex<V>, IEdge<E>>();
			if(isDirected) { 
				// need separate incoming and outgoing maps
				incoming = new HashMap<IVertex<V>, IEdge<E>>();
			} else {
				outgoing = new HashMap<IVertex<V>, IEdge<E>>();
			}
		}
	
		public V getElement() { 
			return element;
		}
	
		public Map<IVertex<V>,IEdge<E>> getIncoming() {
			return incoming;
		}
	
		public Map<IVertex<V>,IEdge<E>> getOutgoing() {
			return outgoing;
		}
	}

Edge Class

Below is the concrete Edge class. It defines the methods:

• constructor
• getElement - return the data associated with this edge
• getEndpoints - return a two-element list containing the vertices at the endpoints of this edge

	/**
	 * Adjacency Map Edge.
	 */
	public class Edge<E> implements IEdge<E> {
	
		// Not storing a position pointer
		private E element;
		private ArrayList<IVertex<V>> endpoints; 
	
		public Edge(IVertex<V> u, IVertex<V> v, E element) {
			this.element = element;
			endpoints = new ArrayList<IVertex<V>>();
			endpoints.add(u);
			endpoints.add(v);
		}
	
		public E getElement() {
			return element;
		}
	
		public ArrayList<IVertex<V>> getEndpoints() {
			return endpoints;
		}
	}

Adjacency Map Graph Class

The adjacency map graph implements the following methods:

• constructor (only takes an argument indicating whether the graph is directed or not)
• validate method for vertices and edges (covered above)
• insert vertex into graph method
• insert edge into graph method
• remove vertex from graph method
• remove edge from graph method
• number of edges/number of vertices methods
• get an iterable collection of vertices
• get an iterable collection of edges
• get the edge that connects two vertices
• get the two vertices at the endpoints of an edge
• get the other endpoint of an edge, given one of its endpoints
• determine the incoming/outgoing degree of a vertex
• get an iterable collection of incoming/outgoing edges to/from a vertex

And of course, a toString() method!

	/**
	 * Adjacency Map Graph class.
	 */

	private boolean isDirected;
	private LinkedList<Vertex<V>> vertexList;
	private LinkedList<Edge<E>> edgeList;

	/** Construct an empty graph. */
	public AdjMapGraph(boolean directed) {
		isDirected = directed;
		vertexList = new LinkedList<Vertex<V>>();
		edgeList = new LinkedList<Edge<E>>();
	}



	// Quite possibly the most important methods,
	// since they may save boatloads of headaches.

  	@SuppressWarnings({"unchecked"})
  	private Vertex<V> validate(IVertex<V> v) {
  	  	if (!(v instanceof Vertex)) {
			throw new IllegalArgumentException("Invalid vertex");
		}

		// Safe cast:
  	  	Vertex<V> vert = (Vertex<V>) v;

		// We COULD check if this vertex is actually in this graph...
		// naah.
  	  	return vert;
  	}

  	@SuppressWarnings({"unchecked"})
  	private Edge<E> validate(IEdge<E> e) {
		if(!(e instanceof Edge)) { 
			throw new IllegalArgumentException("Invalid edge");
		}
		// Safe cast:
		Edge<E> edge = (Edge<E>) e;

		// We COULD check if this edge is actually in this graph...
		// naah.
  	  	return edge;
	}



	// Methods to Modify Graph

	/** Create a Vertex with the given element and insert it into the graph. */
	public IVertex<V> insertVertex(V element) {
		Vertex<V> v = new Vertex<>(element, isDirected);
		vertexList.add(v);
		// Skip position.
		return (IVertex<V>) v;
	}

	/** Create an Edge with the given element between nodes u and v. */
	public IEdge<E> insertEdge(IVertex<V> u, IVertex<V> v, E element) throws IllegalArgumentException {
		if(getEdge(u,v)==null) { 
			Edge<E> e = new Edge<>(u, v, element);
			edgeList.add(e);
			Vertex<V> origin = validate(u);
			Vertex<V> dest = validate(v);
			// Skip position.
			origin.getOutgoing().put(v, e);
			dest.getOutgoing().put(u, e);
			return (IEdge<E>) e;
		} else {
			throw new IllegalArgumentException("There is already an edge between u and v!");
		}
	}

	/** Remove a Vertex from the graph, and delete all incident edges. */
	public void removeVertex(IVertex<V> vert) throws IllegalArgumentException {
		Vertex<V> v = validate(vert);
		for(IEdge<E> e : v.getOutgoing().values()) {
			removeEdge(e);
		}
		for(IEdge<E> e : v.getIncoming().values()) {
			removeEdge(e);
		}
		vertexList.remove(vertexList.indexOf(v));
	}

	/** Remove an Edge from the graph. */
	public void removeEdge(IEdge<E> edge) throws IllegalArgumentException {
		Edge<E> e = validate(edge);

		ArrayList<IVertex<V>> vertices = e.getEndpoints();

		// Remove vertices at edge endpoints from their incoming/outgoing list
		Vertex<V> v0 = validate(vertices.get(0));
		Vertex<V> v1 = validate(vertices.get(1));
		v0.getOutgoing().remove(v1);
		v1.getIncoming().remove(v0);

		// Remove edge from list of edges
		edgeList.remove(edgeList.indexOf(e));
	}



	// Vertex/Edge Utility Methods:

	/** Return number of vertices in graph. */
	public int numVertices() { 
		return vertexList.size();
	}

	/** Return number of edges in graph. */
	public int numEdges() { 
		return edgeList.size();
	}

	/** Return all vertices in graph. */
	public Iterable<Vertex<V>> vertices() { 
		return vertexList;
	}

	/** Return all edges in graph. */
	public Iterable<Edge<E>> edges() { 
		return edgeList;
	}



	// Vertices to Edges and Vice-Versa:

	/** Return edge connecting vertex u to vertex v. */
	public IEdge<E> getEdge(IVertex<V> u, IVertex<V> v) {
		Vertex<V> vxu = validate(u);
		return vxu.getOutgoing().get(v);
	}

	/** Return the vertices at the endpoints of the edge e. */
	public ArrayList<IVertex<V>> endpoints(IEdge<E> edge) { 
		Edge<E> e = validate(edge);
		return e.getEndpoints();
	}

	/** Return the vertex opposite a given vertex. */
	public IVertex<V> opposite(IVertex<V> vertex, IEdge<E> edge) throws IllegalArgumentException {
		Edge<E> e = validate(edge);
		ArrayList<IVertex<V>> endpoints = e.getEndpoints();
		if(endpoints.get(0).equals(vertex)) {
			return endpoints.get(0);
		} else if(endpoints.get(1).equals(vertex)) {
			return endpoints.get(1);
		} else {
			throw new IllegalArgumentException("The vertex you passed is not incident to the edge you passed.");
		}
	}



	// Incoming/Outoing Edges from Vertex:

	/** Return the incoming edge degree of the vertex v. */
	public int inDegree(IVertex<V> v) {
		return validate(v).getIncoming().size();
	}

	/** Return the outgoing edge degree of the vertex v. */
	public int outDegree(IVertex<V> v) {
		return validate(v).getOutgoing().size();
	}

	/** Return an iterable set of Edge objects incoming to the vertex v. */
	public Iterable<IEdge<E>> inEdges(IVertex<V> v) {
		return validate(v).getIncoming().values();
	}

	/** Return an iterable set of Edge objects outgoing from the vertex v. */
	public Iterable<IEdge<E>> outEdges(IVertex<V> v) {
		return validate(v).getOutgoing().values();
	}



	public String toString() { 
		StringBuilder sb = new StringBuilder();
		for(IVertex<V> v : vertexList) {
			sb.append("Vertex "+v.getElement()+"\n");
			if(isDirected) { 
				sb.append(" [outgoing]");
			}
			sb.append(" "+outDegree(v)+" adjacent vertices.");
			for(IEdge<E> e : outEdges(v)) {
				sb.append(String.format(" (%s,%s)", opposite(v,e).getElement(), e.getElement()));
			}
			sb.append("\n");
			if(isDirected) { 
				sb.append(" [incoming]");
				sb.append(" "+inDegree(v)+" adjacent vertices.");
				for(IEdge<E> e : inEdges(v)) {
					sb.append(String.format(" (%s,%s)", opposite(v,e).getElement(), e.getElement()));
				}
				sb.append("\n");
			}
		}

		return sb.toString();
	}

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag