Come adattare un grafico personalizzato al modello della libreria del grafico boost?

Question

Sono arrugginito su modelli C++ e sto usando la libreria di grafici boost (una combinazione fatale). Ho cercato sul Web e non riesco a trovare alcuna istruzione diretta su come prendere una struttura grafica personalizzata e adattarla a BGL (boost graph library) che posso utilizzare algoritmi di traversamento grafico boost. Qualcuno ha familiarità con la biblioteca per aiutarmi?

EDIT: Quindi, il problema principale che ho riscontrato è dove trovare una fonte in cui i requisiti totali per mappare un grafico arbitrario a un grafico BGL. Sono davvero nuovo con i modelli, quindi è difficile per me leggere le specifiche/esempi di BGL. Forse dovrei cercare una fonte generale sui modelli?

Answer 1

L'approccio, a quanto ho capito, è di specializzare la struttura boost::graph_traits per il tipo di grafico. Questo configura BGL con varie importanti proprietà di cui ha bisogno per conoscere il tuo grafico. Quindi specializzate le funzioni globali del modello per il tipo di grafico specialistico di graph_traits per implementare qualsiasi interfaccia di grafico di incremento che potrebbe applicarsi al vostro tipo specifico di grafico.

Un esempio è proprio lì nella documentazione BGL:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/leda_conversion.html

Non ci sono collegamenti per alcune delle diverse interfacce là, che indicano quali funzioni template globali avrete bisogno di specializzarsi per il grafico, se vuoi supportare quell'interfaccia. L'elenco completo delle interfacce è qui:

http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/graph_concepts.html

Answer 2

mio suggerimento sarebbe quello di abbandonare l'uso di BGL del tutto a meno che non si dispone già di una notevole quantità di codice scritto su di esso. Lo stavo testando di recente per un uso futuro su un grande progetto di analisi del grafico, e l'ho trovato quasi inutilizzabile a causa di un'API eccessivamente complessa e mal progettata.

Non ci sono compiti semplici in BGL, solo complessi, e io stavo combattendo costantemente il compilatore a causa della gerarchia dei template eccessivamente complicata di BGL. Poca o nessuna documentazione utile (almeno non dove è realmente necessaria) e non abbastanza esempi aggravano solo le questioni. Non è il modo di scrivere codice.

Si consiglia di passare a LEMON. È stabile, scritto in C++, facile da capire e codificato, offre diverse forme specializzate di grafici per supportare le diverse esigenze di utilizzo e supporta sia le funzioni di ricerca/visitatore BFS che DFS. Ha anche il suo equivalente di mappe di proprietà per nodi/spigoli, quindi dovresti essere in grado di adattare la tua struttura grafica e altri dati su di essa.

Prova LEMON; ha un sapore molto migliore e causerà meno ulcere. ;-)