도면을 작성하는 자동 레이아웃 알고리즘

지난 몇 달 동안 저는 finite state machine editor를 토대로 개발했습니다React Flow.어느 순간, 나는 신기하게도 상태기를 시각화하는 설정을 가져오고 싶었다.그래픽 레이아웃 알고리즘이 필요합니다.몇 년 전에 나는 업무 흐름 편집기를 위해 유사한 기능을 실현했다.해결해야 할 가장 큰 문제는 무엇입니까?생성된 시각화가 이해할 수 있고 읽을 수 있는지 확인하십시오.이것은 믿을 만한 알고리즘이 필요하다.
만약 도형의 모든 노드가 화면에 분산된다면, 그것들 사이의 직선을 따라 이동하기 매우 어렵다.내가 취한 방법은 논문"A technique for drawing directed graphs (1993)"에 기초를 두고 있다.이것은 교차변의 수량에서 (부분적) 최소치를 찾아내는 기술을 바탕으로 하는 것이다. 아래와 같다.나의 실현은 세 가지 절차를 포함한다. (1) 모든 노드를 정렬하고 (2) 노드의 순서를 최적화하며 (3) 각 노드의 위치를 확정한다.

모든 노드 정렬

알고리즘의 첫 번째 단계는 모든 노드를 정렬하는 것이다.모든 그림에는 초기 노드가 있습니다.프로세스/워크플로우의 시작점 또는 상태기의 초기 상태입니다.이 특정 노드는 질 0에 있다.이 기점에서 우리는 세 가지 절차에 따라 모든 노드의 초기 순서를 확정한다.

각 노드의 초기 등급을 확정한다.노드의 등급은 이 노드와 초기 노드 사이의 가장 짧은 경로의 길이와 같다.레벨은 breadth-first search algorithm로 확정할 수 있습니다.

를 사용하여 depth-first search algorithm를 사용하여 시작 노드에서 시작할 수 있는 모든 경로를 확인합니다. 아래와 같습니다.

가장 긴 경로에 나타나는 상황에 따라 열 그룹 내의 모든 노드를 정렬합니다.경로가 긴 노드는 한 열의 위치가 비교적 높다.

function getPaths(nodeId, edges, path = [], paths = []) {
  const children = edges.filter((e) => e.source === nodeId);

  const _path = [...path, nodeId];

  // To avoid cycles in paths
  if (path.includes(nodeId)) {
    paths.push(path);
  } else if (!children || children.length === 0) {
    paths.push(_path);
  } else {
    children.map((c) => getAllPaths(c.target, edges, _path, paths));
  }

  return paths.sort();
}

다음 예제에서는 이러한 단계를 수행할 때의 결과를 보여 줍니다.모든 노드가 설명한 대로 정렬되어 있음을 알 수 있습니다.이 예에서 노드 4는 질 2의 꼭대기에 위치하는데, 가장 긴 경로에 나타나고 노드 5는 없기 때문이다.

노드 순서 최적화

위의 시각화 디스플레이는 이 절차에 따라 노드를 정렬하면 읽을 수 있는 결과를 얻을 수 있다.하지만 개선은 가능하다.이른바 'NP-hard' 문제이기 때문에 완벽한 해결 방안은 없다.그러나 일정한 절차의 순서에 따라 몇 번, 우리가 경계 조건에 도달할 때까지 우리는 (부분적으로) 가장 좋은 것에 접근할 수 있다.아니면 교차변의 최소 수량을 아시오.이것은 계발식이라고 불린다.

A heuristic is a practical problem-solving approach that is not guaranteed to be optimal, perfect, or rational. It is enough for an (intermediate) goal.

이런 계발식의 중요한 부분은 배치에 점수를 매기는 능력이다.이 점수는 도형의 각종 돌연변이를 비교하는 데 사용되며, 이 점수에 따라 (국부) 최적치를 찾을 수 있다.앞에서 말한 바와 같이 이 알고리즘의 사상은 교차변의 수량을 최소화하는 것이다.따라서 우리의 점수는 이와 관련이 있어야 한다.간단한 채점 메커니즘은 다음과 같습니다.

계산 원본과 목표가 같은 열에 있고 서로 인접하지 않는 변수.그것들 사이의 노드 수를 계산할 수도 있다.원본과 목표가 더 멀리 떨어져 있을 때, 이것은 더욱 높은 점수를 줄 것이다.

모든 열 그룹 조합을 보고 두 열 그룹 사이의 모든 모서리(방향에 상관없이)를 계산합니다.

// Assumes both edges have the source in a lower rank
// edge = [sourceIndexInRank, targetIndexInRank]

function edgesCross(edge1, edge2) {
  if (edge1[0] < edge2[0] && edge1[1] > edge2[1]) {
    return true;
  } else if (edge1[0] < edge2[0] && edge1[1] > edge2[1]) {
    return true;
  }
  return false;
}

