AGE에서 Cypher로 발생시킨 그래프 탐색

 

AGE에서 Cypher로 발생시킨 Graph를 Application단에서 알고리즘을 

사용하여 (다중) ShortestPath 및 모든 경로 구하기

 

 

개요 

Application단에서 알고리즘을 사용하여 age에서 실행시킨 Cypher의 ShortestPath 구해보려 고한다. 

이를 구하는 이유는 AgensGraph에는 최단경로를 찾는 Function이 존재하지만 AGE에서는 최 단경로를 찾는 Function이 존재하지 않는 것으로 알고 있다. 

그러므로 Application 단에서 AGE의 최단 경로의 정보를 조회할 수 있는 알고리즘을 만들어 보았다. 

참고로 Application 단에서 사용한 언어는 Typescript이다. 

우선 Cypher를 발생시킬 때 Node(노드)와 Edge(간선)을 조회할 수 있는 형태로 Cypher를 실 행시 켜야 한다. 

AGE에서 Cypher로 조회한 Graph에서 다음 3가지의 경우를 구할 예정이다. 1. 하나의 최단경로 

2. 모든 최단경로 

3. 모든 경로 

위 3가지 경우를 어떤 알고리즘을 통해서 구할지 알아보자 

Application 단에서 

하나의 최단경로와 모든 최단경로는 BFS를 활용하는 것이 좋다. 

BFS(Breadth-first search : 너비 우선 탐색)를 사용하면 다음과 같은 장점이 있다. 너비를 우선으로 탐색하므로 답이 되는 경로가 여러 개인 경우에도 최단경로를 얻을 수 있다. 경로가 무한히 깊어져도 최단경로를 반드시 찾을 수 있다. 

노드 수가 많지 않고 깊이가 얕은 해가 존재할 때 유리하다. 

그러므로 위 조건이 그래프에서 최단 경로 그래프를 찾을 때 충분히 괜찮은 조건이라고 볼 수 있다.. 즉, BFS는 너비 우선 탐색이기 때문에 최단경로를 찾기에 적합하다. 

모든 경로를 찾기 위해서는 BFS보다는 DFS알고리즘을 사용하는 것이 더 좋다. DFS(Depth First Search : 깊이 우선 탐색)를 사용하면 다음과 같은 장점이 있다. 현 경로상의 노드들만 기억하면 되므로 저장공간 수요가 비교적 적다.

 

목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 

그러므로 위 조건이 그래프에서 모든 경로를 찾을 때 충분히 괜찮은 조건이라고 볼 수 있다. 즉, DFS는 깊이 우선 탐색이기 때문에 모든 경로를 찾기에 적합하다. 

최단 경로를 찾을 때 From노드와 To노드가 있으면 단방향으로 경로를 찾겠을 조건으로 한다. Application 단에서는 BFS로 경로를 탐색한다면 인접리스트와 인접행렬을 사용할 수 있다. 인접리스트는 BFS로 시간 복잡도가 O(V + E)가 나온다. 

인접 행렬은 BFS로 시간 복잡도가 O(V^2)가 나오는데 너무 많은 시간이 걸려서 사용하지 않았다. 

 

V : Vertex = 정점(노드) 

E : Edge = 간선(에지) 

3가지 경우 전부 Cypher(사이퍼) 쿼리를 조회해서 인접리스트 정보를 담았다. 

기존 BFS 예제를 서치 해보면 전부다 startNode부터 endNode까지의 최단 경로만 출력을 하는 데 

최단 경로의 노드 정보와 간선 정보를 따로 구하는 경우 예제는 찾아보기 힘들다. 나는 BFS를 사용하여 최단 경로의 노드 정보와 간선 정보를 모두 구하는 코드를 작성해 보았다. 

우선 인접리스트를 사용하는 경우 AGE의 Cypher 조회 정보를 알아보자 

SELECT * FROM cypher('graphizer_exp_test', $$ 

MATCH (v1)-[e]->(v2) 

RETURN v1, e, v2 

$$) AS (v1 agtype, e agtype, v2 agtype); 

먼저 AGE에서 위 Cypher로 조회한 쿼리의 결과를 보면 다음과 같은 형식을 가진다. 

{"id": 844424930132006, "label": "Person",  "properties": {"age": 20, "name": "Tom", "height": 172}}::vertex

