It's just like pok    version4


Graph (Ruby)

 | 

그래프 루비버전


module Pok
	class Stack < Array
		def push_back( _element )
			push( _element )
		end
		
		def pop_back
			pop
		end
	end
	
	class Queue < Array
		def push_back( _element )
			push( _element )
		end
		
		def pop_front
			shift
		end
	end
end


class Cell
	attr_accessor :cell_id, :edge_container
	def initialize
		@edge_container = Hash.new
	end
	def addEdge( _rConnectedCell, nWeight )
		if @edge_container[_rConnectedCell.cell_id] != nil && @edge_container[_rConnectedCell.cell_id] != nWeight
			puts "Hei, this graph is not directional graph. weight between vertexes must same value!\n"
		end
		@edge_container[_rConnectedCell.cell_id] = nWeight	
	end
end

class Graph
	def initialize( _nCellidStartNum )
		@nNextCellid = _nCellidStartNum
		@aCellContainer = Hash.new
	end
	def makeCell
		aCell = Cell.new
		aCell.cell_id = @nNextCellid
		@aCellContainer[ aCell.cell_id ] = aCell
		@nNextCellid += 1
		return aCell
	end
	def connectCells( _rCell1, _rCell2 , nWeight)
		_rCell1.addEdge( _rCell2, nWeight )
		_rCell2.addEdge( _rCell1, nWeight )
	end
	
	def dfsWithStack( _rStartCell )
		aCurrentCell = @aCellContainer[_rStartCell.cell_id]
		return if aCurrentCell == nil
		
		aMarkedCell = Hash.new
		aDepthStack = Pok::Stack.new
		
		#start dfs
		aDepthStack.push_back( aCurrentCell )
		print "DFS init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
		
		#stack loop
		while aDepthStack.empty? == false
			aCurrentCell = aDepthStack.pop_back
			next if aMarkedCell[ aCurrentCell.cell_id ] == true
			
			# marking
			aMarkedCell[aCurrentCell.cell_id] = true
			print "Cell id : " + aCurrentCell.cell_id.to_s + " is just now visited\n"
			
			#Test 확인을 쉽게 하기 위해 거꾸로 순회를 하도록 해서 pop할때는 작은수부터 나오게~
			aConnectedCells = aCurrentCell.edge_container.sort
			aConnectedCells.reverse!
			aConnectedCells.each do | id_value_array |
				#print "--connected" + id_value_array[0].to_s + "\n"
				aCandidateCell = @aCellContainer[ id_value_array[0] ]
				if aMarkedCell[aCandidateCell.cell_id] == nil
					#print "==pushed" + aCandidateCell.cell_id.to_s + "\n"
					aDepthStack.push_back(aCandidateCell)
				end
			end
		end
	end
	
	def dfsRecursiveCore( _rCell , _rMarkedCells)
		_rMarkedCells[ _rCell.cell_id ] = true
		print "Cell id : " + _rCell.cell_id.to_s + " is just now visited\n"
		
		#테스트 확인을 쉽게 하기 위해 셀 번호순서대로 소팅하기
		aConnectedCellsContainer = _rCell.edge_container.sort
		aConnectedCellsContainer.each do | vertex_id_weight |
			nCell_id = vertex_id_weight[0]
			if _rMarkedCells[ nCell_id ] == nil
				dfsRecursiveCore( @aCellContainer[nCell_id], _rMarkedCells )
			end
		end
	end
	
	def dfsRecursive( _rStartCell )
		aCurrentCell = @aCellContainer[_rStartCell.cell_id]
		return if aCurrentCell == nil
		
		aMarkedCellsContainer = Hash.new
		print "DFS(Recursive version) init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
		dfsRecursiveCore( aCurrentCell, aMarkedCellsContainer )
	end
	
	def bfs( _rStartCell )
		aCurrentCell = @aCellContainer[_rStartCell.cell_id]
		return if aCurrentCell == nil
		
		aMarkedCell = Hash.new
		aBreadthQueue = Pok::Queue.new
		
		#start bfs
		aBreadthQueue.push_back( aCurrentCell )
		print "BFS init With Cell id : " + aCurrentCell.cell_id.to_s + "\n"
		
		#stack loop
		while aBreadthQueue.empty? == false
			aCurrentCell = aBreadthQueue.pop_front
			next if aMarkedCell[ aCurrentCell.cell_id ] == true
			
			# marking
			aMarkedCell[aCurrentCell.cell_id] = true
			print "Cell id : " + aCurrentCell.cell_id.to_s + " is just now visited\n"
			
			aConnectedCells = aCurrentCell.edge_container.sort
			aConnectedCells.each do | id_value_array |
				#print "--connected" + id_value_array[0].to_s + "\n"
				aCandidateCell = @aCellContainer[ id_value_array[0] ]
				if aMarkedCell[aCandidateCell.cell_id] == nil
					#print "==pushed" + aCandidateCell.cell_id.to_s + "\n"
					aBreadthQueue.push_back(aCandidateCell)
				end
			end
		end
	end
	
	def dijkstra( _rStartCell, _rEndCell )
		# 최단길 찾기
		# 최종 목표는 시작 셀로부터 하여 각 노드까지의 거리 테이블을 작성하는 것이다.
		
		#1. 초기화
		#    1.1 시작셀에서부터의 거리테이블 만들기. 연결되어 있지 않는것은 무한대값.
		#    1.2 열린노드 / 닫힌노드 구성
		#2. 셀 탐색 
		#    2.1 열린노드중에서 제일 짧은 거리를 가진것을 거리테이블로부터 선택, 닫힌 노드에 넣기
		#           (음수 Edge가 없으므로 다시 연산할 필요가 없는것은 닫힌노드에 넣고 연산시에 고려하지 않는다.)
		#    2.2 모든 노드가 닫혔다면 종료
		#    2.3 선택된 셀과 연결 된것중 열린노드에 있는것에 대해, 거리테이블 재작성
		
		#1.1
		aDistanceContainer = Hash.new
		aDistanceContainer[ _rStartCell.cell_id ] = 0
		_rStartCell.edge_container.each do | key_cell_id, value_weight |
			aDistanceContainer[ key_cell_id ] = value_weight
		end
		#1.2
		aClosedCellsContainer = Hash.new
		
		#2
		while true
		
			# 2.1
			nMinDist = 10000000 #초기값. 아주 큰값. 절대 dist값으로 될 수 없는 값.
			nSelectedCell_id = -1
			aDistanceContainer.each do | key_id, key_value |
			if aClosedCellsContainer[ key_id ] == nil && key_value < nMinDist
					nSelectedCell_id = key_id
					nMinDist = key_value
				end
			end
			
			#2.2, 모든 노드가 닫혔다면 알고리듬을 종료한다.
			if nSelectedCell_id != -1
				# 선택된것은 닫힌노드에 넣어주고, 거리테이블 재작성을 수행한다.
				aClosedCellsContainer[ nSelectedCell_id ] = true
			else
				# 모든 노드가 닫혔다면, 알고리듬 종료.
				break
			end
			
			# 2.3
			# 선택된 셀과 연결된 셀중 열린노드에 있는것에 대해
			@aCellContainer[ nSelectedCell_id ].edge_container.each do | key_cell_id, value_weight |
				next if aClosedCellsContainer[ key_cell_id ] == true # 열린노드에 대해서만. 닫힌노드라면 계산하지 않는다.
				
				# 거리 테이블에 기록되지 않았다는것은 예전에 무한대(연결 없음)를 의미한다.
				# 이번에 선택된 셀에는 연결되어 있으므로 새로 계산해 준다.
				if aDistanceContainer[ key_cell_id ] == nil || aDistanceContainer[ nSelectedCell_id ] + value_weight < aDistanceContainer[ key_cell_id ]
					aDistanceContainer[ key_cell_id ] = aDistanceContainer[ nSelectedCell_id ] + value_weight
					#puts "relaxation, " + key_cell_id.to_s + ", " + value_weight.to_s + "\n"
				end
			end
		end
		
		return aDistanceContainer[ _rEndCell.cell_id ]
	end
	
	def disconnectCell( _rSrcCell, _rCellToDisconnect )
		puts "Not implement yet.\n"
	end
	def removeCellFromGraph( _rCell )
		puts "Not implement yet.\n"
	end