채점 메커니즘이 확정됨에 따라 실제의 계발을 볼 때가 되었다.내가 선택한 계발식 방법은 모든 열을 반복해서 훑어보고 두 개의 인접한 노드를 교환하는 것이다.만약 그들이 평점을 개선하거나 적어도 악화시키지 않는다면, 돌연변이는 잠시 변하지 않을 것이다.이런 메커니즘이 완벽하지 않고 모든 가능한 돌연변이를 탐색한 것도 아니기 때문에 우리는 이런 계발식을 최대 X회 응용하여 성능과 최상의 결과를 균형 있게 할 수 있다.계발식의 상세한 절차는 다음과 같다.

i = 1를 rank[i]로 이동시킵니다.

양보j = 0.rank[i][j]로 교환rank[i][j + 1].

새 도형의 점수를 확정하고 점수가 나빠지면 돌연변이를 반전시키고 그렇지 않으면 돌연변이를 보류한다.

가능한 경우 설정j = j + 1, 가능한 경우 설정i = i + 1, 단계 2를 반복합니다.둘 다 불가능하면 단계 5로 이동합니다.

생성된 그림에 더 좋은 점수가 있으면 새 그림에 대해 1단계를 최대 X회까지 반복합니다.그렇지 않으면 너는 가장 좋은 것을 찾을 것이다.

앞서 사용한 예제 그래픽에는 두 개의 교차 모서리가 있습니다.상술한 계발식을 응용함으로써 우리는 두 가지 돌연변이를 응용하여 이 점을 최적화할 수 있다. 위의 그림과 같다.우리가 노드 2와 노드 3을 교환했을 때 우리는 같은 점수2를 얻었다.이것은 돌연변이를 응용하고 계속하는 것을 의미한다.그림% 1개의 캡션을 편집했습니다.2와 3을 교환한 후에 4와 5를 교환할 때 우리는 완벽한 점수를 찾아 우리의 결과도를 얻을 수 있다.

각 노드의 위치 결정

우리가 모든 노드를 최적화한 후에 각 노드의 위치를 확정할 때가 되었다.여러 가지 경로를 사용할 수 있지만 가장 간단한 방법은 노드를 격자 안에 놓는 것이다.결국 우리 팀은 하나의 격자였다.다음은 앞의 장에서 운행 예시를 사용하여 이에 대해 설명하였다.메쉬를 사용하여 여러 옵션을 작성하여 도면을 배치할 수 있습니다.이전 절에 표시된 시각화와 같은 전통적인 노선을 선택할 수 있습니다.
모든 노드가 중심선을 중심으로 배치되는 보다 균형 잡힌 그래픽을 사용할 수도 있습니다.초기 랭킹에서 시종일관 하나의 노드만 있다.도면의 방향에 따라 이 초기 노드는 수평 또는 수직 중심선에 배치됩니다.예시에서 보듯이 노드 1, 2, 8은 모두 이 중심선에 있는 것이지 한 선에 다섯 개의 노드가 있는 것이 아니다.

|   |   | 3 |   |   |   |   |   |   |
|   |   |   |   | 5 |   | 6 |   |   |
| 1 |   | 2 |   |   |   |   |   | 8 |
|   |   |   |   | 4 |   | 7 |   |   |
|   |   | 9 |   |   |   |   |   |   |

마무리

방향도(또는 상태기)의 자동(또는 신기한) 레이아웃을 해결하는 것은 내가 겪은 가장 재미있는 도전 중의 하나이다.연구를 통해 나는 내가 이해하고 실행할 수 있는 알고리즘을 발견했다.묘사한 알고리즘은 중소형 그림에 효과적이다.이 그림의 대부분은 거미줄이 아니라 유한한 변이 있다(예를 들어 노드마다 2-3개의 출구변이 있다).날 못 믿어?나는 자신이 만든 온라인 state machine editor 에서 이 알고리즘을 사용했다.그러나 이것은 정의적으로 완벽하지 않다는 계발이다.나는 이미 몇 가지 개선을 생각했다.

는 특정 유형의 교차변의 권중을 변경할 수 있다(예를 들어 열 그룹과 교차변의 권중이 더 높다).이것은 사용자가 자신의 필요에 따라 알고리즘을 제어할 수 있도록 합니다.

노드가 최적화 단계에서 열 그룹 사이를 이동할 수 있도록 합니다.그래픽의 시작점과 끝점 노드가 고정되어 있지만 경로 길이가 많이 변하는 경우 이를 개선하는 데 도움이 됩니다.

돌연변이 방식을 최적화하고 어떤 돌연변이를 응용해야 하는가.예를 들어, 인접 열 그룹만 검사하여 성능을 향상시킬 수 있습니다.그러나 이는 결과를 악화시킬 수 있다.

I've created a JavaScript package called DIGL that implements the described algorithm. It is framework agnostic and can be used in the front-end or back-end.