Module: NPGRT::Algorithm

Included in:
NPGRT
Defined in:
lib/npgrt/algorithm.rb

Defined Under Namespace

Classes: AlgorithmError, CycleFound, Graph, NotFound

Instance Method Summary collapse

Instance Method Details

#array_to_hash(arr) ⇒ Object 



11
12
13
14
15
 
# File 'lib/npgrt/algorithm.rb', line 11

def array_to_hash(arr)
	hsh = {}
	arr.each_with_index{|e, i| hsh[i] = e if e}
	hsh	
end

#bfs(*start) ⇒ Object 



7
8
9
 
# File 'lib/npgrt/algorithm.rb', line 7

def bfs(*start)
	yield(start.method(:push), start.shift)	until start.empty?
end

#dfs(start) {|lambda{|v| dfs(v, &b)}, start| ... } ⇒ Object

Yields:

  • (lambda{|v| dfs(v, &b)}, start) 


3
4
5
 
# File 'lib/npgrt/algorithm.rb', line 3

def dfs(start, &b)
	yield(lambda{|v| dfs(v, &b)}, start)
end

#graph_buildpath(st, ed, pre) ⇒ Object 



26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/npgrt/algorithm.rb', line 26

def graph_buildpath(st, ed, pre)
	ret = []
	while ed != st && ed != -1
		raise CycleFound, 'path cycled' if ret.include?(ed)
		ret.unshift ed
		ed = pre[ed]
	end	
	if ed == st
		ret.unshift st
	else
		raise NotFound
	end	
	ret		
end

#hash_to_array(hsh) ⇒ Object 



17
18
19
20
21
 
# File 'lib/npgrt/algorithm.rb', line 17

def hash_to_array(hsh)
	arr = []
	hsh.each{|k, v| arr[k] = v}
	arr
end