end

# Unit Test
#require 'test/unit'
#class TestGraph < Test::Unit::TestCase
#	def testGraphFunction
#	end
#end

if __FILE__ == $0
#if __FILE__ == ""

	aGraph = Graph.new(1)
	
	aCell1 = aGraph.makeCell
	aCell2 = aGraph.makeCell
	aCell3 = aGraph.makeCell
	aCell4 = aGraph.makeCell
	aCell5 = aGraph.makeCell
	aCell6 = aGraph.makeCell
	
	# connect cells
	aGraph.connectCells( aCell1, aCell2, 3)
	aGraph.connectCells( aCell1, aCell3, 4)
	
	aGraph.connectCells( aCell2, aCell1, 3)
	aGraph.connectCells( aCell2, aCell3, 2)
	aGraph.connectCells( aCell2, aCell4, 5)
	aGraph.connectCells( aCell2, aCell5, 1)
	
	aGraph.connectCells( aCell3, aCell1, 4)
	aGraph.connectCells( aCell3, aCell2, 2)
	aGraph.connectCells( aCell3, aCell4, 4)
	
	aGraph.connectCells( aCell4, aCell3, 4)
	aGraph.connectCells( aCell4, aCell2, 5)
	aGraph.connectCells( aCell4, aCell5, 2)
	aGraph.connectCells( aCell4, aCell6, 3)
	
	aGraph.connectCells( aCell5, aCell2, 1)
	aGraph.connectCells( aCell5, aCell4, 2)
	aGraph.connectCells( aCell5, aCell6, 1)
	
	aGraph.connectCells( aCell6, aCell5, 1)
	aGraph.connectCells( aCell6, aCell4, 3)
	
	aGraph.dfsWithStack( aCell3 )
	aGraph.dfsRecursive( aCell3 )
	aGraph.bfs( aCell5 )
	
	nDistance = aGraph.dijkstra( aCell1, aCell4 )
	print "Dijkstra:: Distance is " + nDistance.to_s + "\n"
