Newsgroup: it.scienza.informatica
Titolo: il contorno di un grafo...

Esiste qualche algoritmo che a partire da un nodo posto sul contorno 
di un grafo sia capace di generare tutti gli altri (in senso 
orario/antiorario)? 


Un grafo non ha un contorno.
Caso mai puo' avere un contorno
l'embedding (in pratica il disegno) di un grafo sul piano o meglio
ancora l'embedding planare di un grafo
sul piano.
ciao,
g.

 orario/antiorario)? 
Scusate, naturalmente tutti i nodi generati devono appartenere al 
contorno del grafo.

cicciocappuccio wrote:

Definisci cosa intendi per "contorno di un grafo".
A meno che il grafo non sia "disegnato" sul piano (e meglio
ancora, planare...) non e' assolutamente chiaro
cosa tu intenda per "contorno".
Se il grafo e' planare e quello che vuoi sono
i nodi periferici del disegno allora un punto di partenza
per un possibile algoritmo potrebbe essere calcolare
il "convex hull" (cercare con google) dell'insieme dei
punti del piano che rappresentano il tuo grafo.
Quelli che stanno nel convex hull sicuramente stanno
nel contorno, poi se ne possono aggiungere altri
in base alle adiacenze etc.etc.
ciao,
v.

 punti del piano che rappresentano il tuo grafo.
So gia come calcolare l'insieme dei nodi periferici.
Mi occorre un algoritmo efficiente che li ordini nel
modo che ho descritto sopra. Penso che in qualche 
modo vadano sfruttate le coordinate cartesiane, ma
come?

 Conoscete qualche algoritmo che lo faccia?
Scusa, ma se come dici i nodi del grafo coincidono con i punti della
griglia (e gli archi corrispondono alla griglia) allora sinceramente
non capisco dove sia la difficolta' del problema.
Ad ogni nodo sara' associata in modo naturale
una coordinata del tipo (i,j) che indica che il
nodo si trova nella i-esima riga e j-esima colonna.
(possiamo assumere che il nodo nell'angolo in alto a sinistra sia
il (1,1) e quello in basso a destra il (M,N))
Allora i nodi del bordo sono tutti e soli quelli
le cui coordinate sono della forma (i,1), (i,N), (1,j), (M,j)
per i=1...M e j=1...N.
Se te ne danno uno a caso sul bordo e' banale
decidere su quale lato si trova (o su un angolo).
Dopo di che segui quel lato e i successivi.
Per esempio se sei in (1,4) sei nella prima
riga, allora per esempio
dovrai toccare i nodi nell'ordine
(1,4) (1,5), ..., (1,N) e cosi' arrivi all'angolo
poi scendi lungo il lato verticale a destra:
(2,N) (3,N) .... (M,N) e cosi' arrivi all'angolo
poi prosegui lungo il lato basso
(M,N-1) (M,N-2), (M,N-3).... (M,1) angolo
poi risali lungo il lato sinistro:
(M-1,1) (M-2,1), (M-3,1).... (1,1) angolo
e poi prosegui lungo il lato originale fino
ad arrivare al punto di origine
(1,2) (1,3) [ (1,4) ]
tutto cio' puo' essere un po' noioso se devi considerare
diversi casi, ma non e' concettualmente complicato.
ciao,
g.

 nodo si trova nella i-esima riga e j-esima colonna.
Nel mio caso, ad ogni nodo e' associato un numero intero progressivo che e' 
l'indice in una tabella che contiene le coordinate cartesiane di tutti i nodi. 
Supponi di scandire orizzontalmente la griglia e di numerarne progressivamente 
i nodi. Adesso costruisci la matrice di adiacenza (nxn dove n e' il numero di 
nodi). Inizia a scandire le righe della matrice, se ci trovi meno di 4 
corrispondenze allora quel nodo sta sul bordo. 
Per come e' modellato il mio problema la soluzione che proponi tu non va bene.

cicciocappuccio wrote:

Magari se lo spiegavi prima non perdevo tempo
a scrivere tutta quella roba...
Secondo me dovresti cambiare struttura dati...
Se i nodi sono in una griglia regolare te ne
fai poco delle coordinate cartesiane, visto
che un numero d'ordine e' bastevole:
se le scandisci orizzontalmente e le numeri
0  1  2  3
4  5  6  7
8  9 10 11
allora sai che per spostarti nella riga sopra togli N (il numero di 
colonne) e per spostarti nella riga sotto aggiungi N.
Per spostarti di una colonna avanti aggiungi 1 e togli
uno per la colonna indietro.
A questo punto se vuoi velocizzare le
cose o memorizzi i nodi del grafo in un
array in modo da poter saltare mediante
un indice da uno all'altro,
oppure, ad esempio, crei una tabella
di puntatori (indicizzati dal numero d'ordine
assegnato sopra) che puntano al nodo corrispondente.
(nel nodo sara' conserato l'indice del nodo stesso).
etc.etc.
Ci sono tante possibili semplici soluzioni, basta
pensarci un momento.
In generale, nel caso di una griglia, la matrice
di adiacenza potrebbe anche non essere necessario
memorizzarla esplicitamente, visto che le adiacenze
si possono dedurre dall'indice del nodo.
ciao,
g.

 pensarci un momento.
In effetti era piu' semplice di quanto pensassi.
Grazie.