Your teacher is going to give a test where each student is to answer one question. None of the neighboring students should have the same question. How many questions are needed? Graph Coloring Algorit...
Your teacher is going to give a test where each student is to answer one question. None of the neighboring students should have the same question. How many questions are needed?
Graph Coloring Algorithm is used to solve this type of problems. It does not guarantee to use the minimum number of questions, but it guarantees an upper bound on the number of questions. The algorithm never uses more than d+1 questions where d is the maximum degree of vertices in the given graph – where the degree of a vertex is the number of edges connected to the vertex.
The Basic Greedy Graph Coloring Algorithm is as follow:
- Assign first vertex with the first color.
- Do following for remaining V-1 vertices.
- Consider the currently picked vertex and color it with the lowest numbered color that has not been used on any previously colored vertices adjacent to it. If all previously used colors appear on vertices adjacent to v, assign a new color to it.
- If there are no more colors available to choose from the problem cannot be solved
Your task is to utilize the above concept to compute how many questions are needed and which question should be assigned to each student. Constructor is given a boolean matrix that indicates if a connection exists between vertexes. Based on the passed parameter the number of vertices is saved in the instance variable and an undirected graph that is represented as adjacency list is created. A vertex in the graph represents a student, an edge connects a pair of students that are neighbors.
Your program starts with the number of questions set to two and tries to find the solution where none of the neighbors have the same question. If the solution is not found one more question is added, and the process is repeated. The program stops when the solution is found and displays to the user the number of questions needed to satisfy the requirement.
class HowManyQuestions
{
private int numberOfVertices;
private LinkedList<Integer> adjacencyList[]; //graph represented as Adjacency List
/**
* Takes the input matrix and creates the graph represented as adjancency list
*
* @param graph two dimensional array of booleans, true indicates
* that the corresponding vertexes are neighbors
*/
public HowManyQuestions(boolean[][] graph)
{
//TODO Lab14b #3.1
}
/**
* Traverses the adjacencyList and displays all neighbors of each vertex
*/
public void displayNeighbors()
{
//TODO Lab14b #3.2
}
/**
* Assigns questions to all vertices and
* prints the assignment of questions
* If the solution is not possible the method throws an Exception
* with appropriate message. The possible exception is handled by this method as well
*/
public boolean greedyQuestionChooser(int numberOfQuestions)
{
boolean solved = false;
int assignedQuesions[] = new int[numberOfVertices];
// Initializes all vertices as unassigned -1
Arrays.fill(assignedQuesions, -1);
// A temporary array to store the available questions.
// Initially, all questions are not taken
boolean taken[] = new boolean[numberOfQuestions];
// Assign the first question to first vertex - first question is 0
assignedQuesions[0] = 0;
try
{
//TODO Lab14b #3.3
} catch (Exception e)
{
System.out.println(e.getMessage());
System.out.println();
}
return solved;
}
// Driver method
public static void main(String args[])
{
HashMap<String, HowManyQuestions> graphsToCheck = new HashMap<>();
graphsToCheck.put("g1",
new HowManyQuestions(new boolean[][]{
{false, true, true, false, false},
{true, false, true, true, false},
{true, true, false, true, false},
{false, true, true, false, true},
{false, false, false, true, false}}));
graphsToCheck.put("g2",
new HowManyQuestions(new boolean[][]{
{false, true, true, true, false},
{true, false, true, true, true},
{true, true, false, false, true},
{true, true, false, false, true},
{false, true, true, true, false}}));
graphsToCheck.put("g3",
new HowManyQuestions(new boolean[][]{
{false, true, true, true, false},
{true, false, true, true, true},
{true, true, false, true, false},
{true, true, true, false, true},
{false, true, false, true, false}}));
// circular
boolean[][] g4 = new boolean[24][24];
for (int i = 0; i < 24; i++)
{
g4[i][(i + 1) % 24] = true;
g4[(i + 1) % 24][i] = true;
}
graphsToCheck.put("g4", new HowManyQuestions(g4));
// SIE 1232
graphsToCheck.put("g5",
new HowManyQuestions(new boolean[][]{
{false, true, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false, false, false, false, false},
{true, false, true, false, false, false, false, false, false, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false},
{false, true, false, true, false, false, false, false, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, false, true, false, true, false, false, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, false, false, true, false, true, true, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, false, false, false, true, false, true, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false},
{false, false, false, false, true, true, false, true, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false},
{false, false, false, true, true, true, true, false, true, false, false, false, false, false, false, true, true, true, false, false, false, false, false, false},
{false, false, true, true, true, false, false, true, false, true, false, false, false, false, false, true, true, true, false, false, false, false, false, false},
{false, true, true, true, false, false, false, false, true, false, true, false, false, true, true, true, false, false, false, false, false, false, false, false},
{true, true, true, false, false, false, false, false, false, true, false, true, true, true, true, false, false, false, false, false, false, false, false, false},
{true, true, false, false, false, false, false, false, false, false, true, false, true, true, false, false, false, false, false, false, false, false, false, false},
{false, false, false, false, false, false, false, false, false, false, true, true, false, true, false, false, false, false, false, false, false, false, true, true},
{false, false, false, false, false, false, false, false, false, true, true, true, true, false, true, false, false, false, false, false, false, true, true, true},
{false, false, false, false, false, false, false, false, true, true, true, false, false, true, false, true, false, false, false, false, true, true, true, false},
{false, false, false, false, false, false, false, true, true, true, false, false, false, false, true, false, true, false, false, true, true, true, false, false},
{false, false, false, false, false, false, true, true, true, false, false, false, false, false, false, true, false, true, true, true, true, false, false, false},
{false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false, true, false, true, true, false, false, false, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, false, true, false, false, false, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, true, false, true, false, false, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, false, false, true, false, true, false, false},
{false, false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, false, false, false, false, true, false, true, false},
{false, false, false, false, false, false, false, false, false, false, false, false, true, true, true, false, false, false, false, false, false, true, false, true},
{false, false, false, false, false, false, false, false, false, false, false, false, true, true, false, false, false, false, false, false, false, false, true, false}}));
final int NUMBER_OF_GRAPHS = 5;
for (int i = 1; i <= NUMBER_OF_GRAPHS; i++)
{
System.out.println("Created graph " + i + ":");
String key = "g" + i;
graphsToCheck.get(key).displayNeighbors();
System.out.println();
}
int numberOfQuestions = 1;
boolean[] solutionFound = new boolean[NUMBER_OF_GRAPHS];
boolean done = false;
while (!done)
{
numberOfQuestions++;
System.out.println("****** Checking if " + numberOfQuestions + " questions are enough ******");
done = true;
for (int i = 1; i <= NUMBER_OF_GRAPHS; i++)
{
if (!solutionFound[i - 1])
{
System.out.println(" *** Checking graph " + i + " ***");
String key = "g" + i;
if (graphsToCheck.get(key).greedyQuestionChooser(numberOfQuestions))
solutionFound[i - 1] = true;
else
done = false;
System.out.println();
}
}
}
System.out.println("***** DONE - all graphs were assigned solutions *****");
}
}
Homework Answers
Please let me know if you have any doubts or you want me to modify
the answer. And if you find this answer useful then don't forget to
rate my answer as thumps up. Thank you! :)
import java.util.*;
class HowManyQuestions
{
private int numberOfVertices;
private LinkedList<Integer>
adjacencyList[];
public HowManyQuestions(boolean[][] graph)
{
this.numberOfVertices
= graph.length;
this.adjacencyList = new
LinkedList[this.numberOfVertices];
for (int i = 0; i <
graph.length; i++)
{
LinkedList<Integer> list = new LinkedList<>();
for (int j = 0; j < graph.length; j++)
{
if (graph[i][j])
list.add(j);
}
this.adjacencyList[i] = list;
}
}
public void displayNeighbors()
{
for (int i = 0; i <
this.adjacencyList.length; i++)
{
System.out.print("Vertex " + i + " has neighbors: ");
ListIterator<Integer> itr =
this.adjacencyList[i].listIterator();
while (itr.hasNext())
{
System.out.print(itr.next() + " ");
}
System.out.println();
}
System.out.println("==============");
}
public boolean greedyQuestionChooser(int
numberOfQuestions)
{
boolean solved =
false;
int assignedQuesions[] =
new int[numberOfVertices];
Arrays.fill(assignedQuesions, -1);
boolean taken[] = new
boolean[numberOfQuestions];
assignedQuesions[0] =
0;
try
{
for (int i = 1; i < this.numberOfVertices; i++)
{
ListIterator<Integer> itr =
this.adjacencyList[i].listIterator();
while (itr.hasNext())
{
int item = itr.next();
if (assignedQuesions[item] != -1)
taken[assignedQuesions[item]] = true;
}
int j = 0;
while (taken[j] && j < numberOfQuestions)
{
j++;
}
assignedQuesions[i] = j;
Arrays.fill(taken, false);
}
System.out.println("---> The solution exists with " +
numberOfQuestions + " questions: ");
for (int i = 0; i < this.numberOfVertices; i++)
{
System.out.println("Student : " + i + " Question " +
assignedQuesions[i]);
}
solved = true;
}
catch (Exception
e)
{
System.out.println("The solution does not exist.");
System.out.println();
}
return solved;
}
public static void main(String args[])
{
HashMap<String,
HowManyQuestions> graphsToCheck = new HashMap<>();
graphsToCheck.put("g1",
new HowManyQuestions(new boolean[][]{
{false, true, true, false, false},
{true, false, true, true, false},
{true, true, false, true, false},
{false, true, true, false, true},
{false, false, false, true, false}}));
graphsToCheck.put("g2",
new HowManyQuestions(new boolean[][]{
{false, true, true, true, false},
{true, false, true, true, true},
{true, true, false, false, true},
{true, true, false, false, true},
{false, true, true, true, false}}));
graphsToCheck.put("g3",
new HowManyQuestions(new boolean[][]{
{false, true, true, true, false},
{true, false, true, true, true},
{true, true, false, true, false},
{true, true, true, false, true},
{false, true, false, true, false}}));
boolean[][] g4 = new
boolean[24][24];
for (int i = 0; i <
24; i++)
{
g4[i][(i + 1) % 24] = true;
g4[(i + 1) % 24][i] = true;
}
graphsToCheck.put("g4",
new HowManyQuestions(g4));
graphsToCheck.put("g5",
new HowManyQuestions(new boolean[][]{
{false, true, false, false, false, false, false, false, false,
false, true, true, false, false, false, false, false, false, false,
false, false, false, false, false},
{true, false, true, false, false, false, false, false, false, true,
true, true, false, false, false, false, false, false, false, false,
false, false, false, false},
{false, true, false, true, false, false, false, false, true, true,
true, false, false, false, false, false, false, false, false,
false, false, false, false, false},
{false, false, true, false, true, false, false, true, true, true,
false, false, false, false, false, false, false, false, false,
false, false, false, false, false},
{false, false, false, true, false, true, true, true, true, false,
false, false, false, false, false, false, false, false, false,
false, false, false, false, false},
{false, false, false, false, true, false, true, true, false, false,
false, false, false, false, false, false, false, false, false,
false, false, false, false, false},
{false, false, false, false, true, true, false, true, false, false,
false, false, false, false, false, false, true, true, false, false,
false, false, false, false},
{false, false, false, true, true, true, true, false, true, false,
false, false, false, false, false, true, true, true, false, false,
false, false, false, false},
{false, false, true, true, true, false, false, true, false, true,
false, false, false, false, false, true, true, true, false, false,
false, false, false, false},
{false, true, true, true, false, false, false, false, true, false,
true, false, false, true, true, true, false, false, false, false,
false, false, false, false},
{true, true, true, false, false, false, false, false, false, true,
false, true, true, true, true, false, false, false, false, false,
false, false, false, false},
{true, true, false, false, false, false, false, false, false,
false, true, false, true, true, false, false, false, false, false,
false, false, false, false, false},
{false, false, false, false, false, false, false, false, false,
false, true, true, false, true, false, false, false, false, false,
false, false, false, true, true},
{false, false, false, false, false, false, false, false, false,
true, true, true, true, false, true, false, false, false, false,
false, false, true, true, true},
{false, false, false, false, false, false, false, false, true,
true, true, false, false, true, false, true, false, false, false,
false, true, true, true, false},
{false, false, false, false, false, false, false, true, true, true,
false, false, false, false, true, false, true, false, false, true,
true, true, false, false},
{false, false, false, false, false, false, true, true, true, false,
false, false, false, false, false, true, false, true, true, true,
true, false, false, false},
{false, false, false, false, false, false, true, true, false,
false, false, false, false, false, false, false, true, false, true,
true, false, false, false, false},
{false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, false, true, true, false,
true, false, false, false, false},
{false, false, false, false, false, false, false, false, false,
false, false, false, false, false, false, true, true, true, true,
false, true, false, false, false},
{false, false, false, false, false, false, false, false, false,
false, false, false, false, false, true, true, true, false, false,
true, false, true, false, false},
{false, false, false, false, false, false, false, false, false,
false, false, false, false, true, true, true, false, false, false,
false, true, false, true, false},
{false, false, false, false, false, false, false, false, false,
false, false, false, true, true, true, false, false, false, false,
false, false, true, false, true},
{false, false, false, false, false, false, false, false, false,
false, false, false, true, true, false, false, false, false, false,
false, false, false, true, false}}));
final int
NUMBER_OF_GRAPHS = 5;
for (int i = 1; i <=
NUMBER_OF_GRAPHS; i++)
{
System.out.println("Created graph " + i + ":");
String key = "g" + i;
graphsToCheck.get(key).displayNeighbors();
System.out.println();
}
int numberOfQuestions
= 1;
boolean[] solutionFound
= new boolean[NUMBER_OF_GRAPHS];
boolean done =
false;
while (!done)
{
numberOfQuestions++;
System.out.println("****** Checking if " + numberOfQuestions + "
questions are enough ******");
done = true;
for (int i = 1; i <= NUMBER_OF_GRAPHS; i++)
{
if (!solutionFound[i - 1])
{
System.out.println(" *** Checking graph " + i + "
***");
String key = "g" + i;
if
(graphsToCheck.get(key).greedyQuestionChooser(numberOfQuestions))
solutionFound[i - 1] = true;
else
done = false;
System.out.println();
}
}
}
System.out.println("***** DONE - all graphs were assigned solutions
*****");
}
}
![HowM L~ldeaProjects/HowManyQuestions] - ./src/HowManyQuestions.java [H Run: /Library/Java/Ja Virtuau chines/ dk 9 0 4 dk/Cont](http://img.homeworklib.com/images/921603b0-afcd-4b0e-933c-881242522342.png?x-oss-process=image/resize,w_560)
![AdeaProjects/HowManyQuestions] .src/HowManyQuestions.java HowManyQuestions src Run: Mainx Checking graph 3 o The solution doe](http://img.homeworklib.com/images/c92328e0-1221-43d0-9f09-346e7022bd5b.png?x-oss-process=image/resize,w_560)
Add Answer to:
Your teacher is going to give a test where each student is to answer one question. None of the neighboring students should have the same question. How many questions are needed? Graph Coloring Algorit...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(),...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(), valence(int vid), DFS(int start), and findPathBFS(int start, int end). I also have a JUnit test file GraphTest.java for you to check your code. Here is Graph.java: import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /* Generic vertex class */ class Vertex<T> { public T data; public boolean visited; public Vertex() { data = null; visited = false; } public Vertex(T _data) { data =...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How would you add a method to delete an edge from the graph? // Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) package algs41; import stdlib.*; import algs13.Bag; /** * The <code>Graph</code> class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex....
Hello, i need help with this homework: Code provided: public class DirectedWeightedExampleSlide18 { public static void...
Hello, i need help with this homework:
Code provided:
public class DirectedWeightedExampleSlide18
{
public static void main(String[] args)
{
int currentVertex, userChoice;
Scanner input = new Scanner(System.in);
// create graph using your WeightedGraph based on author's
Graph
WeightedGraph myGraph = new WeightedGraph(4);
// add labels
myGraph.setLabel(0,"Spot zero");
myGraph.setLabel(1,"Spot one");
myGraph.setLabel(2,"Spot two");
myGraph.setLabel(3,"Spot three");
// Add each edge (this directed Graph has 5 edges,
// so we add 5 edges)
myGraph.addEdge(0,2,9);
myGraph.addEdge(1,0,7);
myGraph.addEdge(2,3,12);
myGraph.addEdge(3,0,15);
myGraph.addEdge(3,1,6);
// let's pretend we are on...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in...
Java: Return an array of booleans in a directed graph. Please complete the TODO section in the mark(int s) function import algs13.Bag; import java.util.HashSet; // See instructions below public class MyDigraph { static class Node { private String key; private Bag<Node> adj; public Node (String key) { this.key = key; this.adj = new Bag<> (); } public String toString () { return key; } public void addEdgeTo (Node n) { adj.add (n); } public Bag<Node> adj () { return adj;...
Original question: I need a program that simulates a flower pack with the traits listed below:...
Original question: I need a program that simulates a flower pack with the traits listed below: - You must use a LinkedList for storage (not an Arrray list). - You must be able to display, add, remove, sort, filter, and analyze information from our flower pack. - The flower pack should hold flowers, weeds, fungus, and herbs. All should be a subclass of a plant class. - Each subclass shares certain qualities (ID, Name, and Color) – plant class -...
JAVA QUESTION!!! please help! The following codes are a Maze program. There are TWO traversable paths...
JAVA QUESTION!!! please help! The following codes are a Maze program. There are TWO traversable paths possible in this maze. The program uses recursion. Can someone please explain to me why the program will pick one path if multiple traversable paths are available? Why does the program choose one path over a different path? (I believe it has something to do with the recursion terminating when a solution is found but I'm not sure.) Thank you!!!! The codes: public class...
Practically dying here with this, need help ASAP, just need to do hide(), hideBoth(), and matchFound(),...
Practically dying here with this, need help ASAP, just need to do hide(), hideBoth(), and matchFound(), then implement them, so far in my version i tentatively made them, but I don't know ho to implement them so i posted the original code before i made my version of the three methods listed above. Need help fast, this is ridiculous. Implement just one requirement at a time. For example, try implementing the case where after the user clicks 2 squares, both...
I have a below codes with all details and need to answer this below question ONLY!...
I have a below codes with all details and need to answer this below question ONLY! How to explain below codes with the two properties of a Greedy algorithm - Optimal Substructure and the Greedy Property line by line? ====================== public class TeamFormation { private static ArrayList buildTeam(ArrayList team, int skill) { ArrayList newTeam = new ArrayList(); newTeam.add(skill); for (int player : team) { if (skill == (player + 1)) { newTeam.add(player); } } return newTeam; } private static boolean...
Please help me to answer the 5 programming questions and give some specific explanations, thanks a...
Please help me to answer the 5 programming questions and give
some specific explanations, thanks a lot !!!
Question Consider a class hierarchy that includes a class called Creature, with subclasses called Unicorn and Dragon. The Creature class has a method called feelsLike, Not yet answered which is overridden in the Unicorn and Dragon class. Marked out of The feelsLike method of the Creature class returns "smooth", while the feelsLike method is overridden in the Unicorn class to return "fluffy"...
**** ITS MULTI-PART QUESTION. PLEASE MAKE SURE TO ANSWER THEM ALL. SOLVE IT BY JAVA. ****...
**** ITS MULTI-PART QUESTION. PLEASE MAKE SURE TO ANSWER THEM ALL. SOLVE IT BY JAVA. **** *** ALSO MAKE SURE IT PASS THE TESTER FILE PLEASE*** Often when we are running a program, it will have a number of configuration options which tweak its behavior while it's running. Allow text completion? Collect anonymous usage data? These are all options our programs may use. We can store these options in an array and pass it to the program. In its simplest...
Hello, i need help with this homework:
Code provided:
public class DirectedWeightedExampleSlide18
{
public static void main(String[] args)
{
int currentVertex, userChoice;
Scanner input = new Scanner(System.in);
// create graph using your WeightedGraph based on author's
Graph
WeightedGraph myGraph = new WeightedGraph(4);
// add labels
myGraph.setLabel(0,"Spot zero");
myGraph.setLabel(1,"Spot one");
myGraph.setLabel(2,"Spot two");
myGraph.setLabel(3,"Spot three");
// Add each edge (this directed Graph has 5 edges,
// so we add 5 edges)
myGraph.addEdge(0,2,9);
myGraph.addEdge(1,0,7);
myGraph.addEdge(2,3,12);
myGraph.addEdge(3,0,15);
myGraph.addEdge(3,1,6);
// let's pretend we are on...
Please help me to answer the 5 programming questions and give
some specific explanations, thanks a lot !!!
Question Consider a class hierarchy that includes a class called Creature, with subclasses called Unicorn and Dragon. The Creature class has a method called feelsLike, Not yet answered which is overridden in the Unicorn and Dragon class. Marked out of The feelsLike method of the Creature class returns "smooth", while the feelsLike method is overridden in the Unicorn class to return "fluffy"...
Most questions answered within 3 hours.
-
Suppose the average male brain weight (in grams) is estimated to
be 13201320 grams. A 1905...
asked 1 minute ago -
Aqueous sulfuric acid (H2SO4) reacts with solid sodium hydroxide
(NaOH) to produce aqueous sodium sulfate (Na2SO4)...
asked 1 minute from now -
QUESTION 25:
Find the pure binary representation of the following decimal
value: You DO NOT need...
asked 2 minutes ago -
The English mathematician John Kerrich tossed a coin
10,000 times and obtained 5067 heads.
a. calculate...
asked 28 minutes ago -
13. Use the Student's t-distribution to find the t-value for
each of the given scenarios. Round...
asked 21 minutes ago -
Explain the nutrition assessment for the lower gastrointestinal
tract, including the components of client history, anthropometric...
asked 20 minutes ago -
1.Marc has tried to quit heroin seven times only to
relapse each and every time. Marc...
asked 29 minutes ago -
A process has an input as the flow q gal/min, and an
output temperature T Fahrenheit. Initially,...
asked 34 minutes ago -
A sample of 30 patients in a doctor's office showed that they
had to wait an...
asked 40 minutes ago -
Please write 6 to 10 paragraphs on the risks associated with
digging an underground hole.
Write...
asked 46 minutes ago -
The function x = (7.9 m) cos[(4πrad/s)t + π/3 rad] gives the
simple harmonic motion of...
asked 47 minutes ago -
A sample of steam with a mass of 0.501 g at a temperature of 100
∘C...
asked 1 hour ago