82 lines
1.6 KiB
Crystal
82 lines
1.6 KiB
Crystal
require "./heaphash.cr"
|
|
|
|
class Graph(A)
|
|
def initialize
|
|
@edges = {} of A => Set({A, Int32})
|
|
@nodes = Set(A).new
|
|
end
|
|
|
|
def add_node(n)
|
|
@nodes << n
|
|
end
|
|
|
|
def add_edge(f, t, c = 1)
|
|
@edges[f] ||= Set({A, Int32}).new
|
|
@edges[f] << {t, c}
|
|
@nodes << f << t
|
|
end
|
|
|
|
def add_biedge(f, t, c = 1)
|
|
add_edge(f, t, c)
|
|
add_edge(t, f, c)
|
|
end
|
|
|
|
def edges?(n)
|
|
@edges[n]? || Set({A, Int32}).new
|
|
end
|
|
|
|
def find_path(f, t)
|
|
visited = Set(A).new
|
|
distances = HeapHash { f => 0 }
|
|
prev = {} of A => A
|
|
dist = nil
|
|
|
|
while !distances.empty?
|
|
candidate, dist = distances.pop
|
|
break if candidate == t
|
|
visited << candidate
|
|
|
|
edges?(candidate).each do |e|
|
|
node, cost = e
|
|
new_dist = dist + cost
|
|
next if visited.includes? node
|
|
next if (old_dist = distances[node]?) && old_dist < new_dist
|
|
distances[node] = new_dist
|
|
prev[node] = candidate
|
|
end
|
|
end
|
|
|
|
backtrack = t
|
|
path = [t] of A
|
|
while backtrack != f
|
|
return nil unless prev_bt = prev[backtrack]?
|
|
path << prev_bt
|
|
backtrack = prev_bt
|
|
end
|
|
{path.reverse!, dist.not_nil!}
|
|
end
|
|
|
|
def topol
|
|
edge_counts = HeapHash(A, Int32).new
|
|
@nodes.each do |k|
|
|
edge_counts[k] = 0
|
|
end
|
|
@edges.each do |k, v|
|
|
v.each do |e|
|
|
edge_counts[e[0]] -= 1
|
|
end
|
|
end
|
|
|
|
order = [] of A
|
|
while !edge_counts.empty?
|
|
k, count = edge_counts.pop
|
|
raise "cycle in graph!" unless count == 0
|
|
order << k
|
|
edges?(k).each do |e|
|
|
edge_counts[e[0]] += 1
|
|
end
|
|
end
|
|
order
|
|
end
|
|
end
|