class NPGRT::Algorithm::Graph
Constants
- DefaultRelax
- RelaxOperators
Attributes
adjlist[RW]
adjmat[RW]
Public Instance Methods
bellman_ford(start = [0], relax = DefaultRelax)
click to toggle source
# File lib/npgrt/algorithm.rb, line 88 def bellman_ford(start = [0], relax = DefaultRelax) a = self.adjlist dis = a.map { relax.maxvalue } pre = a.map { -1 } start.each{|i| dis[i] = 0; pre[i] = i } n = a.size (n-1).times{ relaxed = false each_edge do |u, v, w| next if w == nil rel = relax.add[ dis[u] , w] if rel == relax.min[ rel, dis[v] ] dis[v] = rel pre[v] = u relaxed = true end end break if !relaxed } [dis, pre] end
deepcopy_adjlist()
click to toggle source
# File lib/npgrt/algorithm.rb, line 168 def deepcopy_adjlist x = Graph.new x.adjlist = Marshal.load Marshal.dump adjlist x.adjmat = nil x end
deepcopy_adjmat()
click to toggle source
# File lib/npgrt/algorithm.rb, line 161 def deepcopy_adjmat x = Graph.new x.adjmat = Marshal.load Marshal.dump adjmat x.adjlist = nil x end
each_edge(start = (0...adjlist.size)) { |u, v, w| ... }
click to toggle source
# File lib/npgrt/algorithm.rb, line 137 def each_edge(start = (0...adjlist.size)) start.each{|u| self.adjlist[u].each{|v, w| yield u, v, w }} end
floyd()
click to toggle source
# File lib/npgrt/algorithm.rb, line 84 def floyd deepcopy_adjmat.floyd! end
floyd!(relax = DefaultRelax)
click to toggle source
# File lib/npgrt/algorithm.rb, line 58 def floyd!(relax = DefaultRelax) a = adjmat n = adjmat.size self.adjlist = nil #reset (0...n).each{|k| (0...n).each{|i| next if i == k next if a[i][k] == nil (0...n).each{|j| next if j == k || j == i next if a[i][k] == nil || a[k][j] == nil if !a[i][j] a[i][j] = relax.add[ a[i][k], a[k][j] ] else a[i][j] = relax.min[ a[i][j], relax.add[a[i][k], a[k][j] ] ] end } } } self end
spfa(start = [0], relax = DefaultRelax)
click to toggle source
# File lib/npgrt/algorithm.rb, line 110 def spfa(start = [0], relax = DefaultRelax) a = self.adjlist dis = a.map { relax.maxvalue } pre = a.map { -1 } inq = [] start.each{|i| dis[i] = 0; pre[i] = i; inq[i] = true } n = a.size NPGRT.bfs *start do |yielder, u| inq[u] = false a[u].each do |v, w| next if w == nil rel = relax.add[ dis[u] , w] if rel == relax.min[ rel, dis[v] ] dis[v] = rel pre[v] = u if !inq[v] inq[v] = true yielder.call v end end end end [dis, pre] end
toposort()
click to toggle source
# File lib/npgrt/algorithm.rb, line 143 def toposort x = self.adjlist id = x.map { 0 } each_edge{|u, v, w| id[v] += 1 if w} n = x.size ret = [] while true a = (0...n).select{|u| id[u] == 0} - ret break if a == [] ret.concat a each_edge a do |u, v, w| id[v] -= 1 if w end end raise CycleFound, 'in toposorting' if ret.size != n ret end