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

이번 시간에는 그래프를 생성 및 수정할 수 있는 프로그램을 제작하기로 했다.

먼저 다음과 같이, 그래프를 다룰 수 있는 변수들을 설정했다.

//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와 flow는 각각 해당 간선의 용량과 현재 흐르고 있는 유량을 의미한다.

네트워크 플로우 알고리즘을 사용할 것이기 때문에 이렇게 2개의 데이터를 관리해 주어야 한다.

 

x와 y에는 각 노드의 좌표를 저장하고, 추가로 boolean 데이터 exist를 관리하여 해당 노드가 존재하는지 판별해 주었다.

 

 

첫 번째로 그래프를 그리는 코드이다. 단순 구현 코드이므로 추가 설명은 생략한다.

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)) 
      {
        stroke(0,0,0,50);
        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[i][j]) + "/" + str(capacity[i][j]);
        text(info, (x[i] + x[j])/2, (y[i] + y[j])/2 );
      }
    }
  }
}
void node_draw() 
{ 
  for(int i=1;i<=100;i++) 
  {
    if(exist[i] == true) 
    {
      stroke(0,0,0);
      fill(255,255,255); ellipse(x[i],y[i],40,40); 
      fill(0,0,0); text(i,x[i],y[i]);
    }
  }
}
void drawscreen()
{
  fill(255,255,255);
  background(255,255,255);
  edge_draw();
  node_draw();
}

 

다음으로, 시스템 내부에서 노드와 간선을 생성 및 삭제하는 코드이다.

노드는 exist 변수로 관리하고, 간선은 capacity가 0임을 판단하여 생성 및 삭제를 관리하였다.

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

 

이제 구현해야 할 것들을 정리하면 다음과 같다.

• 노드 생성
• 노드 삭제
• 노드 이동
• 간선 생성
• 간선 삭제
• 간선 용량 변경

먼저 이 6가지를 동시에 수행되게 하려면 꽤나 복잡하기 때문에, 노드 편집 상태와 간선 편집 상태로 나누게 하였다.

이는 변수 current_mode로 관리하여, 1이면 노드 편집, 2면 간선 편집을 의미하게 하였다.

 

먼저 노드 생성의 경우, 처음 생성한 노드는 당연히 아무 노드에도 연결되어 있지 않을 것이므로 그냥 중앙에 생성되게 하였다.

이때, 항상 노드가 연속적으로 존재한다는 보장이 없으므로, 존재하지 않는 노드 중 가장 작은 번호의 노드로 생성되게 하였다.

 

노드 생성은 엔터 키를 눌렀을 때 생성되게 하였다.

 

코드는 다음과 같다.

void keyPressed()
{
  if(key == ENTER && current_mode == 1)
  {
    for(int i=1;i<=100;i++)
    {
      if(exist[i] == true) continue;
      add_node(i);
      break;
    }
  }
}

 

 

다음으로 노드 삭제 연산이다.

노드를 클릭하는 것을 감지해야 하는데, 이는 마우스를 클릭했을 때노드와 마우스 간의 거리가 적당히 작다면

노드를 클릭한 것으로 판별하도록 구성하였다.

 

select_node 함수를 구성해준 후, 모든 노드를 순차적으로 탐색하여 거리가 가까운 노드가 발견될 때까지 탐색하였다.

조건을 만족하는 노드가 발견되었고, 우클릭이 감지되었다면 이는 삭제 연산으로 판별한다.

 

굳이 함수로 정의한 이유는 추후 어떤 노드를 선택했는지를 판별하는 것이 자주 쓰이므로 아래 코드와 같이 구성하였다.

 

 

코드는 다음과 같다.

int selected_node = 0;
float X, Y;
float distance(float x_, float y_){return (X - x_) * (X - x_) + (Y - y_) * (Y - y_);}

void select_node()
{
  selected_node = 0;
  txt = 1234567;
  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)
  {
    delete_node(selected_node);
    selected_node = 0;
  }
}

 

다음으로 노드 이동 연산이다. 이는 좌클릭 후 드래그하는 것으로 처리되게 하였다.

직전에 select_node 함수 호출로 현재 클릭한 노드의 번호를 저장하였으므로, 이를 마우스가 떼질 때까지 따라다니게 하면 된다.

 

이때 transform, scale이 지원되게 하였으므로 이에 맞추어 선형변환시켜준 새로운 좌표를 활용한다.

 

코드는 다음과 같다.

void selected_node_follow() { x[selected_node] = X; y[selected_node] = Y; }

 

 

이제 간선 연산을 구성할 단계이다.

 

먼저 간선 생성은, 좌클릭 후 드래그로 생성되게 하였다.

처음 클릭했을 때 적당한 거리에 노드가 존재하고, 마우스 클릭을 뗐을 때의 위치에도 적당한 노드가 존재한다면 이를 연결시켜 주었다.

이때 두 노드가 같은 경우나 이미 간선이 있는 경우는 제외하고 생성해 주었다.

 

코드는 다음과 같다.

이때 처음 클릭한 노드는 이미 select_node로 호출되었으니 생략한다.

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

 

다음으로 간선 삭제 연산이다.

마찬가지로 우클릭 시 삭제되게 하였고, 간선 클릭 판별은 간선의 중점이 클릭되었을 때로 간주하였다.

간선은 직선이므로 두 정점의 좌표로 구할 수 있게 된다.

 

코드는 다음과 같다.

(istyping 변수는 바로 뒤에서 구성할 간선 수정 연산에 사용되는 변수이다.)

void 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;
    }
  }
}

 

마지막으로, 간선 가중치 수정 연산이다.

클릭 감지는 간선 삭제와 동일하게 구성하면 되고, 타이핑 부분만 관리해주면 된다.

 

현재 가중치에서 백스페이스를 누른다면, 마지막 한 자리가 소멸된다.

이는 현재 가중치를 10으로 나누고 그 몫을 취하는 것과 동치이다.

 

현재 가중치에서 0부터 9까지의 키를 누른다면, 맨 끝에 수 하나가 추가된다.

이는 현재 가중치에 10을 곱하고 해당 키를 더하는 것과 동치이다.

 

이 원리를 활용하여 타이핑 기능을 만들 수 있다.

 

코드는 다음과 같다.

key 변수가 char임을 이용하여 간략화해주었다.

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

 

이를 종합적으로 구성하면 그래프 생성 및 수정 기능을 완성할 수 있다.

 

아래는 전체 코드와 사용된 이미지 및 폰트 파일 폴더이다.

GraphEditor.zip

0.03MB

 

향후 계획

생성된 그래프에 네트워크 플로우 알고리즘을 적용시켜 경로를 찾을 수 있게 구성할 것이다.

또한, 간선의 비용도 관리할 수 있게 기능을 추가할 계획이다.