[알고리즘] critical activity path 찾기 (임계 작업 찾기)

critical activity path 찾기

1) topological sort의 순서대로 vertex 방문

   . indegree가 0인 것들 부터 방문

   . 방문 시 주변 vertex의 indegree를 -1

             주변 vertex의 weight를 누적

2) 누적된 가중치 중 maximum value를 찾음

3) reverse topological sort의 순서대로 vertex 방문

   . lastest_weight[n]를 누적된 가중치 중 maximum value로 초기화

     (vertex 갯수 n 만큼 모두 초기화)

   . outdegree가 0인 것 부터 방문

   . 방문 시 해당 vertex의 시작 vertex(out 연결)의 outdegree에 -1

         vertx에 대해서 각각의 인접 list 중

         같은 vertex가 있다면, 이것의 outdegree를 -1

         outdegree가 0이 되면, 방문 queue에 push

         그리고

         latest_weight를 간선의 가중치만큼 감소

   . 이제 각 vertex 별로 max에서 차감한 weight 값을 알고 있음(latest_wegith)

4) 모든 vertex를 돌며,

   . 인접 list의 vertex에 대해

   . 시작부터 누적된 가중치와(earliest weight),

     뒤에서 부터의 가중치 - 현재 vertex의 weight 한 것이 같은 vertex를 찾음

   . 이 vertex의 weight이 0 이상인 경우,

   . 이 vertex를 방문

void graph_forward_critical_activity(item_t *items, uint32 n, s32 *earlist_weight) {    uint32 i, j, k, pos;    queue<uint32> que;    adj_node_t *adj_node;    list_node_t *node;    int *indegree = new int[n];    for (i = 0; i < n; i++) {        indegree[i] = 0;        earlist_weight[i] = 0;    }    for (i = 0; i < n; i++) {        if (RET_TYPE_FAILURE ==            items[i].adj_list->get_head_position(&pos))            continue;        while (1) {            node = items[i].adj_list->get_next(&pos);            if (NULL == node)                break;            adj_node = (adj_node_t *)node->data;            k = item_find_slot(items, adj_node->vertex->name, n);            indegree[k]++;        }    }    for (i = 0; i < n; i++) {        if (0 == indegree[i])            que.push(i);    }    for (i = 0; i < n && !que.empty(); i++) {        j = que.front();        que.pop();        //LOGD("%s -> ", items[j].vertex.name);        if (RET_TYPE_FAILURE ==            items[j].adj_list->get_head_position(&pos))            continue;        while (1) {            node = items[j].adj_list->get_next(&pos);            if (NULL == node)                break;            adj_node = (adj_node_t *)node->data;            k = item_find_slot(items, adj_node->vertex->name, n);            indegree[k]--;            if (0 == indegree[k])                que.push(k);            if (earlist_weight[k] <                earlist_weight[j] + adj_node->edge.getWeight())                earlist_weight[k] = earlist_weight[j] +                    adj_node->edge.getWeight();        }    }    delete []indegree; } void graph_backward_critical_activity(item_t *items, uint32 n, s32 *latest_weight, s32 max_weight) {    LOGD("+%s: ----------------\r\n", __FUNCTION__);    uint32 i, j, k, pos;    queue<uint32> que;    adj_node_t  *adj_node;    list_node_t *node;    int *outdegree = new int[n];    for (i = 0; i < n; i++) {        outdegree[i] = 0;        latest_weight[i] = max_weight;    }    for (i = 0; i < n; i++) {        outdegree[i] = items[i].adj_list->get_elem_count();    }    for (i = 0; i < n; i++) {        if (outdegree[i] == 0)            que.push(i);    }    for (i = 0; i < n && !que.empty(); i++) {        j = que.front();        que.pop();                //LOGD("%s -> ", items[j].vertex.name);        for (k = 0; k < n; k++) {            if (RET_TYPE_FAILURE ==                items[k].adj_list->get_head_position(&pos))                continue;            while (1) {                node = items[k].adj_list->get_next(&pos);                if (NULL == node)                    break;                adj_node = (adj_node_t *)node->data;                if (*adj_node->vertex == items[j].vertex) {                    outdegree[k]--;                    if (outdegree[k] == 0)                        que.push(k);                    if (latest_weight[k] > latest_weight[j] -                        adj_node->edge.getWeight())                        latest_weight[k] = latest_weight[j] -                            adj_node->edge.getWeight();                }            }        }    }    delete []outdegree; } void graph_critical_activity(item_t *items, uint32 n) {    LOGD("+%s: ----------------\r\n", __FUNCTION__);    u32  i, pos, i_earlist_weight, l_weight, adj_idx;    s32 *earlist_weight = new s32[n];    s32 *latest_weight  = new s32[n];    s32  max_weight = 0;    adj_node_t  *adj_node;    list_node_t *node;    graph_forward_critical_activity(items, n, earlist_weight);    for (i = 0; i < n; i++) {        if (max_weight < earlist_weight[i])            max_weight = earlist_weight[i];    }    graph_backward_critical_activity(items, n,        latest_weight, max_weight);    for (i = 0; i < n; i++) {        if (RET_TYPE_FAILURE ==            items[i].adj_list->get_head_position(&pos))            continue;        while (1) {            node = items[i].adj_list->get_next(&pos);            if (NULL == node)                break;            adj_node = (adj_node_t *)node->data;            adj_idx  = item_find_slot(items,                adj_node->vertex->name, n);            i_earlist_weight = earlist_weight[i];                        l_weight = latest_weight[adj_idx] -                adj_node->edge.getWeight();            if (l_weight == i_earlist_weight &&                adj_node->edge.getWeight() > 0) {                LOGD("%s --%u--> %s, ", items[i].vertex.name,                          adj_node->edge.getWeight(),                          adj_node->vertex->name);            }        }    }    delete []earlist_weight;    delete []latest_weight;    LOGD("\r\n", __FUNCTION__);    LOGD("-%s: ----------------\r\n", __FUNCTION__); }