Top Level Namespace
Instance Method Summary collapse
-
#topological_sort(root_nodes) ⇒ Object
Performs a topological sort on a graph.
Instance Method Details
#topological_sort(root_nodes) ⇒ Object
Performs a topological sort on a graph.
Args:
nodes:: Enumerable of all the nodes in the graph, or at least a subset of
nodes that the entire graph is reachable from
Requires a block that takes a node as an argument and returns a hash with the following keys:
:id:: a unique ID for the node; this makes the algorithm work with graphs
that have multiple objects representing the same node; if the :id key
is not set, the node object is used as its own ID
:next:: array of nodes that are reachable by direct edges from the given
node; if the :next key is not set, the given node is assumed to be a
sink
Returns the graph’s nodes, in topological order. This means that if node A is before node B, there is no path from A to B in the graph.
Raises an ArgumentError if the graph is cyclic.
22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
# File 'lib/topological_sort.rb', line 22 def topological_sort(root_nodes) nodes = [] # Topological-sorting DFS. visited = Set.new # IDs for the visited nodes. active = Set.new # IDs for the nodes that are currently on the stack. stack = [] # DFS stack state. Entries are [node, id, child_number, children]. root_nodes.each do |root_node| node_data = yield root_node node_id = node_data.has_key?(:id) ? node_data[:id] : root_node next if visited.include? node_id visited << node_id stack << [root_node, node_id, -1, node_data[:next] || []] active << node_id until stack.empty? stack.last[2] += 1 node, node_id, child_number, children = *stack.last if child_node = children[child_number] node_data = yield child_node node_id = node_data.has_key?(:id) ? node_data[:id] : child_node if active.include? node_id raise ArgumentError, 'Cyclical graph' end unless visited.include? node_id visited << node_id active << node_id stack << [child_node, node_id, -1, node_data[:next] || []] end else nodes << node active.delete stack.last[1] stack.pop end end end nodes end |