CSC212 Lab 13 Solutions 2014

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

---

Some solution programs for Lab 13.

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

Source

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

Problem #5

import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
/**
 * Code taken from http://www.algolist.com/code/java/Dijkstra's_algorithm
 */

/**
 * Implementation of a Vertex object.
 * Each vertex has a unique Id.  The first vertex created
 * has an Id of 0. 
 * Each vertex contains a list of edges that emanate from it.
 */
class Vertex implements Comparable<Vertex> {
	public final int Id;
	public Edge[] adj;    // adjacency list for vertex
	public double minDistance = Double.POSITIVE_INFINITY;
	public Vertex predecessor;

	public Vertex(int i) {	Id = i;	}
	public String toString() {	return Id + " "; }
	public int compareTo(Vertex other) {
		return Double.compare(minDistance, other.minDistance);
	}
}

/**
 * Implementation of an edge.  An edge is directed and goes from
 * source vertex to dest vertex.  It has a real weight.
 */
class Edge {
	public final Vertex source;
	public final Vertex dest;
	public final double weight;

	public Edge(Vertex argSource, Vertex argTarget, double argWeight) {
		source = argSource;
		dest   = argTarget;
		weight = argWeight;
	}
}

/**
 * The graph class. 
 * The graph is simply implemented as an array of vertices.  The connections
 * between vertices are held in adjacency lists in the vertices.
 *
 */
public class Graph2 {
	Vertex[] vertices;
	boolean[] visited;
	
	/**
	 * constructor.  The graph must be initialized by adding vertices 
	 * and their adjacency list to the Vertex[] vertices.
	 */
	Graph2() {
		vertices = null;
	}

	/**
	 * Find the shortest path from source to the other reachable nodes.
	 * @param source
	 */
	public static void dijkstraPaths(Vertex source) {
		source.minDistance = 0.;
		PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
		vertexQueue.add(source);

		while (!vertexQueue.isEmpty()) {
			Vertex u = vertexQueue.poll();

			// Visit each edge emanating from u
			for (Edge e : u.adj) {
				Vertex v = e.dest;
				double weight = e.weight;
				double distanceThroughU = u.minDistance + weight;
				if (distanceThroughU < v.minDistance) {
					vertexQueue.remove(v);
					v.minDistance = distanceThroughU;
					v.predecessor = u;
					vertexQueue.add(v);
				}
			}
		}
	}

	/**
	 * Return an ArrayList of vertices that go from source (see Dijkstra)
	 * to target.
	 * @param target the destination of the path.
	 * @return an arraylist of vertices
	 */
	public static List<Vertex> getShortestPathTo(Vertex target) {
		List<Vertex> path = new ArrayList<Vertex>();
		for (Vertex vertex = target; vertex != null; vertex = vertex.predecessor)
			path.add(vertex);
		Collections.reverse(path);
		return path;
	}

	/**
	 * generates a graph with 5 vertices
	 * @return array of vertices
	 */
	private static Vertex[] generateSampleGraph1() {
		Vertex v0 = new Vertex(0);
		Vertex v1 = new Vertex(1);
		Vertex v2 = new Vertex(2);
		Vertex v3 = new Vertex(3);
		Vertex v4 = new Vertex(4);

		v0.adj = new Edge[] { new Edge(v0, v1, 5), new Edge(v0, v2, 10),
				new Edge(v0, v3, 8) };
		v1.adj = new Edge[] { new Edge(v1, v0, 5), new Edge(v1, v2, 3),
				new Edge(v1, v4, 7) };
		v2.adj = new Edge[] { new Edge(v2, v0, 10), new Edge(v2, v1, 3) };
		v3.adj = new Edge[] { new Edge(v3, v0, 8), new Edge(v3, v4, 2) };
		v4.adj = new Edge[] { new Edge(v4, v1, 7), new Edge(v4, v3, 2) };

		return new Vertex[] { v0, v1, v2, v3, v4 };
	}

