그래프 루비버전
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