1. 네트워크의 ADT
/*-----------ADT------------*/
void Init_Headnodes(void); // List롤 네트워크를 구성하기 위한 초기화를 진행합니다.
Node* Init_Vertex(int vertex); // 정점에 대한 정보를 저장하는 구조체 포인터를 동적할당합니다.
void Input_Head_2_Node(int u, int v); // 헤드 노드에 다른 노드를 연결합니다.
void Activity_On_Vertex(void); // AOV를 위상 정렬 합니다. (스택과 DFS를 사용)
void Cal_EST(void); // AOV에서 각 정점의 Earliest Start Time을 구합니다.
void Inverting_Graph(void); // 그래프의 인접 리스트를 역순으로 구성합니다.
void Cal_LST(void); // AOV에서 각 정점의 Latest Start Time을 구합니다.
/*--------------------------*/
2. 그래프 초기화 함수
Init_Headnodes
count = 헤드 노드가 다른 노드에 연결된 횟수를 저장
weight = 해당 노드의 작업 시간
EST = 해당 작업을 시작할 수 있는 가장 빠른 시간
LST = 해당 작업을 시작할 수 있는 가장 늦은 시간
link = 헤드 노드와 다른 노드를 연결하는 구조체 포인터
Init_Vertex
임의의 vertex 정보를 포함하는 Node 구조체 포인터를 생성하고 반환합니다.
Input_Head_2_Node
Init_Vertex에서 생성된 Node 구조체 포인터를 헤드 노드에 연결합니다.
void Init_Headnodes(void) {
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i].count = 0;
graph[i].weight = 0;
graph[i].EST = 0;
graph[i].LST = 0;
graph[i].link = NULL;
}
}
Node* Init_Vertex(int vertex) {
Node* tmp = (Node*)malloc(sizeof(Node));
tmp->vertex = vertex;
tmp->link = NULL;
return tmp;
}
void Input_Head_2_Node(int u, int v) { // 헤드 노드에서 다른 노드로 가는 경로를 이어줍니다.
Node* cur = Init_Vertex(v);
Node* tmp;
tmp = graph[u].link; // tmp는 기존에 헤드 노드에 연결되어있던 노드입니다.
graph[u].link = cur; // 헤드 노드에 현재 이어주고자 하는 노드를 연결해주고
cur->link = tmp; // 현재 이어주고자 하는 노드 뒤에 기존에 헤드 노드에 연결되어 있던 노드를연결해줍니다.
graph[v].count++; // 연결이 된 정점의 count를 증가시켜준다.
// count는 해당 노드가 다른 노드에 연결된 갯수를 저장합니다.
// 즉, 헤드 노드 u가 아닌 헤드 노드 v의 count를 증가시켜줍니다.
}
void Inverting_Graph(void) {
// 그래프의 리스트를 역순으로 다시 정렬해줍니다.
// EX) 괄호 안은 count 입니다.
// 0 (0) -> 1 (1)
// 0 (0) -> 2 (1)
// Invert 하면 다음과 같습니다.
// 1 (0) -> 0 (1)
// 2 (0) -> 0 (2): 0이 두 번 찔렸으니까!
int u;
int i = 0;
int j;
Node* tmp;
Node* cur;
Node* tmp1;
for (i = 0; i < MAX_VERTICES; i++) {
cur = graph[i].link;
// 정점 i와 연결된 정점들을 하나씩 방문한다.
// 방문한 정점의 inverted_graph에 정점 i를 연결해준다.
while (cur != NULL) {
tmp = (Node*)malloc(sizeof(Node));
u = cur->vertex;
tmp->vertex = i;
tmp->link = NULL;
tmp1 = inverted_graph[u].link;
inverted_graph[u].link = tmp;
tmp->link = tmp1;
inverted_graph[i].count++;
cur = cur->link;
}
}
}
3. Stack
AOV를 위상 정렬할 때 사용됩니다.
위상 정렬할 때 시작 정점 부터 해당 정점과 연결된 정점을 방문하며 방문된 정점의 count를 1 씩 낮춰줍니다.
이때 방문된 정점을 Stack에 저장합니다.
/*--------Stack---------*/
int top = -1;
int stack[MAX_VERTICES];
void Input_Stack(int n) {
if (top == MAX_VERTICES) {
//printf("Stack is full\n");
}
else {
stack[++top] = n;
//printf("Input stack[%d] = %d\n", top, n);
}
}
int Delete_Stack(void) {
int n = -1;
if (top == -1) {
//printf("Stack is empty\n");
}
else {
n = stack[top--];
//printf("Deleted stack[%d] = %d\n", top + 1, n);
}
return n;
}
/*----------------------*/
3. AOV의 위상 정렬 알고리즘 (DFS, Stack 사용)
AOV를 위상 정렬 합니다.
아래의 절차에 따라 진행됩니다.
1) 시작 정점을 스택에 저장합니다.
2) 스택에 저장된 정점과 연결된 정점을 방문합니다.
3) 방문된 정점의 count를 1 감소시킵니다.
4) count가 0이 된 정점은 스택에 저장합니다.
5) 스택에 저장된 정점이 없을 때까지 1) ~ 4)를 반복합니다.
스택에 저장된 순서대로 출력하면, 위상 정렬의 결과를 확인할 수 있습니다.
void Activity_On_Vertex(void) { // aov 네트워크에 대한 위상 정렬을 실시합니다.
int i, j;
printf("AOV\n");
for (j = 0; j < MAX_VERTICES; j++) {
if (graph[j].count == 0) // count가 0인 것은 해당 노드 이전에 해야할 작업이 없다는 것을뜻합니다.
Input_Stack(j);
}
int n;
Node* tmp;
Node* cur;
while (top != -1) {
// 스택에 저장된 데이터가 없을 때까지 반복합니다.
n = Delete_Stack(); // 스택에 저장된 데이터를 하나 꺼내고
printf("%2d ", n);
cur = graph[n].link;
while (cur != NULL) {
// 해당 노드에 연결된 정점이 없을 때까지 반복합니다.
//printf("cur->vertex = %d\n", cur->vertex);
// 이게 스텍이 아니라면 순서가 반대로 출력될 것이다.
// 위상 정렬이란게 딱 한 순서만 있는게 아닌 듯 하다.
// 연결 리스트를 사용하므로 정점이 연결된 순서도 영향을 미친다.
graph[cur->vertex].count--; // 스택에서 나온 정점과 연결된 정점의 count를 감소 시킵니다.
if (graph[cur->vertex].count == 0) // 만약 연결된 노드의 count가 0이 되면 스택에입력해줍니다.
Input_Stack(cur->vertex); // 이 부분 때문에 가장 바깥 while문이 다시 한번반복됩니다.
cur = cur->link;
}
}
printf("\n\n");
}
4. Earliest Start Time 함수
AOV를 기준으로 EST를 구하는 알고리즘입니다.
특정 정점이 실행될 수 있는 제일 빠른 시간을 구합니다.
제일 빠른 시간의 개념을 헷갈리면 안 됩니다.
EX)
팀원들이 자료 조사를 다 해줘야 발표 자료를 만들 수 있을 때
다른 사람은 저녁 6시까지 자료 다 보내줬는데
한 놈이 저녁 10시에 보내면 저녁 10시가 '발표 자료 만들기'의 EST 입니다.
void Cal_EST(void) {
int i = 0;
Node* tmp;
Node* cur;
int max = 0;
while (i < MAX_VERTICES) { // 여기를 for문으로 구성해도 됩니다.
cur = graph[i].link;
//printf("111graph[%d].EST = %d\n", i, graph[i].EST);
while (cur != NULL) {
if (graph[cur->vertex].EST < graph[i].EST + graph[i].weight) { // i와 연결된 정점의 EST가 (i의 EST) + (i의 작업 시간) 보다 작을 때, i와 연결된 노드의 EST를 업데이트해준다.
graph[cur->vertex].EST = graph[i].EST + graph[i].weight;
//printf("222graph[%d].EST = %d\n", cur->vertex, graph[cur->vertex].EST);
if (graph[cur->vertex].EST >= max) {
max = graph[cur->vertex].EST; // 나중에 LST 계산을 위해 설정해줍니다.
}
}
cur = cur->link;
}
i++;
}
for (int j = 0; j < MAX_VERTICES; j++) {
//if (graph[j].EST == max) {
inverted_graph[j].LST = max; // LST는 EST의 max 보다 항상 작거나 같기 때문에 이와같이 초기화 합니다.
//printf("inverted_graph[%d].LST = %d\n", j, inverted_graph[j].LST);
//}
}
}
5. Lastest Start Time 함수
AOV의 역인접 리스트를 이용하여 LST를 계한합니다.
최대한 밍기적 거릴 수 있는 시간을 구합니다.
EX)
A, B, C가 숙제를 다 끝내야 D가 숙제를 끝내고 다 같이 치킨을 먹을 수 있다고 가정합니다.
숙제를 마치는데 A는 3일, B는 7일, C는 10일이 걸립니다.
어차피 10일이 지나야 D가 시작할 수 있습니다.
따라서 A는 10 - 3 = 7일 동안 놀다가 숙제를 시작해도 되고,
B는 10 - 7 = 3일 동안 놀다가 숙제를 해도 됩니다.
C는 10 - 10 = 0일.. 즉, 놀 시간이 없죠
위의 결과값이 각각의 LST입니다.
항상 마지막 작업의 EST는 곧 LST입니다. (마지막 작업(정점)의 EST == LST == 최대값)
그렇기 때문에 위에 EST를 구하는 함수에서 max를 구하고 초기화 했습니다.
void Cal_LST(void) {
int i = MAX_VERTICES - 1; // 리스트의 가장 마지막 노드부터 시작합니다.
Node* cur;
for (; i >= 0; i--) { // EST와 if 문의 조건문과 역순으로 진행되는 것을 제외하고 모두 동일합니다.
cur = inverted_graph[i].link;
//printf("111inverted_graph[%d].LST = %d\n", i, inverted_graph[i].LST);
while (cur != NULL) {
int u = cur->vertex;
//printf("i = %d, u = %d\n", i, u);
if (inverted_graph[u].LST > inverted_graph[i].LST - inverted_graph[u].weight) {
inverted_graph[u].LST = inverted_graph[i].LST - inverted_graph[u].weight;
graph[u].LST = inverted_graph[u].LST;
}
//printf("222inverted_graph[%d].LST = %d\n", u, inverted_graph[u].LST);
graph[i].LST = inverted_graph[i].LST; // graph에도 LST 정보를 업데이트 하기 위함
cur = cur->link;
}
}
}
6. 전체 코드
AOV에 대한 위상 정렬과 EST, LST를 이용한 임계 경로, 임계 작업을 찾는 코드입니다.
// main.c
// Network_AoE_AoV
//
// Created by 김경민 on 2020/04/21.
// Copyright © 2020 김경민. All rights reserved.
//
// aov와 aoe를 활용한 임계 작업 시간 검색 방법을 구현한다
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 6
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
typedef struct NODE { // 헤드노드에 연결되는 노드 데이터를 저장합니다.
int vertex;
struct NODE* link;
}Node;
typedef struct HEADNODES { // 헤드노드에 대한 데이터를 저장합니다.
int count;
int weight;
int EST; // 작업을 시작할 수 있는 가장 빠른 시간입니다.
int LST; // 작업을 시작할 수 있는 가장 느린 시간입니다.
Node* link;
} Headnodes;
Headnodes graph[MAX_VERTICES];
Headnodes inverted_graph[MAX_VERTICES];
/*-----------ADT------------*/
void Init_Headnodes(void);
Node* Init_Vertex(int vertex);
void Input_Head_2_Node(int u, int v);
void Activity_On_Vertex(void);
void Cal_EST(void);
void Inverting_Graph(void);
void Cal_LST(void);
/*--------------------------*/
void Init_Headnodes(void) {
for (int i = 0; i < MAX_VERTICES; i++) {
graph[i].count = 0;
graph[i].weight = 0;
graph[i].EST = 0;
graph[i].link = NULL;
}
}
Node* Init_Vertex(int vertex) {
Node* tmp = (Node*)malloc(sizeof(Node));
tmp->vertex = vertex;
tmp->link = NULL;
return tmp;
}
void Input_Head_2_Node(int u, int v) { // 헤드 노드에서 다른 노드로 가는 경로를 이어줍니다.
Node* cur = Init_Vertex(v);
Node* tmp;
tmp = graph[u].link; // tmp는 기존에 헤드 노드에 연결되어있던 노드입니다.
graph[u].link = cur; // 헤드 노드에 현재 이어주고자 하는 노드를 연결해주고
cur->link = tmp; // 현재 이어주고자 하는 노드 뒤에 기존에 헤드 노드에 연결되어 있던 노드를연결해줍니다.
graph[v].count++; // 연결이 된 정점의 count를 증가시켜준다.
// count는 해당 노드가 다른 노드에 연결된 갯수를 저장합니다.
// 즉, 헤드 노드 u가 아닌 헤드 노드 v의 count를 증가시켜줍니다.
}
void Inverting_Graph(void) {
// 그래프의 리스트를 역순으로 다시 정렬해줍니다.
// EX) 괄호 안은 count 입니다.
// 0 (0) -> 1 (1)
// 0 (0) -> 2 (1)
// Invert 하면 다음과 같습니다.
// 1 (0) -> 0 (1)
// 2 (0) -> 0 (2): 0이 두 번 찔렸으니까!
int u;
int i = 0;
int j;
Node* tmp;
Node* cur;
Node* tmp1;
for (i = 0; i < MAX_VERTICES; i++) {
cur = graph[i].link;
// 정점 i와 연결된 정점들을 하나씩 방문한다.
// 방문한 정점의 inverted_graph에 정점 i를 연결해준다.
while (cur != NULL) {
tmp = (Node*)malloc(sizeof(Node));
u = cur->vertex;
tmp->vertex = i;
tmp->link = NULL;
tmp1 = inverted_graph[u].link;
inverted_graph[u].link = tmp;
tmp->link = tmp1;
inverted_graph[i].count++;
cur = cur->link;
}
}
}
/*--------Stack---------*/
int top = -1;
int stack[MAX_VERTICES];
void Input_Stack(int n) {
if (top == MAX_VERTICES) {
//printf("Stack is full\n");
}
else {
stack[++top] = n;
//printf("Input stack[%d] = %d\n", top, n);
}
}
int Delete_Stack(void) {
int n = -1;
if (top == -1) {
//printf("Stack is empty\n");
}
else {
n = stack[top--];
//printf("Deleted stack[%d] = %d\n", top + 1, n);
}
return n;
}
/*----------------------*/
void Activity_On_Vertex(void) { // aov 네트워크에 대한 위상 정렬을 실시합니다.
int i, j;
printf("AOV\n");
for (j = 0; j < MAX_VERTICES; j++) {
if (graph[j].count == 0) // count가 0인 것은 해당 노드 이전에 해야할 작업이 없다는 것을뜻합니다.
Input_Stack(j);
}
int n;
Node* tmp;
Node* cur;
while (top != -1) {
// 스택에 저장된 데이터가 없을 때까지 반복합니다.
n = Delete_Stack(); // 스택에 저장된 데이터를 하나 꺼내고
printf("%2d ", n);
cur = graph[n].link;
while (cur != NULL) {
// 해당 노드에 연결된 정점이 없을 때까지 반복합니다.
//printf("cur->vertex = %d\n", cur->vertex);
// 이게 스텍이 아니라면 순서가 반대로 출력될 것이다.
// 위상 정렬이란게 딱 한 순서만 있는게 아닌 듯 하다.
// 연결 리스트를 사용하므로 정점이 연결된 순서도 영향을 미친다.
graph[cur->vertex].count--; // 스택에서 나온 정점과 연결된 정점의 count를 감소 시킵니다.
if (graph[cur->vertex].count == 0) // 만약 연결된 노드의 count가 0이 되면 스택에입력해줍니다.
Input_Stack(cur->vertex); // 이 부분 때문에 가장 바깥 while문이 다시 한번반복됩니다.
cur = cur->link;
}
}
printf("\n\n");
}
void Cal_EST(void) {
// AOV를 기준으로 EST를 구하는 알고리즘입니다.
// 특정 정점이 실행될 수 있는 제일 빠른 시간을 구합니다.
// 제일 빠른 시간을 헷갈리면 안 됩니다.
// 팀원들이 자료 조사를 다 해줘야 발표 자료를 만들 수 있을 때
// 다른 사람은 저녁 6시까지 자료 다 보내줬는데
// 한 놈이 저녁 10시에 보내면 저녁 10시가 '발표 자료 만들기'의 EST 입니다.
int i = 0;
Node* tmp;
Node* cur;
int max = 0;
while (i < MAX_VERTICES) { // 여기를 for문으로 구성해도 됩니다.
cur = graph[i].link;
//printf("111graph[%d].EST = %d\n", i, graph[i].EST);
while (cur != NULL) {
if (graph[cur->vertex].EST < graph[i].EST + graph[i].weight) { // i와 연결된 정점의 EST가 (i의 EST) + (i의 작업 시간) 보다 작을 때, i와 연결된 노드의 EST를 업데이트해준다.
graph[cur->vertex].EST = graph[i].EST + graph[i].weight;
//printf("222graph[%d].EST = %d\n", cur->vertex, graph[cur->vertex].EST);
if (graph[cur->vertex].EST >= max) {
max = graph[cur->vertex].EST; // 나중에 LST 계산을 위해 설정해줍니다.
}
}
cur = cur->link;
}
i++;
}
for (int j = 0; j < MAX_VERTICES; j++) {
//if (graph[j].EST == max) {
inverted_graph[j].LST = max; // LST는 EST의 max 보다 항상 작거나 같기 때문에 이와같이 초기화 합니다.
//printf("inverted_graph[%d].LST = %d\n", j, inverted_graph[j].LST);
//}
}
}
void Cal_LST(void) {
// AOV의 역인접 리스트를 이용하여 LST를 계한합니다.
// 최대한 밍기적 거릴 수 있는 시간을 구합니다.
// 예를들어 A, B, C가 숙제를 다 끝내야 D가 숙제를 끝내고 다 같이 치킨을 먹을 수 있다고 가정합니다.
// 숙제를 마치는데 A는 3일, B는 7일, C는 10일이 걸립니다.
// 어차피 10일이 지나야 D가 시작할 수 있습니다.
// 따라서 A는 10 - 3 = 7일 동안 놀다가 숙제를 시작해도 되고,
// B는 10 - 7 = 3일 동안 놀다가 숙제를 해도 됩니다.
// C는 10 - 10 = 0일.. 즉, 놀 시간이 없죠
// 위의 결과값이 각각의 LST입니다.
// 항상 마지막 작업의 EST는 곧 LST입니다. (마지막 작업(정점)의 EST == LST == 최대값)
// 그렇기 때문에 위에 EST를 구하는 함수에서 max를 구하고 초기화 했습니다.
int i = MAX_VERTICES - 1; // 리스트의 가장 마지막 노드부터 시작합니다.
Node* cur;
for (; i >= 0; i--) { // EST와 if 문의 조건문과 역순으로 진행되는 것을 제외하고 모두 동일합니다.
cur = inverted_graph[i].link;
//printf("111inverted_graph[%d].LST = %d\n", i, inverted_graph[i].LST);
while (cur != NULL) {
int u = cur->vertex;
//printf("i = %d, u = %d\n", i, u);
if (inverted_graph[u].LST > inverted_graph[i].LST - inverted_graph[u].weight) {
inverted_graph[u].LST = inverted_graph[i].LST - inverted_graph[u].weight;
graph[u].LST = inverted_graph[u].LST;
}
//printf("222inverted_graph[%d].LST = %d\n", u, inverted_graph[u].LST);
graph[i].LST = inverted_graph[i].LST; // graph에도 LST 정보를 업데이트 하기 위함
cur = cur->link;
}
}
}
int main(void) {
// 가중치를 설정해붑니다.
// 이부분을 다른 그래프 함수에 사용된 랜덤 변수로 설정하셔도 됩니다.
graph[0].weight = 7;
graph[1].weight = 5;
graph[2].weight = 10;
graph[3].weight = 8;
graph[4].weight = 3;
graph[5].weight = 5;
for (int j = 0; j < MAX_VERTICES; j++) {
inverted_graph[j].count = 0;
inverted_graph[j].weight = graph[j].weight;
inverted_graph[j].link = NULL;
inverted_graph[j].LST = 0;
}
// 노드를 연결해줍니다.
// 마찬가지로 랜덤 변수를 사용할 수 있을 것 같습니다.
Input_Head_2_Node(0, 3);
Input_Head_2_Node(0, 2);
Input_Head_2_Node(0, 1);
Input_Head_2_Node(1, 4);
Input_Head_2_Node(2, 4);
Input_Head_2_Node(2, 5);
Input_Head_2_Node(3, 4);
Input_Head_2_Node(3, 5);
Inverting_Graph();
/* AOV의 위상정렬 */
Activity_On_Vertex();
puts("");
/* AOV를 이용한 Critical Path 찾기 */
Cal_EST();
Cal_LST();
for (int i = 0; i < MAX_VERTICES; i++) {
printf("graph[%2d].est = %2d, graph[%2d].lst = %2d", i, graph[i].EST, i, graph[i].LST);
if (graph[i].EST == graph[i].LST)
printf(" => vertex[%2d] is critical activity.", i);
printf("\n");
}
return 0;
}
'기타(임시)' 카테고리의 다른 글
| 현대자동차 (0) | 2020.05.22 |
|---|---|
| 프로젝트에 관하여 (0) | 2020.05.21 |
| BFS_DFS 임시 (0) | 2020.05.13 |
| 코드 저장 (0) | 2020.04.21 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 21 : 해싱 (Hasing) (0) | 2020.03.19 |