Визуализация графа силами PHP (без GraphViz)

[mizhgan]

Визуализация графа силами PHP (без GraphViz)

Есть ли каки либо наработки по сабжу? Перерыл все ПХПКлассесы и т.д. - не нашел ничего...

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

Если кому есть чем поделиться - пните в нужную сторону =)

 

[Gas]

а js/flash реализации искал? думаю с их помощью будет нагляднее.

 

[mizhgan]

а js/flash реализации искал? думаю с их помощью будет нагляднее.

Искал все... Единственный вариант нашел - обертка для GraphViz - а это совсем не то, ибо скрипт поставляется пользователям, и лишние зависимости ни к чему.

 

[dimagolov]

Re: Визуализация графа силами PHP (без GraphViz)

Автор оригинала: mizhgan
пользователю необходимо постоянно иметь перед глазами отрисованный граф. В который он будет добавлять-удалять узлы-связи.

из этого однозначно следует, что визуализация должна быть на клиенте, тем более что рисовать графику в броузере это сотни div-ов размером в 1 пиксель и перепихивать их все с сервера на клиента мягко скажем не разумно. библиотеки рисования в JS есть в сети, общение с сервером надо возложить на AJAX и будет вполне красивое решение...

 

[cDLEON]

Я б лучше флешем рисовал...

 

[mizhgan]

Re: Re: Визуализация графа силами PHP (без GraphViz)

Автор оригинала: dimagolov
из этого однозначно следует, что визуализация должна быть на клиенте, тем более что рисовать графику в броузере это сотни div-ов размером в 1 пиксель и перепихивать их все с сервера на клиента мягко скажем не разумно. библиотеки рисования в JS есть в сети, общение с сервером надо возложить на AJAX и будет вполне красивое решение...

Не спорю с тем, что лучше все отрисовывать у клиента. Но может я неправильно выразил суть вопроса - мне нужен сам алгоритм отрисовки направленного графа. Это несколько проблематично, т.к. возможны различные пересечения ветвей, у узлов может быть по нескольку предков и т.д. А уж где все это отрисовывать, я решу.

-~{}~ 08.11.07 18:05:

cDLEON
Я не очень хорошо могу себе представить, как из PHP передавать данные для отрисовки во флеше, ибо не силен в последнем =)

 

[dimagolov]

Re: Re: Re: Визуализация графа силами PHP (без GraphViz)

Автор оригинала: mizhgan
суть вопроса - мне нужен сам алгоритм отрисовки направленного графа.

ооо... батенька... вам в теорию графоав прямая дорога. берите книжечку и читайте. причем далеко не любой граф имеет плоское представление без пересечений.

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

 

[mizhgan]

Re: Re: Re: Re: Визуализация графа силами PHP (без GraphViz)

Автор оригинала: dimagolov
ооо... батенька... вам в теорию графоав прямая дорога. берите книжечку и читайте. причем далеко не любой граф имеет плоское представление без пересечений.

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

Теорию графов я изучал уже давненько и довольно плотно =) Все что касается графов, их способа хранения в базе, обработку и т.д. - все это сделано. Необходим лишь алгоритм визуализации графа.

Насчет второго - представьте такое. Юзер запускает скрипт. Ему выводятся перечень графов, хранящихся в базе. Он нажимает напротив нужного - отобразить - и вуаля, ему должен отобразиться этот самый выбранный им граф. Тут одним дрэг-энд-дропом не обойтись, т.к. сначала нужно отобразить удобоваримо уже записанный в базу граф, а потом уже юзер сможет его редактировать.

В общем похоже все таки придется самому сидеть, придумывать как его отобразить... хотел сэкономить время, используя что нибудь готовое =) Но кроме консольного GraphViz похоже нет ничего в паблике...

 

[neko]

есть, есть
недавно совсем видел.

 

[mizhgan]

neko

Буду премного благодарен, если укажешь где можно найти.

 

[crocodile2u]

mizhgan
не знаю, может быть, покопать в сторону SVG? Богатые средства визуализации + возможность упралять элементами с помощью скриптов...

 

[mizhgan]

crocodile2u

Да, SVG будет скорей всего использоваться для ВЫВОДА графа в браузер (хотя может проще будет обычными дивами). Но нужно именно сама логика, как будут располагаться элементы графа, исходя из его структуры. SVG будет уже в конце, именно сам вывод, когда уже будет сформировано представление, где располагается каждый узел.
Мне нужно именно такой алгоритм, который берет граф, представленный допустим матрицами, и выдает для каждого узла - узел первый должен располагаться по таким то координатам допустим, узел второй - по таким, третий...десятый и т.д. И соответсвенно для ребер - из таких то координат в такие то нарисовать ребро и т.д.
Что то вроде этого...

 

[crocodile2u]

mizhgan
ну да, я и говорил только про пользовательский интерфейс.

 

[dimagolov]

mizhgan
я имел в виду, что если графы не машиногенеренные изначально, а рисуются юзером, то надо просто сохоанять логическое представление графа, плюс координаты вершин в окошке, которое получилось у юзера. чтобы он открыв свой граф во 2-й раз получил именно то, что он нарисовал, а не эквивалентный его графу граф, нарисованный скриптом.

 

[Gremboloid]

mizhgan
лет пять назад страдал графами (дискретная математика).
Автоматизировать построение изображения ( в данном случае ориентированного графа) полностью не получится.
А если есть ограничение чтобы ребро не накладывалось на вершину и наоборот, то тем более для построения графа нужна рука человека.

Помимо самого графа придётся хранить координаты его вершин на изображении, которые вводит человек.

dimagolov +1

 

[mizhgan]

dimagolov
Понял твою мысль, буду пробовать...

Gremboloid
Единственный приемлемый способ визуализации, который я нашел - это отрисовка всех узлов по кругу(эллипсу) с последующим соединением их ребрами. Но тут конечно ни о какой красоте и наглядности для юзера речи нет.

neko
Кудаж ты пропал... может все таки поделишься информацией?