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

Returns:

  • (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