Algoritmo per progettare un grafico di un insieme di connessioni tra i nodi

Question

Algoritmo per progettare un grafico di un insieme di connessioni tra i nodi

#1 da (1 voti)
#2 da (1 voti)

2

Immaginiamo di avere punti in un piano 2D che voglio collegare in un grafico senza direzione. Tuttavia, non voglio che queste connessioni si sovrappongano. L'unico dato che mi viene dato è dove esiste una connessione e quale direzione va. Ad esempio, uno dei miei set di dati molto semplice potrebbe essere simile a questo

1 > 2

2 > 3

4 > 3, 5

5 > 3

E quindi, un buon esempio di ciò che vorrei sarebbe simile a questo:

Questaimmaginenonhapuntisovrappostidiconnessioniesarebbeunadelletantesoluzioni.Lapartegraficadell'algoritmononèunproblemaperme.Vogliosolounalgoritmochepossarestituirelecoordinatedeivaripuntiame,equindipossosostituirmidalì.

D'altraparte,questoèquellochenonvoglio:

Non sono necessariamente alla ricerca di un codice reale, ma semplicemente una spinta nella giusta direzione, o forse un algoritmo che posso adattare ai miei dati specifici. Pseudo codice andrebbe bene se necessario per rispondere alla domanda.

EDIT:

Ora, naturalmente, potrei controllare se i segmenti di linea intersecano in questo esempio questo piccolo, ma i normali set di dati per questo algoritmo saranno molto più grandi. Non sarebbe efficiente calcolare manualmente ogni posizione dei punti e molto probabilmente non risulterebbe nella soluzione più "ottimizzata".

algorithms graph

posta Nick Pandolfi 06.08.2016 - 03:08

fonte

2 risposte

Leggi altre domande sui tag algorithms graph

Migrazione dallo schema del database precedente, riscrittura legacy o sync su new Quali sono le interfacce mIa, mId e dIa?

score 1 · Answer 1

Presumo che tu abbia le coordinate (X, Y) di ogni punto nel tuo grafico.

Determinare se due segmenti di linea intersecano è un problema risolto - vedere Come si rileva dove si intersecano due segmenti di linea?

Tutto (come se!) è necessario fare un elenco dei segmenti di linea, quindi per ogni segmento determinare se si interseca con qualsiasi segmento più in basso nell'elenco (se hai già determinato che il segmento 1 non interseca il segmento 3, non c'è motivo di testare se il segmento 3 interseca il segmento 1)

Se hai migliaia di punti questo sarà un processo costoso e lento, a meno che non ci si preoccupi di estirpare segmenti di linea che non potrebbero intersecarsi.

score 1 · Answer 2

(Disclaimer: non conosco abbastanza teoria dei grafi per determinare se le seguenti informazioni sono corrette.)

Se hai solo il grafico, cioè le etichette per i vertici e i bordi definiti tra due vertici, cioè non hai le coordinate:

Per verificare se un dato grafico è planare, l'articolo di Wikipedia su Grafico planare elenca molti algoritmi per farlo.

Lo stesso articolo fornisce anche esempi di grafici che non sono planari. Se ti viene fornito un grafico di questo tipo, è inutile cercare di trovare un incorporamento planare per questo.

Se si desidera utilizzare un software per generare le coordinate per tale grafico:

Dai un'occhiata all'elenco dei software di impaginazione grafica su questi articoli di Wikipedia:

link
link

Si noti che questi software non garantiscono il non-crossing, anche per i grafici che sono planari. Questo è spiegato nel seguente post di Overflow dello stack:

link

Per quanto riguarda un normale programmatore di software (cioè non un esperto di teoria e algoritmi dei grafi), questo problema è abbastanza complicato che una persona normale non dovrebbe tentare di risolverlo da solo.