글쓴이 ·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

글쓴이 ·0개의 댓글

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

영야초-4A

맨날 결계조로만 해서 다른 기체는 익숙하지 않아서 4A에서 각부를 못 채워서 라스트 스펠을 획득하지 못 하고 있었는데 오랜만에 홍마조로 플레이해서 획득. 결계조가 성능이 좋은건지 다른조가 성능이 안 좋은건지 잘 모르겠지만 호밍탄이 없으니까 불편해 죽겠다 =ㅅ=

글쓴이 ·0개의 댓글

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

주먹왕 랄프를 봤다. 아이스 에이지 3를 보고 엄청 실망했던 기억이 있어서 애니메이션 영화라 조금 미뤄 두고 있었는데, 우연히 기회가 되서 보게 되었다. 3D 애니메이션 영화 치고 유치하지 않아서 좋았다.

자세한 걸 말하면 스포일러가 되서 말하지 않겠지만, 복선 부분이 상당히 잘 짜여져 있었다. 여러 다른 게임 간의 요소들이 유기적으로 결합되어서 하나의 큰 스토리를 만들어 가는 점이 인상적이었다.

게임기가 꺼지고 사람들이 없어지면 게임 속의 인물들이 살아난다는 아이디어 자체는 토이 스토리 등에서 이미 나왔던 주제였기 때문에 그렇게 신선하지는 않았지만, 세계관을 통해서 그것을 극복해냈다. 특히 게임들이 연결된 플러그에 ‘게임 센트럴’이 있고, 거기서 다른 게임으로 이동한다는 아이디어가 굉장히 독특했다.

이 작품의 히로인인 바넬로피도 매력적인 캐릭터였다. ‘말괄량이 꼬맹이’ 이미지를 굉장히 잘 살려 냈고, 그 이미지 덕분에 랄프와 화해하는 장면이 더욱 감동적으로 다가왔다.

오락실을 기반으로 했기 때문에 나오는 깨알같은 재미도 있다. 캔디 킹이 코나미 커맨드를 입력하는 장면이나 류랑 켄이 싸우다가 술 마시러 가는 장면 등 아는 사람은 아는 굉장히 재밌는 장면들이 많다.

3D 애니메이션 영화는 애들이나 본다는 생각을 가진 사람들이 많은데, 청소년들이나 어른들이 봐도 충분히 재밌을 것 같은 영화였다. 정말 다양한 매력을 가진 영화였다.

안 본 사람들은 꼭 한 번 보시길!