module Librarian::Algorithms::AdjacencyListDirectedGraph
Public Instance Methods
cyclic?(graph)
click to toggle source
# File lib/librarian/algorithms.rb, line 28 def cyclic?(graph) each_cyclic_strongly_connected_component_set(graph).any? end
feedback_arc_graph(graph)
click to toggle source
Returns an approximately minimal feedback arc set, lifted into a graph.
# File lib/librarian/algorithms.rb, line 41 def feedback_arc_graph(graph) edges_to_graph(feedback_arc_set(graph)) end
feedback_arc_set(graph)
click to toggle source
Returns an approximately minimal feedback arc set.
# File lib/librarian/algorithms.rb, line 46 def feedback_arc_set(graph) fas = feedback_arc_set_step0(graph) feedback_arc_set_step1(graph, fas) end
tsort_cyclic(graph)
click to toggle source
Topological sort of the graph with an approximately minimal feedback arc set removed.
# File lib/librarian/algorithms.rb, line 34 def tsort_cyclic(graph) fag = feedback_arc_graph(graph) reduced_graph = subtract_edges_graph(graph, fag) GraphHash.from(reduced_graph).tsort end
Private Instance Methods
each_cyclic_strongly_connected_component_graph(graph) { |sccg| ... }
click to toggle source
Partitions the graph into its strongly connected component subgraphs, removes the acyclic single-vertex components (multi-vertex components are guaranteed to be cyclic), and yields each cyclic strongly connected component.
# File lib/librarian/algorithms.rb, line 88 def each_cyclic_strongly_connected_component_graph(graph) return enum_for(__method__, graph) unless block_given? each_cyclic_strongly_connected_component_set(graph) do |scc| sccs = scc.to_set sccg = GraphHash.new scc.each do |n| vs = graph[n] sccg[n] = vs && vs.select{|v| sccs.include?(v)} end yield sccg end end
each_cyclic_strongly_connected_component_set(graph) { |scc| ... }
click to toggle source
# File lib/librarian/algorithms.rb, line 72 def each_cyclic_strongly_connected_component_set(graph) return enum_for(__method__, graph) unless block_given? GraphHash.from(graph).each_strongly_connected_component do |scc| if scc.size == 1 n = scc.first vs = graph[n] or next vs.include?(n) or next end yield scc end end
edges_to_graph(edges)
click to toggle source
# File lib/librarian/algorithms.rb, line 53 def edges_to_graph(edges) graph = {} edges.each do |(u, v)| graph[u] ||= [] graph[u] << v graph[v] ||= nil end graph end
feedback_arc_set_step0(graph)
click to toggle source
The 0th step of computing a feedback arc set: pick out vertices whose removals will make the graph acyclic.
# File lib/librarian/algorithms.rb, line 103 def feedback_arc_set_step0(graph) fas = [] each_cyclic_strongly_connected_component_graph(graph) do |scc| scc.keys.sort.each do |n| # demand determinism vs = scc[n] or next vs.size > 0 or next vs.sort! # demand determinism fas << [n, vs.shift] break end end fas end
feedback_arc_set_step1(graph, fas)
click to toggle source
The 1st step of computing a feedback arc set: pick out vertices from the 0th step whose removals turn out to be unnecessary.
# File lib/librarian/algorithms.rb, line 119 def feedback_arc_set_step1(graph, fas) reduced_graph = subtract_edges_graph(graph, edges_to_graph(fas)) fas.select do |(u, v)| reduced_graph[u] ||= [] reduced_graph[u] << v cyclic = cyclic?(reduced_graph) reduced_graph[u].pop if cyclic cyclic end end
subtract_edges_graph(graph, edges_graph)
click to toggle source
# File lib/librarian/algorithms.rb, line 63 def subtract_edges_graph(graph, edges_graph) xgraph = {} graph.each do |n, vs| dests = edges_graph[n] xgraph[n] = !vs ? vs : !dests ? vs : vs - dests end xgraph end