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