Graphs/Java/Adjacency Map

Adjacency Map Graph class implementation: https://charlesreid1.com:3000/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://charlesreid1.com:3000/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://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IVertex.java
• Link to IEdge: https://charlesreid1.com:3000/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://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L21
• Link to Edge class: https://charlesreid1.com:3000/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://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L104
• Link to validate edge method: https://charlesreid1.com:3000/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;
		}
	}

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag