module RailsBetterFilters::WeightedTopologicalSort
Public Class Methods
sort(nodes, edges)
click to toggle source
Input: nodes = Hash of node name => priority. edges = Hash of node name => list of children. Output: List of node names.
# File lib/rails-better-filters/weighted_topological_sort.rb, line 9 def self.sort(nodes, edges) # We use the algorithm of Kahn (1962) from # http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=586746444 # and enhance it by sorting the set of nodes with no # incoming edges by their priority. # First convert to our own data structures. nodes = make_nodes(nodes) edges = make_edges(edges) # The list. l = [] # Find all nodes with no incoming edges. s = nodes.select { |n| edges.none? { |e| e.to?(n) } } while !s.empty? # Here's the priority trick. s.sort!.reverse! # Get the one with the highest priority. current = s.shift l << current # Get all outgoing edges from current node and remove them from the graph. outgoing, edges = edges.partition { |e| e.from?(current) } # Find current's children. children_names = outgoing.map { |e| e.to } children = nodes.select { |n| children_names.include?(n.name) } # If child has no other incoming edges, we can add it to s. children.each do |n| if edges.none? { |e| e.to?(n) } s << n end end end # If there are still edges in the graph, there is at least one cycle. raise 'graph is not acyclic!' if !edges.empty? # Convert to names again. l.map { |n| n.name } end
Private Class Methods
make_edges(edges)
click to toggle source
# File lib/rails-better-filters/weighted_topological_sort.rb, line 60 def self.make_edges(edges) edges.map { |from, to_list| to_list.map { |to| [from, to] }}.flatten(1).map { |a| Edge.new(a[0], a[1]) } end
make_nodes(nodes)
click to toggle source
# File lib/rails-better-filters/weighted_topological_sort.rb, line 56 def self.make_nodes(nodes) nodes.map { |name, priority| Node.new(name, priority) } end