[그래프 데이터베이스][무작정해보기] [7/30] A*(A-star) Algorithm Neo4j에서 실행해보기

 

들어가기 전에

복습하기

2021/01/10 - [30일 프로젝트/Graph DB] - [그래프 데이터베이스][무작정해보기] [6/30] A*(A-star) Algorithm 그림으로 이해하기.

[그래프 데이터베이스][무작정해보기] [6/30] A*(A-star) Algorithm 그림으로 이해하기.

바쁘다면 한줄요약

A* 알고리즘은 다음과 같은 f(n)값을 최소화하는 방식으로 작동합니다.

$f(n) = g(n) + h(n)$
$g(n) = 현재 노드까지 cost의 합$
$h(n) = 현재 노드에서 도착점까지 직선거리$

위의 식을 생각해 보면 아래에 속성들이 왜 필요한지 유추할 수 있습니다.

---

교재에 나온 코드 실행해보기

기본 속성값 이해

$startNode $
 The node where our shortest path search begins. 최단경로를 탐색하는 시작 노드 

$endNode $
 The node where our shortest path search ends. 최단경로를 탐색하는 도착 노드

$nodeProjection $
 Enables the mapping of specific kinds of nodes into the in-memory graph. We can declare one or more node labels. 인메모리 그래프에 실행시킬 특정한 종류의 노드들의 매핑을 활성화한다. 하나 또는 여러개의 노드 라벨을 선언할 수 있음.

$relationshipProjection $
 Enables the mapping of relationship types into the in-memory graph. We can declare one or more relationship types along with direction and properties. 인메모리 그래프에 실행시킬 특정한 종류의 관계들의 매핑을 활성화한다.하나 또는 여러개의 관계 라벨을 선언할 수 있음.

$relationshipWeightProperty $
 The relationship property that indicates the cost of traversing between a pair of nodes. The cost is the number of kilometers between two locations. 노드 한쌍 사이를 횡단하는데 소요되는 비용인 관계 속성을 가르킴. 비용은 두 위치 사이의 거리 킬로미터임

$propertyKeyLat$
 The name of the node property used to represent the latitude of each node as part of the geospatial heuristic calculation. 지리공간 경험적 계산의 일부로서 각 노드의 위도를 나타내기 위해 사용된 노드 속성의 이름
$propertyKeyLon $
 The name of the node property used to represent the longitude of each node as part of the geospatial heuristic calculation. 지리공간 경험적 계산의 일부로서 각 노드의 경도를 나타내기 위해 사용된 노드 속성의 이름

지난 Dijkstra(다익스트라, 데이크스트라) 알고리즘과 비교해봤을때 Lat(위도),Lon(경도)값이 추가된 것을 볼 수 있습니다. 이는 알고리즘의 공식에서 $h(n)$ 값, 즉 해당 노드와 도착점까지 거리를 구하기 위해서 필요합니다. 복잡한 계산식은 알고리즘이 보여주지 않으니 실행해보도록 합시다.

 

교재에 나온 코드

MATCH (source:Place {id: "Den Haag"}),
       (destination:Place {id: "London"})
CALL gds.alpha.shortestPath.astar.stream({
	startNode: source,
	endNode: destination,
	nodeProjection: "*",
	relationshipProjection: {
		all: {
			type: "*",
			properties: "distance",
			orientation: "UNDIRECTED"
 		}
 	},
	relationshipWeightProperty: "distance",
	propertyKeyLat: "latitude",
	propertyKeyLon: "longitude"
	})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;

입력하고, 오른쪽 위의 파란 화살표를 누릅니다.

결과

처참한 결과

오류 메세지를 보겠습니다.

Neo.ClientError.Procedure.ProcedureCallFailed
Failed to invoke procedure `gds.alpha.shortestPath.astar.stream`: Caused by: java.lang.NullPointerException

