c++ - ¿Usar una biblioteca de gráficos/nodo Biblioteca de red o escribir mi propia cuenta?

templates boost

Question

Estoy tratando de decidir entre ir con una biblioteca de red de nodos / gráficos pre-hecha o rodar la mía.

Estoy implementando algunos algoritmos de búsqueda gráfica que pueden requerir cierta personalización significativa de la estructura de clase del nodo y / o bordes.

La razón por la que no estoy seguro de qué hacer es porque no estoy seguro de que la personalización de un pre-hecho pueda ser más costoso / problemático que el mío en primer lugar. También soy curioso, pero no tanto, de las compensaciones de rendimiento.

¿Hay alguien por ahí que tenga experiencia directa con el uso de una de las bibliotecas y tiene consejos basados ​​en una historia de éxito o fracaso? Quiero escuchar lo peor para que lo que sea que elija, sé en lo que me estoy metiendo.

Hay solo dos que he encontrado en mi búsqueda hasta ahora: la biblioteca de gráficos de Boost (BGL) y GOBLIN . El consejo específico sobre cualquiera de estos, o sugerencias para otros también es muy apreciado. BGL parece bastante maldito arcano. ¿Vale la pena luchar a través de?

Answer 1

"Requiere cierta personalización significativa de la estructura de clase del nodo y / o bordes".

¿Has mirado la característica de "propiedades agrupadas" del BGL?

http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html

Esto es a la vez potente y no en absoluto acrano.

Se definen unas clases para tus aristas y tus vértices.

class cMyVertex
{
…
};
class cMyEdge
{
…
};

Ahora define un tipo de gráfico que usará sus clases

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    cMyVertex, cMyEdge > graph_t;

Ahora puedes crear gráficos de este tipo que usarán tus clases, cualesquiera que sean, para los vértices y los bordes.

Puedes acceder a los atributos y métodos de tus clases de una manera perfectamente natural.

Graph_t g(10)       // create a graph with 10 vertices
g[1].setA1( “alpha” );  // invoke an accessor on node #1

Answer 2

