Qual è il modo più efficace per rappresentare una matrice di adiacenza ridimensionabile

1

Sto costruendo una semplice app che rappresenta una matrice, in cui i nodi vengono aggiunti abbastanza spesso. Attualmente ho il seguente codice per aggiungere un nuovo nodo:

let mut new_edges = Array2::default((position + 1, position + 1));
for i in 0..position {
    for j in 0..position {
        new_edges[[i, j]] = self.edges[[i, j]]
    }
}

self.edges = new_edges;

Quindi in pratica copia solo tutto su ciascun nodo inserito.

Un modo molto più efficiente è stato aggiungere nuovi elementi alla fine del vettore a dimensione singola e trattarlo come matrice 2D. Ad esempio, potrebbe essere vettore di lunghezza 9 che rappresenta la seguente matrice:

0|1|8|
_| | |
3 2|7|
___  |
4 5 6|
_____

Quindi vedi. Teniamo gli indici del vettore sottostante in ordine di serpente. Quando vogliamo ridimensionarlo, non spostiamo nulla ma aggiungiamo semplicemente nuovi 2n-1 nodi alla fine. L'aggiunta di 4 colonne e righe comporterebbe l'aggiunta di 7 nodi nel modo seguente:

0 |1 |8 |9 |
__|  |  |  |
3  2 |7 |10|
_____|  |  |
4  5  6 |11|
________|  |
15 14 13 12|
___________|

Il problema con questo approccio che non posso esprimerlo matematicamente, cioè in questo caso matrix[[2,2]] è memorizzato in vec sull'indice 6 , matrix[[2,0]] è memorizzato sull'indice 8 e matrix[[0,1]] è memorizzati nell'indice 3 .

Sto facendo la cosa giusta e se la risposta è sì, come si può eseguire la traduzione da 1 a 2?

    
posta Alex Zhukovskiy 25.03.2018 - 09:45
fonte

1 risposta

1

Se vuoi "esprimerlo matematicamente" (le tue parole sopra)
prova a sistemare i tuoi indici (n, m) in modo molto simile, invece ...

  n\m| 0  1  2  3  4  5
 ----+----------------
  0  | 0  2  5  9 14 20
     |   /  / /  /  /
  1  | 1  4  8 13 19 26
     |   / /  /  /  /
  2  | 3  7 12 18 25 33
     |   / /  /  /  /
  3  | 6 11 17 24 32 41

Quindi l'espressione matematica è solo
  (n, m) - > 1/2 * (n + m) * (n + m + 1) + m
Questa è la "funzione di enumerazione della coppia" standard, ad esempio,
  link
(il loro diagramma è "topsy-turvy" relativo a questo, ma ammonta al stessa cosa).
L'enumerazione delle coppie è essenzialmente solo un incorporamento NxN - > N .

La mia comprensione di ciò è venuta dalle pagine 118-120 del libro di Stoy
  link
Ma, mi dispiace, non riesco a convincere books.google a visualizzare pagine complete per questo.

    
risposta data 25.03.2018 - 11:02
fonte

Leggi altre domande sui tag