Since undirected graphs are really interesting structures I decided to practice my data structures skills by implementing it in Java. Vertices are stores in a SortedArrayList which was made in one of my course assignments. Binary search is used to find a vertex in the set, reducing the worst case runtime efficiency of adding a new vertex with a …

Graph.java

package util;

import java.util.*;
import javax.xml.crypto.*;

public class Graph<E extends Comparable<E>> {
	private SortedArrayList<Vertex<E>> vertexSet;

	public Graph() {
		this.vertexSet = new SortedArrayList<Vertex<E>>();
	}

	public void addVertex(E data, E[] adjV){
        int idx = this.contains(data);
        
        //if the vertex is not in the set 
        if(idx == -1){
            Vertex<E> v = new Vertex<E>(data); 
            this.vertexSet.add(v);
        }
        idx = this.contains(data);
        //if the vertex is in the set

		if (adjV != null) {
			for (int i = 0; i < adjV.length; i++) {
				int j = this.contains(adjV[i]);
				if (j == -1) {
					this.addVertex(adjV[i], data);
				}
				j = this.contains(adjV[i]);
				this.vertexSet.get(idx).addAdj(this.vertexSet.get(j));

			}
		}
        
        

    }

	public void addVertex(E data, E adjV) {
		int idx = this.contains(data);

		// if the vertex is not in the set
		if (idx == -1) {
			Vertex<E> v = new Vertex<E>(data);
			this.vertexSet.add(v);
		}
		idx = this.contains(data);
		
		if (adjV != null) {
			int j = this.contains(adjV);
			if (j == -1) {
				this.addVertex(adjV, data);
			}
			j = this.contains(adjV);
			this.vertexSet.get(idx).addAdj(this.vertexSet.get(j));
		}
	}

	public int contains(E data) {
		if (this.vertexSet.size() == 0) {
			return -1;
		} else {
			return this.binarySearchVertex(data, 0, this.vertexSet.size()-1);
		}
	}
	
	public int binarySearchVertex(E key, int low, int high) {
		int middle = (low + high)/2; 
		
		if(high < low) {
			return -1; 
		}
		
		if(key.equals(this.vertexSet.get(middle).getData())) {
			return middle ;
		}
		else if(key.compareTo(this.vertexSet.get(middle).getData()) < 0) {
			return binarySearchVertex(key,low,middle-1); 
		}
		else {
			return binarySearchVertex(key,middle+1,high); 
		}
		
	}

	public String toString() {
		String result = "";

		for (int i = 0; i < this.vertexSet.size(); i++) {
			result += this.vertexSet.get(i).toString() + "\n";
		}

		return result;
	}

	private class Vertex<E extends Comparable<E>> implements Comparable<Vertex<E>> {
		private E data;
		private SortedArrayList<Vertex<E>> adj;

		public Vertex(E data) {
			this.data = data;
			this.adj = new SortedArrayList<Vertex<E>>();

		}

		public void addAdj(Vertex<E> v) {
			// if the vertex is not in the adjacency list
			if (this.contains((E) v.getData()) == -1) {
				this.adj.add(v);
				v.addAdj(this);
			}
		}

		public E getData() {
			return this.data;
		}

		public int contains(E data) {
			if (this.adj.size() == 0) {
				return -1;
			} else {
				for (int i = 0; i < this.adj.size(); i++) {
					if (this.adj.get(i).getData().equals(data)) {
						return i;
					}
				}
				return -1;
			}
		}

		public String toString() {
			String result = this.data.toString() + ": [";
			for (int i = 0; i < this.adj.size(); i++) {
				result += this.adj.get(i).getData().toString() + ",";
			}
			result += "]";
			return result;
		}

		@Override
		public int compareTo(Vertex<E> o) {

			return this.data.compareTo(o.getData());
		}

	}
}

SortedArrayList.java

package util;

import java.util.Arrays;

/**
 * Sorted ArrayList implementation for the GetOutdoors project
 * 
 * @author Sam Crochet
 *
 * @param <E> Generic
 */
public class SortedArrayList<E extends Comparable<E>> implements SortedList<E> {

	/** Resizing ratio for the array list when needing to grow. */
	private static final int RESIZE = 10;
	/** inner array that holds data */
	private E[] list;
	/** field that holds the current size of the array */
	private int size;

	/**
	 * Constructor for a SortedArrayList without a size parameter and thus without a
	 * inital size
	 */
	@SuppressWarnings("unchecked")
	public SortedArrayList() {
		this.size = 0;
		this.list = (E[]) (new Comparable[RESIZE]);
	}

	/**
	 * Constructor for a new Sorted ArrayList where the parameter is the initial
	 * size;
	 * 
	 * @param value
	 *            initial size
	 */
	@SuppressWarnings("unchecked")
	public SortedArrayList(int value) {
		if (value < 0) {
			throw new IllegalArgumentException();
		}
		this.size = 0;
		this.list = (E[]) new Comparable[value];
	}

	/**
	 * Returns the number of elements in this list. If this list contains more than
	 * Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.
	 *
	 * @return the number of elements in this list
	 */
	@Override
	public int size() {
		return this.size;
	}

	/**
	 * Returns true if this list contains no elements.
	 *
	 * @return true if this list contains no elements
	 */
	@Override
	public boolean isEmpty() {
		return (this.size == 0);
	}

