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;

/**
 * An implementation of a graph based on an adjacency matrix.
 * The graph contains N integer vertices labeled from 0 to N-1 
 * @author D. Thiebaut
 *
 */

/**
 * Exception Class for use with Graph1
 */
class NoSuchElementException extends Exception {
	public NoSuchElementException() {
	}
	public NoSuchElementException( String msg ) {
		super( msg );
	}
}

/**
 * The graph class
 */
public class Graph1 {

	private boolean[][] adjMat;          // the 2-dimensional adjacency matrix
	private int noVertices;                 // number of vertices
  	private int noEdges;                    // number of edges
	private Set<Integer> vertices;     // the vertices held in a Set
	private boolean visited[];
	private int count;
	
	public Graph1( int V ) {
		adjMat = new boolean[V][V]; // allocated to false by default
		noVertices = V;
		noEdges = 0;
		vertices = new TreeSet<Integer>();
	}
	
	public void addEdge( int v1, int v2 ) {
		vertices.add( v1 );
		vertices.add( 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 neighbors of 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() {			
		}
    }
    
    private static Graph1 init1() {
	    /**
	     * (0) --- (1) --- (2)
	     *  |       | \  
	     *  |       |  \
	     * (3) --- (4)  (5) --- (6)
	     *  |       |
	     * (7) --- (8)
	     * 
	     * @param args
	     */
		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 + " " );
		
		
	}

}