[알고리즘] 두 Graph 비교

 브랜치가 포함된 두 배관 라인을 비교하는 방법입니다.

아래와 같이 두 배관 라인이 존재할때 바뀐 부분을 찾는 로직입니다.

이 두 라인을 비교하기 위해 문자열 diff 알고리즘을 적용할 수 있습니다.

먼저 라인을 구성하는 항목들을 코드화 시킵니다.

두 라인을 문자열로 표현하면

$OLD = PRPTPRPBPOPRP$

$NEW = PRPRPBPOPRPTP$

가 됩니다.

이제 배관 라인을 두 문자열로 만들었으니 문자열 diff 알고리즘을 적용시킬 차례입니다.

LCS(Longest Common Subsequence)를 이용하여 두 문자열을 비교합니다.

LCS는 다음 식으로 표현됩니다.

$$LCS(X_i,Y_j) = \begin{eqnarray} \left\{ \begin{aligned} &0 && if\text{ }i = 0\text{ }or\text{ }j=0\\ &LCS(X_{i-1},Y_{j-1})+1 && if\text{ }X_i=Y_j\\&max(LCS(X_i,Y_{j-1}),LCS(X_{i-1},Y_j)) && if\text{ }X_i \neq Y_j \end{aligned} \right. \end{eqnarray}$$

$X,Y$는 비교할 문자열이고 $i,j$는 문자열의 인덱스입니다.

위 식을 이해하기 쉽게 2차원 배열로 나타내면 아래와 같습니다.

가장 큰 숫자인 11이 공통 부분 수열의 길이가 됩니다.

1에서 11까지 비용($Cost\text{ }=\text{ }i+j$)이 가장 작은 위치의 숫자를 선택하여 그 위치의 문자를 연결하면 공통 부분 수열이 됩니다.(공통 부분 수열은 하나가 아니라 여러개가 나타날 수 있습니다.)

공통 부분 수열은 $PRP\text{ }RPBPOPRP$(동그라미 친 부분)이며 변경이 일어나지 않은 부분입니다.

해석을 해보면 $OLD$에서 가운데 $TP$가 삭제되고 $NEW$에서 맨 끝에 $TP$가 추가되었습니다.

두 라인에서 브랜치가 변동이 없는 경우에는 두 브랜치를 비교하여 차이점을 찾아 냅니다.

(위에서 설명한 로직과 동일하게 적용하면 됩니다.)

그렇지 않을 경우에는 브랜치 전체에 Cloud 마크를 그리면 됩니다.

아래는 LCS를 구현한 Python예시입니다.

1. A = ['P','R','P','T','P','R','P','B','P','O','P','R','P']
2. B = ['P','R','P','R','P','B','P','O','P','R','P','T','P']
3.  
4. LCS = []
5. for i in range(len(A) + 1):
6. LCS.append([0 for j in range(len(B) + 1)])
7.  
8. for i in range(len(A) + 1):
9. for j in range(len(B) + 1):
10. if i == 0 or j == 0:
11. pass
12. elif A[i-1] == B[j-1]:
13. LCS[i][j] = LCS[i-1][j-1] + 1
14. else:
15. LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j])
16.  
17. for i in range(len(A) + 1):
18. print(LCS[i])

두 배관 라인의 차이점을 비교하는 문제를 해결할때 어려웠던 점은 이 문제를 '문자열을 비교하는 알고리즘을 이용하여 해결해보자'라고하는 발상의 전환이었습니다.

이렇게 문제를 바꾸고 나니 해결이 어렵지 않았습니다.