Disegno grafico con bordi ponderati

Question

Sto cercando di creare un algoritmo (o riutilizzarlo) che organizza nodi e bordi su una tela bidimensionale in cui i bordi possono avere pesi corrispondenti.

Qualsiasi materiale di partenza e informazioni sarebbe utile.

Answer 1

Cosa farebbero i pesi per influenzare il loro posizionamento sulla tela?

Detto questo, si potrebbe voler esaminare graphviz e, in particolare, la lingua DOT, che organizza i nodi su una tela.

Numerose strutture di visualizzazione dei grafici utilizzano una simulazione basata sulla forza, in cui tutti i nodi esercitano una forza repulsiva l'uno contro l'altro (con la massa della loro dimensione) ei bordi esercitano una tensione sui nodi che connettono. Questo crea visualizzazioni grafiche organizzate esteticamente.

Anche se non sono sicuro di dove si desidera che i "pesi" del nodo entrino in gioco. Vuoi che i nodi ponderati siano più al centro? Per essere più grande? Più ulteriormente a parte?

Answer 2

Molti algoritmi di layout grafico/di rete sono implicitamente in grado di gestire reti ponderate, ma potrebbe essere necessario eseguire alcune pre-elaborazione e modifiche all'implementazione per farlo funzionare. Di solito il primo passo è determinare se i pesi rappresentano "somiglianze" (di solito interpretato nel senso che pesi più forti dovrebbero mettere i nodi più vicini) o "dissimilarità" (pesi più forti = padre a parte). Il caso più comune è il primo, quindi sarà necessario tradurli in dissomiglianze, spesso eseguite sottraendo ogni valore del bordo dal valore limite massimo osservato nella rete. La matrice di valori di dissomiglianza per ogni spigolo può quindi essere alimentata all'algoritmo e interpretata come le distanze desiderate nello spazio di layout per ogni spigolo (cioè "lunghezze della molla") - di solito dopo aver moltiplicato per alcune costanti per trasformare in unità di visualizzazione (pixel) .

Se mi dici quale lingua stai usando, potrei essere in grado di indicarti alcuni esempi di codice.