회전 제한 및 양방향 성질을 가진 네트워크 DB를 활용한 A* 알고리즘

실제 도로망은 U턴 제한이나 우회전 제한 등과 같은 회전 제한에 대한 성질과 좌측 및 우측 차로에 대한 방향에 대한 성질을 가집니다. 이러한 성질에 대한 속성값을 가지는 네트워크 데이터는 지능형 교통체계 표준 노드링크 관리시스템(http://nodelink.its.go.kr)에서 제공하고 있습니다.

이 글은 지능형 교통체계 표준 노드링크 관리시스템에서 제공하는 네트워크 DB에 대해 A* 알고리즘을 적용하는 각 단계별 과정에 대한 상태정보를 기록한 자료에 대한 글입니다. A*에 대한 자세한 설명은 기존의 최단 경로 탐색 – A* 알고리즘이라는 글을 참고하시기 바랍니다. 본 글은 A* 알고리즘을 확장하고 응용한 글이므로 반드시 A* 알고리즘을 완전하게 이해하고 있는 상태에서만 의미있게 이해될 수 있는 글이라는 점을 알려드립니다.

해결하고자 하는 네트워크 DB에서의 최적경로에 대한 문제는 아래 그림과 같습니다.

위의 문제에 대해 확장된 A* 알고리즘을 통해 최종적으로 도출된 그 결과는 아래의 그림과 같습니다.

해결하고자 하는 문제와 그 결과 도출을 위한 알고리즘의 각 단계를 정리한 내용은 아래의 pdf 파일에 담겨 있습니다.

Java에서 HashMap을 위한 Custom Key 정의하기

Java의 HashMap 자료구조는 고유한 값인 Key와 1:1로 연관되는 값(Value)을 하나의 쌍(Pair)로 하여 여러 개의 쌍을 저장하는 자료구조입니다. 흔히 Key 값으로 문자열이나 정수값을 사용하는 것으로도 충분합니다. 그러나 기능에 따라서 개발자가 특별한 Key에 대한 타입을 정의해야할 필요가 있습니다.

만약 개발자가 Key 타입으로 아래와 같은 클래스를 정의했다고 합시다.

public class Identifier {
    private long A;
    private long B;
    private long C;
	
    public Identifier(long A, long B, long C) {
        this.A = A;
        this.B = B;
        this.C = C;
    }
}

그리고 위의 Identifier 클래스를 Key로 하는 HashMap을 사용하는 코드를 아래와 같이 작성했다고 합시다.

HashMap<Identifier, String> map = new HashMap<Identifier, String>();
		
Identifier id1 = new Identifier(1,2,3);
map.put(id1, "White");
		
Identifier id2 = new Identifier(2,1,3);
map.put(id2, "Yellow");
		
Identifier id3 = new Identifier(2,1,3);
map.put(id3, "Red");
		
System.out.println(map.get(id2));

Key로써의 Identifier 클래스의 동일성을 Identifier가 가지는 3개의 필드인 A, B, C의 동일함으로 정의한다고 할때, 두개의 Identifier 객체 o1, o2가 있다고 한다면 o1과 o2가 같을 조건은 o1.A == o2.A && o1.B == o2.B && o1.C == o2.C라고 할 수 있습니다. 이러한 정의대로라면 위의 코드의 결과는 new Identifier(2,1,3)으로 생성된 객체 중 가장 마지막으로 저장된 “Red” 문자열을 출력해야 하는데, “Yellow”를 출력하게 됩니다. 그렇다면 원하는 결과를 얻기 위해서 무엇을 해야 할까요?

HashMap의 Key 타입으로써 기능을 충족하기 위해서는 Object 클래스의 equals와 hashCode 함수를 재정의해야 합니다. 아래가 Identifier 클래스에 이 2개의 함수를 재정의한 전체 코드입니다.

import java.util.Objects;

public class Identifier {
    private long A;
    private long B;
    private long C;
	
    public Identifier(long A, long B, long C) {
        this.A = A;
        this.B = B;
        this.C = C;
    }
	
    @Override
    public boolean equals(Object o) {
        if(this == o) return true;	
        if(o == null || getClass() != o.getClass()) return false;
		
        Identifier other = (Identifier)o;
		
        return other.A == A && other.B == B && other.C == C;
    }
	
    @Override
    public int hashCode() {
        int result = (int)(A ^ (A >>> 32));
        
        result = 31 * result + (int)(B ^ (B >>> 32));
        result = 31 * result + (int)(C ^ (C >>> 32));
		
        return result;
    }
}

위의 equals 함수는 앞서 설명한 동일성에 대한 정의를 코드로 작성한 것입니다. hashCode 함수는 최대한 중복되지 않고 다양한 값을 반환할 수 있어야 함과 동시에 같은 값이라고 한다면 같은 hashCode 값을 반환해야 합니다. 즉, new Identifier(2,1,3)를 2번 호출하여 2개의 객체를 생성했다면 이 2개의 객체에 대한 hashCode 함수의 반환값은 같아야 합니다. 이러한 조건을 최대한 수용할 수 있도록 작성했다고 작성한게 위의 hashCode 함수의 구현입니다만… 이게 애매한지라 hashCode 함수에 대해서만큼은 아래의 코드로 대체할 수 있습니다.

@Override
public int hashCode() {
    return Objects.hash(A, B, C); // import java.util.Objects; 가 필요함
}

이제 실행해 보면, 우리가 원하는 결과를 얻을 수 있습니다. 이상으로 HashMap에 대한 Custom Key 타입을 정의하는 방식에 대한 정리였습니다.

jetty를 이용한 WebSocket 서버 구현하기

어플리케이션에 Servlet Container 이외도 여러가지 서버 기능을 내장할 수 있는 jetty 라이브러리를 이용해 WebSocket 서버를 구현하는 코드에 대한 뼈대를 정리한다. WebSocket는 HTML5에서 지원하는 기능으로 서버와 클라이언트는 연결되어 있는 상태에서 상호간에 데이터를 주고니 받거니 할 수 있는 기술이다. WebSocket은 그 막강한 통신 기능에 비해 서버와 클라이언트의 코드가 매우 작다. 그래서인지 뭔가 부족한 느낌이 드는데, 일단 기본적인거 정리하고 부족한 느낌이 드는 이유는 나중에 파악해 보자.

먼저 서버 단의 코드이다. Server를 구동하는 클래스와 WebSocket를 통해 접속하는 클라이언트를 나타내는 Session 범위의 클래스인데, 먼저 Server를 구동하는 클래스는 아래와 같다.

import org.eclipse.jetty.server.Server;
import org.eclipse.jetty.server.handler.ContextHandler;
import org.eclipse.jetty.websocket.server.WebSocketHandler;
import org.eclipse.jetty.websocket.servlet.WebSocketServletFactory;

public class test_webSocket {
    public static void main(String[] args) {
        Server server = new Server(8080);
		
        WebSocketHandler wsHandler = new WebSocketHandler() {
            @Override
            public void configure(WebSocketServletFactory factory) {
                factory.register(MyEchoSocket.class);
            };
        };

        ContextHandler context = new ContextHandler();
        context.setContextPath("/echoServer");
        context.setHandler(wsHandler);
		
        server.setHandler(context);

        try {
            server.start();
            server.join();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

그리고 다음은 서버에 접속하는 클라이언트(Session 객체로 구분) 마다 생성되는 Echo 기능을 갖는 MyEchoSocket 클래스이다.

import org.eclipse.jetty.websocket.api.Session;
import org.eclipse.jetty.websocket.api.WebSocketListener;

public class MyEchoSocket implements WebSocketListener {
    private Session outbound;
	
    public MyEchoSocket() {
        System.out.println("class loaded " + this.getClass());
    }

    @Override
    public void onWebSocketConnect(Session session) {
        this.outbound = session;		
    }

    @Override
    public void onWebSocketError(Throwable cause)
    {
        cause.printStackTrace(System.err);
    }

    @Override
    public void onWebSocketText(String message)
    {
        if ((outbound != null) && (outbound.isOpen()))
        {
            String echoMessage = outbound.hashCode() + " : " + message;
            outbound.getRemote().sendString(echoMessage, null);
        }
    }

    @Override
    public void onWebSocketBinary(byte[] payload, int offset, int len)
    {
        //.
    }

    @Override
    public void onWebSocketClose(int statusCode, String reason)
    {    	
    	System.out.println("Close, statusCode = " + statusCode + ", reasone = " + reason);
        this.outbound = null;
    }	
}

요즘 웹이 그렇듯이 WebSocket 기술은 Binary 데이터도 주고 받을 수 있다는 것을 알 수 있다. 중요한 것은 클라이언트 하나가 접속을 하면 위의 클래스가 매번 생성된다는 것이고, 클라이언트는 Session 객체를 통해 나타내지며, 이 객체를 통해 데이터를 주고 받을 수 있다.

서버를 살펴봤으니, 이제 클라이언트 코드를 살펴보면..




    
    


    

위의 13번 부분에 들어가는 js 코드는 다음과 같다.

        var webSocket = new WebSocket("ws://localhost:8080/echoServer/");
        var msgField = document.getElementById("messageField");
        var divMsg = document.getElementById("msg-box");

        function sendMsg() {
            var msgToSend = msgField.value;

            webSocket.send(msgToSend);

            divMsg.innerHTML += "
Client> " + msgToSend + "
"; msgField.value = ""; } webSocket.onmessage = function (message) { divMsg.innerHTML += "Server> : " + message.data; } webSocket.onopen = function () { alert("connection opened"); } webSocket.onclose = function () { alert("connection closed"); } webSocket.onerror = function (message) { alert("error: " + message); }

서버를 기동한 뒤, 클라이언트를 실행하고 메세지를 날리면, 해당 메세지가 메아리로 돌아오는 것을 볼 수 있다.

도로명주소DB의 도로중심선을 활용한 최단거리 기능 소개

도로명주소DB에는 도로중심선이 있습니다. 예전에 도로중심선을 네트워크 DB로 가공하는 글을 포스팅한 적이 있었는데요. 찾으시는 분을 위해 주소를 정리하면 아래와 같습니다.

도로중심선만으로 네트워크 데이터 구축하기 ㅡ 1/3
도로중심선만으로 네트워크 데이터 구축하기 ㅡ 2/3
도로중심선만으로 네트워크 데이터 구축하기 ㅡ 3/3

아울러 이러한 네트워크 DB를 이용하는 알고리즘 중에 하나인 최단경로를 탐색하는 A*에 대해 정리하는 글은 아래와 같습니다.

최단 경로 탐색 – A* 알고리즘

이러한 과거의 작업 내용을 토대로 두 지점간의 최단 경로를 분석해 그 결과를 제공하는 서비스를 개발하였고, 기능에 대한 실행이 아래의 동영상입니다.

사실, 도로명주소DB의 도로중심선만으로 길찾기 서비스를 개발하는 것은 충분하지만, 길찾기 서비스의 품질으로써 도로중심선은 추가적인 보완이 필요합니다. 도보용으로는 적당하지만, 차량용과 같이 보다 더 나은 서비스 개발을 위해서는 나라에서 제공하는 표준 노드/링크 데이터를 활용하는 것을 권장합니다. 그럼에도 도로명주소DB의 도로중심선을 이용한 최단 경로를 개발한 이유는 상수관, 하수관, 가스관, 전력선, 통신선 등과 같은 설비들의 관망 해석에 대한 기반 기술 마련입니다. 이러한 관망은 최단경로라는 의미보다는 어떤 조건을 만족하는 관망을 탐색하여야 하는데, 어떠한 조건에 대한 과제를 “최단거리”라고 정한 것 뿐입니다. A*라는 알고리즘을 이해하고 구현함으로써 이를 응용하고 확장해 어떠한 조건에서의 관망이라도 탐색할 수 있습니다.

FingerEyes-Xr에서 WKT 문자열로부터 GraphicRow 생성하기

서버 측으로부터 뭔가를 요청해서 얻은 결과가 Geometry 일때, 그 Geometry의 형식은 WKT가 가장 일반적입니다. WKT는 Well-Known Text의 약자입니다.

예를 들어, 두 개의 좌표 사이의 최단경로에 대한 결과로써, Polyline 형태로 경로에 대한 연속된 좌표 리스트값을 WKT로 요청하는 서비스 호출이 아래와 같다고 합시다.

var url = "http://localhost/Gp?command=wlkroute;start=(132648 283024);end=(155054 243212);db=gdb";

위의 요청에 대한 결과는 두 지점간의 최단경로에 대한 연속된 좌표값을 가지는 WKT 형식입니다. 이런 WKT 형식의 데이터를 지도 상에 시각화 하기 위해 FingerEyes-Xr에서 그래픽 요소로 추가하고자 한다면.. 아래와 같은 코드를 적용할 수 있습니다.

var url = "http://localhost/Gp?command=wlkroute;start=(132648 283024);end=(155054 243212);db=gdb";
$.ajax({
    url: url,
    dataType: "text",
    type: "GET",
    statusCode: {
        200: function (response) {
            response = JSON.parse(response);
            var wkt = response.wkt;

            var map = ...;
            var layers = map.layers();
            var lyrName = "gl_route";
            var grp = new Xr.layers.GraphicLayer(lyrName);

            layers.remove(lyrName);
            layers.add(grp);

            var rs = grp.rowSet();
            var psd = new Xr.data.PolylineShapeData([[]]);

            psd.fromWKT(wkt);

            var pgr = new Xr.data.PolylineGraphicRow(0, psd);
            pgr.penSymbol().width(10).color("red").opacity(0.5);

            rs.add(pgr);

            var mbr = psd.MBR();
            map.coordMapper().zoomByMBR(mbr);
            map.update();
        }
    }
});

9번 코드가 서버단에서 받아온 WKT 문자열이고, 이 문자열을 22번 코드에서처럼 그래픽 요소의 좌표값으로 해석하기 위해 fromWKT 함수를 사용합니다. 여튼.. 이러한 서버단에서 보내온 WKT 형식의 지오메트리에 대한 시각화의 예제 화면은 아래와 같은데요.

위의 화면은 두 지점에 대한 최단 경로입니다.