CSC212 Lab 13 Solutions 2014

--D. Thiebaut (talk) 08:07, 19 November 2014 (EST)

---

Problems 1 & 2

You may want to keep the print statements in the DFS methods for Problem 1, and comment them out for Problem 2.

	private void recurseDFS(int v) {
		visited[v] = true;
		
		for (int w : adj(v))
			if (!visited[w]) {
				System.out.println( String.format( "visiting Edge (%d)---(%d)", v, w ) );
				recurseDFS(w);
			}
	}

	public void DFS(int v) {
		System.out.print( "DFS starting on " + v +":\n");
		visited = new boolean[noVertices];
		recurseDFS(v);
		System.out.println();
	}

	public boolean isConnected() {
		DFS( 0 );
		for ( int i=0; i<noVertices; i++ )
			if ( !visited[i] )
				return false;
		return true;
	}
	
	public int noConnectedComponents() {
		visited = new boolean[noVertices];
		int count = 0;
		for ( int v=0; v < noVertices; v++ ) {
			if ( ! visited[ v ] ) {
				count++;
				System.out.println( "\nComponent # " + count + " starting with Vertex " + v  );
				recurseDFS( v );
			}
		}
		System.out.println( "\n" );
		return count;
	}

Problem 3: Dot Output

       public void generateDot() {
		
		System.out.println( "graph G {" );
		for ( int i=0; i<noVertices; i++ ) {
			boolean hasEdges = false; // assume Vertex i has no edges emanating...
			for ( int j=0; j<=i; j++ ) 
				if ( adjMat[i][j] ) {
					hasEdges = true;   // Ah, Vertex i has 1 or more neighbors! 
					System.out.println( i + " -- " + j + ";" );
				}
			// if this vertex is by itself, just print its name
			// the Dot visualizer will display it as a vertex with no edges.
			if ( ! hasEdges )
				System.out.println( i +  ";" );
		}
		System.out.println( "}" );
	}

Problem 4: Kevin Bacon

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
 *
 */
class Hollywood {
	public static String[] stars = new String[] {"Naomi Watts", "Angelina Jolie", 
			"Megan Fox", "Franco Nero", "Peter Billingsley", "Jason London",
			 "Ron Jeremy", "George Pal", "Patricia Arquette", "Selena Gomez", 
			"Vincent D'Onofrio", "Matt Damon", "Jennifer Lopez", "Shia LaBeouf", 
			"Marisa Tomei", "Seth Rogen", "Robert Redford", "Jennifer Lawrence", 
			"Tom Hanks", "Justin Bieber", "James Caviezel", "Bill Murray", 
			"Charlie Sheen", "Catherine Zeta-Jones", "Kelly Lynch", "Kristen Stewart", 
			"Ben Affleck", "Jeremy Renner", "Brad Pitt", "Ashley Judd", "Jason Schwartzman", 
			"Robert De Niro", "Jude Law", "Natalya Rudakova", "Jason Bateman",
			 "Jennifer Aniston", "Johnny Depp", "Gabriel Macht", "John Malkovich", 
			"Channing Tatum", "Amanda Seyfried", "Mary-Louise Parker", "Mark Harmon",
			"Bradley Cooper", "Christina Aguilera", "Jason Statham", "Sarah Jessica Parker", 
			"Jessica Alba", "Stacey Dash", "Paige Simpson", "Will Ferrell", "Gemma Arterton", 
			"Sylvester Stallone", "Miley Cyrus", "Vince Vaughn", "Leonardo DiCaprio", 
			"Golshifteh Farahani", "Tommy Lee Jones", "Angelu DeLeon", "Philip Seymour Hoffman", 
			"George Clooney", "Justin Timberlake", "Kathleen Turner", "Martin Sheen", 
			"Nicole Kidman", "Skylar Astin", "Bruce Willis", "Scarlett Johansson", 
			"Mickey Rourke", "Roman Coppola", "Denzel Washington", "Danny Trejo", 
			"Adam Sandler", "Chris Hemsworth", "Matthew McConaughey", "Famke Janssen", 
			"Lucas Black", "Kim Kardashian", "Tom Cruise", "Eddie Murphy", 
			"Ron Howard", "Jennifer Garner", "Robert Pattinson", "Christopher Waltz", 
			"Beyonce Knowles", "Lindsay Lohan", "Jeananne Goossen", "Emily Mortimer", 
			"Jane Fonda", "Meryl Streep", "Tom Hardy", "Wesley Snipes", 
			"Sean Penn",  

			                        "Kevin Bacon", 

			"Zooey Deschanel", "Jessica Chastain", "Emma Thompson", 
			"Viola Davis", "Maksim Vitorgan", "Sarah Shahi" };
}


