Network Flow를 활용한 그래프 시뮬레이터 제작
서론
그래프(Graph)는 여러 개의 점과 선분으로 구성된 도형으로, 실생활의 여러 상황을 모델링하는 데 사용한다.
내비게이션에서 경로를 찾을 때 도시를 그래프로 모델링하는 경우도 존재하고,
여러 컴퓨터 간의 연결 관계를 나타나는 데에도 사용한다.
이 중 도시의 교통량을 최대한 분산시키거나,
시스템 간의 연결 관계가 주어졌을 때 데이터를 최대한 빠르게 전송시키는 경우를 구해야 할 때가 있다.
이를 일반화하면 그래프에서 간선의 용량이 주어질 때, 한 정점에서 다른 정점으로 최대한의 유량을 보내는 것이다.
이를 네트워크 유량 (Network Flow) 문제라 부른다.
본 탐구에서는 이를 편리하게 분석할 수 있도록 네트워크 유량 알고리즘이 포함된 그래프 시뮬레이터를 제작하였다.
사용 알고리즘
본 탐구에서는 에드몬드-카프 알고리즘 (Edmonds-Karp)을 활용하였다.
이는 기존의 포드-풀커슨 알고리즘에서 발전시킨 형태로,
시간 복잡도가 $O(VE^{2})$이기 때문에 안정적일 것이라 예측하였다.
에드몬드 카프 알고리즘은 BFS를 기반으로, 지속적으로 가능한 경로를 찾아 유량을 흘려주는 것을 반복하여 구성된다.
순서도는 다음과 같이 구성된다.
프로그램 설계
I. 그래프 출력
먼저 다음과 같이, 그래프를 다룰 수 있는 변수들을 구성하였다.
//network flow
int [][]capacity = new int[101][101];
int [][]flow = new int[101][101];
int []parent = new int[101];
//graph simulation
float []x = new float[101];
float []y = new float[101];
boolean []exist = new boolean[101];
capacity: 간선의 용량을 의미한다. capacity가 0일 경우 해당 간선은 없는 것으로 간주한다.
flow: 간선에 흐르는 유량을 의미한다.
parent: 에드몬드-카프 알고리즘에 사용되는 변수로, 경로를 역추적하는 데 사용한다.
x,y: 정점의 좌표를 나타낸다.
exist: 해당 정점이 존재하는 지를 나타낸다.
먼저 x, y, exist 변수를 활용하여 다음과 같이 정점을 그리는 함수를 구축하였다.
void node_draw()
{
for(int i=1;i<=100;i++)
{
if(exist[i] == true)
{
stroke(0,0,0);
if(i == source || i == sink) fill(150,150,200);
else fill(255,255,255);
ellipse(x[i],y[i],40,40);
if(i == source || i == sink) fill(255,255,255);
else fill(0,0,0);
text(i,x[i],y[i]);
}
}
}
source / sink: 각각 유량 근원, 도착 정점의 번호를 의미한다.
다음으로 간선 생성 함수이다.
유량과 용량의 정보 및 유량의 방향성을 나타낼 수 있도록 구축하였다.
방향성은 기초적인 기하학 지식을 활용하여 구성할 수 있다.
다음과 같이 삼각비를 응용하여, 삼각형의 좌표를 나타낼 수 있다.
이때 삼각형의 크기는 기본값 스케일 기준 밑변 16, 높이 14의 이등변삼각형이다.
각도는 기울기로 구현하였고, 이 과정에서 고려해야 할 사항이 2가지 존재한다.
1. 기울기가 x축에 수직일 때
두 정점을 지나는 직선의 기울기는 $\frac{y_{to} - y_{from}}{x_{to} - x_{from}}$이다.
이때, $x_{to} = x_{from}$이면 0으로 나누기 때문에 오류가 발생할 수 있다.
따라서 이 경우는 충분히 큰 값을 기울기로 설정하도록 하였다.
2. 반대 방향 구분
기울기를 $\frac{y_{to} - y_{from}}{x_{to} - x_{from}}$으로만 구하면, 두 정점 from, to의 위치가 변해도 이는 동일하다.
따라서 이 경우를 구분해 주기 위해, $x_{to} > x_{from}$일 때와 그렇지 않을 때를 구분해 주었다.
이렇게 하면 모든 각도에 대해 일대일 대응을 시킬 수 있으므로 방향을 표시할 수 있다.
추가로, 기울기가 x축에 수직인 경우는 y좌표의 대소 관계로 구분하였다.
아래는 간선 생성 코드이다.
void edge_draw()
{
for(int i=1;i<100;i++)
{
if(exist[i] == false) continue;
for(int j=i+1;j<=100;j++)
{
if(i == j) continue;
if(exist[j] == false) continue;
if(capacity[i][j] > 0 || (i == ss && j == se))
{
int flow_amount = max(flow[i][j], flow[j][i]);
float percentage = float(flow_amount) / float(capacity[i][j]);
float p = percentage * 55;
stroke(200,200,200 + p);
//display direction
if(flow_amount > 0)
{
//i → j
int from = i, to = j;
if(flow[i][j] < flow[j][i])
{
to = i;
from = j;
}
strokeWeight(0);
float d;
if(x[to] != x[from]) d = (y[to] - y[from]) / (x[to] - x[from]);
else
{
if(y[from] < y[to]) d = 1000000;
else d = -1000000;
}
float Sin = d / sqrt(d * d + 1);
float Cos = 1 / sqrt(d * d + 1);
if(x[to] < x[from])
{
Sin *= -1;
Cos *= -1;
}
float x1 = x[to] - 20 * Cos;
float y1 = y[to] - 20 * Sin;
float x2 = (x[to] - 34 * Cos) - 8 * Sin;
float y2 = (y[to] - 34 * Sin) + 8 * Cos;
float x3 = (x[to] - 34 * Cos) + 8 * Sin;
float y3 = (y[to] - 34 * Sin) - 8 * Cos;
fill(200, 200, 200 + p);
triangle(x1, y1, x2, y2, x3, y3);
strokeWeight(3);
}
line(x[i],y[i], x[j],y[j]);
stroke(0,0,0);
fill(0,0,0);
if(i == ss && j == se) fill(255,0,0);
String info = str(flow_amount) + "/" + str(capacity[i][j]);
text(info, (x[i] + x[j])/2, (y[i] + y[j])/2 );
}
}
}
}
flow_amount: 현재 흐르고 있는 유량을 의미한다.
percentage: 간선에서 유량이 차지하는 비율을 의미한다.
이 외의 변수들은 삼각비를 통해 구성된 변수들이다.
II. 그래프 수정
아래는 정점과 간선을 시스템 내부에서 생성, 삭제하는 함수이다.
void add_node(int num) { exist[num] = true; x[num] = 0; y[num] = 0; }
void delete_node(int num)
{
exist[num] = false;
for(int i=1;i<=100;i++)
{
capacity[i][num] = 0; flow[i][num] = 0;
capacity[num][i] = 0; flow[num][i] = 0;
}
}
void add_edge(int from, int to, int cap)
{
capacity[from][to] = cap;
flow[from][to] = 0;
capacity[to][from] = cap;
flow[to][from] = 0;
}
void delete_edge(int from, int to)
{
capacity[from][to] = 0;
flow[from][to] = 0;
capacity[to][from] = 0;
flow[to][from] = 0;
}
만약 정점이 삭제되었을 경우, 해당 정점을 한 끝 점으로 포함하는 모든 간선이 삭제되도록 구성하였다.
다음과 같이 마우스를 클릭했을 때, 정점까지의 거리를 통해 클릭한 정점을 찾는 함수를 구현하였다.
float distance(float x_, float y_){return (X - x_) * (X - x_) + (Y - y_) * (Y - y_);}
void select_node()
{
selected_node = 0;
for(int i=1;i<=100;i++)
{
if(exist[i] == false) continue;
if(distance(x[i], y[i]) <= 400 ) { selected_node = i; break; }
}
if(mouseButton == RIGHT && selected_node != 0 && current_mode == 1 && selected_node != source && selected_node != sink)
{
delete_node(selected_node);
selected_node = 0;
}
}X, Y: 마우스 좌표를 좌표계에 맞도록 변환한 결과를 의미한다.
selected_node: 선택된 노드의 번호를 의미한다.
current_mode: 현재 편집 모드를 의미한다. 각 숫자에 따른 편집 모드는 다음과 같다.
- 1: 정점 이동 및 삭제
- 2: 간선 가중치 변경 및 삭제
- 3: 유량 근원 & 목적지 변경, 알고리즘 실행
- 4: 그래프 저장 및 불러오기
아래는 마우스를 클릭하고 있는 동안 정점이 마우스 커서를 따라다니게 하는 함수로, draw() 안에서 반복적으로 호출한다.
void selected_node_follow() { x[selected_node] = X; y[selected_node] = Y; }
다음으로 각 모드에 따른 마우스 클릭 이벤트를 구성한 함수이다.
간선의 중앙을 클릭했는 지는 간선이 잇는 두 정점을 잇는 선분의 중점으로 판단할 수 있다.
void graph_edit_mousepressed()
{
select_node();
//간선 선택
if(selected_node == 0 && current_mode == 2 && istyping == false)
{
ss = 0; se = 0;
for(int i=1;i<100;i++)
{
if(exist[i] == false) continue;
for(int j=i+1;j<=100;j++)
{
if(capacity[i][j] == 0) continue;
if(distance( (x[i] + x[j]) / 2 , (y[i] + y[j]) / 2) <= 500)
{
ss = i; se = j;
if(mouseButton == RIGHT)
{
delete_edge(ss, se);
ss = 0; se = 0;
}
else istyping = true;
break;
}
}
if(ss != 0) break;
}
}
if(current_mode == 3 && selected_node != 0)
{
if(mouseButton == LEFT && selected_node != sink && flow_res == 0) source = selected_node;
if(mouseButton == RIGHT && selected_node != source && flow_res == 0) sink = selected_node;
}
}istyping: 현재 간선의 가중치를 수정하고 있는지를 판별하는 변수이다.
ss, se: 선택한 간선이 잇는 두 정점의 번호를 의미한다.
다음으로 마우스를 떼었을 때 발생하는 이벤트를 나타낸 함수이다.
정점 수정 모드인 경우 마우스를 떼었다는 것은 정점 이동을 멈춘다는 의미이고,
간선 수정 모드인 경우 마우스를 떼었다는 것은 드래그를 통해 간선 생성을 시도한다는 의미이다.
만약 마우스를 떼었을 때 마우스 커서 근처에 적당한 정점이 존재하고,
드래그가 잇는 두 정점 간의 간선 생성 시도가 유효하다면 이를 실행하도록 하였다.
void node_connect()
{
if(current_mode == 1) selected_node = 0;
else
{
int prv = selected_node;
select_node();
int cur = selected_node;
if(prv > cur)
{
int temp = prv;
prv = cur;
cur = temp;
}
if(prv != cur && capacity[prv][cur] == 0) add_edge(prv, cur, 1);
selected_node = 0;
}
}
다음으로 간선 가중치 수정 함수이다.
클릭 감지는 간선 삭제와 동일하게 구성하면 되고, 타이핑 부분만 관리해주면 된다.
현재 가중치에서 백스페이스를 누른다면, 마지막 한 자리가 소멸된다.
이는 현재 가중치를 10으로 나누고 그 몫을 취하는 것과 동치이다.
현재 가중치에서 0부터 9까지의 키를 누른다면, 맨 끝에 수 하나가 추가된다.
이는 현재 가중치에 10을 곱하고 해당 키를 더하는 것과 동치이다.
이 원리를 활용하여 타이핑 기능을 만들 수 있다.
void typing()
{
if(delay == true) return;
if(key == BACKSPACE && keyPressed == true)
{
capacity[ss][se] /= 10;
capacity[se][ss] /= 10;
delay = true;
}
else if(capacity[ss][se] <= 100000000 && '0' <= key && key <= '9' && keyPressed == true)
{
capacity[ss][se] *= 10;
capacity[ss][se] += (key - '0');
capacity[se][ss] *= 10;
capacity[se][ss] += (key - '0');
delay = true;
}
}
III. 알고리즘 구성
에드몬드-카프 알고리즘은 기본적으로 BFS를 활용하기 때문에 큐 자료구조를 필요로 한다.
따라서 다음과 같이 배열을 활용하여 Circular Queue를 구현해 주었다.
//queue
int mod = 200;
int []queue = new int[201];
int s = 0,e = 0;
void push(int data)
{
queue[e] = data;
e = (e + 1) % mod;
}
int front()
{
if(s == e) return 0;
int res = queue[s];
s = (s + 1) % mod;
return res;
}
boolean empty() { return s == e ? true : false; }
최대 유량 알고리즘 크게 두 단계로 구성된다.
먼저 모든 노드들을 탐색하여 유량 근원에서 목적지까지 도달할 수 있는 경로를 찾는다.
이때, 에드몬드-카프 알고리즘은 유량을 보낼 수 있다면 모두 보내는 것이 이득임을 기반으로 하므로 아무 경로나 찾아도 된다.
이 과정에서 경로 역추적을 위하여 parent 배열을 관리한다.
다음으로 찾은 경로에 대해서 유량을 흘려준다.
이때 가능한 유량은 모든 간선들의 잔여 용량 중 최솟값이므로 먼저 이를 한 번 탐색하여 구해준 후 유량을 흘려야 한다.
이를 반복하여 최대 유량을 구할 수 있다.
이때 시간 복잡도는 $O(VE^{2})$임이 증명되어 있다.
int []parent = new int[101];
int source = 1, sink = 2;
int flow()
{
int res = 0;
while(true)
{
for(int i=1;i<=100;i++) parent[i] = -1;
s = e; //queue reset
parent[source] = source;
push(source);
while(empty() == false && parent[sink] == -1)
{
int cur = front();
for(int nxt = 1; nxt <= 100; nxt++)
{
if(nxt == source) continue;
if(capacity[cur][nxt] > flow[cur][nxt] && parent[nxt] == -1)
{
parent[nxt] = cur;
push(nxt);
}
}
}
if(parent[sink] == -1) break;
int amount = 10000000;
for(int cur = sink; cur != source; cur = parent[cur])
{
int prv = parent[cur];
amount = min(amount, capacity[prv][cur] - flow[prv][cur]);
}
for(int cur = sink; cur != source; cur = parent[cur])
{
int prev = parent[cur];
flow[prev][cur] += amount;
flow[cur][prev] -= amount;
}
res += amount;
}
return res;
}
IV. 시스템 구성
먼저 현재 모드 상태 확인 및 실행 결과 텍스트 안내 함수들이다.
단순 반복적 구현이므로 설명은 생략한다.
PFont myfont;
PImage node_icon, edge_icon, select_icon, load_icon;
void ui_init()
{
myfont = loadFont("SUIT-Bold-48.vlw");
textFont(myfont, 20);
textAlign(CENTER,CENTER);
imageMode(CENTER);
node_icon = loadImage("node_icon.png");
edge_icon = loadImage("edge_icon.png");
select_icon = loadImage("select_icon.png");
load_icon = loadImage("load_icon.png");
}
void print_icon()
{
if(current_mode == 1) image(node_icon, 750 / scaleFactor, 400 / scaleFactor, 70 / scaleFactor, 70 / scaleFactor);
else if(current_mode == 2) image(edge_icon, 750 / scaleFactor, 400 / scaleFactor, 70 / scaleFactor, 70 / scaleFactor);
else if(current_mode == 3) image(select_icon, 750 / scaleFactor, 400 / scaleFactor, 70 / scaleFactor, 70 / scaleFactor);
else if(current_mode == 4) image(load_icon, 750 / scaleFactor, 400 / scaleFactor, 70 / scaleFactor, 70 / scaleFactor);
}
void mode_switch()
{
if(key == '1' && mousePressed == false && istyping == false)
{
if(flow_res > 0) flow_reset();
current_mode = 1;
}
if(key == '2' && mousePressed == false && istyping == false)
{
if(flow_res > 0) flow_reset();
current_mode = 2;
}
if(key == '3' && mousePressed == false && istyping == false)
{
if(flow_res > 0) flow_reset();
current_mode = 3;
}
if(key == '4' && mousePressed == false && istyping == false)
{
if(flow_res > 0) flow_reset();
current_mode = 4;
}
}
int saved_time = -1230, load_time = -1230;
void print_text()
{
textSize(30 / scaleFactor);
textAlign(LEFT,CENTER);
if(current_mode == 3)
{
fill(255,0,0,255);
text("flow : " + str(flow_res),-700 / scaleFactor, -350 / scaleFactor);
}
if(millis() - saved_time < 1000)
{
fill(0,255,0, 255 - (millis() - saved_time) * 255 / 1000);
text("data saved",-700 / scaleFactor, 350 / scaleFactor);
}
else if(millis() - load_time < 1000)
{
fill(0,0,255, 255 - (millis() - load_time) * 255 / 1000);
text("data loaded",-700 / scaleFactor, 350 / scaleFactor);
}
fill(0,0,0,0);
textSize(20);
textAlign(CENTER,CENTER);
}
scaleFactor: 화면 확대 비율을 의미한다.
saved_time, load_time: 각각 마지막으로 저장된 시간, 마지막으로 불러온 시간을 의미한다.
다음으로 그래프 저장 및 불러오기 함수이다.
먼저 그래프 정보는 다음과 같이 구성하였다.
노드 수
(노드 번호) (x좌표) (y좌표)
(노드 번호) (x좌표) (y좌표)
(노드 번호) (x좌표) (y좌표)
.
.
.
간선 수
(정점 번호) (정점 번호) (용량)
(정점 번호) (정점 번호) (용량)
(정점 번호) (정점 번호) (용량)
.
.
.
(유량 근원) (목적지)
저장 함수의 경우 exist 배열과 capacity 배열을 탐색하여 개수를 세 주고, 이를 바탕으로 데이터를 담도록 하였다.
데이터 저장은 String[] 변수에 담았다.
여담으로, 시행착오를 거치며 saveStrings 함수는 현재 소스코드 파일과 동일한 폴더에 저장하고,
loadStrings 함수는 현재 소스코드 파일의 data 폴더 내에서 읽어온다는 것을 알게 되었다.
따라서 상대경로를 이용하여 loadStrings 함수와 동일한 곳에 접근할 수 있도록 파일 경로를 지정해 주었다.
불러오기 함수의 경우 loadStrings 함수를 활용하여 데이터를 읽었으며,
splitToken 함수를 이용하여 문자열을 파싱해 수로 변환하였다.
이 정보들을 바탕으로 그래프를 구성해 주었다.
void save_graph()
{
String[] save;
int N = 0, M = 0;
for(int i=1;i<=100;i++) if(exist[i]) N++;
for(int i=1;i<100;i++)
{
for(int j=i+1;j<=100;j++)
{
if(capacity[i][j] > 0) M++;
}
}
save = new String[N+M+3];
save[0] = str(N);
int idx = 1;
for(int i=1;i<=100;i++)
{
if(exist[i] == false) continue;
save[idx] = str(i) + " " + str(x[i]) + " " + str(y[i]);
idx++;
}
save[idx] = str(M);
idx++;
for(int i=1;i<100;i++)
{
for(int j=i+1;j<=100;j++)
{
if(capacity[i][j] == 0) continue;
save[idx] = str(i) + " " + str(j) + " " + str(capacity[i][j]);
idx++;
}
}
save[N+M+2] = str(source) + " " + str(sink);
saveStrings("./data/data.txt", save);
saved_time = millis();
}
void load_graph()
{
//delete graph
for(int i=1;i<=100;i++)
{
exist[i] = false;
for(int j=1;j<=100;j++)
{
capacity[i][j] = 0;
flow[i][j] = 0;
}
}
String[] input = loadStrings("data.txt");
int N = int(input[0]);
for(int i=1;i<=N;i++)
{
String[] tok = splitTokens(input[i]);
int num = int(tok[0]);
exist[num] = true;
x[num] = float(tok[1]);
y[num] = float(tok[2]);
}
int M = int(input[N+1]);
for(int i=N+2;i<N+M+2;i++)
{
String[] tok = splitTokens(input[i]);
int p = int(tok[0]);
int q = int(tok[1]);
int cap = int(tok[2]);
capacity[p][q] = cap;
capacity[q][p] = cap;
}
String[] tok = splitTokens(input[N+M+2]);
source = int(tok[0]);
sink = int(tok[1]);
load_time = millis();
}
이후 키 설정 및 함수 조직 과정을 거치면 네트워크 플로우를 활용한 그래프 시뮬레이터가 완성된다.
전체 코드는 맨 아래에 첨부하였다.
실행 화면
 |
 |
간선을 추가하는 과정
결론
비교적 생소한 그래프와 네트워크 플로우 알고리즘에 대한 개념을 시각적으로 잘 이해할 수 있도록 표현하여
그래프 이론에 대해 학습하는 사람들이 한눈에 볼 수 있을 것으로 예측된다.
또한, 그래프 시뮬레이션 기능을 활용하여 네트워크 플로우 알고리즘 대신
다익스트라 알고리즘, 크루스칼 알고리즘, Strongly Connected Components 등
막연히 코드로만 학습하는 경우가 대부분인 여러 그래프 알고리즘을 시각적으로 확인하여
그래프 이론과 알고리즘에 대한 폭넓은 학습이 가능할 것으로 예상된다.
한편, 교통량 분산이나 데이터 송신 등 최대 유량 알고리즘을 요구하는 문제가 있을 때
간단한 경우를 본 프로그램을 통해 쉽게 모델링하여 확인하면 문제 해결에 유용할 것이라 기대한다.
프로젝트 파일