Доброго дня или ночи уважаемые коллеги!

Есть задачка которую я полгода тащу и даже боюсь начать решать...
Речь идет о сортировке. Попробую объяснить:

В общем есть ... например база данных по учету друзей и их связей.
Таблица с полями (имя первого человека, имя второго человека) - чел1,чел2. Каждая запись в таблице означает что между ними есть связь т.е. - дружба ;).

Итак имеется большое кол-во друзей, и необходимо построить графическую связь м/у всеми участниками "друзьями". (Сразу всплывает на ум яз.прог. - Пролог).
Задача решить проблему наиболее оптимальным расположением объектов (друзей) и их связей.

Например имеем базу с записями:
Миша, Вова
Надя, Вадим
Вадим, Наташа
Наташа, Миша
Вова, Вадим
Вова, Надя

Графический (псевдографически) это выглядит примерно так:

Миша --- Вова ---------
| |
Наташа --- Вадим --- Надя

Может кто-нибудь сталкивался с подобной задачей, или может кто силен в сортировках прошу внести свою лепту в существующей проблеме.

Спасибо за внимание.

Вобще-то символ | стоял над Надей, показывая связь между Вовой и Надей... Но в итоге получилось смещение.

Кое какую схему я все таки отображаю в виде связей, но сделать это с наименьшим количеством пересечений не получается...

BMJ

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

Уважаемый ВладимирМ! Спасибо за отклик.
Не будь Вы таким профи в фоксе я бы Вам ответил, зря Вы не дооцениваете фокс...

Как раз графическая часть проги у меня проработан, т.е. объекты и линии уже продуманы, также есть возможность перемещать пользователем каждый объект на схеме сохраняя при этом связующие линии.

И Вы совершенно правы на счет кругового отображения в части одного человека (я это и применяю), но когда объектов несколько сотен и от каждого объекта исходят десятки (сотни) связей (при конечных связях в одном объекте построение идет кругом) и пересечений скажем премножество, возникает задача расположить объекты так чтобы пересечений (линий) м/у объектами было наименьшим иначе это все принимает неудобоваримый вид.

Задача не из легких, но и не из области фантастики :)

Примерно вот так, если конечно увидете - не знаю как файл прикрепить :)

Алгоритм у меня примерно таков:

1. Определить количество друзей у каждого объекта.
2. Удалить обратные и лишние повторы в связях (н-ер Миша, Света = Света, Миша)
3. Начать цикл с наиболее "дружественных" объектов у которых больше всего друзей и идти по нисходящей (хотя не факт!)

_отклонение=0
_Цикл
____ ob =текущий объект
____координаты(x+отклонение,y)
____перебор всех друзей ob
________если текущий друг имеет своих друзей (т.е. кол-во друзей >0)
________то оставить его на потом
________иначе пристроить его кругом к товарищу ob
____конец перебора
____отклонение=отклонение+1
_конец цикла

А вот когда его смещать по Y и в какой очередности понятия не имею...

ВладимирМ Вот именно про это я и говорил, что эта задача не для FoxPro. Проблема не в том, чтобы отобразить, а в том, чтобы рассчитать координаты узлов графа. Это огромное количество сочетаний вариантов. Впрочем, если есть формализовааная теория (я просто не в курсе), то, разумеется, можно попробовать выполнить этот расчет и в FoxPro.

Расчет зулов графа, по моему не вопрос графики ведь эти узлы накладываю я сам, т.е. сам задаю координаты из каких то соображений (правда их пока у меня нет :)).

ВладимирМ Как еще один вариант - отдать вопрос расположения на откуп пользователю. Т.е. "набрасываешь" узлы и линии графа как получится (как смог рассчитать), а уже пользователь сам сдвигает картинки как ему удобно. Ты только фиксируешь новые координаты узлов графа.

Вот-вот для любителей рисования это подойдет, но только для них...

ВладимирМ Лично я пошел бы все-таки по пути уменьшения количества одновременно отображаемых узлов. Например, не более 2...3 уровней от указанного человека.

Уверяю Вас 2 или 3 уровня это и то уже тысячные объекты.

ВладимирМ Может быть также стоит поискать другие способы визуализации. Сомневаюсь я как-то, что граф удебен с точки зрения анализа. Самое большее, что он может дать - это общее качественное представление по принципу много/мало. Если же дело дойдет до конкретного анализа по конкретному человеку, то граф - слишком неудобный инструмент.

Проследить связи в графическом виде где не один объект является интересным, по моему является самым удобным видом представления... По крайней мере альтернативу от Вас выслушал бы с нескрываемым любопытством.

К радиальной системе я перешел.

ВладимирМ Если есть пересечение линий (это просто найти по массиву координат линий), то попробуй просто увеличить радиус, чтобы пересечения не было. Если радиус увеличивается больше чем некая фиксированная величина, то увеличение радиуса для данной комбинации - тупиковый путь. Оставь как есть.
Все промежуточные данные - в курсор. Массив - это тормоза.

Да можно сначало все раскинуть на поле а затем гонять все по массиву пересечений, но меня убивает что эти самые линии я кладу сам - зачем мне их повторно рассчитывать?... Мне кажется здесь решать нужно на уровне объектов а не получившихся линий от них, но это представление настолько смутное что у меня случаются теоретические припадки :)

Ваше замечание согласен имеет место быть, в случае когда нам интересны какие то несколько объектов и можно начинать пляски от них, но когда все имеют один ранг и все равны перед Богом, наиболее главное значение имеет связующие звенья т.е. главные узлы.

Правильное действие мне кажется кроется в изначальном определении мест объектов в некоей матрице размером (x,y) где x*y кол-во объектов и каждый объек имеет свое "место". Где рассчет главных узлов теоретически должно падать в центр и по ней от центра пристраиваться остальные объекты, хотя опять же если бы я был уверен в этом и с чего начинать...

Здесь по моему математическая модель более важнее чем применение FoxPro...

Может мне в другой форум обратиться? Где мне могут помочь, как вы думаете?