가중치 그래프와 임계 경로(Critical Path)

가중치 그래프 Weighted Graph

숫자로 된 가중치를 각 간선에 부여하여 가중치 그래프(weighted graph)로 확장할 수 있다. 이는 비가중치 그래프를 일반화한 것인데, 비가중치 그래프는 모든 간선의 가중치가 동일해서 생략한 가중치 그래프이고 더 많은 정보를 표현할 수 있어서 유용하다. 그래프가 도로망을 나타낸다면 가중치는 거리 또는 두 지점 사이를 여행하는데 걸리는 시간일 수 있다.

가중치 그래프는 비가중치 그래프와 유사하게 표현할 수 있다. 인접 행렬로 나타낸다면, 가중치 그래프의 인접 행렬은 엔트리로 간선들의 가중치를 갖거나 연결되지 않은 엔트리들에 대해서는 특수한 값을 갖는다. 아래는 위 그래프를 인접행렬로 표현한 것이다.

이 인접행렬에서는 연결된 간선이 없을 때는 특수 값으로 \infty∞를 사용했지만, 가중치들이 음수가 아니면 -1을 사용할 수도 있고, NULL이나 다른 것을 사용할 수도 있다. 인접행렬이 아닌 인접 리스트를 사용할 수도 있다. 인접 리스트를 사용하면, 리스트의 각 노드에는 정점이 이름뿐만 아니라 해당 간선의 가중치를 저장해야 한다.

임계 경로 Critical Path

가중치 그래프를 작업 스케줄링에 초점을 맞추면 위상 정렬은 프로세스에서 수행될 단계들을 표현하는 DAG에서 임계 경로(Critical Path)를 찾는 문제가 된다. 이 문제에서 처리할 프로세스는 그래프로 표현되고, 각 노드(정점)은 작업, 링크(간선)는 프로세스 작업 간 순서 관계를 나타낸다. 여기서 각 간선 (u, v)(u,v)에서 가중치 w(u, v)w(u,v)를 할당하는데, 이는 작업 vv를 시작하기 전에 작업 uu를 완료하는데 걸리는 시간이다.

아래 이미지는 이러한 스케줄링 그래프(scheduling graph)를 보여준다.

노드는 개별 작업(0부터 코드화된 숫자)에 해당하며, 가중치는 한 작업에서 다른 작업으로 이동하는 데 필요한 시간(예를 들어 주 weak)에 해당한다. 위 그래프에서 작업 0에서 작업 1까지 도달하는데 17주가 걸린다. 여기서 발생하는 문제는 프로세스를 완료하는데 필요한 최소 시간이 얼마인가이다. 일부 작업은 병렬로 수행할 수 있는데, 예를 들어 작업 0과 작업 5의 처리를 동시에 시작할 수 있다. 작업 0과 5의 실행이 완료되면 마찬가지로 작업 1, 6, 9 또한 서로를 기다리지 않고 실행할 수 있다. 그러나 모든 작업들이 동시에 수행될 수 있는 것은 아니다. 작업 3은 작업 2와 7이 완료된 후에 실행될 수 있다. 

 

먼저 두 개의 노드를 그래프에 추가한다. 하나는 시작 노드 s이고 전체 프로세스의 시작 지점이다. 이 노드는 소스 노드(source node)라고 불린다. 그래프에서 선행 작업이 없는 노드에 각각 s를 연결하며, 추가되는 연결 간선들은 가중치가 0이 된다. 다른 하나는 전체 프로세스의 끝을 나타내는 또 다른 노드 t를 추가하는데, 이 노드는 싱크 노드(sink node)라고 하며 후속 작업이 없는 노드들을 t에 연결한다.

이 작업이 끝나면 아래처럼 그래프가 구성된다.

노드 s에서 노드 t로 가는 가장 긴 경로를 알기 위해선 그래프의 모든 노드를 방문해야 한다. 물론 일부 경로는 병렬로 작업할 수 있지만, 가장 긴 시간이 걸리는 경로를 완료할 때까지 프로세스를 완료할 수 없다. 프로세스에서 가장 긴 경로를 임계 경로(Critical Path)라고 한다. 

 

경로 0 -> 1 -> 2 -> 4의 길이는 16이다. 경로 0 -> 4의 길이는 14, 경로 0 -> 3 -> 4는 20이다. 길이 단위가 주라면 20주가 되기 전에 작업 4를 시작할 방법이 없으므로 임계 경로는 0 -> 3 -> 4가 된다. 같은 방식으로 위의 그래프에서 s에서 t까지의 가장 긴 경로에 걸리는 시간이 지나서야 프로세스의 마지막인 t(프로세스의 마지막을 나타내는 자리 표시자)를 시작할 수 있다.

가장 긴 경로를 찾는방법