자바를 많이 해보신 분들은 보셨겠지만 NullPointerException이 떴습니다. 이 오류가 뜨는 이유는 쉽게 "너가 찾고자 하는 값이 없다" 입니다. 제가 몇가지 코드를 쓰며 고쳐보며 봤을때, 문법 자체는 오류가 없지만 돌려본 결과 너가 찾는 값은 없다 라는 뜻으로 해석하면 될것 같습니다. 코딩은 항상 왜 안되지와 왜 되지의 연속입니다. 해결해보도록 합시다.

---

코드 수정하기

결론적으로 nodeProjection 부분만 수정하면 됩니다. 

참고한 코드

Neo4j 공식 사이트 중 '4.2 Native projection' 부분¹

MATCH (start:Station {name: 'King\'s Cross St. Pancras'}), (end:Station {name: 'Kentish Town'})
CALL gds.alpha.shortestPath.astar.stream({
  nodeProjection: {
    Station: {
      properties: ['longitude', 'latitude']
    }
  },
  relationshipProjection: {
    CONNECTION: {
      type: 'CONNECTION',
      orientation: 'UNDIRECTED',
      properties: 'time'
    }
  },
  startNode: start,
  endNode: end,
  propertyKeyLat: 'latitude',
  propertyKeyLon: 'longitude'
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).name AS station, cost

 위의 코드 중 nodeProjection 부분이 다른것을 볼 수 있습니다.

  nodeProjection: {
    Station: {
      properties: ['longitude', 'latitude']
    }
  }

nodeProjection: "*",

 책에 써있는 코드 예시의 경우, "*"로 표시되어 있는데, 이는 모든 노드들을 선택한다는 뜻일 겁니다. 이 nodeProjection에 관한 부분을 이해해보려고 했지만, 아직은 무리인것 같습니다. 우선 이해한 수준에서 얘기한다면, 위의 station의 경우 노드 들 중 Station의 속성중 'longitude'와 'latitude'를 불러와라. 정도로 이해할 수 있으며, 아래

propertyKeyLat: 'latitude', 

propertyKeyLon: 'longitude'

에서 위의 결과값을 가져온다고 보면 될 것 같습니다. 

코드수정

MATCH (source:Place {id: "Amsterdam"}),
	(destination:Place {id: "London"})
CALL gds.alpha.shortestPath.astar.stream({
	startNode: source,
	endNode: destination,
	nodeProjection: {
		Place: {
			properties: ['longitude', 'latitude']
		}
	},
	relationshipProjection: {
		all: {
			type: "*",
			properties: "distance",
			orientation: "UNDIRECTED"
		}
	},
    	relationshipWeightProperty: "distance",
        propertyKeyLat: "latitude",
        propertyKeyLon: "longitude"
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId).id AS place, cost;

nodeProjection 부분을 수정하고 실행해보겠습니다.

---

최종 실행 결과 및 시각적 표현

실행 부분. nodeProjection을 바꾼것을 볼 수 있음.

실행결과

테이블 뷰로 봤을때

	place	cost
1	"Amsterdam"	0.0
2	"Den Haag"	59.0
3	"Hoek van Holland"	86.0
4	"Felixstowe"	293.0
5	"Ipswich"	315.0
6	"Colchester"	347.0
7	"London"	453.0

 이제 정상적으로 작동하는 것을 볼 수 있습니다. 그럼 그래프에서 다시 한번 표시해보겠습니다.

시각적으로 표현하면 다음과 같습니다.

끝맺으며

다음과 같은 사항을 좀더 잘 알았더라면 좋았을것 같습니다.

• Projected Graph와 Neo4j Graph 차이
• nodeProjection에 대한 이해
• Neo4j의 native projection과 Cypher projection 응용

다음엔 또 다음장 내용으로 찾아오겠습니다.

참고자료 및 풋노트

---

Neo4j Graph Data Science 6.5.5

1. 6.5.5. A* ↩︎