class Craph::DAG(T)

Overview

Directed Acyclic Graph, extends Graph with cycle detection and topological sorting.

Defined in:

craph/dag.cr

Constructors

Instance Method Summary

Instance methods inherited from class Craph::Graph(T)

add_edge(from : T, to : T) add_edge, add_node(name : T) add_node, empty? empty?, has_edge?(from : T, to : T) : Bool has_edge?, has_node?(name : T) : Bool has_node?, neighbors(name : T) : Set(T) neighbors, nodes nodes, size size

Constructor methods inherited from class Craph::Graph(T)

new new

Constructor Detail

def self.new #

[View source]

Instance Method Detail

def acyclic? #

Check if the graph has no cycles using DFS


[View source]
def topological_sort(strict : Bool = true) : Array(Set(T)) #

Return the nodes sorted topologically. The algorithm uses clustered output to allow for parallel processing. When strict (default), raises CycleError if cycles exist. When not strict, cyclic nodes are excluded from the result.


[View source]