Incorporamento di un grafico nello spazio euclideo

Question

Ho un grafico totale non orientato in cui i nodi rappresentano punti sui punti di un piano ei bordi sono distanze euclidee approssimative tra i punti. Mi piacerebbe "incorporare" questo grafico in uno spazio bidimensionale. Cioè, voglio convertire ogni vertice in una tupla di posizione (x, y) in modo che per qualsiasi due due vertici vew, il bordo (v, w) abbia un peso vicino a dist (v, w).

Ad esempio, se avessi il grafico con i nodi A, B, C e D e i bordi con i pesi (A, B): 20; (A, C): 22; (A, D): 26; (B, C): 30; (B, D): 20, (C, D): 19, quindi è possibile assegnare i punti A: (0,0); B: (10, 0); C: (0, 10); D: (10, 10). Chiaramente questo è imperfetto, ma è un'approssimazione ragionevole.

Non mi interessa ottenere la migliore soluzione possibile, voglio solo uno ragionevole in un ragionevole lasso di tempo.

(Nel caso in cui si desideri la motivazione per questo problema, ho un sistema fisico in cui ho misurazioni rumorose delle distanze da tutte le coppie di punti. Le misurazioni della distanza sono rumorose, ma tendono ad essere all'interno di un fattore di due Ho realizzato tutte queste misurazioni e ora ho un grafico con diverse migliaia di nodi e diversi milioni di spigoli e voglio posizionare i punti su un aereo.

Answer 1

Potrebbe essere possibile adattare l'algoritmo di disegno grafico force-based alle proprie esigenze.

Questo algoritmo tenta di trovare un buon layout per un grafo non orientato G(V,E) trattando ogni vertice in V come punto cartesiano e ogni bordo in E come molla lineare. Inoltre, una forza repulsiva a coppie (vale a dire la legge di Coulomb) viene calcolata tra i vertici globalmente - ciò impedisce il raggruppamento dei vertici nello spazio cartesiano che non sono adiacenti in G(V,E).

Nel tuo caso puoi impostare la lunghezza di equilibrio delle molle uguale al peso dei bordi - questo dovrebbe dare un layout con le distanze dei vertici euclidei in coppia vicino ai pesi del bordo.

L'algoritmo aggiorna una distribuzione iniziale (possibilmente casuale) in modo pseudo-temporale basato sulla somma delle forze su ciascun vertice. L'algoritmo termina quando viene raggiunto uno stato stazionario approssimativo. Uno pseudo-codice semplificato:

while(not converged) 
    for i = vertices in V 
     F(i) = sum of spring + repulsive forces on ith vertex 
    endfor 
    Update vertex positions based on force vector F 
    if (vertex positions not changing much) 
     converged = true 
    endif 
endwhile 

Ci sono un certo numero di ottimizzazioni che possono essere applicati per ridurre la complessità dell'algoritmo. Per esempio, un indice spaziale (come un quadruplo) può essere usato per consentire un calcolo efficiente di una forza approssimativa di repulsione tra i vertici "vicini", piuttosto che il calcolo globale lento. È anche possibile utilizzare tecniche di agglomerazione di grafici multilivello per migliorare la convergenza e l'ottimalità.

Infine, si noti che esistono numerose buone librerie per il disegno grafico che implementano versioni ottimizzate di questo algoritmo, ad esempio, si potrebbe voler controllare Graphviz.

Answer 2

Per i principianti, penso che mi piacerebbe andare un approccio di ricerca euristico.

si vuole realmente trovare una serie di punti p1, p2, ..., p_n che minimizza la funzione:

f(X) = Sum (|dist(p_i,p_j) - weight(n_i,n_j)|) [for each i,j ] 

il problema può essere risolto in modo euristico da alcuni algoritmi tra cui Hill Climbing e Genetic Algorithms.

Personalmente, come Hill Climbing, e l'approccio è il seguente:

best <- [(0,0),(0,0),...,(0,0)] 
while there is still time: 
    S <- random initialized vector of points 
    flag <- true 
    while (flag): 
     flag <- false 
     candidates <- next(S) (*) 
     S <- X in candidates such that f(X) <= f(Y) for each X in candidates (**) 
     if f(S) was improved: 
      flag <- true 
    if f(S) <= f(best): 
     best <- S 
return best 

(*) next() genera una lista di candidati. Può utilizzare informazioni sul gradiente di funzione (e fondamentalmente il decadimento in qualcosa di simile a gradient descent) per esempio, o campionare alcune 'direzioni' casuali e metterle come candidati (tutti nel vettore multidimensionale, dove ogni punto è una dimensione) .
(**) Qui, in pratica, hai scelto il candidato "migliore" e lo hai archiviato in S, quindi continuerai con esso nella prossima iterazione.

Nota, l'algoritmo è any-time, quindi è previsto che migliori tutto il tempo necessario a fornirlo. Questo comportamento è ottenuto dall'inizializzazione casuale del punto iniziale, che probabilmente modificherà il risultato finale e dalla selezione casuale di punti per i candidati.