Question
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
- Consider the currently picked vertex and color it with the
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 *****");
}
}
Solutions
Expert Solution
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
*****");
}
}