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