Graph theory problem. Quickest path through college.
#Represent Graph as Data Structure.Rather than reformat the data given to us into something that represents an adjacency list and create a protocol to parse said list, I decided to use regular expressions to generate the graph.
The data, after parsed with the regular expression "[A-Z]{2,4} [0-9]{4}", looks like this:
MATH 1390 COLLEGE ALGEBRA
MATH 1591 Calculus I (MATH 1390)
MATH 2330 Discrete Mathematics (MATH 1591 and CSCI 1470)
MATH 3320 Linear Algebra (MATH 2330)
CSCI 1470 COMPUTER SCIENCE I (MATH 1390)
MATH 1390
MATH 1591, MATH 1390
MATH 2330, MATH 1591, CSCI 1470
MATH 3320, MATH 2330
CSCI 1470, MATH 1390
In this form, the prerequisites are the second and onward elements of the first listed course.
To create a Directed Acyclic Graph from this.
- Loop through the lines, extract the first element, and add it to a list.
- Call the addPrereqs method passing in the list of courses, current course, and prerequisites for that course.
This step is very straighforward. Someone just needs to implement the DFS algorithm in C++. Since we are using the adjacency list and a struct to represent nodes, there are a couple caveats.
- The adjacency list is of type
shared_ptr<unordered_map<string, Course>>
so the method signatures should resemble
DFS(shared_ptr<unordered_map<string, Course>> graph)
and
Explore(shared_ptr<unordered_map<string, Course>> graph, Course node)
- The nodes are Course structs
struct Course
{
string Name;
shared_ptr<vector<Course>> PrereqFor;
};
To cycle through the nodes in the DFS algorithm use iterators or a for-range loop like:
//Note: you must dereference graph for this to work properly.
for (auto node : *graph)
{
}
To keep track of visits you can use another unordered_map like:
auto visited = unordered_map<string, bool>();
for (auto node : *graph)
{
//To visit.
visited[node.first] = true;
}
//To check whether visited or not
for (auto nextCourse : node.PrereqFor)
{
if (visited[nextCourse.Name])
//Visited before.
else
//Not visited before.
}
I used an
unordered_map<string, bool>
to keep track of whether or not we had visited a node.
--- #Modify DFS algorithm to get Topological OrderingsThis part is very straightforward as well. Since the last post-visit is of first intrest to us, we can use a stack to store the topological ordering.
unordered_map<string, bool> _visits;
vector<string> _topologicalOrdering;
void DFS(shared_ptr<unordered_map<string, Course>> graph)
{
for (auto node : *graph)
{
Explore(graph, node);
}
}
void Explore(shared_ptr<unordered_map<string, Course>> graph, Course node)
{
if (!_visits[node.Name])
{
_visits[node.Name] = true;
for (auto childNode : *(node.PrereqsFor))
{
Explore(graph, childNode);
//This would be the post-visit. We can add the course to our stack here.
_topologicalOrdering.push_back(childNode.Name);
}
}
}
At the end, we have a cpp vector<string>
of classes in topological order.
This part was the trickiest part and depended on your designs to the above problems.
- Cycle through the courses in topological order.
- Determine whether or not you could enroll in the course.
- If a course you were currently enrolled in was a prerequisite for a prospect course, you could not enroll.
- If a course that you could not enroll in was as prerequisite for a prospect course, you could not enroll.
- Otherwise, you were free to enroll in the course.
- Remove enrolled courses from topological order, preserving order.
- Repeat with remaining courses for the next semester.