Antes de decidir construir tu propia biblioteca de gráficos, debería echar un buen vistazo a igraph ( http://igraph.sourceforge.net/ ). Está escrito en C, es extremadamente rápido y ofrece una gama más amplia de algoritmos de grafos básicos y avanzados (incluida la visualización). Además, tiene una envoltura de python para la codificación rápida, así que creo que esta solución combina la velocidad de codificación y la velocidad de ejecución.

Answer 3

Creo que si puedes aprovechar los algoritmos de recorrido del gráfico, vale la pena utilizar el gráfico de impulso. Crear y usar vértices personalizados es bastante fácil. Los ejemplos incluidos con BGL fueron útiles para aprender a usarlo.

Estoy de acuerdo con Clifford, usé GraphViz para ayudar a visualizar el gráfico durante el desarrollo y lo encontré muy útil.

Answer 4

Esto realmente no es una respuesta concisa, es más como una adición a lo que ya se ha dicho.

La solución a este problema depende del contexto del problema. Si desea obtener una gran comprensión de cómo funcionan los algoritmos de grafos y el software. Escribe lo tuyo. Si desea obtener un conocimiento avanzado de algoritmos y estructuras de gráficos o implementarlos en su propio programa, aprenda una biblioteca de gráficos estándar. (Vea las razones para usar código reutilizable)

Lo mejor de ambos mundos. Haz ambos. Si no tiene tiempo, obtenga un libro sobre esto o siga los tutoriales y los ejemplos.

Otra sugerencia: formule una nueva pregunta acerca de cuál es la biblioteca gráfica {mejor, más confiable y más fácil de aprender} para {describir un problema muy general}? Esto le ayudará a elegir qué aprender, en lugar de intentar al azar encontrar el que mejor se adapte a sus necesidades. Alguien ya ha visto este problema, pide consejo.

Utilizando Código Reutilizable:

1. El código que alguien más haya escrito, incluidos los casos de prueba, generalmente será más confiable que el suyo.
2. Las correcciones son más fáciles de implementar (con las actualizaciones del componente que está reutilizando), esto es cierto en Boost (ya que hacen actualizaciones frecuentes y que Boost es revisado por pares).
3. Una vez que aprenda un marco, puede aplicarlo a otras aplicaciones ... quien sabe que podría obtener un trabajo más adelante utilizando el marco. A las empresas les gusta reutilizar en lugar de reinventar la rueda.

Answer 5

Hace poco le di a la biblioteca de gráficos de boost una prueba para el problema de la ruta más corta de Dijkstras. Resultados:

• Muy alto rendimiento

• Muy poco código necesario

• Muy flexible y extensible.

• Difícil de entender o depurar

Consejo: utilícelo, pero antes de hacerlo, lea The Boost Graph Library: Guía del usuario y manual de referencia.

Answer 6

Rodé el mío. No debes seguir ese ejemplo, a menos que estés absolutamente seguro de que lo necesitas.

Aún así, es una gran experiencia de aprendizaje, si tu teoría de grafos está oxidada.

Me divertí mucho combinando digraphs usando operadores EBNF y haciendo eliminación de épsilon y minimización basada en Hopcroft. Especialmente con la minimización, si puede llamar desesperadamente tratando de encontrar buena información y descubrir cómo funciona "divertido" :-(

Si lo hace por su cuenta, le recomiendo que separa las operaciones de alto nivel de las estructuras de datos de dígrafos de bajo nivel: diferentes clases, no solo métodos diferentes. No lo hice, y muy pronto estaré refactorizando en gran medida debido a esa mala decisión.

Algunos gráficos anotan nodos, algunos anotan bordes, algunos ambos. A veces, dos anotaciones son útiles, incluso si son solo claves externas para algunos datos externos. Por ejemplo, en las máquinas de estados finitos, un borde puede anotarse con una entrada y una salida. Es probable que esté interesado en el determinismo WRT la entrada pero no la salida, por lo que tenerlos ocultos detrás de una única ID es una molestia, y eso no es todo el asunto de los contenedores secundarios para la referencia de qué hace esta ID -a las búsquedas.

Además, a veces solo desea trabajar con cosas que no fueron diseñadas explícitamente como IYSWIM de dígrafo, por ejemplo, un grupo de nodos de estructura de datos que se vinculan entre sí.

IOW, es útil poder conectar diferentes representaciones de dígrafos, y aun así usar las mismas herramientas de alto nivel para muchas operaciones.

OMI Lo entendí bien cuando escribí una clase de ''herramienta de árbol'' que hace cosas como iterar y realizar subíndices en orden de vista de árbol y en orden de etiqueta de elemento XML. La representación del árbol subyacente es conectable (plantilla basada en políticas). Con los dígrafos, me equivoqué.

De todos modos, no sé qué es lo que realmente proporciona Boost o cualquier otra biblioteca de gráficos, pero si proporciona lo que necesita, le digo que lo use. Te ahorrará muchos dolores de cabeza.

Answer 7

Tal vez pueda proporcionar un poco de orientación sobre el BGL.

La biblioteca es muy flexible. El costo de esto es que la sintaxis puede ser muy barroca, para acomodar todas las posibilidades. Sin embargo, es lo suficientemente flexible como para que las cosas simples se puedan hacer de manera simple.

Desafortunadamente, la documentación del impulso va en todo a la perfección, y proporciona una descripción de la complejidad total, sin dar una idea de lo simples que pueden ser las cosas.

("Cualquier tecnología suficientemente avanzada es indistinguible de la magia" - Arthur C. Clarke. Lo que debería haber dicho es "Cualquier tecnología avanzada, lo suficientemente mal documentada, es indistinguible de la magia)

Considerar:

typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
   std::cout << index[*vp.first] <<  " ";
}

Así es como el "recorrido rápido" sugiere que imprimamos una lista de los vértices del gráfico. Sin embargo, un pequeño estudio muestra que un vértice no es más que un índice entero, y el código puede simplificarse enormemente para

for (int v = *vertices(g).first; v != *vertices(g).second; ++v)
    std::cout << v << " ";

Tal vez hay algunas cosas mágicas que no se pueden lograr con este código simplificado, pero para todos los días se usa de manera razonable para eliminar drásticamente la sintaxis de BGL incrustada para que pueda ver lo que está codificando.

A veces la sintaxis elaborada no se puede eliminar. (O tal vez simplemente no he notado la verdad subyacente). Luego, normalmente uso una pequeña función de utilidad para encapsular la complejidad y mantenerla alejada del algoritmo en el que estoy trabajando.

Por ejemplo, a menudo necesito pasar sobre los hijos de un vértice

vector<int> getVertexChildren( int v )
{
    vector<int> vc;
    typedef std::pair<graph_traits<graph_t>::out_edge_iterator, graph_traits<graph_t>::out_edge_iterator> out_edge_iter_pair_t;
    for( out_edge_iter_pair_t ep = out_edges(v,m_tree);
        ep.first != ep.second; ++(ep.first))
    {
        vc.push_back( target( *ep.first, m_tree ) );
    }
    return vc;
}
#define FOR_ALL_CHILDREN( v ) vector<int> vc=getVertexChildren(v); BOOST_FOR_EACH( int child, vc )

La conclusión es: seguir adelante y usar BGL. Se puede simplificar el hacer cosas simples, pero una vez que haya aprendido a usarlo, toda la inmensa flexibilidad estará disponible cuando la necesite.

Answer 8

También puede probar con la biblioteca de gráficos LEMON .

Podría usarlo para realizar la búsqueda de ruta más corta de Dijsktra después de leer el gráfico de un archivo de configuración.

Acaba de salir una nueva versión.

Answer 9

Utilizo mucho el BGL, pero lo que me molesta con BGL es la falta de algoritmos básicos como la conectividad de borde y vértice, el flujo de costo mínimo y, en general, el ajuste de peso máximo perfecto, solo para nombrar los que más extraño.

LEMON ofrece todo eso y también tiene una sintaxis más simple, lo que me molesta con LEMON son los problemas de instalación y compilación en las plataformas WINDOWS, pero probablemente cambiaré a LEMON a pesar de esos problemas.