Come disporre un grafico linearmente senza sovrapposizioni?

Question

Sto tentando di scrivere un plugin per Blender che dispone automaticamente un albero dei nodi ordinatamente, senza sovrapposizioni o connessioni che scorrono a sinistra. Ho accesso all'elenco dei nodi, le loro posizioni, le loro dimensioni e un elenco di connessioni/collegamenti. Il grafico viene eseguito da sinistra a destra e può più nodi di inizio e fine. L'uscita di un nodo non riesce a connettersi con l'ingresso di un nodo prima di esso, o è proprio ingresso

Qualcuno sa di un documento o un articolo che si concentra su di codifica qualcosa che può trasformare questo (senza dipendenze cicliche.):

In questo?

Il metodo che in origine si avvicinò con era: Per tutti i nodi che non hanno connessioni di ingresso, allinearli a sinistra. Per tutti i nodi connessi a questi nodi iniziali, posizionarli a destra del nodo di inizio connessione. Ripeti l'operazione per ciascun nodo fino alla fine. Se un nodo si sovrappone a un altro, spostarlo e la catena di nodi a destra, in basso.

Questo funzionava bene per ogni catena isolato, ma quando un nodo di una catena collegata ad un nodo di un altro (un ramo che collega indietro al tronco per esempio), sarebbe spesso avere un collegamento a ritroso:

Questo metodo che ho trovato sembra essere piuttosto ... grezzo. Ho letto un po 'sui layout di Spring Force-Directed, ma sembrano essere più per i grafici che fluiscono in tutte/tutte le direzioni, e non sono del tutto sicuro di come lo avrei implementato manualmente qui comunque, dal momento che m limitato all'utilizzo della matematica di base da solo senza altre librerie esterne.

Non è esattamente un problema comune, ma sono lontano dal primo tentativo di capirlo. Non sto chiedendo esempi di codice esattamente, solo qualcosa da guardare per aiutarmi a elaborare un algoritmo decente.

Answer 1

Piuttosto che tentare di creare il sistema perfetto, ho deciso di forzare la mia strada verso un grafico pulito risolvendo ciascun problema da solo, piuttosto che prevenirne la causa. E 'grezzo, è lento ed è tutt'altro che ideale, ma funziona:

sarò rilasciarlo sotto licenza GNU quando è più completo, ma per ora ecco il nocciolo della questione: http://www.pasteall.org/43213/python

EDIT: Rilasciato: http://wiki.blender.org/index.php/Extensions:2.6/Py/Scripts/Nodes/Node_Wrangler

Answer 2

A topological sort dei nodi, se esiste, fornirà un ordine corretto di nodi per la visualizzazione. Se due nodi non sono correlati ma ordinati adiacenti, possono essere posizionati alla stessa coordinata X se lo si desidera.

In generale, il disegno di alberi con spaziatura corretta è NP-completo [vedere i riferimenti allo Drawing Presentable Trees, di Bill Mill] e disegnare i grafici non è più semplice.

Answer 3

vorrei utilizzare GraphViz per questo: http://www.graphviz.org/

1. Leggi il grafico Blender nella memoria
2. Scrivete stesso grafico nel formato di file grafico GraphViz
3. Eseguire uno dei eseguibili graphviz (vorrei suggeriscono dot (link))
4. leggere il grafico equivalente ma con posizioni di nodo creato da GraphViz
5. Scrivi il tuo grafico Blender, con le posizioni modificate in base ai risultati di GraphViz

A meno che non si desideri per ragioni accademiche, non reinventare la ruota. Questo approccio dovrebbe essere facile da fare e non richiederà la progettazione di un algoritmo di layout grafico complesso.