In Java Language Part I: Finding vertices reachable by length-2 paths (2 points)
ID: 3581991 • Letter: I
Question
In Java Language
Part I: Finding vertices reachable by length-2 paths (2 points)
----------------------------------------------------------------
Fill in the body of the method UDGraph.length2Paths(). This method constructs
and returns a UDGraph with the same number of vertices as "this" UDGraph. The
new graph contains the edge (v, w) if and only if there is a path of length 2
from v to w in "this" graph--in other words, there is some vertex u such that
(v, u) and (u, w) are both edges of "this" graph.
Note that a length-2 path can start and end at the same vertex: if "this"
graph contains the edges (v, w) and (w, v), then it contains a length-2 path
from v to itself, and the new graph should contain the self-edge
(v, v). Moreover, if "this" graph contains the self-edge (v, v), then
is a length-2 path, so the new graph should contain (v, v).
If a vertex w can be reached from a vertex v by a length-1 path (one edge) in
"this" graph but _not_ by a length-2 path, the new graph should _not_ contain
(v, w).
Try to think of the fastest, simplest code for length2Paths(). It's possible
to do it with a relatively simple triply-nested loop. You will have to explain
your algorithm to your TA. If your TA thinks your algorithm is too slow,
you'll be asked to do it again.
Your solution should not change "this" graph.
Part II: Finding vertices reachable by length-k paths (2 points)
----------------------------------------------------------------
Fill in the body of the method UDGraph.paths(int length). This method creates
and returns a UDGraph with the same number of vertices as "this" UDGraph. The
new graph contains the edge (v, w) if and only if there is a path of length
"length" (the parameter) from v to w in "this" graph. Your method should work
for any "length" of 2 or greater.
Note that a length-k path is permitted to use an edge multiple times. For
example, is a valid length-5 path.
Hint: First calculate all the paths of length (k - 1). Once you know these,
it's straightforward to compute all the paths of length k in a manner similar
to what you did for Part I.
There is code in UDGraph.main() for both Parts I and II.
Code for copying here:
/* UDGraph.java */
import java.io.*;
import java.util.*;
/**
* The UDGraph class represents an unweighted directed graph.
* Implemented with an adjacency matrix.
*/
public class UDGraph
{
/**
* adjMatrix references the adjacency matrix of the graph.
* vertices is the number of vertices in the graph.
* edges is the number of edges in the graph.
*
* DO NOT CHANGE THE FOLLOWING FIELD DECLARATIONS.
*/
private boolean[][] adjMatrix;
private int vertices;
private int edges;
/**
* Constructs a graph with n vertices and no edges.
*/
public UDGraph(int n) {
vertices = n;
edges = 0;
adjMatrix = new boolean[n][n];
for (int i = 0; i < vertices; i++ ) {
for (int j = 0; j < vertices; j++ ) {
adjMatrix[i][j] = false;
}
}
}
/**
* Returns the number of vertices.
* @return this graph's vertex count.
*/
public int getNumVertices() {
return vertices;
}
/**
* Returns the number of edges.
* @return this graph's edge count.
*/
public int getNumEdges() {
return edges;
}
/**
* Returns true if v is a valid vertex number; false otherwise.
* @param v the vertex.
* @return boolean indicating existence of vertex number v.
*/
public boolean validVertex(int v) {
return (v >= 0) && (v < vertices);
}
/**
* Returns true if edge (origin, destination) exists; false otherwise.
* @param origin the origin vertex.
* @param destination the destination vertex.
* @return boolean indicating the presence of edge (origin, destination).
*/
public boolean hasEdge(int origin, int destination) {
if (validVertex(origin) && validVertex(destination)) {
return adjMatrix[origin][destination];
} else {
return false;
}
}
/**
* Creates the edge (origin, destination). If the edge did not already
* exists, increments the edge count.
* @param origin the origin vertex.
* @param edstination the destination vertex.
*/
public void addEdge(int origin, int destination) {
if (validVertex(origin) && validVertex(destination)) {
if (!adjMatrix[origin][destination]) {
adjMatrix[origin][destination] = true;
edges++;
}
}
}
/**
* Deletes the edge (origin, destination). If the edge existed, decrements
* the edge count.
* @param origin the origin vertex.
* @param destination the destination vertex.
*/
public void removeEdge(int origin, int destination) {
if (validVertex(origin) && validVertex(destination)) {
if (adjMatrix[origin][destination]) {
adjMatrix[origin][destination] = false;
edges--;
}
}
}
/**
* Returns a new UDGraph with the same vertices as "this" UDGraph.
* The new graph has an edge (v, w) if and only if there is a path of
* length 2 from v to w in "this" graph.
* *** DO NOT CHANGE "this" GRAPH!!! ***
* @return the new UDGraph.
*/
public UDGraph length2Paths() {
UDGraph newGraph = new UDGraph(vertices);
// Put your answer to Part I here.
return newGraph;
}
/**
* Returns a new UDGraph with the same vertices as "this" UDGraph.
* The new graph has an edge (v, w) if and only if there is a path of
* length "length" from v to w in "this" graph.
* @param length the length of paths used to construct the new graph.
* @return the new UDGraph.
*/
public UDGraph paths(int length) {
UDGraph newGraph = new UDGraph(vertices);
// Put your answer to Part II here.
return newGraph;
}
/**
* Returns a String representing the adjacency matrix, including the number
* of vertices and edges.
* @return a String representing the adjacency matrix.
*/
public String toString() {
int i, j;
String s = vertices + " vertices and " + edges + " edges ";
for (i = 0; i < vertices; i++) {
for (j = 0; j < vertices - 1; j++) {
s = s + (adjMatrix[i][j] ? "t" : ".") + " ";
}
s = s + (adjMatrix[i][j] ? "t" : ".") + " ";
}
return s;
}
public static void main(String[] args) {
System.out.println(" *** Square the unweighted directed graph! *** ");
// Create an 11-vertex graph.
System.out.println("Creating a graph with 11 vertices");
UDGraph graph = new UDGraph(11);
graph.addEdge(0, 8);
graph.addEdge(1, 0);
graph.addEdge(1, 3);
graph.addEdge(2, 0);
graph.addEdge(3, 2);
graph.addEdge(3, 5);
graph.addEdge(4, 2);
graph.addEdge(4, 5);
graph.addEdge(5, 7);
graph.addEdge(5, 9);
graph.addEdge(6, 4);
graph.addEdge(6, 7);
graph.addEdge(8, 4);
graph.addEdge(8, 6);
graph.addEdge(8, 10);
graph.addEdge(9, 1);
graph.addEdge(10, 6);
boolean goodJob = true;
String t1String = "11 vertices and 17 edges . . . . . . . . t . . " +
"t . . t . . . . . . . t . . . . . . . . . . . . t . . t . . . . . " +
". . t . . t . . . . . . . . . . . . t . t . . . . . t . . t . . . " +
". . . . . . . . . . . . . . . t . t . . . t . t . . . . . . . . . " +
". . . . . . t . . . . ";
System.out.println(" The original graph is " + graph);
if (!t1String.equals(graph.toString())) {
System.out.println("Error: the original graph should be " +
t1String);
goodJob = false;
}
// Do length-2 paths work?
String t2String = "11 vertices and 25 edges . . . . t . t . . . t " +
". . t . . t . . t . . . . . . . . . . t . . t . . . . . . t . t . " +
"t . . . . . . t . t . . t . . . . . . . . . . . t . . t . . . . . " +
". . . . . . . . . . . . . t . t t t t . . . t . . t . . . . . . . " +
". . . . t . . t . . . ";
System.out.println("Testing length-2 paths.");
System.out.println("The graph of length-2 paths is " +
graph.length2Paths());
if (!t2String.equals(graph.length2Paths().toString())) {
System.out.println("Error: the length-2 path graph should be " +
t2String);
goodJob = false;
}
// Do length-3 paths work?
String t3String = "11 vertices and 34 edges . . t . t t t t . . . " +
"t . . . t . t t . t t . . . . t . t . . . t . t . . . . . . t . . " +
". t . . . . . . t . . t . . t . . . . . . . t . . . . . . t . t . " +
". . . . . . . . . . . t . t . t t . t . t . . . t . . t . . t . . " +
". . t . . t . . . . . ";
System.out.println("Testing length-3 paths.");
System.out.println("The graph of length-3 paths is " +
graph.paths(3));
if (!t3String.equals(graph.paths(3).toString())) {
System.out.println("Error: the length-3 path graph should be " +
t3String);
goodJob = false;
}
// Do length-4 paths work?
String t4String = "11 vertices and 49 edges t . t . t t . t . t . " +
". t t . t t t t t . . . . t . t t t t . . . t . . t t . t . . . t " +
"t . . t t . t . . . t . . t . . t . . t . . . t . . . . . . t . . " +
". . . . . . . . . . . t t t . . t . t t t . t . . . t . t t . t t " +
"t . . . . . . t . t . ";
System.out.println("Testing length-4 paths.");
System.out.println("The graph of length-4 paths is " +
graph.paths(4));
if (!t4String.equals(graph.paths(4).toString())) {
System.out.println("Error: the length-4 path graph should be " +
t4String);
goodJob = false;
}
// Do length-5 paths work?
String t5String = "11 vertices and 63 edges t t t . . t . t t t . " +
"t . t t t t t t . t t t . t . t t . t . t . . . t . t t t t t . . " +
". . t . t t t t t . . t . . . t . t t . t t t . . t t . t . . . t " +
". . . . . . . . . . . t t . t t . t t t t t . t t . t t t t t . . " +
". t . . . . . . t . . ";
System.out.println("Testing length-5 paths.");
System.out.println("The graph of length-5 paths is " +
graph.paths(5));
if (!t5String.equals(graph.paths(5).toString())) {
System.out.println("Error: the length-5 path graph should be " +
t5String);
goodJob = false;
}
if (goodJob) {
System.out.println(" *** Good Job! *** ");
}
}
}
Explanation / Answer
Part 1:
// Java program to check if there is exist a path between two vertices
// of a graph.
import java.io.*;
import java.util.*;
import java.util.LinkedList;
// This class represents a directed graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
//prints BFS traversal from a given source s
Boolean isReachable(int s, int d)
{
LinkedList<Integer>temp;
// Mark all the vertices as not visited(By default set
// as false)
boolean visited[] = new boolean[V];
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);
// 'i' will be used to get all adjacent vertices of a vertex
Iterator<Integer> i;
while (queue.size()!=0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
int n;
i = adj[s].listIterator();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
while (i.hasNext())
{
n = i.next();
// If this adjacent node is the destination node,
// then return true
if (n==d)
return true;
// Else, continue to do BFS
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
// If BFS is complete without visited d
return false;
}
// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
int u = 1;
int v = 3;
if (g.isReachable(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);;
u = 3;
v = 1;
if (g.isReachable(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);;
}
}
Part 2:
// Java program to count walks from u to v with exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class KPaths
{
static final int V = 4; //Number of vertices
// A naive recursive function to count walks from u
// to v with k edges
int countwalks(int graph[][], int u, int v, int k)
{
// Base cases
if (k == 0 && u == v) return 1;
if (k == 1 && graph[u][v] == 1) return 1;
if (k <= 0) return 0;
// Initialize result
int count = 0;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
if (graph[u][i] == 1) // Check if is adjacent of u
count += countwalks(graph, i, v, k-1);
return count;
}
// Driver method
public static void main (String[] args) throws java.lang.Exception
{
/* Let us create the graph shown in above diagram*/
int graph[][] =new int[][] { {0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
int u = 0, v = 3, k = 2;
KPaths p = new KPaths();
System.out.println(p.countwalks(graph, u, v, k));
}
}
// Java program to check if there is exist a path between two vertices
// of a graph.
import java.io.*;
import java.util.*;
import java.util.LinkedList;
// This class represents a directed graph using adjacency list
// representation
class Graph
{
private int V; // No. of vertices
private LinkedList<Integer> adj[]; //Adjacency List
//Constructor
Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList();
}
//Function to add an edge into the graph
void addEdge(int v,int w) { adj[v].add(w); }
//prints BFS traversal from a given source s
Boolean isReachable(int s, int d)
{
LinkedList<Integer>temp;
// Mark all the vertices as not visited(By default set
// as false)
boolean visited[] = new boolean[V];
// Create a queue for BFS
LinkedList<Integer> queue = new LinkedList<Integer>();
// Mark the current node as visited and enqueue it
visited[s]=true;
queue.add(s);
// 'i' will be used to get all adjacent vertices of a vertex
Iterator<Integer> i;
while (queue.size()!=0)
{
// Dequeue a vertex from queue and print it
s = queue.poll();
int n;
i = adj[s].listIterator();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it
// visited and enqueue it
while (i.hasNext())
{
n = i.next();
// If this adjacent node is the destination node,
// then return true
if (n==d)
return true;
// Else, continue to do BFS
if (!visited[n])
{
visited[n] = true;
queue.add(n);
}
}
}
// If BFS is complete without visited d
return false;
}
// Driver method
public static void main(String args[])
{
// Create a graph given in the above diagram
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
int u = 1;
int v = 3;
if (g.isReachable(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);;
u = 3;
v = 1;
if (g.isReachable(u, v))
System.out.println("There is a path from " + u +" to " + v);
else
System.out.println("There is no path from " + u +" to " + v);;
}
}
Part 2:
// Java program to count walks from u to v with exactly k edges
import java.util.*;
import java.lang.*;
import java.io.*;
class KPaths
{
static final int V = 4; //Number of vertices
// A naive recursive function to count walks from u
// to v with k edges
int countwalks(int graph[][], int u, int v, int k)
{
// Base cases
if (k == 0 && u == v) return 1;
if (k == 1 && graph[u][v] == 1) return 1;
if (k <= 0) return 0;
// Initialize result
int count = 0;
// Go to all adjacents of u and recur
for (int i = 0; i < V; i++)
if (graph[u][i] == 1) // Check if is adjacent of u
count += countwalks(graph, i, v, k-1);
return count;
}
// Driver method
public static void main (String[] args) throws java.lang.Exception
{
/* Let us create the graph shown in above diagram*/
int graph[][] =new int[][] { {0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
int u = 0, v = 3, k = 2;
KPaths p = new KPaths();
System.out.println(p.countwalks(graph, u, v, k));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.