최단 경로 탐색 – Dijkstra 알고리즘

다익스트라 알고리즘은 시작 노드만을 지정하면, 이 시작 노드에서 다른 모든 노드에 대한 최단 경로들을 분석해 줍니다. 참고로 최단 경로 탐색 알고리즘의 다른 형태로  A*(에이스타) 알고리즘이 있는데요. A* 알고리즘은 시작 노드에서 목적지 노드를 지정해주면 이 2개의 노드 간의 최단 경로 하나만을 분석해 줍니다.

이 글은 다익스트라 알고리즘에 대한 이런 저런 장황한 설명을 배제하고 실제 예를 들어, 그 예에 대한 최단 경로 탐색을 위한 다익스트라 알고리즘에 대해 설명합니다.

먼저 다음과 같은 예를 들어 보겠습니다.

위의 그림을 간단히 설명하면, 0부터 6번까지의 노드(Node)가 존재하고 각 노드를 연결하는 선인 링크(Link)가 있습니다.  각 링크에는 숫자가 표시되어 있는데요. 이 숫자는 해당 링크를 지나갈때에 소요되는 비용(Cost, 경비)로 생각할 수 있습니다. 예를 들어, 2번 노드와 6번 노드 사이에 비용 8인 링크가 있는데요. 이는 2번 노드에서 6번 노드를 지나간다고 할때 8의 비용이 필요하다는 의미입니다. 비용이 적을 수록 상대적으로 더 좋은 경로이겠지요.

이제 위의 예, 즉 0번 노드를 시작점으로 해서 나머지  1, 2, 3, 4, 5, 6 번 노드를 목적지로 하는 최단 경로 6개를 구할 수 있는 방법이 바로 다익스트라 알고리즘입니다.

이상의 문제 해결을 위해 가장 먼저 시작되는 연산은 다음 그림과 같습니다.

위의 그림에서 S 은 이미 처리가 완결된 노드의 집합인데요. 가장 먼저 시작 노드인 0번을 집어 놓음으로써 0번 노드에 대한 처리를 시작합니다. D 저장소는 0번~6번까지의 노드에 대해, 시작노드로부터 소요되는 비용을 저장하고 있습니다. D 저장소의 상단 행은 노드의 번호이고 하단 행은 시작노드로부터 소요되는 비용입니다. 위 그림에서 D 저장소를 보면 0번 노드는 시작노드이므로 소요되는 비용이 0이고, 0번 노드와 링크로 연결된 1번과 3번 노드는 각각 5와 1의 비용이 소요되는 것으로 기록되어 있습니다. T 저장소는 해당 노드로 가는데 연결된 노드의 번호를 담고 있는데요. T 저장소이 상단 행은 노드의 번호이고 하단 노드는 연결된 노드 번호입니다. 위의 그림을 보면 1번 노드와 3번 노드는 0번 노드와 연결되어 있으므로 0으로 기록되어져 있습니다. 이게 주어진 문제에 대한 다익스트라 알고리즘의 첫번째 처리입니다.

이제 다음 처리에 대한 그림을 살펴 보겠습니다.

S집합에 3번 노드를 추가했습니다. 이유는 D 저장소에 3번 노드에 대한 비용값이 가장 최소이기 때문입니다. S집합에 3번 노드를 추가함으로써 3번 노드와 링크로 연결된 2번과 5번 노드에 대한 비용값을 계산해 D 저장소에 기록해야 하는데요. 시작 노드인 0번 노드에서 2번 노드까지 가기 위해서 소요되는 비용은 총 3입니다. 이유는 0번-3번-2번 노드로 가야하므로 비용값은 0번-3번 노드로 가는 비용 1과 3번과 2번 노드로 가는 비용 2를 합한 값입니다. 이러한 계산은 D 저장소를 활용하면 쉽게 계산할 수 있는데요. 이미 시작노드에서 각 노드로 가는 비용이 계산되어 있기 때문에 마지막 노드로 가는 비용만을 더해주면 되기 때문입니다. 5번 노드에 대한 비용은 동일한 방식으로 1+1인 2가 됩니다. 그리고 T 저장소도 각 노드에 대해 이전에 연결된 노드값을 기록해 둡니다. T 저장소의 2번과 5번 노드는 3번 노드를 통해 연결되어 있으므로 3을 기록합니다. 다음 처리에 대한 그림을 살펴봅시다.