end

#if __FILE__ == $0
if __FILE__ == ""
	aGraph = Graph.new(0)
	
	aCell0 = aGraph.makeCell
	aCell1 = aGraph.makeCell
	aCell2 = aGraph.makeCell
	aCell3 = aGraph.makeCell
	aCell4 = aGraph.makeCell
	aCell5 = aGraph.makeCell
	aCell6 = aGraph.makeCell
	aCell7 = aGraph.makeCell
	
	# connect cells
	aGraph.connectCells( aCell0, aCell1, 3)
	aGraph.connectCells( aCell0, aCell2, 6)
	
	aGraph.connectCells( aCell1, aCell0, 3)
	aGraph.connectCells( aCell1, aCell3, 7)
	aGraph.connectCells( aCell1, aCell4, 1)
	
	aGraph.connectCells( aCell2, aCell0, 6)
	aGraph.connectCells( aCell2, aCell5, 4)
	aGraph.connectCells( aCell2, aCell6, 2)
	
	aGraph.connectCells( aCell3, aCell1, 7)
	aGraph.connectCells( aCell3, aCell7, 4)
	
	aGraph.connectCells( aCell4, aCell1, 1)
	aGraph.connectCells( aCell4, aCell7, 9)
	
	aGraph.connectCells( aCell5, aCell2, 4)
	aGraph.connectCells( aCell5, aCell7, 1)
	
	aGraph.connectCells( aCell6, aCell2, 2)
	aGraph.connectCells( aCell6, aCell7, 7)
	
	aGraph.connectCells( aCell7, aCell3, 4)
	aGraph.connectCells( aCell7, aCell4, 9)
	aGraph.connectCells( aCell7, aCell5, 1)
	aGraph.connectCells( aCell7, aCell6, 7)
	
	aGraph.dfsWithStack( aCell0 )
	aGraph.dfsRecursive( aCell0 )
	aGraph.bfs( aCell0 )
	
	nDistance = aGraph.dijkstra( aCell0, aCell7 )
	print "Dijkstra:: Distance is " + nDistance.to_s + "\n"
end


프로그래밍