Построение графа по ребрам
Написать программу для построения орграфа по списку ребер. ( ВОЗМОЖЕН ВАРИАНТ АДАПТАЦИИ ЧУЖИХ РАЗРАБОТОК ПОД ТЗ, и даже использование стороннего ПО). Можно делить программу на отдельные модули связывая простыми действиями пользователя.
Входные данные: таблица в БД MySQL вида: вершина1 (int64), тест1 (50 символов), вершина2(int64), текст2 (50 символов), сила (int). Ключ пара: вершина1-вершина2. Каждая строка это 1 ребро, направление стрелки от 1 к 2. Текст однозначно привязан к номеру вершины (в случае если вершина входит в несколько ребер, текст дублируется). Сила должна символизировать жирность линии, соединяющую вершины (или быть отмечена другим способом, например, надписана над стрелкой). Вершины обозначаются номерами, но не по порядку (т.е. например вершины с номером 10 может не быть, а 11 уже быть, а потом 12 снова не быть).
Выходные данные: картинка, с приблизительными пропорциями бумаги, в распространенном векторном формате. Требование к картинке одно - легкочитаемость. Крайне желательно что бы надписи не накладывались и было меньше мазьни (увеличивайте размеры картинки, уменьшайте текст если надо).
Описание программы и алгоритма обязательно (в случае адаптации чужих проектов, соответственно описание процесса взаимодействия модулей и последовательность действий).
Программа должна быть работоспособной при больших массивах данных. Следует орентироваться на ~2 млн. ребер и 0,5 млн вершин. Время счета должно быть разумным (хотя бы несколько дней). Т.к. счет может затянуться, то обязательно что бы была возможность сохранения промежуточных результатов и прерывания работы на ночь. Если вы найдете алгоритм, который расставит вершины быстрее чем за 5 часов, то эта опция не обязательна.
Язык программирования на выбор программиста (желательно PHP, Delphi). Система Windows XP-2003. Можно использовать жесткий диск и MySQL (в составе Денвера). Желательно что бы программа работала с приоритетом ниже среднего.
Для сдачи проекта необходима демонстрация и внятные объяснения почему алгоритм всегда будет делать красивую картинку.
Бюджет можно увеличить за счет реализации доп. наворотов (оговариваются отдельно):
1. Работа на 2х-4х процессорных системах.
2. Различные виды отображения.
3. Раскраска и заливка графа.
4. Поддержка других графических форматов: png, svg.
5. Группировка нескольких вершин в область. (формат данных оговаривайте отдельно)
6. Возможность редактирования картинки, т.е. движение вершин и ребер и сохранение произведенных изменений.
7. Выбор пропорций листа.
8. Процентная стрелка и расчет временных затрат.
и другие функции повышающие удобство работы.
Сроки предлагайте сами, обговорим, я рассчитываю на месяц.