Newsgroup: it.scienza.informatica
Titolo: Graph drawing

Salve a tutti!
Sto cercando informazioni (bibliografie, articoli, sorgenti)
riguardanti il problema del graph drawing.
grazie
a presto
Stefano

Stefano Rodighiero wrote:

Cioè la colorazione di un grafo ?
Sarebbe, se non sbaglio, il problema dei 4 colori ?
So che è stato dimostrato formalmente di recente che
una qualsiasi carta geografica può essere colorata con 4 colori
--
--------------------------------------------------------------
Fabrizio Sebastiani, 
http://userspace.ats.it/free/fsebasti
--------------------------------------------------------------

Cioč la colorazione di un grafo ?
No. Dato un grafo, si tratta di disegnarlo. Se ci pensi un po' ti
accorgi che il problema non e` per niente banale. I criteri attraverso
i quali scegliere una soluzione sono di diversa natura: minimizzare il
numero di incroci degli archi, massimizzare la simmetria della
disposizione dei nodi e cosi` via.
Stando a quello che ho trovato finora, ci sono parecchi ricercatori
che se ne occupano. A me serve qualcosa di semplice, per fare un
piccolo software che consenta di "vedere" algoritmi quali Dijkstra e
simili su grafi arbitrari, che devono dunque essere rappresentati in
qualche maniera ragionevole (da stabilire).
a presto
ciao

 ciao
Si, hai ragione: non č per nulla banale.
Avevo capito male, scusa.
Comunque non posso aiutarti .... :-(
Ciao.


Salve
Scusa ma mi pare tu nescoli un po' di cose. Che legame c'e' fra 
l'algoritmo di  Dijkstra e il modo in cui rappresenti un grafo?
Mi pare strano che la modalita' di tracciamento influenzi 
l'algoritmo anzi lo escludo (conosco il suddetto algo).
Per il tracciamento di grafi puoi veder testi sul VLSI
dato che i suddetti problemi sono stati affrontati e risolti
nel caso della progettazione di circuiti integrati.
Cheers
Yuri

Yuri
a presto
ciao

Salve a tutti!
Di nuovo a proposito del graph drawing, ecco cosa e` passato sulla
mailing list theory-edge:
~~~~~~~~~~~~~~
recently I have run into AT&T graphviz software.
the idea is that it can display large arbitrary graphs.
anyone working in complexity research will
recognize the frequent yearning to see results
visually. I work with graph concepts very 
commonly & CS papers show an increasing emphasis
on graph diagrams over the years. it is surely much more
amenable to thinking about problems than symbolic
approaches.
http://www.research.att.com/sw/tools/graphviz/
~~~~~~~~~~~~~~
Nel momento in cui scrivo, non ho ancora scaricato il software
menzionato. Se volete, vi faro` sapere.
salve
Stefano

Neanche io so risponderti esattamente, pero' un aiuto posso fornirtelo: ho
visto girare un algoritmo che fa piu' o meno quello che dici.
Si tratta di una applet java. In esecuzione, mostra un grafo (o meglio,
diversi grafi di topologia differente) con i suoi bei cerchietti a
rappresentare i nodi e delle linee che li uniscono a rappresentare le
connessioni (pesate e simmetriche) che, dinamicamente, si dispone sullo
schermo senza sovrapposizioni e minimizzando le intersezioni.
Il programma era ovviamente dimostrativo, per cui mostrava tutta la sequenza
di passi compiuti dall'algoritmo con un effetto grafici di "movimento" dei
nodi che venivano respinti da quelli troppo vicini, ma credo che possa fare
al caso tuo.
Il programma era tra quelli allegati ad un libro su java: se non ricordo
male di naba barkakati (o qualcosa del genere). E' tutto rosso e molto
voluminoso. Il titolo in inglese e' "java unleashed", in italiano non mi
ricordo, edizioni Apogeo.
Purtroppo non sono sicuro che quell'esempio sia opera dell'autore del libro
o sia gia' tra quelli standard del JDK2.0, semmai puoi risparmiarti la spesa
del libro se prima controlli.
Ciao
Al...@polic.cilea.it
P.S.
Se credi che ti possa servire, posso controllare bene e darti  informazioni
piu' precise, come ho gia' detto in un'altra lettera, adesso mi trovo in
ufficio, sul NG bazzico poco, ma alla posta diretta rispondo sempre. (magari
con qualche giorno di ritardo)
--
Posted from 
ro...@polic.cilea.it
 [131.175.215.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

Si tratta di una applet java. [...]
Grazie per la risposta. Credo che l'esempio cui fai riferimento non
sia incluso nella distribuzione Sun del jdk (se non sbaglio, con il
jdk, c'e` soltanto un esempio in cui la posizione dei nodi cambia
dinamicamente in maniera tale che la topologia del grafo rifletta i
pesi degli archi - non so se e` chiaro)
Colgo l'occasione per segnalare a te e agli interessati un software
molto bello che ho scaricato dal sito dei laboratori di ricerca della
AT&T (l'indirizzo e` 
http://www.research.att.com/sw/tools/graphviz/
).
Uno dei moduli si chiama dotty, e consente di visualizzare grafi
diretti e non in maniera automatica. E` sufficiente passargli un file
come questo
digraph Dummy {
	A -> B;
	B -> C;
	C -> A;	
}
e lui visualizzera` il grafo. Il linguaggio per descrivere i grafi e`
piuttosto ampio, e consente di specificare vincoli aggiuntivi
(posizione dei nodi, lunghezza minima degli archi). Oltre alla
visualizzazione su schermo, si possono ottenere file .gif o .ps. La
qualita` mi sembra molto buona (da libro, direi)
Altro modulo, ancora piu` interessante, e` lefty. Si tratta di un vero
e proprio linguaggio per la realizzazione di schemi tecnici. La cosa
interessante e` che e` possibile interfacciarlo con processi esterni:
nella documentazione e` citata come esempio un'applicazione che,
interfacciata a un debugger Unix, consente di visualizzare sotto forma
di grafo le complesse strutture dati basate su puntatori. Oppure un
software che "visualizza" il funzionamento di un automa a stati.
Ho scritto qualche programmino che produce file per dotty, e lo trovo
un programma molto utile. Ora vorrei fare qualche esperimento con
lefty, che dovrebbe consentirmi di fare quello di cui parlavo.
a presto
Stefano
-- 
# Giorgio Vecchiocattivi.










a presto
Stefano
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Nota del moderatore.
% Per sbaglio ho rigettato questo articolo. 
% Sempre per sbaglio l'ho ripostato con il mio nome,
% Sempre per sbaglio 
tin.it
 non ha corretto l'errore. (iunet si)
% Quindi puo' darsi che troviate un articolo con il mio nome identico.
% Mi scuso con tutti e in particolare con l'autore.
% 
% # Giorgio Vecchiocattivi.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