public class Graph1_Lab8 {
	private boolean[][] adjMat;		// the adjacency matrix
	private int[][] weight;
	private int noVertices;			// number of vertices in graph
	private int noEdges;			// number of edges
	private boolean visited[];		// array used by various algorithms

	
	
	public Graph1_Lab8(int V) {
		adjMat     = new boolean[V][V]; // allocated to false by default
		weight     = new int[V][V];     // allocated to false by default
		// make all the edges "infinity" (we use the max value possible with an int)
		for ( int i=0; i<V; i++ )
			for ( int j=0; j<V; j++ )
				weight[i][j] = 1000;
		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++;

		weight[v1][v2] = 1;  // we use 1 for weight, since we 're interested in degrees
		weight[v2][v1] = 1;  // of separation.
		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) {
		visited[v] = true;
		
		for (int w : adj(v))
			if (!visited[w]) {
				System.out.println( String.format( "visiting Edge (%d)---(%d)", v, w ) );
				recurseDFS(w);
			}
	}

	public void DFS(int v) {
		//System.out.print( "DFS starting on " + v +":\n");
		visited = new boolean[noVertices];
		recurseDFS(v);
		//System.out.println();
	}

	public boolean isConnected() {
		DFS( 0 );
		for ( int i=0; i<noVertices; i++ )
			if ( !visited[i] )
				return false;
		return true;
	}
	
	public int noConnectedComponents() {
		visited = new boolean[noVertices];
		int count = 0;
		for ( int v=0; v < noVertices; v++ ) {
			if ( ! visited[ v ] ) {
				count++;
				System.out.println( "\nComponent # " + count + " starting with Vertex " + v  );
				recurseDFS( v );
			}
		}
		System.out.println( "\n" );
		return count;
	}
	
