Class: NPGRT::Algorithm::Graph

Inherits:
Object
  • Object
show all
Defined in:
lib/npgrt/algorithm.rb

Defined Under Namespace

Classes: RelaxOperators

Constant Summary collapse

DefaultRelax = 
RelaxOperators.new(
	lambda{|a, b| a + b},
	lambda{|a, b| [a,b].min},
	Float::INFINITY
)

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#adjlist ⇒ Object

Returns the value of attribute adjlist.



43
44
45
 
# File 'lib/npgrt/algorithm.rb', line 43

def adjlist
  @adjlist
end

#adjmat ⇒ Object

Returns the value of attribute adjmat.



43
44
45
 
# File 'lib/npgrt/algorithm.rb', line 43

def adjmat
  @adjmat
end

Instance Method Details

#bellman_ford(start = [0], relax = DefaultRelax) ⇒ Object 



88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# 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 ⇒ Object 



168
169
170
171
172
173
 
# 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 ⇒ Object 



161
162
163
164
165
166
 
# 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)) ⇒ Object 



137
138
139
140
141
 
# 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 ⇒ Object 



84
85
86
 
# File 'lib/npgrt/algorithm.rb', line 84

def floyd
	deepcopy_adjmat.floyd!
end

#floyd!(relax = DefaultRelax) ⇒ Object 



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
 
# 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) ⇒ Object 



110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
# 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 ⇒ Object

Raises:



143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
 
# 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