Directed graphs have numerous uses (travel plans, compiling, communications, planning, etc.). Several of those uses rest on the idea that Z must, at some point, follow A.
For compiling, this can mean things like dependencies (implementation An depends on interface/specification As; library L depends on components As, Bs, and Cs; etc.).
But let's look at something simpler. Suppose a student is part-time, getting a second degree, and may only take a single course at a time. This student wishes to get a rough feel for which courses would be available to take in which order.
For example, one would not try taking MATH 1P02 prior to MATH 1P01, since 1P01 is a prerequisite of 1P02. Taking COSC 2P03 must follow taking COSC 1P03, but may be before or after COSC 2P12.
Let's look at one possible subset of courses for consideration:
Of course, one wouldn't (couldn't) really take this particular selection of courses. Prerequisites have been simplified and mixed to the point where they don't actually align with any specific program on the calendar.
We can look at this as a directed acyclic graph.
• Why a graph? Because we have vertices/nodes with edges to other vertices
• Why directed? Because there's a clear progression of time
• Why acyclic? Because “you must take 1P01 both before and after 1P02” doesn't make much sense
*disclaimer: when depicting dependencies, it isn't uncommon to have the arrows drawn in the reverse direction as above (e.g. an arrow from MATH 1P02 → MATH 1P01, to show that 1P02 is dependent on 1P01). However, this version is far better suited to our needs.
So, we have a DAG. Now what?
• All we need is a listing of the courses, such that prerequisites will certainly be fulfilled, right?
◦ This is immensely easy to do by hand (for a problem size this small)
◦ We need an automated version that will always work To accomplish this, we can perform a simple topological sort.
Topological Sorts:
A topological sort of a graph is simply a listing of the vertices in such a sequence that, for every pair of vertices,
u and v, if there exists a path from u to v, then u will be listed before v in the sequence.
• That's why it has to be directed acyclic graph; you couldn't list u both before and after v
There are a few ways to solve this, but there's one super-easy method. We just need one more definition first. For an undirected graph (i.e. not what we're using here), the degree of a vertex is the number of edges connecting it.
For a directed graph, the indegree of a vertex is the number of inbound edges connecting into the vertex. So, for the graph above, MATH 1P01 has an indegree of 0, while COSC 4P75 has an indegree of 3.
For many graphs (including the one above), there are multiple potential solutions for a topological sort. Since the only risk of making the wrong choice is to accidentally select a vertex before one of its ancestors, we know that it's always safe to select a vertex with an indegree of 0.
• e.g. for my first choice, I could pick MATH 1P01, MATH 1P11, COSC 1P02, or MATH 1P67. It wouldn't matter which, since they're all safe
◦ Similarly, any of the remaining ones would be entirely safe for the second selection
◦ However, if we were to pick MATH 1P01, then MATH 1P02 would also be safe, right? Why? Once we make a selection, we've satisfied the requirements of its outbound edges, and thus reduced the prerequisite concerns for anything that depended on it.
Knowing all of this, our algorithm is pretty simple:
• Determine the indegrees of all vertices in the graph
• Pick any unvisited vertex, v, with an indegree of zero
◦ Process (in this case, print) v
◦ For each outbound edge of v, leading to vertex w, reduce the indegree of w by 1
• Repeat until either all vertices have been exhausted, or there are no remaining vertices with 0 indegree
You might notice this also provides a makeshift test for whether the graph is cyclic or acyclic. If you stop before processing all vertices, then there must have been a cycle.
For the sake of output, since you'll probably be finding out whether or not it's cyclic when you're partway through the algorithm, you might want to queue up your print statements into a stringstream (to then retrieve the .str() at the end to print).
If you go this route, don't forget to include sstream.
For testing, you've been provided with two sample files: prereqs.txt (which will work), and dangit.txt
(which is cyclic, so won't).
You can see sample executions from both on the last page. Don't forget that there are multiple possible answers, so your sort might not look like mine!
DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma
Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t
Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th
1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of
| Sun | Mon | Tue | Wed | Thu | Fri | Sat |
|---|---|---|---|---|---|---|
23 | 24 | 25 | 26 | 27 | 28 | 1 |
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 | 1 | 2 | 3 | 4 | 5 |
