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

## Instance Method Summary collapse

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

• Returns an approximately minimal feedback arc set.

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

## 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```