Ridurre al minimo i bordi trasversali in un grafico

Sto usando networkx (un pacchetto di disegno grafico python) http://networkx.lanl.gov/index.html per uno dei miei progetti. Sebbene networkx sia piuttosto interessante, il tipo di funzione di visualizzazione fa schifo a causa del numero di crocini. C'è un modo per minimizzare i crocini in un grafico? Intendo un algoritmo in grado di ordinare i nodi in modo tale da ridurre al minimo i bordi incrociati?Ridurre al minimo i bordi trasversali in un grafico

fonte

2011-02-20 Anil Katti

Hai provato Graphviz per il disegno? Potrebbe fare meglio a ridurre al minimo gli incroci (specialmente Dot se si ha il tipo di grafici che preferisce). Che tipo di grafico hai (cioè, da dove viene)? –

Ho pensato che networkx utilizza graphviz per la visualizzazione (tramite pydot). Questi grafici provengono da tracce di tipi speciali di reti. Gli anelli sono il colpo peggiore :( –

possibile duplicato di [Layout grafici planari] (http://stackoverflow.com/questions/2347748/planar-graph-layouts) –

Determinazione di un layout di un grafico planare che riduce al minimo il numero di incroci è NP-Hard. Vedi la pagina della wiki su Crossing Number.

Si potrebbe provare un po 'di euristica, il layout basato sulla forza sono molto popolari credo (Graphviz li usa, se ricordo bene).

Si potrebbe anche provare alcuni algoritmi di approssimazione, si dovrebbero trovare riferimenti nella pagina wiki che ho collegato.

Spero che questo aiuti.

fonte

2011-02-20 16:16:58

Ridurre al minimo i bordi trasversali in un grafico

risposta

Problemi correlati