Utilice una biblioteca / Nodo de la Red de Bibliotecas gráfico o escribir mi propio?

https://stackoverflow.com/questions/1499878

19-09-2019
|

Pregunta

Estoy tratando de decidir entre ir a una biblioteca de red pre-hechos gráfico / nodo o para rodar mi propia.

estoy poniendo en práctica algunos algoritmos de búsqueda gráfico que podrían requerir algún tipo de personalización significativa a la estructura de clases del nodo y / o bordes.

La razón por la que no estoy seguro de qué hacer es que no estoy seguro si la personalización de un pre-hechos podría ser más caro / dificultad de hacer mi propia en el primer lugar. También tengo curiosidad, pero en menor medida, del rendimiento de las compensaciones.

¿Hay alguien por ahí tiene experiencia directa con el uso de una de las bibliotecas por ahí y tener asesoramiento basado en una historia de éxito o fracaso? Quiero oír lo peor por lo que todo lo que he elegido, sé lo que estoy metiendo.

Sólo hay dos que he encontrado en mi búsqueda hasta el momento: El Boost Graph Library (BGL) "noreferrer" y GOBLIN . consejos específicos sobre cualquiera de ellos, o sugerencias para otros es muy apreciada también. BGL parece muy muy arcano. ¿Vale la pena luchando a través de?

Solución

Me quizá puede proporcionar un poco de orientación en el BGL.

La biblioteca es muy flexible. El costo de esto es que la sintaxis puede ser muy barroco, con el fin de dar cabida a todas las posibilidades. Sin embargo, es suficientemente flexible para que las cosas simples se puede hacer simplemente.

Desafortunadamente la documentación impulso va en plena inclinación cosas, proporcionar una descripción única de toda la complejidad, sin una pizca de cómo las cosas pueden ser simples.