일단 순차적으로 그래프를 탐색해야한다. 특히, s부터 시작하여 그래프에 있는 모든 노드를 방문하고, s에서 각 노드까지 경로의 길이를 계산한다. 초기에 알고 있는 유일한 길이는 s까지의 길이인 0이다. 각 노드들을 방문하면서 길이를 갱신하는데, 노드 uu를 방문해서 s에서 uu까지 가장 긴 경로를 찾았고, uu는 vv와 연결되었다고 가정해보자. s부터 vv까지에서 찾은 가장 긴 경로가 s부터 uu까지 경로에 간선 (u, v)(u,v)의 가중치를 더한 것보다 작거나 같다면, vv까지 발견한 가장 긴 경로는 uu를 지나간다는 정보를 기록하고 계산된 길이를 갱신해야 한다. (uu를 수행하기 전까지 vv를 수행할 수 없다는 뜻이다.)

이렇게 노드를 탐색하면서 더 긴 경로를 찾을 때마다 길이를 갱신해야 하므로, 시작할 때 s까지의 길이를 제외하고는 모든 길이를 가능한 가장 낮은 추정값(ex, -\infty−∞)으로 설정해야 한다.

정확한 측정을 통해 그래프 측량에 대한 추정값을 확인하고 필요에 따라 갱신하는 프로세스는 많은 그래프 알고리즘에서 일어나는 일인데, 이를 완화(relaxation)이라고 한다. 여기에서 경로 길이에 대한 초기 추정값은 가장 작은 값인 -\infty−∞이며, 경로 길이를 갱신할 때마다 덜 극단적인고 더 정확한 값으로 완화된다.

vv로의 경로를 처음 확인할 때 가능한 가장 작은 값인 -\infty−∞임을 알게 되면 uu에서 전달되는 경로의 길이로 정확히 갱신해야 한다. 또한, vv로 향하는 모든 노드를 방문하기 전까지 노드 vv를 방문해서 vv의 인접 노드로 방문하면 안된다. 이는 앞선 글의 위상 정렬(Topological Sort)로 그래프를 탐색하면 방문 순서를 쉽게 얻을 수 있다.

 

위 내용을 알고리즘으로 나타내면 다음과 같다.

임계 경로 알고리즘

이 알고리즘에서는 배열 pred와 배열 dist라는 두 가지 자료 구조를 사용한다. pred의 원소 i, 즉, pred[i]는 i에 해당하는 노드까지의 임계 경로에서 i 앞에 오는 노드를 가리킨다. 즉, i 전에 위치하는 노드다. dist의 원소 i, dist[i]는 i에 해당하는 노드까지 임계 경로의 길이를 나타낸다. 여기서 Weight는 노드 uu와 vv 사이의 가중치를 반환하는 함수다. t가 어느 노드인지를 아는 것으로 충분하기 때문에 입력으로 요구하지 않는다, 임계 경로의 길이는 dist[t]로 주어지고, 경로를 찾기 위해 pred[t]에서 출발하여 pred를 추적하면 된다.

1~6행에서는 pred와 dist 자료 구조를 생성하고 초기화한다. pred의 각 원소를 유효하지 않으며 존재하지 않는 노드 -1로 설정했는데, 이는 그래프를 어떻게 사용하느냐에 따라 달라질 수 있다. 각 노드의 길이인 dist는 각 원소를 시작 노드인 s를 제외하고는 -\infty−∞로 설정한다. 그 다음 그래프에서 위상정렬을 수행하여, 위상 순서를 얻는다.

8~12행에서 위상 순서에 따라서 모든 노드를 처리한다. 즉, 차례대로 인접 리스트를 이용해 각 노드와 이웃 노드들에 대해 반복처리 한다.

10~12행에서는 현재 노드에서 각 이웃 노드로 가는 경로의 길이가 이 지점까지 계산한 이전 노드보다 더 큰지 확인한다. 더 크다면 현재 노드까지 오는 가장 긴 경로에 있는 이웃의 선행 노드와 경로 길이를 갱신한다.

위상 정렬은 O(|V| + |E|)O(∣V∣+∣E∣) 시간이 걸린다. 3~5행의 루프는 O(|V|)O(∣V∣) 시간이 걸린다. 그리고 8~12행의 루프는 간선당 한 번씩 11~12행을 수행하고, 각 간선은 한 번 relaxation 된다. 이는 전체 루프가 O(|E|)O(∣E∣) 시간이 걸린다는 것을 의미한다. 정리하면 전체 알고리즘을 수행하는 데는 O(|V| + |E| + |V| + |E|) = O(|V| + |E|)O(∣V∣+∣E∣+∣V∣+∣E∣)=O(∣V∣+∣E∣) 시간이 필요하다.

 

