네트워크 플로우를 활용한 그래프 시뮬레이터 제작 (3)

마지막으로, UI를 개선하고 데이터 저장 및 불러오기 기능을 제작하였다.

 

먼저 UI 개선이다.

기존에 제작한 프로그램에서는 유량이 어느 방향으로 흐르는 지 알 수 없었다.

따라서 방향을 표시해주어 이를 알 수 있도록 제작하였다.

 

화살표는 밑변 16, 높이 14의 이등변삼각형으로 구성해 주었다.

이때, 유량이 흐르는 방향을 판별하여 이를 향하게 해주어야 하므로 삼각비를 응용하였다.

 

기본적으로 다음과 같이 설정을 해줄 수 있다.
꼭짓점에서 20만큼 뺀 이유는 정점의 반지름이 20으로 표현되기 때문에 이렇게 설정하였다.

각도는 기울기로 구현하였고, 이 과정에서 고려해야 할 사항이 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 );
      }
    }
  }
}

 

이를 실행하면 다음과 같이 여러 방향에 대하여 잘 나타내는 것을 확인할 수 있다.

 

다음으로 데이터 저장 및 불러오기 기능이다.

저장할 데이터는 다음과 같이 구성하였다.

노드 수
(노드 번호) (x좌표) (y좌표)
(노드 번호) (x좌표) (y좌표)
(노드 번호) (x좌표) (y좌표)
.
.
.
간선 수
(정점 번호) (정점 번호) (용량)
(정점 번호) (정점 번호) (용량)
(정점 번호) (정점 번호) (용량)
.
.
.
(유량 근원) (목적지)

 

먼저 데이터 저장 함수이다.

exist 배열과 capacity 배열을 탐색하여 개수를 세 주고, 이를 바탕으로 데이터를 담도록 하였다.

데이터 저장은 String[] 변수에 담았다.

 

여담으로, 시행착오를 거치며 saveStrings 함수는 현재 소스코드 파일과 동일한 폴더에 저장하고,

loadStrings 함수는 현재 소스코드 파일의 data 폴더 내에서 읽어온다는 것을 알게 되었다.

 

따라서 상대경로를 이용하여 loadStrings 함수와 동일한 곳에 접근할 수 있도록 파일 경로를 지정해 주었다.

아래는 그래프 저장 함수이다.

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();
}

 

예시로 다음과 같이 그래프를 생성하고, 저장하였다.

그 결과 생성된 data.txt 파일은 다음과 같다.

4
1 -150.0 0.0
2 -2.0 -121.0
3 0.0 113.0
4 161.0 -5.0
3
1 2 3
2 3 1
3 4 2
1 4

 

각 노드의 좌표, 간선의 정보, 시작점과 도착점이 잘 저장된 것을 확인할 수 있다.

 

다음으로 데이터 불러오기 함수이다.

loadStrings 함수를 활용하여 데이터를 읽었으며, splitToken 함수를 이용하여 문자열을 파싱해 수로 변환하였다.

이 정보들을 바탕으로 그래프를 구성해 주었다.

 

아래는 그래프 불러오기 함수이다.

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();
}

 

예시로 다음과 같은 그래프 데이터를 기존의 data.txt 파일에 덮어썼다.

16
1 -150 -150
2 -150 -50
3 -150 50
4 -150 150
5 -50 -150
6 -50 -50
7 -50 50
8 -50 150
9 50 -150
10 50 -50
11 50 50
12 50 150
13 150 -150
14 150 -50
15 150 50
16 150 150
24
1 2 1
2 3 1
3 4 1
1 5 1
5 9 1
9 13 1
4 8 1
8 12 1
12 16 1
13 14 1
14 15 1
15 16 1
2 6 2
3 7 2
5 6 2
7 8 2
9 10 2
11 12 2
10 14 2
11 15 2
6 7 3
6 10 3
7 11 3
10 11 3
1 16

 

이후 불러오기를 진행하면 아래와 같이 성공적으로 불러오기가 된 것을 볼 수 있다.

또한 다음과 같이 이후의 알고리즘 실행에도 문제는 발견되지 않았다.

이후 몇몇 함수들을 현재 추가한 기능에 맞도록 수정을 진행하였다.

이로써 그래프 생성, 수정, 불러오기가 가능한 네트워크 플로우 시뮬레이터를 완성할 수 있었다.

 

아래는 실행 예시 영상이다.