Graphs/Java/Adjacency Map

From charlesreid1

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.

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.

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.

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: 

  	@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;
	}
Retrieved from "https://charlesreid1.com/w/index.php?title=Graphs/Java/Adjacency_Map&oldid=20714"