우선 기존 코드에서 수정된 함수는 다음과 같다.

#include <tuple>
 
template<typename T>
class DirectedGraph {
    ...
    
public:
    typedef struct arc {
        ...
        int32_t weight;
    } ARC;
    ...
    int insertArc(T fromKey, T toKey, int32_t weight = 0);
    ...
    std::tuple<std::map<T, T>, std::map<T, int32_t>> criticalPath(T start);
};

가중치를 적용하기 위해서 ARC 구조체에 weight 변수를 추가했고, 간선을 추가하는 메서드 insertArc에 매개 변수로 weight 값을 입력받고, 구조체의 weight에 대입한다. default로 0이 들어간다. 그리고 criticalPath를 구해서, 각 노드의 pred node와 시작 노드 start부터의 거리를 반환하는 메서드 criticalPath 메서드를 추가했다.

template <typename T>
std::tuple<std::map<T, T>, std::map<T, int32_t>> DirectedGraph<T>::criticalPath(T start)
{
    std::map<T, int32_t> pred;
    std::map<T, int32_t> dist;
    std::map<T, VERTEX*> vertices;
 
    VERTEX* walkVertPtr = this->first;
    // dist, pred initiation, set vertex mapping table
    while (walkVertPtr) {
        dist[walkVertPtr->data] = (1 << 32);
        pred[walkVertPtr->data] = -1;
        vertices[walkVertPtr->data] = walkVertPtr;
 
        walkVertPtr = walkVertPtr->pNextVertex;
    }
 
    dist[start] = 0;
    auto sorted = this->topologicalSort_DFS();
 
    for (auto& u : sorted) {
        ARC* walkArcPtr = vertices[u]->pArc;
 
        while (walkArcPtr) {
            T v = walkArcPtr->destination->data;
            if (dist[v] < dist[u] + walkArcPtr->weight) {
                dist[v] = dist[u] + walkArcPtr->weight;
                pred[v] = u;
            }
 
            walkArcPtr = walkArcPtr->pNextArc;
        }
    }
    
    return { pred, dist };
}

 

최종적인 모습은 아래와 같다

#include <iostream>
#include <stdio.h>
 
#include "DirectedGraph.hpp"
 
int main(void) {
    DirectedGraph<int32_t> graph([](const int32_t& a, const int32_t& b) {
        if (a > b)
            return 1;
        else if (a < b)
            return -1;
        else
            return 0;
        });
 
    // add vertex(0 ~ 11)
    for (int32_t i = 0; i < 12; i++) {
        graph.insertVertex(i);
    }
 
    // add edge
    graph.insertArc(0, 1, 17);
    graph.insertArc(1, 2, 13);
    graph.insertArc(2, 3, 9);
    graph.insertArc(3, 4, 11);
    graph.insertArc(3, 8, 10);
    graph.insertArc(5, 6, 11);
    graph.insertArc(5, 9, 15);
    graph.insertArc(6, 7, 18);
    graph.insertArc(7, 3, 16);
    graph.insertArc(7, 8, 13);
    graph.insertArc(7, 11, 19);
    graph.insertArc(9, 10, 14);
    graph.insertArc(10, 11, 17);
 
    // add start(-1)/end(12) point
    graph.insertVertex(-1);
    graph.insertVertex(12);
    graph.insertArc(-1, 0, 0);
    graph.insertArc(-1, 5, 0);
    graph.insertArc(4, 12, 0);
    graph.insertArc(8, 12, 0);
    graph.insertArc(11, 12, 0);
 
    int32_t start = -1, end = 12;
    auto ans = graph.criticalPath(start);
    auto pred = std::get<0>(ans);
    auto dist = std::get<1>(ans);
 
    printf("--------- distance from start ---------\n");
    printf("idx  : ");
    for (int32_t i = 0; i <= end; i++) {
        printf("%2d  ", i);
    }
    printf("\ndist : ");
    for (int32_t i = 0; i <= end; i++) {
        printf("%2d  ", dist[i]);
    }
 
    printf("\n\n--------- pred node from each node ---------\n");
    printf("idx  : ");
    for (int32_t i = 0; i <= end; i++) {
        printf("%2d  ", i);
    }
    printf("\npred : ");
    for (int32_t i = 0; i <= end; i++) {
        if (pred[i] == -1)
            printf("%2c  ", 's');
        else
            printf("%2d  ", pred[i]);
    }
    printf("\n");
 
    return 0;
}

출발 노드부터 도착 노드까지 가장 긴 경로의 길이는 56이며, 이는 pred 결과를 통해서 도착지점 12부터 역추적하면, 임계 경로가 [s -> 5 -> 6 -> 7 -> 3 -> 4 -> 12] 라는 것을 알 수 있다.

 

출처 : https://junstar92.tistory.com/198