	/**
	 * generates a graph with 7 vertices
	 * @return array of vertices
	 */
	private static Vertex[] generateSampleGraph2() {
		Vertex v0 = new Vertex(0);
		Vertex v1 = new Vertex(1);
		Vertex v2 = new Vertex(2);
		Vertex v3 = new Vertex(3);
		Vertex v4 = new Vertex(4);
		Vertex v5 = new Vertex(5);
		Vertex v6 = new Vertex(6);

		v0.adj = new Edge[] { new Edge(v0, v3, 1), new Edge(v0, v6, 1) };
		v1.adj = new Edge[] { new Edge(v1, v5, 5), new Edge(v1, v2, 1),
				new Edge(v1, v4, 3) };
		v2.adj = new Edge[] { new Edge(v2, v1, 1), new Edge(v2, v4, 2),
				new Edge(v2, v6, 5) };
		v3.adj = new Edge[] { new Edge(v3, v0, 1), new Edge(v3, v4, 9) };
		v4.adj = new Edge[] { new Edge(v4, v1, 3), new Edge(v4, v2, 2),
				new Edge(v4, v6, 2), new Edge(v2, v3, 9) };
		v5.adj = new Edge[] { new Edge(v5, v1, 5) };
		v6.adj = new Edge[] { new Edge(v6, v2, 5), new Edge(v6, v4, 2),
				new Edge(v6, v0, 1) };

		return new Vertex[] { v0, v1, v2, v3, v4, v5, v6 };
	}

	/**
	 * displays the shortest paths found from the start vertex to ALL
	 * reachable vertices.
	 * @param start
	 */
	public void displayShortestPaths(Vertex start) {
		dijkstraPaths(start);
		for (Vertex v : vertices) {
			System.out.println("Distance to " + v + ": " + v.minDistance);
			List<Vertex> path = getShortestPathTo(v);
			System.out.println("Path: " + path);
		}
	}

	/**
	 * generate the dot version of the digraph.
	 */
	private void dot() {
		System.out.println("digraph G {");
		for (Vertex v : vertices) {
			Edge[] adj = v.adj;
			if ( adj.length == 0 )
				System.out.println( v + ";" );
			else 
				for (Edge e : adj) {
					int source = e.source.Id;
					int dest = e.dest.Id;
					double weight = e.weight;
					System.out.println(String.format("%d -> %d [label=\"%1.0f\"];",
						source, dest, weight));
				}
		}
		System.out.println("}");
	}

	private void recurseDFS( Vertex v ) {
		visited[ v.Id ] = true;
		System.out.print( v );
		for ( Edge e: v.adj ) {
			Vertex u = e.dest;
			if ( ! visited[u.Id ] ) 
				recurseDFS( u );
		}
	}
	
	public void DFS( int vertexId ) {
		Vertex v = vertices[ vertexId ];
		visited = new boolean[ vertices.length ];
		System.out.print( "DFS starting on " + vertexId + ": visiting " );
		recurseDFS( v );
		System.out.println();
	}
	
	public static void main(String[] args) {
		Graph2 G = new Graph2();
		G.vertices = generateSampleGraph2();
		// G.displayShortestPaths( G.vertices[5] );
		G.dot();
		G.DFS( 0 ); // explore in DFS mode starting at Vertex 0
		G.DFS( 6 ); // explore in DFS mode starting at Vertex 6
	}
}

Output

digraph G {
0 -> 3 [label="1"];
0 -> 6 [label="1"];
1 -> 5 [label="5"];
1 -> 2 [label="1"];
1 -> 4 [label="3"];
2 -> 1 [label="1"];
2 -> 4 [label="2"];
2 -> 6 [label="5"];
3 -> 0 [label="1"];
3 -> 4 [label="9"];
4 -> 1 [label="3"];
4 -> 2 [label="2"];
4 -> 6 [label="2"];
2 -> 3 [label="9"];
5 -> 1 [label="5"];
6 -> 2 [label="5"];
6 -> 4 [label="2"];
6 -> 0 [label="1"];
}
DFS starting on 0: visiting 0 3 4 1 5 2 6 
DFS starting on 6: visiting 6 2 1 5 4 3 0