Switch to an adjacency list storage of vertices.

Aperta
  • Qualcosa non va?
#25 3 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
30/100
Tipo di issue
Refactoring
Chiarezza
Da chiarire
Stato di attività
Ferma
Stack tecnologico
julia
Ambito
data

Direzione di ricerca

Inizia dalla conversazione Discourse collegata ed esamina l’attuale rappresentazione come sparse matrix, le liste di adiacenza, l’accesso ai vicini uscenti e il comportamento della ricerca dei pesi. Esegui benchmark dell’accesso a un singolo peso e dell’iterazione sui vicini, quindi confronta i design proposti per le liste di adiacenza; il lavoro è completato quando è stato selezionato e implementato l’approccio di memorizzazione meglio supportato.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

enhancement

See this conversation

This seems to be mostly equivalent to a sparse matrix (I mentioned slower access of weights, but using binary search, I think it should be same complexity than for a sparse matrix)
You can get back the sparse matrix by simply:

  • collecting the weights in the order found in the adjacency list
  • concatenating the outneighbors adjacency lists
  • computing the cumulative degrees of the vertices.

As shown in the discussion, the benefit obtained by iterating simultaneously weights and vertices can be also achieved with the sparse matrix implementation, although it seems a bit slower.

The proposed implementation is by storing tuples in the adjacency lists, but it might be better to store in some aside adjacency list to avoid the penalty cost of accessing tuple when considering only neighbors. (we can still zip through both lists at the same time).

At this point, I think the bigger drawback will be the linear cost for generating the weight matrix, all other computations should be asymptotically equivalent.
I think we need some benchmarking to find the best implementation, by considering both the access of a single weight and the access of weights when iterating neighbors.

Lingua principale
Julia
Stelle
41
Fork
9
Merge medio
1g 21h
PR unite (30g)
1

Preparare l'ambiente

Questo progetto non fornisce container di sviluppo, Dockerfile né guida per i contributori, quindi l'ambiente è a tuo carico: parti dal suo README e consulta la nostra guida al primo contributo per i passaggi generali.

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di JuliaGraphs/SimpleWeightedGraphs.jl

Tutte le issue di JuliaGraphs/SimpleWeightedGraphs.jl

Issue simili

Altre issue su Julia

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.