( "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 documentado, es indistinguible de la magia)

Tenga en cuenta:

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 "viaje rápido" sugiere que imprimir 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 de enteros, y el código se puede simplificar en gran medida a

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 alcanzar con este código simplificado, pero por cada día lo utilizan razonable para podar drásticamente la sintaxis que incrustan BGL para que pueda ver lo que su están codificando.

A veces la sintaxis compleja no se puede quitar. (O tal vez simplemente no me he dado cuenta de la verdad subyacente). A continuación, por lo general utilizo una función de utilidad poco a encapsular la complejidad del abd mantenerlo lejos del algoritmo que estoy trabajando.

Por ejemplo, a menudo necesito bucle 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 utilizar BGL. Se puede simplificarse para hacer cosas simples, pero una vez que haya aprendido a usarlo, toda la inmensa flexibilidad estará disponible siempre que lo necesite.

Otros consejos

“requerir algún tipo de personalización significativa a la estructura de clase del nodo y / o bordes.”

¿Has mirado en la función de “paquetes de propiedades” de la BGL?

http://www.boost.org/ doc / libs / 1_40_0 / libs / gráfico / doc / bundles.html

Esto es a la vez potente y no acrcane lo más mínimo.

Se define una clase para sus aristas y sus vértices

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

Ahora se define un tipo de gráfico que utilizará sus clases

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

Ahora usted puede crear gráficos de este tipo que se vayan a utilizar las clases, cualesquiera que sean, para los vértices y aristas.

Puede acceder a los atributos y métodos de sus 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

Hace poco me di la biblioteca gráfica impulso de un juicio por Dijkstras problema del camino más corto. Resultados:

Muy alto rendimiento
Muy poco código necesario
Muy flexible y extensible
Es difícil de entender o de depuración

Consejo: Se usa , pero antes de hacerlo leer El Boost Graph Library: Guía del usuario y manual de referencia

Creo que si se puede aprovechar los algoritmos de recorrido gráfico, vale la pena usar el Gráfico Boost. Creación y uso de vértices personalizados es bastante fácil. Los ejemplos que se incluyen con BGL fueron útiles para aprender a usarlo.

Estoy de acuerdo con Clifford, he utilizado GraphViz para ayudar a visualizar el gráfico durante el desarrollo y lo encontraron muy útil.

También puede tomar una oportunidad con la biblioteca gráfica LIMÓN .

Podría utilizarlo para realizar Dijsktra búsqueda del camino más corto después de leer la gráfica de un archivo de configuración.

Una nueva versión acaba de salir.

Esto realmente no es una respuesta concisa, sus más de añadir 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 funciona algoritmos de grafos, y software. Escribe lo tuyo. Si desea obtener un conocimiento avanzado de algoritmos y estructuras de gráfico o de ponerlas en práctica en su propio programa y luego aprender una biblioteca gráfica estándar. (Vea las razones para utilizar el código reutilizable)

Lo mejor de ambos mundos. Haz ambos. Si se estiran por el tiempo, conseguir un libro sobre esto o seguir tutoriales y los ejemplos.

Otra sugerencia: Formular una nueva pregunta directa sobre lo que es la biblioteca {mejor, más fiable, más fácil de aprender} {gráfico para describir un problema muy general}? Esto le ayudará a elegir qué aprender, en lugar de tratar de forma aleatoria para encontrar el que mejor se adapte a sus necesidades. Alguien ya ha visto este problema, pedir consejo.

El uso de código reutilizable:

Código que alguien ha escrito que incluye casos de prueba generalmente será más fiable que el suyo propio.
Correcciones son easer para poner en práctica (con actualizaciones al componente va a reutilizar), esto es cierto en Boost (ya que las actualizaciones frecuentes, y que Boost es revisada por pares).
Una vez que aprenda un marco que se puede aplicar a otras aplicaciones ... quien sabe que podría conseguir un trabajo en el futuro el uso del marco. Empresas como la reutilización en lugar de reinventar la rueda.

Me di la mía. Usted no debe seguir ese ejemplo, a menos que esté absolutamente seguro de que lo necesite.

Aún así, es una gran experiencia de aprendizaje, si usted es la teoría de grafos es oxidado.

Yo tenía un montón de "diversión" con la combinación de dígrafos utilizando operadores EBNF, y haciendo eliminación épsilon y minimización basada en Hopcroft. Especialmente con la reducción al mínimo, si se puede llamar desesperadamente tratando de encontrar una buena información y averiguar cómo funciona la "diversión": - (

Si liar, recomiendo que separa las operaciones de alto nivel de las estructuras de datos de bajo nivel dígrafo - diferentes clases, no sólo los diferentes métodos. No lo hice -. Y muy pronto voy a estar refactorización en gran medida debido a que la mala decisión

Algunas gráficas anotar nodos, algunos bordes anotar, algunos ambos. A veces dos anotaciones son útiles, incluso si son extranjeros las teclas sólo para algunos datos externos. Por ejemplo, en máquinas de estados finitos, un borde puede ser anotado con una entrada y una salida. Es muy probable que estar interesado en el determinismo WRT la entrada pero no la salida, por lo que tener a ambos escondido detrás de un único ID es un dolor - y eso es además de todo el tema de los contenedores secundarios para el lo-hace-el-ID-se refiere búsquedas -to.

También, a veces lo que desea es trabajar con cosas que no fueron diseñados explícitamente como un dígrafo IYSWIM - por ejemplo, un grupo de nodos de la estructura de datos que enlazan entre sí.

IOW, es útil ser capaz de conectar en diferentes representaciones dígrafo, y aún usar las mismas herramientas de alto nivel para muchas operaciones.

OMI que lo hizo bien cuando escribí una clase de 'herramienta árbol', que hace cosas como la iteración y el subíndice con el fin de árbol y el orden etiqueta de elemento XML. La representación del árbol subyacente es conectable (plantilla basada en la política). Con dígrafos, metí la pata.

De todos modos, no sé lo Boost o cualquier otra biblioteca gráfica que ofrece en realidad, pero si ofrece lo que necesita digo usarlo. Se ahorrará muchos dolores de cabeza.

Antes de decidirse a construir su propia biblioteca gráfica, me gustaría tener un buen vistazo a igraph ( http: // igraph. sourceforge.net/ ). Está escrito en C y es extremadamente rápido y ofrece una gama más amplia de algoritmos básicos y avanzados de gráficos (incluyendo la visualización). Además, cuenta con un envoltorio de Python para la codificación rápida así que creo que esta solución combina la velocidad de codificación y velocidad de ejecución.

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

Lemon ofrece todo eso y también tiene una sintaxis más simple, lo que me molesta con limón es los problemas de instalación y compilación de las plataformas de Windows, pero probablemente cambiará a pesar LIMÓN esos problemas.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow