Neo4j에서 그래프 알고리즘: 깊이 우선 탐색

이 기사에 대하여

Neo4j를 사용한 그래프 알고리즘의 구현을 소개해 보자고 하는 계획 "그래프 알고리즘 입문 - java와 Neo4j에서 배우기 -" 의 일부입니다 (어디까지 계속할까・・・)

샘플 코드는 여기에 있다.

깊이 우선 탐색

그래프 탐색과 폭 우선 탐색에 대해서는 여기 다음으로, 깊이 우선 검색의 샘플 프로그램을 나타낸다. 이것은 Neo4j 프로 시저로 작성되었습니다. 프로 시저를 만드는 방법에 대해서는 이 기사에 설명했다. 입력으로서는 노드의 id를 받고, 출력에는, 도달한 노드와, 그 노드에 이르는 패스를 넣고 있다. 도달한 노드는 탐색에서 방문한 순서대로 모두 출력된다. 패스를 얻는 함수와 출력의 클래스에 대해서는 폭 우선 탐색의 기사에 있다.

깊이 우선 탐색에는 스택을 사용하면 간단하게 쓸 수 있다. 아래의 프로그램은, 폭 우선 탐색으로 큐를 사용한 곳을 스택에 재기록한 것 뿐이다. Java의 스택은 ArrayDeque 클래스를 사용하면 된다. 이것은 큐에도 스택에도 사용할 수 있는 양방향으로 출입할 수 있는 배열이다.

깊이 우선 탐색 샘플

    // sample6_2: DFS
    @Procedure(value = "example.sample6_2")
    @Description("sample6_2: DFS")
    public Stream<Output> sample6_2( @Name("id") Long id )
    {
        // start node
        Node start_nd = db.getNodeById(id);
        // map for keeping Node id and parent relationship
        Map<Node, Relationship> parent = new HashMap<>();
        // to avoid coming back to start node
        parent.put(start_nd, null);
        // array for checking whether the node was visited 
        List<Node> visited = new ArrayList<>(); 
        // queue
        Deque<Node> queue = new ArrayDeque<>();
        // current node
        Node c_nd = start_nd;
        // list for result
        List<Output> o_l = new ArrayList<>();
        // end if queue is empty
        while(c_nd != null) {
            Iterable<Relationship> rels = c_nd.getRelationships();
            if(!(visited.contains(c_nd))) {
                for(Relationship rel: rels){
                    // if not visited add next node
                    Node n_nd = rel.getOtherNode(c_nd);
                    if(!parent.containsKey(n_nd)) {
                        queue.push(n_nd);
                        parent.put(n_nd, rel);
                    }
                }           
                visited.add(c_nd);
            }
            Output o = new Output();
            o.node = c_nd;
            // get path from start_nd to c_nd
            o.path = getPath(start_nd, c_nd, parent);
            o_l.add(o);
            // get next node from queue
            c_nd = queue.poll();
        }
        return o_l.stream();
    }

폭 우선 탐색 때와 같은 샘플로 이 프로그램을 실행해 보자. 하기 샘플이다.

A(id가 0)에서 시작한 실행 결과는

된다. 확실히 깊이 우선으로 노드가 얻어진다. 이 결과를 나타내는 트리(목)는 폭 우선시와 마찬가지로 깊이 우선 탐색 트리라고 불린다(이 표시를 얻기 위해서는 Neo4j Browser의 옵션을 OFF로 할 필요가 있다.설명은 폭 우선 기사 참조).