Perché le strutture dati C++ per i grafici nascondono indici interi contigui?

Question

Le strutture dati per grafici diretti e non orientati sono di fondamentale importanza. Implementazioni ben note e ampiamente utilizzate come Boost Graph Library e Lemon sono progettate in modo tale che gli indici interi contigui di nodi e spigoli non siano esposti all'utente tramite l'interfaccia.

Invece, l'utente identifica nodi e spigoli con (piccoli) oggetti rappresentativi. Un vantaggio è che questi oggetti vengono aggiornati automaticamente quando gli indici di nodi e spigoli cambiano a causa della rimozione di spigoli o nodi dal grafico.

A mio parere (!), Questo vantaggio è sopravvalutato. In genere gli utenti archiviano gli oggetti rappresentativi di nodi e/o spigoli in un contenitore, ad esempio std::vector. Ora, se i nodi oi bordi vengono rimossi dal grafico e i loro oggetti rappresentativi diventano non validi, l'utente deve ignorare questo o riorganizzare il vettore in modo da mantenere contigui indici interi validi, cioè fare esattamente la contabilità che il progetto avrebbe dovuto rendere inutile.

Quindi, la mia domanda è: La scelta progettuale (di nascondere gli indici interi contigui di nodi e spigoli dell'utente) presenta altri vantaggi?

Answer 1

Non riesco a parlare per il grafico a limone, ma per il grafico di incremento penso che l'obiettivo principale sia di essere generico. Quindi l'astrazione dall'accesso al vertice (bordo) aiuta a raggiungere questo obiettivo.

Nella documentazione si afferma che il grafico di incremento si basa sulla tesi di laurea di Dietmar Kühl sugli algoritmi di grafici generici. (Vedi la mia risposta a Do property maps remain necessary for BGL?). Quindi l'obiettivo principale dietro la biblioteca è di essere generico ed estensibile. La scelta dell'accesso incapsulante è parte dell'astrazione degli algoritmi dalla rappresentazione grafica. Per me, gli indici interi continui sono un dettaglio di implementazione.

Boost non formula alcuna ipotesi su come si utilizzerà il grafico o quali compromessi in termini di prestazioni sono importanti per l'utente. Ti consente di scegliere (o implementare) il contenitore più adatto alle tue esigenze.

Se si desidera interrompere questo incapsulamento, si è liberi di farlo. In realtà, il mio utilizzo più comune del grafico boost include i contenitori vecS e uno vector di struct s. Di solito lavoro con grafici in cui la dimensione è fissa. Potrei altrettanto facilmente utilizzare uno map di vertex_descriptor s (o edge_descriptor s) su oggetti per raggiungere lo stesso obiettivo.

Quindi, in sintesi, direi che questa non è tanto una scelta di design, ma piuttosto una conseguenza del raggiungimento dell'obiettivo più ampio di essere generico. Quindi l'occultamento dell'accesso ha il vantaggio di essere più generico.

Answer 2

_{(sono a casa nel mondo Java, ma spero che sia OK per dare una risposta che non è focalizzata su particolari librerie in questione)}

ci sono diversi vantaggi possibili di una tale astrazione. Uno dei più importanti è già stato menzionato nella domanda: La consistenza quando si eseguono modifiche in un grafico è molto più difficile da eseguire quando gli indici devono essere mantenuti.

La ragione per cui puo essere difficile risiede nelle varie rappresentazioni possibili grafico: Può essere facile da mantenere indici coerenti se la rappresentazione interna (o sempre) consisteva di elenchi di accesso casuale di Vertex e Edge oggetti.Ma per altre rappresentazioni, determinare un indice può essere difficile.

Questo direttamente correlato al secondo vantaggio principale: Uno è libero di utilizzare diverse implementazioni dell'interfaccia grafico. La sezione "Strutture dati grafiche" nello Review of Elementary Graph Theory della documentazione di boost elenca diverse strutture di dati che sono già offerte dal BGL (e tutti possono aggiungere la propria implementazione). I tempi di esecuzione per determinate operazioni sono indicati in notazione Big-O e una volta possono vedere che variano notevolmente tra le diverse strutture di dati.

Quindi si può facilmente immaginare che diverse implementazioni siano più adatte per determinati compiti. Ad esempio, si consideri che un algoritmo deve spesso verificare se un particolare vertice è contenuto in un grafico. Per un'archiviazione vertice indicizzata (ovvero, list), ciò richiederebbe O (n) per ciascun test. Con una memoria basata su set dei vertici, ciò potrebbe essere fatto in O (1) - ma semplicemente non ci sono "indici" sensibili in questo caso.

Inoltre, come menzionato nella Graph Concepts panoramica:

Infatti, l'interfaccia BGL deve neppure essere implementato usando una struttura di dati, come per alcuni problemi è più facile o più efficiente per definire un grafico implicitamente basato su alcune funzioni.

Così suggerendo che c'è un "accesso indicizzato" anche quando il grafico non esiste nemmeno in memoria potrebbe impedire una tale realizzazione puramente funzionale.