글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

원더플에서도 확인하실 수 있습니다.

JAVA 버전을 플래시로 포팅한 버전입니다.

JAVA 버전과는 달리 그래프 생성까지 내부에서 처리하며, 항상 연결 그래프를 생성합니다.
플래시 버전에서는 드래그 가능 범위가 조금 더 제한되어 있습니다.

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

JAVA를 사용해 구현한 Force-Directed Graph Drawing입니다.
프로젝트 이름에 ‘Forced’라고 오타가 있습니다 ㅜㅠ

노드를 드래그 할 수 있습니다.

input.txt에서 그래프 데이터를 읽어오며, 형식은 다음과 같습니다.

  • 첫 번째 줄에 노드 개수 n과 간선 개수 m이 공백으로 구분되어 주어집니다.
  • 두 번째 줄부터 m줄에 걸쳐 숫자 두 개가 공백으로 구분되어 주어집니다. 두 숫자 번호를 가진 노드를 연결하는 간선을 의미합니다.

FDG.zip

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

위키피디아

Force-Directed Graph Drawing는 그래프 시각화 중 한 방법으로써 노드들끼리는 척력을, 에지로 연결된 노드에는 인력을 적용시키는 방법입니다.

보통 노드끼리의 반발력은 전하(쿨롱의 법칙) 형태로 적용시키고, 에지로 연결된 노드끼리의 인력은 용수철(훅의 법칙) 형태로 적용시키게 됩니다.

Force-Directed Graph Drawing의 장점은 다음과 같습니다.

  • 좋은 결과 : 중간 크기 정도의 그래프(50~100개의 노드)에서 통일성 있는 에지 길이와 노드 분산, 대칭성의 세 가지 기준을 굉장히 잘 만족하는 결과를 보여줍니다.
  • 유연성 : 확장하기 쉽습니다. Force-Directed Graph Drawing을 확장해서 방향 그래프, 3D 그래프, 클러스터 드로잉, 동적 그래프 드로잉 등 다양한 분야에 적용시킬 수 있습니다.
  • 직관성 : 용수철 등과 같은 물리 법칙을 사용하기 때문에 결과를 예상하고 이해하기 쉽습니다.
  • 단순성 : 전형적인 Force-Directd Graph Drawing은 다른 그래프 시각화 방법에 비해 쉽게 구현할 수 있습니다.
  • 유동성 : 알고리즘 적용 중간 과정을 보여줌으로써 사용자는 그래프가 어떻게 진화해 나가는지 관찰할 수 있습니다.
  • 강력한 이론적 토대

단점은 다음과 같습니다.

  • 낮은 퍼포먼스 : 전형적인 구현에서는 n을 그래프의 노드 개수라 할 때, O(n^3)의 시간복잡도를 가집니다. 물리학의 N-body problem과 관련있습니다. N-body problem과 관련된 알고리즘을 사용해 시간복잡도를 낮출 수 있지만, 구현이 복잡해집니다.
  • 나쁜 지역 최적해 : Force-Directed Graph Drawing은 종종 전역 최적해가 아닌 지역 최적해를 생성합니다. 이는 낮은 품질의 결과를 가져오게 됩니다. 그래프를 구성하는 노드 개수가 많아질수록 초기 상태에 더 큰 영향을 받게 됩니다.

글쓴이 ·0개의 댓글

[이 글은 이전에 쓰던 블로그에서 작성된 이후 새 블로그로 이전된 글입니다.]

정점 개수와 간선 개수를 입력하면 그에 맞게 그래프의 정보를 생성해 주는 프로그램입니다.

첫 줄에 정점 개수와 간선 개수를 출력하고, 그 아래줄에 연결된 간선들 사이의 정보를 출력해줍니다.

중복된 간선은 출력하지 않는데, 간선 개수가 그 정점 개수로 나올 수 있는 총 간선의 수보다 많다면 프로그램이 끝나지 않는 버그(?)가 있습니다.

from random import randrange

n, m = map(int, raw_input().split())
print n, m

dict = {}

for i in range(m):
    a, b = randrange(0, n), randrange(0, n)
    s = tuple(sorted((a,b)))
    while a==b or s in dict:
        a, b = randrange(0, n), randrange(0, n)
        s = tuple(sorted((a,b)))
    dict[s] = 1
    print a, b