Topological Algorithm
Topological Sorting Algorithm is a linear ordering technique used for directed graphs, where nodes represent tasks and edges represent dependencies between the tasks. It is mainly used to find a valid sequence of performing tasks, respecting the given dependencies. This algorithm is applicable only to Directed Acyclic Graphs (DAGs), meaning the graphs should have directed edges and no cycles. Topological sort has a wide range of applications in computer science, such as scheduling tasks with dependencies, determining the order of compilation tasks in a build system, and finding a valid sequence of courses in a curriculum with prerequisites.
The algorithm works by repeatedly selecting a node with no incoming edges, adding it to the sorted list, and then removing the node and its outgoing edges from the graph. This process continues until all the nodes are added to the sorted list, or there are no more nodes with no incoming edges, indicating the presence of a cycle in the graph. There are two common methods for implementing topological sorting: the Kahn's algorithm, which uses a queue to store the nodes with no incoming edges, and the Depth-First Search (DFS) based algorithm, which traverses the graph in a depth-first manner, marking nodes visited and adding them to the sorted list in the post-order traversal. Both algorithms have a time complexity of O(V+E), where V is the number of nodes and E is the number of edges in the graph.
package org.gs.digraph
/** Find topological order of a digraph
*
* The reverse post-order of a directed acyclic graph (DAG) is its topological order
*
* @constructor creates a new Topological with either a Digraph or EdgeWeightedDigraph
* @tparam A constrains g to classes that mixin DigraphMarker
* @param g either a Digraph or EdgeWeightedDigraph
* @see [[https://algs4.cs.princeton.edu/42directed/Topological.java.html]]
* @author Scala translation by Gary Struthers from Java by Robert Sedgewick and Kevin Wayne.
*/
class Topological[A <: DigraphMarker](g: A) {
val finder = g match {
case d: Digraph => new DirectedCycle(d)
case e: EdgeWeightedDigraph => new EdgeWeightedDirectedCycle(e)
}
private def createOrder(noCycle: Boolean): Option[List[Int]] = if (noCycle) {
val dfs = g match {
case d: Digraph => new DepthFirstOrder(d)
case e: EdgeWeightedDigraph => new EdgeWeightedDepthFirstOrder(e)
}
Some(dfs.reversePost)
} else None
private lazy val _order = createOrder(!finder.hasCycle)
/** returns if it has a topological order */
def hasOrder(): Boolean = _order != None
/** returns list of vertex numbers in topological order */
def order(): Option[List[Int]] = _order
}