S 집합에 5를 추가했습니다. 이는 이미 처리가 완료된 노드 이외의 노드 중 5번 노드의 비용이 2로 가장 최소이기 때문입니다.  이미 처리가 완료된 노드인지 S 집합에 존재하는지를 보면 알 수 있습니다. 5번 노드에 대해 연결된 노드는 2, 3, 6번 노드인데요. 이미 3번은 처리가 완료되었으므로 2번 노드와 3번 노드에 대해 D 저장소의 값을 갱신해야 합니다. 5번 노드를 거쳐 2번 노드를 갈 경우 소요되는 비용은 2+2로 4입니다. 이 값은 이미 전 단계에서 계산된 비용값(3)보다 크므로 무시합니다. 6번 노드에 대한 비용값은 5번 노드까지 오는데 소요된 비용값(2)와 5번에서 6번 노드로 가는데 추가적으로 필요한 비용 3을 합한 값 5이므로, 이 값을 D 저장소에 기록하고 T 저장소의 6번 노드 값에 5번 노드를 기록합니다. 다음 단계로 넘어 갑니다. 

처리가 완결되지 않은 노드 중 비용이 최소인 노드는 2번인데요. 2번 노드와 연결된 노드는 1, 3, 5, 6번 노드입니다. 처리가 완결된 노드를 저장하고 있는 S 집합을 통해 3번 노드와 5번 노드는 더 이상 고려할 필요가 없다는 것을 알 수 있으니, 1, 6번만 고려하면 됩니다. 먼저 1번의 경우 소요되는 비용은 3+1로 4인데요. 이 값은 이전 단계에서 계산된 비용값(5)보다 작으로 D 저장소의 값을 변경 합니다. D 저장소가 변경되면  T 저장소의 값도 2번 노드로 변경합니다. 중요한 부분이므로 위의 그림에서 빨간색으로 표시했습니다. 이제 남은 6번 노드에 대한 비용값을 계산해 보면 3+8로 11인데요. 이 값은 이전 단계에서 계산된 비용인 5보다 크므로 무시합니다. 다음 단계로 진행합니다.

처리가 완료된 노드가 아닌 것 중 1번 노드의 비용이 현재 가장 최소이므로 집합 S에 1번 노드를 추가하고 1번 노드와 연결된 0, 2, 4번 노드 중 완결되지 않은 4번 노드에 대한 비용값을 계산합니다. 4번 노드의 비용값은 4+3으로 7이므로 이 값을 D 저장소에 기록하고 T 저장소에 1번 노드를 기록합니다.

이미 처리가 완료된 노드가 아닌 것 중 최소인 노드는 6번 노드인데요. 이 6번 노드를 집합 S에 추가하고 6번 노드와 링크로 연결된  1, 2, 4, 5 중 처리가 완결되지 않은 노드는 4번인데요. 6번 노드를 경유해 4번 노드로 가기 위한 비용은 5 + 1인 6으로 계산되며, 이 값은 이전 단계에서 계산된 값(7)보다 작으므로 D 저장소가 변경되고, 이와 함께 T 저장소에 대해서도 4번 노드에 대해 6번 노드로 변경합니다.  다음 단계로 진행합니다.

처리되지 않은 노드 중, 이제 유일하게 4번 노드만 남았는데요. 4번 노드와 연결된 1, 6번 노드에 대해 처리를 해야 하는데 이미 1, 6번 노드는 처리가 완결되었으므로 더 이상 진행하지 않고 종료됩니다.

