1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
|
require "set"
require "tsort"
module Librarian
module Algorithms
class GraphHash < Hash
include TSort
def tsort_each_node(&block)
keys.sort.each(&block) # demand determinism
end
def tsort_each_child(node, &block)
children = self[node]
children && children.sort.each(&block) # demand determinism
end
class << self
def from(hash)
o = new
hash.each{|k, v| o[k] = v}
o
end
end
end
module AdjacencyListDirectedGraph
extend self
def cyclic?(graph)
each_cyclic_strongly_connected_component_set(graph).any?
end
# Topological sort of the graph with an approximately minimal feedback arc
# set removed.
def tsort_cyclic(graph)
fag = feedback_arc_graph(graph)
reduced_graph = subtract_edges_graph(graph, fag)
GraphHash.from(reduced_graph).tsort
end
# Returns an approximately minimal feedback arc set, lifted into a graph.
def feedback_arc_graph(graph)
edges_to_graph(feedback_arc_set(graph))
end
# Returns an approximately minimal feedback arc set.
def feedback_arc_set(graph)
fas = feedback_arc_set_step0(graph)
feedback_arc_set_step1(graph, fas)
end
private
def edges_to_graph(edges)
graph = {}
edges.each do |(u, v)|
graph[u] ||= []
graph[u] << v
graph[v] ||= nil
end
graph
end
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
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
# 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.
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
# The 0th step of computing a feedback arc set: pick out vertices whose
# removals will make the graph acyclic.
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
# The 1st step of computing a feedback arc set: pick out vertices from the
# 0th step whose removals turn out to be unnecessary.
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
end
end
end
|
