Rende l'ordine dei grafici dei nodi diretti a due bordi

Question

Rende l'ordine dei grafici dei nodi diretti a due bordi

Naviga le tue risposte

#1 da (3 voti)

0

Sto cercando di trovare un algoritmo per i grafici con i seguenti contenuti:

Nodi senza bordi che ne derivano (mostrato qui come un cerchio rosso)

Tuttiglialtrinodihannoesattamenteduebordichesiaprono(mostratiquicomediamantiverdi)

Ho bisogno di rendere questi grafici in un modo specifico:

Ogni cerchio ha una posizione nota.
La posizione di ogni diamante è determinata dalle posizioni dei nodi a cui è collegata .

I dati sono disposti come mostrato, ma per essere chiari

CircleNode : { Position }
DiamondNode : { NodeA, NodeB, Position = Route(NodeA, NodeB) }
Graph : { CircleNodes, DiamondNodes }

La mia soluzione funziona per la maggior parte dei grafici che ho costruito, ma i grafici più complessi che ho overflow lo stack molto prima che convergono. Penso di poter usare la maggior parte del mio codice esistente se fornisco ai nodi in profondità l'ultimo ordine: cerchi, quindi diamanti più vicini, quindi più vicini a quelli e così via. Tuttavia, non sono sicuro di come dimostrare che funzionerà con tutti i grafici di questo tipo.

Che cos'è questo tipo di problema chiamato?

Esiste un algoritmo comprovato che può essere applicato?

Nota : i diagrammi precedenti non riflettono il layout di rendering previsto, ma solo il modo in cui i dati sono rappresentati in memoria.

algorithms graph

posta jzx 07.04.2015 - 06:10

fonte

1 risposta

Leggi altre domande sui tag algorithms graph

Come eseguire la prioritizzazione di MoSCoW in Scrum? Lucene vs Solr - Documenti di indicizzazione pdf / word reisiding su un drive NAS usando .Net [closed]

score 3 · Accepted Answer

1) sull'overflow dello stack: se il tuo algoritmo si interrompe, ma il grafico è troppo grande, usa lo stack esplicito (su heap) invece della ricorsione. Un modo (non l'unico modo) per dimostrare che si fermerà un giorno, è che la dimensione del problema è ridotta OGNI "round" e che "round" stesso è limitato da alcune costanti.

2) Non hai detto esattamente come deve essere determinata la posizione dei diamon, quindi presumo che tu voglia che il nodo sia da qualche parte tra i nodi a cui si connette.

Un modo per farlo sarebbe qualcosa come la simulazione simulata: posiziona nodi fissi. posiziona in modo casuale altri nodi. Tutti i nodi respingono altri nodi (si riduce ad esempio il quadrato della distanza), i nodi connessi dal bordo vengono atratti (aumenta con il quadrato della distanza).

Calcola "forze" su tutti i nodi mobili. Sposta proporzionalmente alla forza e "tempo".

Al primo avvio con un tempo maggiore, ogni passo lo riduce.

Per uscire dai minimi locali, aggiungi forza casuale (e riducila con il tempo).

Dopo alcune iterazioni verranno trovate delle posizioni stabili per i nodi e ci sono possibilità che sia ragionevole.