	/**
	 * Returns true if this list contains the specified element. More formally,
	 * returns true if and only if this list contains at least one element a such
	 * that (o==null ? a==null : o.equals(a)).
	 *
	 * @param e
	 *            element whose presence in this list is to be tested
	 * @return true if this list contains the specified element
	 */
	@Override
	public boolean contains(E e) {
		for (int i = 0; i < this.size; i++) {
			// This is what the documentation suggested but I dont really know if this works
			if (list[i] == null ? e == null : list[i].equals(e)) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Private helper method to grow the internal array
	 */
	@SuppressWarnings("unchecked")
	private void growArray() {
		E[] temp = list;
		list = (E[]) new Comparable[this.size + RESIZE];
		for (int i = 0; i <= size; i++) {
			list[i] = temp[i];
		}
	}

	/**
	 * Adds the specified element to list in sorted order
	 *
	 * Lists that support this operation may place limitations on what elements may
	 * be added to this list. In particular, some lists will refuse to add null
	 * elements, and others will impose restrictions on the type of elements that
	 * may be added. List classes should clearly specify in their documentation any
	 * restrictions on what elements may be added.
	 *
	 * @param e
	 *            element to be appended to this list
	 * @return true (as specified by Collection.add)
	 */
	@Override
	public boolean add(E e) {
		// if we are about to reach capacity
		if (this.contains(e)) {
			throw new IllegalArgumentException("Cannot add duplicate element");
		}

		if ((this.size() + 1) >= list.length) {
			this.growArray();
		}

		if (this.isEmpty()) {
			list[0] = e;
			size++;
			return true;
		}
		// case adding to the front
		if (list[0].compareTo(e) > 0) {
			for (int j = this.size(); j > 0; j--) {
				list[j] = list[j - 1];
			}
			list[0] = e;
			size++;
			return true;
		}
		// case adding to the back
		else if (list[this.size() - 1].compareTo(e) < 0) {
			list[this.size()] = e;
			size++;
			return true;
		}
		// case adding in the middle
		else {
			for (int i = 0; i < (this.size - 1); i++) {
				if (list[i].compareTo(e) < 0 && list[i + 1].compareTo(e) > 0) {
					for (int j = this.size(); j > i; j--) {
						list[j] = list[j - 1];
					}
					list[i + 1] = e;
					size++;
					return true;
				}
			}
		}
		return false;
	}

	/**
	 * Returns the element at the specified position in this list.
	 *
	 * @param index
	 *            index of the element to return
	 * @return the element at the specified position in this list
	 * @throws IndexOutOfBoundsException
	 *             if the index is out of range (index less than 0 || index grater
	 *             than or equal to size())
	 */
	@Override
	public E get(int index) {
		if (index < 0 || index >= size()) {
			throw new IndexOutOfBoundsException();
		}
		return list[index];
	}

	/**
	 * Removes the element at the specified position in this list (optional
	 * operation). Shifts any subsequent elements to the left (subtracts one from
	 * their indices). Returns the element that was removed from the list.
	 *
	 * @param index
	 *            the index of the element to be removed
	 * @return the element previously at the specified position
	 * @throws IndexOutOfBoundsException
	 *             if the index is out of range (index less than 0 || index greater than/equal to size())
	 */
	@Override
	public E remove(int index) {
		if (index < 0 || index >= size()) {
			throw new IndexOutOfBoundsException();
		}
		E temp = list[index];
		list[index] = null;
		for (int i = index; i < size - 1; i++) {
			list[i] = list[i + 1];
		}
		list[size--] = null;
		return temp;
	}

	/**
	 * Returns the index of the first occurrence of the specified element in this
	 * list, or -1 if this list does not contain the element. More formally, returns
	 * the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))), or
	 * -1 if there is no such index.
	 *
	 * @param e
	 *            element to search for
	 * @return the index of the first occurrence of the specified element in this
	 *         list, or -1 if this list does not contain the element
	 */
	@Override
	public int indexOf(E e) {
		int result = -1;
		for (int i = 0; i < this.size; i++) {
			// dont know if this actually works
			if (e == null ? get(i) == null : e.equals(get(i))) {
				return i;
			}
		}
		return result;

	}

	/**
	 * Generates a unique hash code for the SortedArrayList object
	 * 
	 * @see java.lang.Object#hashCode()
	 * @return result integer hash code
	 */
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + Arrays.hashCode(list);
		result = prime * result + size;
		return result;
	}

	/**
	 * Determines if two SortedArrayLists are equal
	 * 
	 * @see java.lang.Object#equals(java.lang.Object)
	 * @return true if the objects are equal
	 */
	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		@SuppressWarnings("unchecked")
		SortedArrayList<E> other = (SortedArrayList<E>) obj;
		if (!Arrays.equals(list, other.list))
			return false;
		if (size != other.size)
			return false;
		return true;
	}

	/**
	 * Gets the string representation of the sorted ArrayList
	 * 
	 * @see java.lang.Object#toString()
	 * @return string of the values
	 */
	@Override
	public String toString() {
		if (this.isEmpty()) {
			return "[]";
		} else {
			String result = "[";
			for (int i = 0; i < this.size - 1; i++) {
				result += list[i].toString() + ", ";
			}
			result += list[this.size - 1].toString() + "]";
			return result;
		}
	}

}