Module: Librarian::Algorithms::AdjacencyListDirectedGraph

Extended by:
AdjacencyListDirectedGraph
Included in:
AdjacencyListDirectedGraph
Defined in:
lib/librarian/algorithms.rb

Instance Method Summary collapse

Instance Method Details

#cyclic?(graph) ⇒ Boolean


28
29
30
# File 'lib/librarian/algorithms.rb', line 28

def cyclic?(graph)
  each_cyclic_strongly_connected_component_set(graph).any?
end

#feedback_arc_graph(graph) ⇒ Object

Returns an approximately minimal feedback arc set, lifted into a graph.


41
42
43
# File 'lib/librarian/algorithms.rb', line 41

def feedback_arc_graph(graph)
  edges_to_graph(feedback_arc_set(graph))
end

#feedback_arc_set(graph) ⇒ Object

Returns an approximately minimal feedback arc set.


46
47
48
49
# 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) ⇒ Object

Topological sort of the graph with an approximately minimal feedback arc set removed.


34
35
36
37
38
# 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