{"id": 2251799813685256, "label":  "Reviewd", "end_id": 2533274790395913, "start_id": 844424930132006, "properties": {"rating": 9.0, "summary": "통쾌합니다 ~"}}::edge

{"id":  2533274790395913,  "label": "Drama",  "properties": {"title": "The Glory1", "release":  2022}}::vertex

물론 Cypher 쿼리로 위와 같은 형식이 아니라 단순히 id나 property에 있는 컬럼 하나의 값만 조 회할 수 도 있다. 하지만 시각적으로 그래프를 조회하기 위해서는 위와 같은 JSON 형식으로 조회를 해야 한다.

 

 

인접리스트를 사용할 경우 아래 자료구조를 사용한다. 

type Edge = { 

edge_id: string; 

sv_id: string; 

tv_id: string; 

weight: number; // 가중치 정보 (AGE에서는 가중치가 없지만 일반적인 다익스트라 알고리즘에 활용하기 위해 포함) }; 

type ShortestPathResult = { 

distance: number; 

nodeIds: string []; // 최단 경로 노드들의 배열 

edgeIds: string[]; // 최단 경로 에지들의 배열 

}; 

 

1. 하나의 최단 경로를 찾는 경우 (oneShortestPath) 

중요한 것은의 Cypher를 발생시켜서 나온 결과를 Application 단에서 Cypher의 결과를 인접리스트로 잘 저장하는 것이 중요하다. 

아래 코드에서는 AGE에서 Cypher를 실행시켰을 때 Vertex(정점 : 노드)와 Edge(간선)을 구분할 수 있는 것은 propertydml start_id와 end_id의 여부이다. 이것으로 노드와 간선을 구분하여 인접리스트로 저장한다. 

인접리스트로 저장만 한다면 O(V + E)의 실행 시간을 기대할 수 있다. 

// 기존의 인접 리스트를 저장할 변수 

let adjacencyList: Record<string, Edge[]> = {}; 

// tmpCypherResult.rows를 순회하면서 인접 리스트에 데이터를 추가 

tmpCypherResult.rows.forEach((row) => { 

// row 객체의 프로퍼티들을 순회하며 동적으로 키 값을 추출 

// 단방향 성공 

Object.keys(row).forEach((key) => { 

const value = row[key]; 

// vertex인 경우 

if (!('start_id' in value) && !('end_id' in value)) { 

const nodeId = value.id.toString(); 

// 시작 노드가 인접 리스트에 없는 경우, 빈 배열로 초기화 

if (!adjacencyList[nodeId]) { 

adjacencyList[nodeId] = []; 

} 

} 

// edge인 경우 

if ('start_id' in value && 'end_id' in value) { 

const edgeId = value.id.toString(); 

const startNode = value.start_id.toString(); 

const endNode = value.end_id.toString();

 

// 시작 노드가 인접 리스트에 없는 경우, 빈 배열로 초기화 

if (!adjacencyList[startNode]) { 

adjacencyList[startNode] = []; 

} 

// 각 노드의 인접한 엣지들을 인접 리스트에 추가 

adjacencyList[startNode].push({ 

edge_id: edgeId, 

sv_id: startNode, 

tv_id: endNode, 

weight: 1, 

}); 

} 

}); 

}); 

위 코드처럼 Cypher의 결과를 인접리스트로 사용할 수 있게끔 코드를 작성했다. 해당 코드는 인접리스트에서 BFS를 사용한 코드이다. 

방문한 노드는 다시 방문하지 않는다. 

그러므로 O(V+E) 의 시간 복잡도를 갖는다. 

그 이유는 인접리스트를 사용한 BFS의 구현 방식이 다음과 같기 때문이다. 

 

1. 시작 노드를 큐에 넣고 방문 표시(visited)한다. 

2. 큐가 비어있지 않은 동안 다음을 반복한다. 

a. 큐에서 하나의 노드를 꺼내어 해당 노드를 현재 노드로 설정한다. 

b. 현재 노드와 연결된 모든 인접 노드들 중에서 아직 방문하지 않은 노드를 큐에 넣고 방문 표시한다. 

이때, 각 노드는 최대 한 번씩 큐에 가기 때문에 각 노드에 대한 방문 시간은 상수 시간이 소요된 다. 

인접리스트를 사용할 때 각 노드의 인접한 노드들을 찾는 데 걸리는 시간은 그래프의 구현 방식에 따라 다르지만, 일반적으로 선형 시간인 O(E)가 걸린다. 이는 모든 간선을 한 번씩만 검사하면서 인접한 노드들을 확인하므로 선형 시간 복잡도를 가진다. 

따라서 인접리스트를 사용한다면 BFS 알고리즘의 전체 시간 복잡도는 O(V + E)가 된다. 아래 코드는 하나의 최단경로를 찾는 BFS 알고리즘 코드이다. 

// 하나의 최단경로의 노드 id, 에지 id를 찾는 알고리즘, 인접리스트 - BFS - 큐(queue) 

async findOneShortestPathByAdjList( 

adjacencyList: Record<string, Edge[]>, 

startNodeId: string, 

targetNodeId: string,

 

 

) { 

const queue: { currentNodeId: string; path: ShortestPathResult }[] = []; const visited: Record<string, boolean> = {}; 

// 시작 노드를 큐에 추가 

queue.push({ 

currentNodeId: startNodeId, 

path: { 

distance: 0, 

nodeIds: [startNodeId], 

edgeIds: [], 

}, 

}); 

while (queue.length > 0) { 

const { currentNodeId, path } = queue.shift()!; // 큐 삭제 : dequeue 

visited[currentNodeId] = true; 

// 현재 노드에서 이동 가능한 모든 에지들을 확인 (키 값 : currentNodeId 이 존재하지 않으면 빈 배열[]을 반환) const edgesFromCurrentNode = adjacencyList[currentNodeId] || []; 

for (const edge of edgesFromCurrentNode) { 

const nextNodeId = edge.tv_id; // adjacent NodeId(tv_id가 인접 노드이다!!) const totalDistance = path.distance + 1; // BFS이므로 항상 거리는 1 증가 

// 방문하지 않은 노드이면 큐에 노드를 추가하고 방문처리한다. 

if (!visited[nextNodeId]) { 

const newPath: ShortestPathResult = { 

distance: totalDistance, 

nodeIds: [...path.nodeIds, nextNodeId], 

edgeIds: [...path.edgeIds, edge.edge_id], 

}; 

queue.push({ 

currentNodeId: nextNodeId, 

path: newPath, 

}); 

// 목표 노드에 도달한 경우 최단 경로 반환 

if (nextNodeId === targetNodeId) { 

return newPath; 

} 

} 

} 

} 

// 목표 노드에 도달하지 못한 경우 빈 결과 반환 

return { 

distance: 0, 

nodeIds: [], 

edgeIds: [], 

}; 

}

 

 

2. 모든 최단 경로를 찾는 경우(AllShortestPath) 

Cypher로 인접리스트에 담는 코드는 하나의 최단경로를 찾는 경우와 유사하다. 

BFS 모든 최단 경로를 찾는 코드이다. BFS로 allShortestPaths 탐색해서 마지막에 allShortestPaths에. 

이 또한 시간 복잡도가 O(V+ E)가 나온다. 

아래 코드는 모든 최단 경로를 찾는 BFS 코드이다. 

async findAllShortestPathByAdjList( 

adjacencyList: Record<string, Edge[]>, 

startNodeId: string, 

targetNodeId: string, 

) { 

const queue: { currentNodeId: string; path: ShortestPathResult }[] = []; const allShortestPaths: ShortestPathResult[] = []; 

const visited: Record<string, boolean> = {}; 

// 시작 노드를 큐에 추가 

queue.push({ 

currentNodeId: startNodeId, 

path: { 

distance: 0, 

nodeIds: [startNodeId], 

edgeIds: [], 

}, 

}); 

while (queue.length > 0) { 

// ... 하나의 최단 경로 찾기와 동일한 코드 

for (const edge of edgesFromCurrentNode) { 

// ... 하나의 최단 경로 찾기와 동일한 코드 

if (!visited[nextNodeId]) { 

// ... 하나의 최단 경로 찾기와 동일한 코드 

// 목표 노드에 도달한 경우 최단 경로 반환 

if (nextNodeId === targetNodeId) { 

allShortestPaths.push(newPath); 

} 

} 

} 

} 

const shortestDistance = allShortestPaths.reduce( 

(minDistance, path) => Math.min(minDistance, path.distance), 

Infinity, 

); 

const shortestPaths = allShortestPaths.filter( 

(path) => path.distance === shortestDistance, 

); 

if (shortestPaths.length === 0) { 

return { 

distance: 0,

 

nodeIds: [], 

edgeIds: [], 

}; 

} 

// 목표 노드에 도달하지 못한 경우 빈 결과 반환 

return shortestPaths; 

} 

3. 모든 경로를 찾는 경우(AllPath) 

Cypher로 인접리스트에 담는 코드는 DFS를 재귀적(recursive)으로 구현했다. 다음은 DFS로 최단 경로가 아니라 모든 경로를 찾는 코드이다. 

모든 경로를 찾기 위해서 목표노드에 도달한 경우 종료하지 않고 결과 배열에 추가한다. 이 또한 시간 복잡도가 O(V + E)가 나온다. 

아래 코드는 모든 경로를 찾는 DFS 코드이다. 

async findAllPathByAdjListByDFS( 

adjacencyList: Record<string, Edge[]>, 

startNodeId: string, 

targetNodeId: string, 

) { 

const allPaths: ShortestPathResult[] = []; 

const visited: Record<string, boolean> = {}; 

function dfs(currentNodeId: string, path: ShortestPathResult) { 

visited[currentNodeId] = true; 

const edgesFromCurrentNode = adjacencyList[currentNodeId] || []; 

for (const edge of edgesFromCurrentNode) { 

const nextNodeId = edge.tv_id; // adjacent NodeId 

if (!visited[nextNodeId]) { 

const newPath: ShortestPathResult = { 

distance: path.distance + 1, 

nodeIds: [...path.nodeIds, nextNodeId], 

edgeIds: [...path.edgeIds, edge.edge_id], 

}; 

if (nextNodeId === targetNodeId) { 

allPaths.push(newPath); 

} else { 

dfs(nextNodeId, newPath); 

} 

} 

} 

visited[currentNodeId] = false; // Reset the visited flag for backtracking }

 

dfs(startNodeId, { 

distance: 0, 

nodeIds: [startNodeId], 

edgeIds: [], 

}); 

if (allPaths.length === 0) { 

return { 

distance: 0, 

nodeIds: [], 

edgeIds: [], 

}; 

} 

return allPaths; 

} 

 

결론 

AGE로 발생시킨 사이퍼를 통해서 JSON형태로 칼럼을 조회하는 형식을 가지고 

Application 단에서 BFS로 하나의 최단 경로와 모든 최단 경로의 Node 정보와 Edge 정보를 구하고 DFS로 모든 경로의 Node 정보와 Edge 정보를 찾는 방법을 알아보았다. 

Agensgraph와 다르게 AGE에는 최단 경로를 구하는 Function이 없기 때문에 해당 코드를 만들었다. 

참고로 AGE에서 그래프의 Edge(간선) 가중치가 없기 때문에 모든 최단 경로 또는 모든 경로처 럼 다중 경로를 구할 때는 다익스트라 알고리즘을 사용하면 안 된다. 왜냐하면 다익스트라 알고리 즘은 가중치를 두고서 가중치의 합이 최소가 되는 최단 경로를 구하는 것이기 때문에 다중 간선에 대한 경로를 구할 수 없다. 또한 하나의 최단 경로를 구할 때도 가중치를 전부 동일하게 설정한 다 음에 최단 경로를 구하기 때문에 굳이 다익스트라 알고리즘을 사용하는 것보다 BFS를 사용하는 게 더 효율적이다. 

Graphizer처럼 AGE를 사용해서 경로를 보여줄 때 Application단에서 BFS와 DFS 알고리즘으 로 원하는 시작 노드에서 원하는 목적지 노드로의 하나의 최단경로, 모든 최단경로, 모든 경로를 모두 구할 수 있다. 

이는 하나의 최단경로, 모든 최단경로, 모든 경로의 Node정보와 Edge정보를 구할 때 인접리스트를 사용해서 O(V+E)의 시간 복잡도를 보장한다.

 

 

 

 

글 : 정택규 전임 ( 비트나인 R&D Lead팀 )