|
Тема
|
Изчертаване на граф
|
|
Автор |
legato (Mr.NoOne) |
Публикувано | 03.12.03 10:33 |
|
Здравейте,
ако имаме тхт файл в който са описани дъгите, ребрата и теглата на дъгите на даден граф - примерно
(а,с,3) // има дъга между а и с, с тегло 3
(а,в,1)
....
как най-лесно може да се визуализира този граф в Delphi ?
Благодаря
| |
|
Никак лесно ;-)))) - и това няма нищо общо с Delphi или който и да е език за програмиране - задачата е доста сложна ще ти трябва основно математика - и много борба.
Друго не мога да ти кажа - само знам, че подобни алгоритми се ползват на много различно място от колкото очакваш - имаше една програма за документация - която изважда класовете от кода и прави диаграма за наследяването - тя ползва подобен алгоритъм (нямаш граф с тегла на връзките а някаква форма на дърво) за да определи местоположението на обектите и връзките между тях. Силно се съмнявам обаче че ще можеш да изполваш нещо от този изроден случай, но ако ти трябва - кажи.
Можем да спретнем една философска дискусийка - защото задачата е интересна - но за съжаление - познанията ми(по математика, май си има и отделна наука за графите) са недостатъчно.
Айде тези които знаят нещо да се обадят - нещата не са само за Delphi.
---
Е т'ва е живот!
| |
Тема
|
Re: Изчертаване на граф
[re: PhantomAS]
|
|
Автор |
SDR (TaskMaster) |
Публикувано | 03.12.03 11:33 |
|
mi ako dokajesh che grafa ne e planaren mojesh da go nachertaesh kakto si iskash - nema nachin da ne se presekat dagite ... be chertaesh kakto ti skimne i twa e
------------------------------
I got a COMPILER, and I'm not afraid to use it!
| |
Тема
|
Re: Изчертаване на граф
[re: SDR]
|
|
Автор |
humperdink (несинеок) |
Публикувано | 04.12.03 10:42 |
|
Здравейте,
Задачата за изчертаване а граф е наистина много сериозна и интересна и определено е извън обсега на този клуб. Отклоняването от главната тема обаче не е голяма рядкост, така че заради занимателната тема може да си го простим...
Преди изобщо да започнем да мислим за решение, трябва да измислим условието . Сигурен съм че не е проблем да се наредят върховете в кръг например и да се нарисуват ребрата или да се измисли подобен универсален метод за показване, но дали няма да се получи чисто и просто една малка непрогледна джунглица...? Според мен шанса е доста голям да стане точно така.
За да избегнем "джнуглирането" на графа, ние тряба да търсим добро (на английски термина е neat, ама още не съм закусвал и не успях да измисля подходящ превод - ако някой се сети да свирка) графично представяне на графа. Тук идва логичния въпрос какво аджаба значи добро? Сигурен съм, че ако ми покажат два графа, няма да ми е трудно да определя кой от двата е по-добре нарисуван, или ако ми дадат описание на достатъчно малък граф след няколко опита ще съм го нарисувал що годе добре. Ама сметачите са си от край време тъпи машинки и от дума не разбират (сега бих казал мамка му, ама няма...). За тази цел трябва да се измислят някакви формални критерии за оценка на това доколко едно представяне е добро. Поначало целите са две:
1) този, който гледа рисунката да може да добие максимална представа за структурата на графа
2) да е красивичко чудото, което сме сътворили (ей ви и тук един чесато срещан английски термин, съжелявам ако от него добиете по-ясно представа отколкото от моите обяснения на български : aesthetically pleasing).
Това са т.н. меки или слаби критерии (soft). Вече споменахме за интелектуалните ограничения на сметачите и за налобителните силни или твърди (hard) критерии. Ето няколко примерни:
1) минимизиране брой пресичания на ребрата;
2) търсене на оптимално отношение ширина/дължина на картинката (за да съвпадне например с това на монитора, телевизора, екрана на прожектора...);
3) минимизиране на дължината на най-дългото ребро (или на средната стойност от първите няколко най-дълги ребра). Не е гот да гледаш една линия през целия граф, нали? А, тук трябва да се отбележи, че все пак не искаме (не че може...поне не толкова лесно) дължината на отсечките в картинката да отговаря на дължината на ребрата. Ако си поставим това условие работата става по-дебела от повечето други работи...
4) Площ. Тук искаме хем, площта на картинката да е най-малка, хем да няма два върха които са по-близо от предварително фиксирано разстояние (иначе мога да ви го наблъскам графа в кибритена кутийка. Без клечките, резбира се!).
Ей такива неща има в една книга: The Algorithm Design Manual.
В едно сайтче пишеше следното:
The best book available for this problem is Graph Drawing: Algorithms for the Visualization of Graphs by Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ionnis G. Tollis.
За съжаление не съм имал шанса да се запозная с тази книга по-отблизо от страничката и в on-line книжарниците ().
Goddam money. It always ends up making you blue as hell.
| |
|
За първия термин не знам, ама за втория много ми допада българският термин "лицеприятно"
| |
|
Като се замисля и на мен ми допада лицеприятно.
Goddam money. It always ends up making you blue as hell.
| |
|
Да не говорим, че поради многообразието от съществуващи графи (ех с носталгия си спомням времената когато за мен множественото число на граф беше "графове" ;) ) - общо взето задачата следва да се разбие на доста подзадачи.
Мне е твърде просто мдам. Но тук таме се въртят разни сорсове например:
http://www.cs.arizona.edu/~kobourov/GRIP/
само че е на Ц :) но идеята горе долу става ясна.
There are 10 types of people in this world one who understand binary jokes and one who not
| |
|
|
|
|