이상의 결과에서 T 저장소를 통해 출발 노드인 0번 노드에서 각 노드에 대한 최단 경로를 파악할 수 있습니다. 0번 노드에서 1번 노드에 대한 최단 경로는 (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)가 됩니다. 이는 T 저장소를 보면, 먼저 1번 노드에 연결되는 노드는 2번 노드라는 것을 알 수 있고, 다시 2번 노드는 3번 노드와 연결되며 3번 노드는 시작 노드인 0번 노드라고 기록되어 있기 때문입니다. 시작 노드 0번에서 각 노드에 대한 최단 경로를 정리하면 다음과 같습니다.

  • 0번 노드에서 1번 노드 : (1번 노드)←(2번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 2번 노드 : (2번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 3번 노드 : (3번 노드)←(0번 노드)
  • 0번 노드에서 4번 노드 : (4번 노드)←(6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 5번 노드 : (5번 노드)←(3번 노드)←(0번 노드)
  • 0번 노드에서 6번 노드 : (6번 노드)←(5번 노드)←(3번 노드)←(0번 노드)

[C++] Stream을 이용한 Typed Binary 데이터 읽고 쓰기

C++은 stream을 통해 반복자(iterator)를 이용해 데이터를  매우 유연하게 처리 할 수 있습니다. 이 스트림을 통해 데이터의 입력을 키보드나 파일 등을 통해 매우 유연하고 효과적으로 읽고 쓸 수 있는데요. 문제는 일반화된 문자열에 대한 읽고 쓰기에 중심을 두고 있다는 점입니다.  즉,  C++의 스트림을 이용해 실수 타입의 값으로 3.14159265라는 값을 파일에 저장하고자 한다면, 이 값을 메모리에 저장된 그대로의 실수형 바이너리 형식으로의 저장이 아닌 “3.14159265”라는 문자열로 저장되는 것이 C++ 개발자에게 흔히 노출된 방식이라는 것입니다.

다 이유가 있겠으나, 필자는 이 실수형 값을 메모리에 저장된 그대로의 실수형 바이너리 형식으로 파일에 저장하고, 이렇게 저장된 값을 다시 파일을 열어 꺼내와 화면에 표시하고자 합니다.

먼저 3.14159265 값을 d 드라이브의 data.bin에 저장하는 코드입니다.

#include <iostream>
#include <fstream>

int main()
{
	std::ofstream os("d:\\data.bin", std::ios::binary);

	double v = 3.141592625;
	os.write(reinterpret_cast<const char*>(&v), sizeof(double));

	os.close();
}

실행해 보면 data.bin 파일이 생성되어졌고, 파일 크기는 double의 바이트 크기와 동일한 8바이트인 것을 확인할 수 있습니다.

이제 이렇게 생성된 파일에서 다시 실수형 값을 읽어 보는 코드는 다음과 같습니다.

#include <iostream>
#include <fstream>

int main()
{
	std::ifstream is("d:\\data.bin", std::ios::binary);

	double v2;
	is.read(reinterpret_cast<char*>(&v2), sizeof(double));
	
	is.close();

	std::cout << v2;
}

여기서 C++의 template을 이용해 개선을 해보도록 하겠습니다. 즉, 다음과 같은 2개의 템플릿 함수를 추가합니다.

template<typename T>
std::ostream& write_typed_data(std::ostream& stream, const T& value) {
	return stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
}

template<typename T>
std::istream & read_typed_data(std::istream& stream, T& value) {
	return stream.read(reinterpret_cast<char*>(&value), sizeof(T));
}

네, write_typed_data와 read_typed_data는 각각 임이의 데이터 타입에 대해서 지정된 스트림에 메모리에 저장된 그대로의 구조인 바이너리 형식으로 쓰고 읽는 범용 함수입니다.

이 두 함수를 활용해 3.141592625 값을 쓰고 읽는 전체 코드를 다시 작성해 보면 다음과 같습니다.

#include <iostream>
#include <fstream>

template<typename T>
std::ostream& write_typed_data(std::ostream& stream, const T& value) {
	return stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
}

template<typename T>
std::istream & read_typed_data(std::istream& stream, T& value) {
	return stream.read(reinterpret_cast<char*>(&value), sizeof(T));
}

int main()
{
	// Write 
	std::ofstream os("d:\\data.bin", std::ios::binary);

	double v = 3.141592625;
	//os.write(reinterpret_cast<const char*>(&v), sizeof(double));
	write_typed_data(os, v);

	os.close();
	// <- test unit end

	// Read
	std::ifstream is("d:\\data.bin", std::ios::binary);

	double v2;
	read_typed_data(is, v2);
	//is.read(reinterpret_cast<char*>(&v2), sizeof(double));
	
	is.close();

	std::cout << v2;
	// <- test unit end
}

C++에서 스트림을 활용해 타입을 가지는 변수를 바이너리 형식으로 저장하는 위의 방식이 정석인지는 모르겠습니다. (이제와서 이게 무슨 소리? -_-;) reinterpret_cast를 사용했다는 점에서 상당히 의구심이 들기 때문인데요. 더욱 나은 방식이 있다면 제안해 주시기 바랍니다. reinterpret_cast는 포인터가 다른 포인터 형식으로 변환될 수 있도록 하거나 정수 계열 형식이 포인터 형식으로 변환될 수 있도록 하고 그 반대로도 변환될 수 있도록 하는 cast 연산자입니다.

[PostgreSQL] CREATE TABLE 예제

PostgreSQL에서 geometry 타입을 갖는 Table을 생성하고자 할때, 사용한 SQL 문에 대해 정리해 봅니다. 아래와 같은 형태의 테이블 2개에 대한 생성인데요.

위 형태의 테이블 2개에 대한 CREATE 문은 아래와 같습니다. 실제 용도는 네트워크 DB에 대한 Node, Link 관련 데이터를 저장하는 Table 생성에 대한 SQL입니다.

CREATE TABLE public.ecl_network_link
(
  networkid uuid PRIMARY KEY,  
  facility_layer character varying(30),
  snode_id uuid,
  snode_layer character varying(30),
  enode_id uuid,
  enode_layer character varying(30),
  the_geom geometry(MultiLineString)
);

ALTER TABLE public.ecl_network_link
  OWNER TO postgres;

CREATE INDEX ecl_network_link_geom_idx
  ON public.ecl_network_link
  USING gist
  (the_geom);
CREATE TABLE public.ecl_network_node
(
  networkid uuid PRIMARY KEY,  
  facility_layer character varying(30),
  the_geom geometry(Point)
);

ALTER TABLE public.ecl_network_node
  OWNER TO postgres;

CREATE INDEX ecl_network_node_geom_idx
  ON public.ecl_network_node
  USING gist
  (the_geom);

[OpenLayers3] 레이어 스파이(Layer Spy)

아래의 지도 위에 마우스를 움직여 보기 바랍니다.


네! 바로 이 기능이 ‘레이어 스파이(Layer Spy)’입니다. 이 기능을 OpenLayer3에서 구현해 보겠습니다.

먼저 필요한 외부 css 및 js를 페이지에 추가합니다.

<script src="https://openlayers.org/en/v3.19.1/build/ol.js"></script>
<script src="https://code.jquery.com/jquery-3.1.1.min.js"></script>

UI를 구성할 텐데요. 위의 지도 페이지에는 지도에 대한 DIV 요소만이 있습니다. 아래의 코드처럼 말입니다.

이제 필요한 css 및 외부 js 라이브러리와 함께 UI까지 준비가 되었으니, 스크립트 코드를 작성할 차례입니다. jQuery의 이벤트 중 UI 등과 같은 요소의 준비가 완료되면 호출되는 ready 이벤트를 아래처럼 작성해 둡니다.

$(function() {
     ....
});

위의 코드에서 …에 해당하는 부분에 스크립트 코드를 추가할 것입니다.

먼저 지도를 구성하는 레이어로 2개를 준비할텐데요. Bing Map에서 제공하는 타일맵을 통해 레이어를 구성합니다. Bing Map의 지도 서비스를 사용하기 위해서는 key가 필요한데, 만약 아래의 코드에서 제공하는 key로 지도가 표시되지 않는다면 직접 발급을 받아 적용하시기 바라니다. 코드는 아래와 같습니다.

var key = 'AgRcrlx0phSk0kDN6HFX9HkMLbG3dBIqtTm-2no4igx0xJPXeDTffQAQfQP1e-Xv';

var roads = new ol.layer.Tile({
    source: new ol.source.BingMaps({ key: key, imagerySet: 'Road' })
});

var imagery = new ol.layer.Tile({
    source: new ol.source.BingMaps({ key: key, imagerySet: 'Aerial' })
});

이제 이 레이어를 지도에 추가하고 지도를 표시할 DIV 요소에 적용할 차례입니다. 아래의 코드와 같습니다.

var container = document.getElementById('map');

var map = new ol.Map({
    layers: [roads, imagery],
    target: container,
    view: new ol.View({
        center: ol.proj.fromLonLat([-109, 46.5]),
        zoom: 6
    })
});

먼저 1번 코드는 지도를 표시할 DIV에 대한 DOM 요소를 id값을 통해 가져와 container이라는 변수에 할당합니다. 그리고 3번은 지도 객체를 생성하는데요. 생성 시 옵션값으로 layers, target, view를 설정합니다. layers 옵션값은 앞서 생성해 둔 레이어를 추가하고, target은 지도가 표시될 DIV에 대한 DIM 요소가 지정되며, view 옵션에는 처음 지도의 위치와 줌 레벨을 지정합니다. layers 옵션에 대해 추가적으로 설명하면.. roads 레이어를 먼저 추가하고 다음에 imagery 레이어를 추가하고 있다는 점이 중요한데요. 이렇게 하면 roads 레이어 위에 imagery 레이어가 표시되는데, 이때 위체 표시되는 imagery 레이어에 대한 렌더링 컨텍스트에 대해 자르기(Clipping)을 적용하면 레이어 스파이 기능이 완성됩니다.

imagery 레이어에 대한 자르기(Clipping)의 형태는 원 모양입니다. 이 원을 위한 반경값으로 사용할 radius 변수와 키보드를 통해 이 radius 변수를 증가하고 감소하는 키 입력 이벤트를 지정합니다. 코드는 아래와 같습니다.

var radius = 100;

document.addEventListener('keydown', function (evt) {
    if (evt.which === 38) { // Up Key
        radius = Math.min(radius + 5, 200);
        map.render();
        evt.preventDefault();
    } else if (evt.which === 40) { // Down Key
        radius = Math.max(radius - 5, 25);
        map.render();
        evt.preventDefault();
    }
});

위의 코드에서, radius 변수값을 증가시키고 감소시키는 키를 입력할때마다 map 객체에 대한 render함수가 호출되고 있습니다. 이 render 함수는 다음과 같은 실행 흐름을 갖습니다.

먼저 precompose 이벤트가 발생하는데, 이 이벤트는 레이어를 그리기(Drawing) 직전에 발생합니다. 그 다음은 실제로 레이어 그리기(Layer Drawing)가 실행됩니다. 레이어 그리기가 완료되면 postcompose 이벤트가 호출됩니다. 이러한 3 단계는 각 레이어마다 반복됩니다. 또 여기서 중요한점은 이 3 단계가 실행되기에 앞서 지도 데이터를 서버측에 요청하여 받게 되는 것이지 이 3 단계 안에서 서버측으로부터 지도 데이터를 받는 것이 아닙니다. 이 3단계에서 imagery 레이어를 원 모양으로 자르기 위해서 주목해야할 이벤트는 레이어가 그려지기 전인 precompose 이벤트입니다. 아래는 imagery 레이어에(지도가 아닌) precompose 이벤트를 지정하는 코드입니다.

imagery.on('precompose', function (event) {
    var ctx = event.context;
    var pixelRatio = event.frameState.pixelRatio;
    ctx.save();
    ctx.beginPath();
    
    if (mousePosition) {
        ctx.arc(mousePosition[0] * pixelRatio, mousePosition[1] * pixelRatio,
            radius * pixelRatio, 0, 2 * Math.PI);
        ctx.lineWidth = 5 * pixelRatio;
        ctx.strokeStyle = 'rgba(255,255,0,1)';
        ctx.stroke();
    }
    
    ctx.clip();
});

위의 코드를 살펴보면, 2번에서 레이어를 그릴 컨텍스트를 얻어와 ctx 변수에 저장합니다. 그리고 3번에서는 현재 지도에 대한 픽셀 비율값을 가져와 pixelRatio 변수에 저장하고 있습니다. 4번ㅡ15번의 코드가 원 모양으로 자르기(Clipping) 하는 코드입니다. 코드를 부면 mousePosition 변수가 보이는데요. 이 변수는 마우스를 지도 위에서 움직일때 현재 마우스 커서의 좌표를 담게 됩니다. 이를 위해서 마우스 이벤트 지정이 필요한데요. 아래의 코드와 같습니다. 잘라내기(Clipping)의 모양을 지정하기 위해 컨텍스의 arc 함수를 호출하고 있는데요. 중심 좌표 및 반경에 대한 인자값 모두에 pixelRatio 값을 곱해주고 있습니다. 이 pixelRatio는 모니터 화면에 대한 물리 픽셀(physical Pixels)와 장치독립적인 픽셀(device-independent pixels)의 비(ratio) 값입니다.

var mousePosition = null;

container.addEventListener('mousemove', function (event) {
    mousePosition = map.getEventPixel(event);
    map.render();
});

container.addEventListener('mouseout', function () {
    mousePosition = null;
    map.render();
});

또한 postcompose 이벤트의 지정도 필요합니다. 이 이벤트는 레이어가 그려지고 난 뒤에 호출되는 이벤트인데요. 앞서 precompose 이벤트에서 수행한 잘라내기(Clipping)를 무효화해줍니다. 코드는 아래와 같습니다.

imagery.on('postcompose', function (event) {
    var ctx = event.context;
    ctx.restore();
});

이제 실행해보면, 레이어 스파이 기능이 작동되는 것을 확인할 수 있습니다. 아래는 지금까지에 대한 전체 코드입니다.