	private static Graph1_Lab8 init1() {
		/**
         * (0) --- (1) --- (2)
         *  |       | \  
         *  |       |  \
         * (3) --- (4)  (5) --- (6)
         *  |       |
         * (7) --- (8)
         * 
         */
		Graph1_Lab8 G = new Graph1_Lab8(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;
	}

	private static Graph1_Lab8 init3() {
		Graph1_Lab8 G = new Graph1_Lab8(6);
		G.addEdge(0, 1); G.addEdge(2, 3); G.addEdge(4, 5);
		return G;
	}
	
	private static Graph1_Lab8 init2() {
		Graph1_Lab8 G = new Graph1_Lab8(100);
		 G.addEdge(0, 83); G.addEdge(1, 41); G.addEdge(1, 42);
         G.addEdge(2, 40); G.addEdge(2, 49); G.addEdge(3, 65);
         G.addEdge(3, 55); G.addEdge(4, 71); G.addEdge(4, 30);
         G.addEdge(5, 43); G.addEdge(6, 85); G.addEdge(6, 65);
         G.addEdge(7, 52); G.addEdge(7, 13); G.addEdge(8, 97);
         G.addEdge(8, 51); G.addEdge(8, 61); G.addEdge(8, 18);
         G.addEdge(11, 59); G.addEdge(12, 89); G.addEdge(13, 71);
         G.addEdge(17, 69); G.addEdge(18, 45); G.addEdge(19, 54);
         G.addEdge(21, 24); G.addEdge(21, 82); G.addEdge(22, 28);
         G.addEdge(22, 23); G.addEdge(23, 52); G.addEdge(24, 75);
         G.addEdge(24, 76); G.addEdge(25, 40); G.addEdge(26, 93);
         G.addEdge(27, 44); G.addEdge(28, 97); G.addEdge(30, 38);
         G.addEdge(33, 81); G.addEdge(39, 82); G.addEdge(39, 70);
         G.addEdge(39, 66); G.addEdge(40, 47); G.addEdge(40, 79);
         G.addEdge(40, 58); G.addEdge(40, 83); G.addEdge(41, 76);
         G.addEdge(41, 80); G.addEdge(42, 92); G.addEdge(46, 71);
         G.addEdge(47, 98); G.addEdge(48, 94); G.addEdge(48, 56);
         G.addEdge(51, 58); G.addEdge(52, 65); G.addEdge(52, 94);
         G.addEdge(55, 82); G.addEdge(58, 88); G.addEdge(59, 66);
         G.addEdge(61, 63); G.addEdge(61, 83); G.addEdge(62, 99);
         G.addEdge(62, 67); G.addEdge(67, 72); G.addEdge(69, 91);
         G.addEdge(73, 76); G.addEdge(73, 86); G.addEdge(78, 98);
         G.addEdge(80, 93); G.addEdge(85, 97); G.addEdge(92, 95);

  		 return G;
	}
	
	public void generateDot() {
		
		System.out.println( "graph G {" );
		for ( int i=0; i<noVertices; i++ ) {
			boolean hasEdges = false; // assume Vertex i has no edges emanating...
			for ( int j=0; j<=i; j++ ) 
				if ( adjMat[i][j] ) {
					hasEdges = true;   // Ah, Vertex i has 1 or more neighbors! 
					System.out.println( i + " -- " + j + ";" );
				}
			// if this vertex is by itself, just print its name
			// the Dot visualizer will display it as a vertex with no edges.
			if ( ! hasEdges )
				System.out.println( i +  ";" );
		}
		System.out.println( "}" );
	}
	
	public void WFIAlgorithm( ) {
		for ( int i = 0; i < noVertices; i++ )
			for ( int j = 0; j < noVertices; j++ )
				for ( int k = 0; k < noVertices; k++ ) 
					if (weight[j][k] > weight[j][i] + weight[i][k] ) {
						weight[j][k] = weight[j][i] + weight[i][k];
						//System.out.println( "updating weight[" + j + "][" + k + "] to " + weight[j][k] );
					}
	}
	
	public static void main(String[] args) {
		Graph1_Lab8 G = init2();
		//G.generateDot();
		//System.out.println( G.isConnected()? "G is a connected graph": "G is not a connected graph"  );
		//System.out.println("G contains " + G.noConnectedComponents() + " connected components" );
		
		// Kevin-Bacon degrees of separation
		G.WFIAlgorithm();
		int Kevin = 93;
		for ( int degree = 1; degree <= 4; degree++ ) {
			System.out.println( "Hollywood stars who have a " + degree + "-Kevin-Bacon degree:" );
			for ( int star = 0; star < G.getNoVertices(); star++ )
                                if ( G.weight[Kevin][star] == degree && star != Kevin )
					System.out.println( "  - (" + star + ") " + Hollywood.stars[star] );
		}
	}

}

Output

Hollywood stars who have a 1-Kevin-Bacon degree:
 - (26) Ben Affleck
 - (80) Ron Howard
Hollywood stars who have a 2-Kevin-Bacon degree:
 - (41) Mary-Louise Parker
Hollywood stars who have a 3-Kevin-Bacon degree:
 - (1) Angelina Jolie
 - (76) Lucas Black
Hollywood stars who have a 4-Kevin-Bacon degree:
 - (24) Kelly Lynch
 - (42) Mark Harmon
 - (73) Chris Hemsworth