Ricerca, memorizzazione e ricerca di attributi e vertici del grafico

TL; DR

Un grafico è il concetto che devi avere in mente. Il modo in cui viene effettivamente implementato dipende da molti fattori e potrebbe non sembrare affatto un grafico.

[..] For DFS and BFS their algorithm loops through all the vertices first and colors them white. [..]

Devi distinguere tra la - come direi io - procedurale descrizione dell'algoritmo e un'implementazione reale. La descrizione qui sta effettivamente sottolineando che un nodo che non è stato ancora visitato deve essere considerato come "bianco".

Il modo in cui viene implementato dipende dalla situazione. Per un grafico che sai non può avere cicli, non si accede in modo concorrente, ecc. Potrebbe essere una buona idea archiviare effettivamente il colore nel nodo grafico.

Un'altra opzione è quella di avere un buffer che memorizza i nodi che consideri "bianchi". Quando si avvia la ricerca, si aggiunge solo il nodo iniziale a quel buffer. Quindi si visita il "primo" nodo di quel buffer, rimuovendolo dal buffer e aggiungendo tutti i suoi vicini diretti al buffer "bianco". A seconda del tipo di buffer che si utilizza, è possibile implementare diverse strategie di ricerca: utilizzando uno stack (aggiungendo == premendo un elemento in cima allo stack, il primo == l'elemento più in alto nello stack) si ottiene un DFS, utilizzando un coda (aggiungendo == accodando fino alla fine, il primo == il primo sulla parte anteriore) ottieni BFS. Aggiungi un buffer per memorizzare i nodi già visitati per ottenere il rilevamento del ciclo.

Se riesci a trovarlo, il libro Artificial Intelligence: A Modern Approach ha una spiegazione molto dettagliata e IMO di strategie di ricerca (e ovviamente molto di più).

[..] Do you have information on all the nodes stored elsewhere? [..]

Penso che tu sia troppo concentrato su questo tipo di nodo:

struct node {
  struct node * neighbors;
  int data1;
  char * data2;
  // ...
};

Ma il tuo nodo può anche essere ...

typedef int node_t;

.. e le informazioni sui vicini, i dati che i nodi contengono ecc. sono memorizzati in tabelle (semplici come int **neighbors; , o in un database SQL, o qualsiasi cosa sia appropriata).

[..] As a follow up to the Facebook and Google thoughts, assuming that information is stored in a graph, I imagine they don't traverse the entire graph every time somebody searches for an address or person. [..]

Non so come sia effettivamente implementato, ma non sarebbe strano pensare di (= avere in memoria) informazioni sulle strade in Canada quando stai cercando un percorso da Parigi a Roma?

Una possibile soluzione è dividere un enorme grafico in più livelli di dettaglio. Ad esempio: un livello più alto, in cui i nodi sono paesi (la Francia è vicina all'Italia, quindi considera solo quei due, o forse anche i loro vicini per considerare anche gli itinerari attraverso la Svizzera), un livello medio dove i nodi sono "regioni" / città e un livello più basso in cui i nodi sono in realtà incroci stradali.

[..] At least in C I can only make arrays so big. [..]

int * buffer = malloc(10 * sizeof(int)); // space for 10 int, add error handling
// ... some code ...
// need more space
void * new_buffer = realloc(buffer, 12 * sizeof(int)); // space for 12 int
if (new_buffer) {
  buffer = new_buffer;
  buffer[11] = 42; // perfectly fine
} else { /* error handling */ }

Per mia comprensione, il colore non fa parte del grafico, ma parte del nodo.

Considera di avere un grafico dei nodi. A- > B B- > C A = {colore: bianco, nome: A} B = {color: nil, nome: B} e così via. Attraversi il grafico a livello di nodo.

Esistono sistemi di archiviazione dei grafici che trattano tutto come node , come il web semantico / RDF. Ma in generale, quando si parla di grafici, l'unità è nodi e i nodi avranno attributi.

Considera 'G, V' una collezione astratta o iteratore. Per te in G, V sta semplicemente iterando sui nodi. Non pensare ancora troppo in profondità all'implementazione. Quindi, non devi attraversare il grafico per colorare tutto.

Oltre un miliardo di nodi? Dipende, se si dispone di un elenco di array di 1 miliardo di nodi, con un computer moderno, ci vuole meno di 1 minuto per passare attraverso tutti (supponiamo che l'elenco si adatti alla memoria). Dalla mia esperienza, questo è memorizzato come oggetto semplice, spesso solo id dei nodi.

2. Il deposito grafico e la ricerca su grande scala sono piuttosto impegnativi. Le persone non usano la lista di adiacenza o la matrice. Anche se è ancora possibile montare un semplice grafico di 5 milioni di nodi con un testo normale da 1 GB. Esistono formati compressi, come il formato di archiviazione a matrice sparsa. Questo è un problema ben noto all'interno della ricerca CS e gli scienziati stanno sviluppando un modo più efficiente di archiviarlo ogni giorno.

3. Spesso non è memorizzato in un grafico. Lo storage grafico non è una buona scelta o alcuni modelli di dati. E sebbene si possa interfacciare un'interfaccia di query basata sulla teoria dei grafi, lo storage sottostante può essere ancora l'archiviazione relazionale tradizionale di SQL. Suppongo che si limitino a interrogare un database del servizio indirizzi con il tuo ID utente e il gioco è fatto.

Per i tuoi pensieri finali, dipende dal tipo esatto di dati del nodo, dalla relazione del nodo e dalla complessità del grafico. Potresti avere un grafico ponderato complesso e la memorizzazione dei bordi nella matrice di adiacenza sarà presto troppo complicata.