query 관련 질문 - Githubissues

SNUCSE-CTA / Graph-Pattern-Matching-Challenge

1 stars 58 forks source link

query 관련 질문 #11

Open Wonseok1017 opened 3 years ago

Wonseok1017 commented 3 years ago

제공된 query의 경우 전부 rooted DAG의 성질을 가지고 있는 것을 확인했습니다. 테스트에 사용되는 query또한 rooted DAG임을 가정해도 무방한가요? (=아래와 같은 상황이 발생할 수 있나요?) ex) t 0 3 v 0 0 v 1 1 v 2 2 e 0 2 0 e 1 2 0

JihoonJang commented 3 years ago

안녕하세요.

쿼리 그래프는 undirected graph로 주어지며, 말씀하신 상황이 발생할 수 있습니다.

즉 query가 rooted DAG로 주어지지 않는다고 생각하시고 코드를 짜셔야 합니다.

Wonseok1017 commented 3 years ago

강의자료에 나온 DAF 알고리즘을 보면 다음과 같습니다.

교수님께서 설명하신 말씀을 기준으로 하면 1, 2번 과정이 진행된 상태에서 BACKTRACK(q, q_D, CS, M); 부분을 자유롭게 구현하는 것으로 이해했습니다. 그렇다면 테스트에 사용되는 query가 rooted DAG가 아닐지라도 제공해주신 기본 알고리즘이 해당 query를 rooted DAG로 만들어 주는 것 아닌가요?

JihoonJang commented 3 years ago

쿼리 그래프를 데이터 그래프로부터 BFS 방식으로 뽑아내면서 rooted DAG 형태로 쿼리 데이터셋이 만들어진 것 같습니다.

실제로 쿼리 그래프 파일의 direction 정보는 알고리즘에서 사용되지 않습니다.

본 챌린지에서 제공되는 부분은 첨부해주신 알고리즘의 q, G, CS (Candidate Set)이며, BuildCS에서 사용된 DAG에 대한 정보(q_D)는 제공되어 있지 않습니다.