CSC212 Graph1.java

--D. Thiebaut (talk) 18:32, 17 November 2014 (EST)

---

Graph1.java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;

/**
 * Implementation of a graph based on an Adjacency Matrix
 * The graph vertices are integers ranging from 0 to N-1.
 * 
 * @author Thiebaut
 *
 */
public class Graph1 {
	private boolean[][] adjMat;		// the adjacency matrix
	private int noVertices;			// number of vertices in graph
	private int noEdges;			// number of edges
	private boolean visited[];		// array used by various algorithms

	public Graph1(int V) {
		adjMat     = new boolean[V][V]; // allocated to false by default
		noVertices = V;
		noEdges    = 0;
	}

	public int getNoVertices() {
		return noVertices;
	}
	
	public int getNoEdges() {
		return noEdges;
	}
	
	public void addEdge(int v1, int v2) {
		if (!adjMat[v1][v2])
			noEdges++;

		adjMat[v1][v2] = true;
		adjMat[v2][v1] = true;
	}

	public boolean contains(int v1, int v2) {
		return adjMat[v1][v2];
	}

	// return list of vertices adjacent to v
	public Iterable<Integer> adj(int v) {
		return new AdjMatIterator(v);
	}

	// support iteration over graph vertices
	private class AdjMatIterator implements Iterator<Integer>,Iterable<Integer> {
		int v, w = 0;

		AdjMatIterator(int v) {
			this.v = v;
		}

		public Iterator<Integer> iterator() {
			return this;
		}

		@Override
		public boolean hasNext() {
			while (w < noVertices) {
				if (adjMat[v][w])
					return true;
				w++;
			}
			return false;
		}

		@Override
		public Integer next() {
			if (hasNext())
				return w++;
			else
				return null;
		}

		@Override
		public void remove() {
			// to be provided later...
		}
	}

	private void recurseDFS(int v) {
	     // code to be provided later...
	}

	public void DFS(int v) {
             // code to be provided later...
	}

	private static Graph1 init1() {
		/**
         * (0) --- (1) --- (2)
         *  |       | \  
         *  |       |  \
         * (3) --- (4)  (5) --- (6)
         *  |       |
         * (7) --- (8)
         * 
         */
		Graph1 G = new Graph1(9);
		G.addEdge(0, 1);		G.addEdge(1, 2);
		G.addEdge(3, 4);		G.addEdge(5, 6);
		G.addEdge(7, 8);		G.addEdge(0, 3);
		G.addEdge(1, 4);		G.addEdge(1, 5);
		G.addEdge(3, 7);		G.addEdge(4, 8);
		return G;
	}

	public static void main(String[] args) {
		Graph1 G = init1();

		System.out.print("Vertices ajacent to 1: ");
		for (int v : G.adj(1))
			System.out.print(v + " ");

	}

}