Mastering Machine Learning with Spark 2.x

Directed acyclic graphs

The next notion we want to discuss is that of acyclicity. A cyclic graph is one in which there is at least one vertex for which there is a path through the graph, connecting this vertex to itself. We call such a path a cycle. In an undirected graph, any chain creating a cycle will do, while in a directed graph, we only speak of cycles if we can reach the starting vertex by means of following the directed edges. For example, consider some of the graphs we have seen before. In Figure 2, there is precisely one cycle formed by {e2, e4, e5}, while in its undirected version, shown in Figure 1, there are precisely two cycles, namely {e2, e4, e5} and {e1, e2, e3}.

There are a few special cases of cyclic graphs that are worth ...