Задача о размещении

При рисовании сети, визуализирующей большую группу людей и связей между ними, требуется решить, где разместить на картинке каждое имя (или значок). Рассмотрим, например, сеть, изображенную на рис. 5.7.

Из рисунка видно, что Август (Augustus) дружит с Вилли (Willy), Вайолетом (Violet) и Мирандой (Miranda). Но сеть нарисована беспорядочно, а при добавлении новых людей в ней вообще будет невозможно разобраться. На рис. 5.8 изображено более понятное размещение.

Рис. 5.7. Неудачное размещение сети

 

Рис. 5.8. Улучшенное размещение сети

В этом разделе мы посмотрим, как применить методы оптимизации для создания упорядоченных визуальных образов. Заведите новый файл socialnetwork.py и включите в него некоторые факты о малом подмножестве социальной сети:

import math

people=[‘Charlie’,’Augustus’,’Veruca’,’Violet’,’Mike’,’Joe’,’Willy’, ‘Miranda’]

links=[(‘Augustus’, ‘Willy’), (‘Mike’, ‘Joe’), (‘Miranda’, ‘Mike’), (‘Violet’, ‘Augustus’), (‘Miranda’, ‘Willy’), (‘Charlie’, ‘Mike’), (‘Veruca’, ‘Joe’), (‘Miranda’, ‘Augustus’), (‘Willy’, ‘Augustus’), (‘Joe’, ‘Charlie’), (‘Veruca’, ‘Augustus’), (‘Miranda’, ‘Joe’)]

Наша задача – написать программу, которая получает на входе информацию о том, кто с кем дружит, и генерирует удобную для восприятия диаграмму сети. Обычно для этого применяется алгоритм масс и пружин. В его основе лежит физическая модель, поскольку различные узлы давят друг на друга, пытаясь «оттолкнуться», тогда как связи сближают соединенные между собой узлы. Следовательно, сеть медленно приближается к такому состоянию, когда несвязанные узлы находятся далеко друг от друга, а связанные – близко, но не слишком. К сожалению, алгоритм масс и пружин не препятствует пересечению линий. В сети с большим количеством звеньев из-за этого трудно понять, какие узлы связаны между собой, поскольку визуально проследить линию проблематично. Но если применить к задаче размещения оптимизацию, то нужно лишь определить целевую функцию и попытаться ее минимизировать. В данном случае интересная целевая функция – это количество пересекающих друг друга линий.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100