import lib280.graph.Edge280; import lib280.graph.GraphMatrixRep280; import lib28
ID: 3731628 • Letter: I
Question
import lib280.graph.Edge280;
import lib280.graph.GraphMatrixRep280;
import lib280.list.LinkedList280;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class QuestProgression {
// File format for quest data:
// First line: Number of quests N
// Next N lines consist of the following items, separated by commas:
// quest ID, quest name, quest area, quest XP
// (Quest ID's must be between 1 and N, but the line for each quest IDs may appear in any order).
// Remaining lines consist of a comma separated pair of id's i and j where i and j are quest IDs indicating
// that quest i must be done before quest j (i.e. that (i,j) is an edge in the quest graph).
/**
* Read the quest data from a text file and build a graph of quest prerequisites.
* @param filename Filename from which to read quest data.
* @return A graph representing quest prerequisites. If quest with id i must be done before a quest with id j, then there is an edge in the graph from vertex i to vertex j.
*/
public static GraphMatrixRep280<QuestVertex, Edge280<QuestVertex>> readQuestFile(String filename) {
Scanner infile;
// Attempt to open the input filename.
try {
infile = new Scanner(new File(filename));
} catch (FileNotFoundException e) {
System.out.println("Error: Unable to open" + filename);
e.printStackTrace();
return null;
}
// Set the delimiters for parsing to commas, and vertical whitespace.
infile.useDelimiter("[,\v]");
// Read the number of quests for which there is data.
int numQuests = infile.nextInt();
// read the quest data for each quest.
LinkedList280<Quest> questList = new LinkedList280<Quest>();
for(int i=0; i < numQuests; i++) {
int qId = infile.nextInt();
String qName = infile.next();
String qArea = infile.next();
int qXp = infile.nextInt();
questList.insertLast(new Quest(qId, qName, qArea, qXp));
}
// Make a graph with the vertices we created from the quest data.
GraphMatrixRep280<QuestVertex, Edge280<QuestVertex>> questGraph =
new GraphMatrixRep280<QuestVertex, Edge280<QuestVertex>> (numQuests, true, "QuestVertex", "lib280.graph.Edge280");
// Add enough vertices for all of our quests.
questGraph.ensureVertices(numQuests);
// Store each quest in a different vertex. The quest with id i gets stored vertex i.
questList.goFirst();
while(questList.itemExists()) {
questGraph.vertex(questList.item().id()).setQuest(questList.item());
questList.goForth();
}
// Continue reading the input file for the quest prerequisite informaion and add an edge to the graph
// for each prerequisite.
while(infile.hasNext()) {
questGraph.addEdge(infile.nextInt(), infile.nextInt());
}
infile.close();
return questGraph;
}
/**
* Test whether vertex v has incoming edges or not
* @param G A graph.
* @param v The integer identifier of a node in G (corresponds to quest ID)
* @return Returns true if v has no incoming edges. False otherwise.
*/
public static boolean hasNoIncomingEdges(GraphMatrixRep280<QuestVertex,Edge280<QuestVertex>> G, int v) {
// TODO Write this method
return false; // replace this with your own return statement -- this is just a placeholder to prevent compiler errors.
}
/**
* Perform a topological sort of the quests in the quest prerequisite graph G, with priority given
* to the highest experience value among the available quests.
* @param G The graph on which to perform a topological sort.
* @return A list of quests that is the result of the topological sort, that is, the order in which the quests should be done if we always pick the available quest with the largest XP reward first.
*/
public static LinkedList280<Quest> questProgression(GraphMatrixRep280<QuestVertex,Edge280<QuestVertex>> G) {
// TODO Write this method
return null; // Replace this with your own return statement -- this is jsut a placeholder to prevent compiler errors.
}
public static void main(String args[]) {
// Read the quest data and construct the graph.
// If you get an error reading the file here and you're using Eclipse,
// remove the 'QuestPrerequisites-Template/' portion of the filename.
GraphMatrixRep280<QuestVertex,Edge280<QuestVertex>> questGraph = readQuestFile("QuestPrerequisites-Template/quests16.txt");
// Perform a topological sort on the graph.
LinkedList280<Quest> questListForMaxXp = questProgression(questGraph);
// Display the quests to be completed in the order determined by the topologial sort.
questListForMaxXp.goFirst();
while(questListForMaxXp.itemExists()) {
System.out.println(questListForMaxXp.item());
questListForMaxXp.goForth();
}
}
}
In this question we wi1ll once again be looking at à problem related to quests in Video games. In many roleplaying video games, one completes quests to gain experience points. When one's charater gains enough experience points, their character advances and grows in power, or gains new abilities. Very often there are quests that can only be attempted after one or more prerequisite quests have been completed. We can represent this as a quest prerequisite graph, much like the course prerequisite graph in Section 2.1, in which each quest is represented by a node, and there is a directed edge from node A to node B if node A's quest is a prerequisite to node B's quest. In this question you will work with just such a graph, and implement a topological sort algorithm that will output an ordering in which all of the quests in the graph can be completed. We can perform the topological sort of the graph using the following algorithm: Algorithm TopologicalSort (G) G is a directed graph L = Empty list that will contain the result of the topological sort S = set of nodes in G with no incoming edges (i.e. indegree 0) while S is non- empty do remove a node n from S add n to the end of the list L for each node m with an edge e from n tom do remove edge e from the graph if m now has no incoming edges (i.e. indegree 0) then insert minto S if the graph has any edges in it then throw exception (the graph had at least one cycle!!!) else return L (a topologically sorted order)Explanation / Answer
Here I am posting two methods which you required to implemented. Do let me know if you have any doubts about it. Thank you.
public static boolean hasNoIncomingEdges(GraphMatrixRep280<QuestVertex,Edge280<QuestVertex>> G, int v) {
boolean result = true;
G.goFirst();
while(!G.after()) {
if(G.isAdjacent(G.itemIndex(),v)) {
result = false;
}
G.goForth();
}
return result;
}
public static LinkedList280<Quest> questProgression(GraphMatrixRep280<QuestVertex,Edge280<QuestVertex>> G) {
LinkedList280<Quest> sortedList = new LinkedList280<>();
ArrayedHeap280<Quest> questHeap = new ArrayedHeap280<Quest>(G.numVertices());
//iterate G to build a quest heap of quests with no prerequisites.
for(int i = 1; i < G.numVertices() + 1; i++) {
if(hasNoIncomingEdges(G,i)) {
questHeap.insert(G.vertex(i).quest());
}
}
// TopologicalSort Algorithm
while(!questHeap.isEmpty()) {
Quest n = questHeap.item();
questHeap.deleteItem();
// add quest n to the end of list
sortedList.insertLast(n);
for(int i = 1; i < G.numVertices() + 1; i++) {
if(G.isAdjacent(n.id(), i)) {
// find the corresponding edge item
G.eSearch(G.vertex(n.id),G.vertex(i));
// remove the edge
G.deleteEItem();
if(hasNoIncomingEdges(G,i)) {
questHeap.insert(G.vertex(i).quest());
}
}
}
}
// the graph should now have no edges throw an except if it does.
if(G.numEdges() == 0) {
return sortedList;
} else {
throw new Exception280("the graph had at least one cycle!!!");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.