Mi vida con Boost Graph Library

El artículo, cuya primera parte se presenta aquí, contiene varias consideraciones del autor, acumuladas durante el largo desarrollo de un sistema especializado para buscar conexiones sociales, basado en la Boost Graph Library (BGL). Esta sección (técnica) resume las impresiones del autor de trabajar con esta biblioteca, plantea problemas de instrumentación al crear aplicaciones de gráficos y toca algunos problemas prácticos de metaprogramación en C ++.

BGL y con qué se come

La biblioteca de plantillas BGL probablemente sea conocida por cualquier desarrollador que haya encontrado tareas gráficas. Apareciendo en Boost 1.18.1 en 2000, de inmediato obtuvo críticas de aprobación de clásicos del género como Alexander Stepanov. La guía de la biblioteca, compilada por Jeremy Sik, Lai-Kwan Lee y Andrew Lamsdane, fue publicada en ruso en 2006 por Peter (original - Jeremy G. Siek, Lie-Quan Lee y Andrew Lumsdaine, "The Boost Graph Library", 2001 , Addison-Wesley). La biblioteca se actualizó intensamente y se desarrolló casi hasta finales de 2013 (Boost 1.55.0). En particular, en 2005, apareció el anuncio de su versión distribuida (PBGL), que se incluyó en Boost desde la versión 1.40 en 2009 y hasta el día de hoy sigue siendo una especie de estándar de facto para la computación gráfica en clústeres de alto rendimiento, en cualquier caso, en el mundo académico Hasta donde se puede juzgar la historia de los commits, hasta 2005, el desarrollador principal de la biblioteca fue Jeremy Sik, después de 2005 - Douglas Gregor, y en general en varias ocasiones una cantidad considerable de personas diversas trabajó en la biblioteca. Las publicaciones dedicadas a él han aparecido repetidamente en habr.com: en primer lugar, debe tenerse en cuenta una serie de artículos de Vadim Androsov: [ 1 , 2 , 3 ]. Por lo tanto, en principio, se dedica una buena y diversa literatura a la biblioteca, pero su propia documentación, también, en general, bastante extensa, sufre algo debido al hecho de que:

1. Su tabla de contenido y secciones raíz, que afirman proporcionar una lista exhaustiva de entidades clave, no han cambiado desde 2001. Por ejemplo, el autor de estas líneas, que ingenuamente creía que:

   El BGL actualmente proporciona dos clases de gráficos y un adaptador de lista de bordes:
   
   lista de adyacencia
   adjacency_matrix
   edge_list

   , después de un tiempo me sorprendió encontrar la representación compressed_sparse_row_graph (matriz dispersa) implementada en 2005. Una historia similar tuvo lugar con el algoritmo Bron-Kerbosch. No crea en la tabla de contenido, use una búsqueda directa en los archivos de encabezado;
   
2. No hay una sola lista comentada de las categorías internas de la biblioteca (categoría_contenedor, paralelas_ediciones_transitivas, estabilidad_ iterador, etc., etc.) necesarias para implementar sus propias vistas. Aparentemente, los problemas con la comprensión de lo que está sucediendo superan a todos los usuarios de la biblioteca que desean profundizar, lo que lleva a la aparición de un "tipo de código de trabajo", que requiere mucho tiempo y esfuerzo para llevarlo a un estado completo: ver, por ejemplo, una discusión típica .

El número de categorías y varios selectores, incluidos los que son confusamente similares, es tan grande que los propios autores a veces se confunden en ellos. Por ejemplo, en los constructores de compressed_sparse_row_graph ya mencionados anteriormente, en la versión actual hay un error sistemático que provoca bloqueos al intentar copiar una lista de adyacencia no dirigida:



Cabe señalar aquí en ocasiones que la prueba completa de un mecanismo tan flexible es un problema separado, ya que se acompaña de una explosión combinatoria del número de posibles sustituciones.

Cabe señalar con pesar que en la actualidad los principales desarrolladores aparentemente han perdido interés en seguir trabajando en la biblioteca y durante los últimos seis años, sin haber agotado su potencial de desarrollo y ni siquiera liberándose por completo de las inconsistencias internas y los errores directos, está en vuelo libre. Los planes expresados ​​en la región de 2011 para expandir significativamente el conjunto de métodos y cubrir nuevas áreas de la teoría de gráficos (incluso mediante la adición de soporte interno de partición de gráficos a la capacidad de leer el formato METIS) no se cumplieron. También parece que la biblioteca podría beneficiarse mucho (al menos en términos de legibilidad) del uso generalizado de nuevos productos que se convirtieron en estándar después de 2011.

Por lo tanto, los problemas de elegir una biblioteca de referencia para aplicaciones de gráficos cuando se mira desde 2019 no parecen tan claros como nos gustaría, y en los últimos 5 años, la incertidumbre ha aumentado en lugar de disminuir.

Esta situación causa cierta tristeza, porque la creación de un mecanismo universal similar a BGL, en sí mismo, es una especie de hazaña intelectual, tanto en términos del poder del enfoque como de la riqueza del arsenal de métodos universales implementados (un buen y medio centenar de un solo subproceso y un par de docenas distribuidos) la biblioteca, hasta donde se conoce al autor de estas líneas, todavía no tiene igual.

Por el momento, solo esta biblioteca permite, en principio, sin pérdida de rendimiento, imponer acuerdos estrictos sobre la presentación de datos y la pérdida de control sobre los mecanismos internos de la biblioteca, para separar por completo los algoritmos gráficos y las representaciones gráficas, lo que hace que esta última sea completamente independiente de la presentación de metadatos asociados con bordes y vértices ( que, en principio, es obviamente la forma más correcta de hacer las cosas).

La palabra "fundamentalmente" se usa aquí por una razón. Teniendo en cuenta una situación específica utilizando el ejemplo de la sufrida clase compressed_sparse_row_graph ya mencionada anteriormente, podemos observar, por ejemplo, las siguientes desviaciones de los altos estándares:

1. El operador [] para la lista de adyacencia y la matriz dispersa manejan las propiedades internas y externas de los bordes de manera diferente (Propiedades internas y agrupadas): el primero devuelve solo propiedades externas (internas son accesibles solo con property_map), el segundo devuelve una propiedad de estructura de trama que contiene una lista común de propiedades.
2. La función get para obtener el índice de borde usando boost :: property_map <compressed_sparse_row_graph, boost :: edge_index_t> :: type cayó en boost :: detail, y no en boost, como en todos los demás casos.

Finalmente, en la plantilla compressed_sparse_row_graph, la especialización para el gráfico no dirigido (boost :: undirectedS) no se cumplió.

En este sentido, cuando se usa la propiedad edge_index (número de serie de borde), surgen dificultades adicionales debido al hecho de que para la lista de adyacencia esta propiedad debe establecerse explícitamente como interna y, como tal, puede cambiarse arbitrariamente, pero para un gráfico no dirigido su valor no depende de la dirección donde pasa la costilla Para una matriz dispersa (siempre direccional), es un mapa_propiedad constante incorporado de una forma especial (calculada como un índice en una matriz de bordes). En consecuencia, los valores para las aristas que se aproximan (que representan un gráfico no dirigido) no pueden cambiar y siempre serán diferentes.

Todas estas discrepancias conducen a la imposibilidad de "simplemente reemplazar la representación gráfica con una equivalente" al llamar a funciones algorítmicas, lo que socava significativamente la ventaja principal de la biblioteca. En la práctica, en tales casos, se requiere una especialización de código excesiva, o su procesamiento para excluir elementos con diferentes comportamientos, o dicho ajuste de plantillas de gráficos para que "se comporten de manera idéntica" con diferentes definiciones de atributos, o, finalmente, la eliminación de archivos individuales de la biblioteca y la creación "Versión de impulso personal".

Además, se pueden observar los siguientes inconvenientes, no tan importantes:

• Las dimensiones de los descriptores internos de las representaciones gráficas tienen un impacto significativo en el consumo de memoria necesario para almacenar el gráfico y, a veces, afectan el rendimiento de los algoritmos.
  
  Algunas vistas (el mismo compressed_sparse_row_graph) le permiten controlar estas dimensiones. Otros (adjacency_list) no tienen tales parámetros y siempre usan enteros de 64 bits (generalmente redundantes), que no se pueden reemplazar sin modificar el código;
  
• A pesar de que los autores de la biblioteca proporcionaron mucho, mucho, algunas primitivas obviamente necesarias no se incluyeron en la biblioteca. Por ejemplo, no existe una función como reverse_edge que realice la inversión de bordes.
  
  La implementación de tales funciones, por supuesto, depende de la representación gráfica: en este caso, puede implementarse mediante un intercambio trivial de elementos de un par, una búsqueda más o menos eficiente por contenedor, o nada en absoluto. Es difícil para el usuario final comprender toda esta variedad de opciones, especialmente porque, de acuerdo con la ideología de la biblioteca, los miembros internos de los descriptores no deberían ser de su interés.
  
• Del mismo modo, algunos guiones lejos de ser inútiles cayeron de la biblioteca. Por ejemplo, puede definir predicados de borde que usen filter_graph para convertir un gráfico no dirigido en un gráfico dirigido, pero no hay forma de llamar la atención de la biblioteca sobre esta transformación. En consecuencia, los algoritmos regulares para gráficos dirigidos no se compilarán con dicho objeto, y los algoritmos para gráficos no dirigidos no funcionarán correctamente con él.
  
  En algún lugar del vecindario existe el tema de soporte para gráficos técnicamente no direccionales que tienen un marcador de dirección de servicio en los bordes. Sin embargo, una mayor atención a este punto de vista puede deberse a la naturaleza particular de las tareas que resuelve el autor, y el interés generalizado en apoyar tales objetos no es obvio.
  
• En cuanto a la función reverse_edge, tomada como un ejemplo anterior, no hay una opción increíble de que la función deseada esté presente en algún lugar de las entrañas de la biblioteca, pero por alguna razón recibió un nombre no obvio. Esto lleva al siguiente problema, que a primera vista no es serio, pero ralentiza significativamente el trabajo con bibliotecas de plantillas complejas (no solo BGL, aunque está claramente entre los líderes según este criterio): trabajar con sistemas extensivos de funciones relacionadas implícitamente sin tipado explícito de parámetros y con La semántica de uso no obvia (a menudo la menos transparente que la más bien pensada) es físicamente difícil, y los entornos de desarrollo existentes no proporcionan ningún soporte para esto en el desarrollador:
  
  
  
  De hecho, los asistentes automáticos:
  
  
  1. Diseñado principalmente para el soporte de OOP, cuando un conjunto de funciones está vinculado al objeto de la derecha según su tipo. Con funciones globales que pueden estar a la izquierda de un tipo (mucho menos un conjunto de tipos), ayudan mucho peor incluso si se conocen todos los tipos.
  2. Son ridículamente incapaces de trabajar con plantillas simples. La versión del asistente visual utilizada por el autor, que tiene frente a él la definición de una clase de plantilla con parámetros predeterminados, ofrece especificar una "sustitución de prueba" para poder generar una pista para la clase. Si la conoces, no pasa absolutamente nada.
  3. Además, son menos capaces de comprender los calificadores de metaprogramas, incluso los más simples, como enable_if.
  4. Acerca de un escenario típico: "estamos dentro de una función de plantilla que se llama desde un número indefinido de longitud indefinida de cadenas de otras funciones, incluidas las plantillas", es imposible hablar sin lágrimas. En este caso, vim sigue siendo el mejor amigo del programador.
  
  Otro aspecto de la misma situación puede ilustrarse utilizando la primera línea del fragmento de código que se muestra en la figura anterior. Se invita al lector a completar las consultas de "impulso de tiempo actual" frente a "tiempo actual de CRT" y comparar los resultados. Sí, boost :: date_time (ahora parcialmente movido a std) hace posible hacer muchas cosas complejas correctamente, mientras que la CRT le permite hacer varias operaciones triviales de forma incorrecta, pero en situaciones cotidianas comunes en el hogar, la CRT es más conveniente desde todos los puntos de vista y polinomiales. Las construcciones de la forma posix_time :: second_clock :: local_time (un ejemplo suave) tienden a convertirse en jeroglíficos que deambulan por el programa. Priva al desarrollador del acceso a la biblioteca personal de dichos jeroglíficos y la velocidad de desarrollo será cero .
  
  Boost :: string_algo hace posible hacer cualquier cosa con cadenas, pero, sinceramente, cada operación no del todo trivial se acompaña de una sesión de relectura de documentación para actualizar la lógica general de la biblioteca, los nombres de predicados, así como un ejercicio separado para descubrir la compatibilidad de los parámetros. Una situación similar ocurre con las operaciones de tokenización en boost :: regexp, con una lógica interna impecable de este último.
  
  Si tal situación ocurre con las bibliotecas más utilizadas, no es sorprendente que BGL, como una biblioteca más especializada, en la que, por ejemplo, hay funciones make_property_map_function y make_function_property_map que no están relacionadas entre sí, así como una función sacramental get que se recarga en cualquier El número de argumentos de cualquier tipo da lugar a los mismos problemas, pero en forma hipertrofiada. Sí, cualquier tarea puede ser resuelta por la cadena get call, pero, lamentablemente, no todas las cadenas get resuelven este problema.
  
  Leer un código de este tipo puede ser fácil y agradable, incluso puede parecer una sinopsis de un algoritmo escrito formalmente en un lenguaje natural, pero al escribirlo, la imposibilidad de reemplazar palabras con sinónimos, etc., manifestaciones de rigidez no es característica de uno real.
  
• En orden general, uno no puede dejar de repetir lo banal, pero no se vuelve menos cierto, la observación de que la metaprogramación en C ++ todavía se basa literalmente en los efectos secundarios de las herramientas del lenguaje, cuyo propósito original era diferente, e incluso las ideas más simples sobre la base de Como resultado, el metalenguaje es difícil de expresar y leer, y vincular el código de la plantilla al sistema arcaico de archivos incluidos no facilita la vida del desarrollador y no reduce la cantidad de código procesado por el compilador.
  
  (Por otro lado, las actualizaciones periódicas de boost y std traen muchas construcciones no triviales y, a menudo, extremadamente útiles y soluciones inesperadas, que realmente permiten escribir código más claro y compacto a un costo menor. Sin embargo, el flujo de nuevos productos es tan amplio, desigual y mal estructurado que lo más importante adiciones a la biblioteca estándar, incluso las obvias como options / apply_visitor o cualquiera de las mencionadas a continuación, si las ventajas conceptuales de su aplicación en el contexto de un proyecto específico no son relevantes De manera evidente, sin la ayuda de un evento feliz, pueden desenfocarse durante mucho tiempo, si no pasa una parte significativa del tiempo de trabajo directamente rastreando cuidadosamente nuevos productos, estudiando ejemplos no triviales de su uso e intentos mentales para aplicarlos a un código existente. para hacer frente a este problema, mantener por cada cinco programadores en práctica de C ++ un C ++, un teórico que solo se ocupa de cuestiones de prioridad de nuevos productos, su implementación ciones en el proyecto y los profesionales de la educación selectivos. Conclusión: no inicie C ++ - proyectos con menos desarrolladores ).
  
• Finalmente, objetivamente, el problema más serio que ocurre cuando se trabaja con código repetitivo BGL . Supongamos que estamos utilizando algún algoritmo de plantilla que hace un pasaje a través de un gráfico y toma una representación del gráfico G como argumento. En un caso típico, esta representación depende de los filtros impuestos en los vértices y bordes $$$F_v$, $$$F_e$y esquema de peso $$$W$. Para trabajar con gráficos filtrados, BGL ofrece la clase de plantilla filter_graph mencionada anteriormente, la forma de adjuntar el esquema de peso es a discreción del usuario. Functores que representan $$$F_v$, $$$F_e$y $$$W$puede incluir al menos las siguientes vistas:
  
  
  • Directamente un contenedor para una función que representa un esquema de ponderación y predicados que representan filtros (lentamente, sin pérdida de inicialización);
  • Cachés sobre estos envoltorios, asignando descriptores de borde / nodo a índices de borde / nodo, abordando el mapa de bits y la matriz de valores (sin pérdidas de inicialización, con un aumento gradual de la velocidad como se usa);
  • Asignación directa de descriptores de nodo / borde a matrices de valores rellenos (requiere inicialización, pero se puede construir sobre la base de la representación previa; la velocidad alcanza su máximo).
  
  Por lo tanto, si este algoritmo se escribiera en un estilo tradicional, tres selectores con al menos tres ramas en cada uno aparecerían en su cuerpo (y la necesidad de ajustar el cuerpo cuando aparezcan nuevas representaciones). Dado que cada ramificación en el cuerpo del algoritmo, que se ejecuta una gran cantidad de veces al pasar por el gráfico, da como resultado una notable pérdida de tiempo, el deseo de evitar estas pérdidas mientras se mantiene el código del mismo estilo tradicional puede conducir a más de 27 implementaciones del algoritmo para varias combinaciones de representaciones.
  
  El estilo de metaprograma debería salvarlo de estos problemas, permitiéndole admitir una metafunción que describe el algoritmo que genera implícitamente todas las implementaciones necesarias (y también, posiblemente, una cantidad considerable y posiblemente innecesaria si las estructuras de código de tiempo de ejecución no generan de facto algunas combinaciones de tipos, que ), .
  
  , , inline- , –O2. - ( 1:3 1:5, – , , ).
  
  , . . , ( ) , «» «» . , . : «» «» , «» , «» .
  
  , : , 100% , , «» . ( , , - , , , , , ).
  
• , , , . C++ , -, , .
  
  , , :
  
  

  void type_selector_fun(type_a a, type_b b, ...) { if (condition_1(a, b, ...)) { auto arg = get_type_1_obj(a, b, ...); run_calc(arg, a, b, ...); } else if (condition_1(a, b, ...)) { auto arg = get_type_2_obj(a, b, ...); run_calc(arg, a, b, ...); } else ... } 

  
  Se puede reescribir de manera algo más compacta usando la variante <...> en aproximadamente la siguiente forma:
  
  

    void type_selector_fun(type_a a, type_b b, ...) { variant<type_1, type_2, ...> arg; if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else if ... ... apply_visitor([&](auto arg_){run_calc(arg_, a, b, ...); }, arg); } 

  
  La desventaja de esta forma de escritura es la necesidad de una enumeración explícita de los tipos type_1, type_2, ... en la declaración de variantes. Estos tipos pueden ser engorrosos, la grabación usando declval / result_of_t no puede ser menos engorrosa.
  
  Al usar any, no hay necesidad de enumerar tipos, pero no hay forma de obtener un apply_visitor analógico.
  
  Se sugiere el uso de alguna función de plantilla make_variant, que le permite escribir código del siguiente tipo:
  
  

    auto arg = make_variant ( bind(condition_1, a, b, ...), bind(get_type_1_obj, a, b, ...), bind(condition_2, a, b, ...), bind(get_type_2_obj, a, b, ...), ... ); 

  
  pero la cura no se ve mejor que la enfermedad.
  
  En general, existe una situación típica para la metaprogramación en C ++, cuando para expresar una idea muy simple debe usar todo un arsenal de herramientas auxiliares que no son muy satisfactorias en términos de legibilidad y facilidad de grabación. Esencialmente, me gustaría poder escribir algo como lo siguiente:
  
  

    //   variant<...>      //  ,   : type_1, type_2 etc. variant<auto...> get_type_obj(typa_a a, type_b b, ...) { if (condition_1(a, b, ...)) { return get_type_1_obj(a, b, ...); } else if (condition_2(a, b, ...)) { return get_type_2_obj(a, b, ...); } else ... } 

  
  o incluso:
  
  

    select_value_type(arg) { if (condition_1(a, b, ...)) { arg = get_type_1_obj(a, b, ...); } else ... ... } run_calc(arg, a, b, …); 

  
  La última opción, aunque está completamente eliminada del estilo C ++, parece la más práctica, ya que puede haber más de una variable arg para la cual se selecciona el tipo, y no hay razón para anticipar la lógica de su construcción .
  
• La otra cara de la misma situación es el uso de estructuras auxiliares (por ejemplo, almacenamiento en caché) que implementan un script que merece el nombre de una "variable de plantilla", pero que difiere de la extensión estándar C ++ 14 del mismo nombre.
  
  El código correspondiente puede verse así:
  
  

    struct CacheHolder { boost::variant< container<T1>, container<T2>, // ... container<TN>> ct; template<typename T> struct result_type_selector { typedef typename if_c<is_compatible<T, T1>::value, T1, if_c<is_compatible<T, T2>::value, T2, // ... if_c<is_compatible<T, TN>::value, TN, std::decay_t<T>>>>::type type; }; template<typename T> auto get() const -> const container<typename result_type_selector<T>::type>& { return boost::get<container<typename result_type_selector<T>::type>>(ct); } }; 

  
  Aquí, como anteriormente, las construcciones largas expresan la idea simple de acceder a una variable que representa el caché por un nombre específico, independientemente de la dimensión del valor almacenado en caché (que pasa de forma transparente a través del código de llamada).
  
  Por brevedad, el código se proporciona para el caso en que solo un tipo puede estar activo, pero en la práctica la situación es más común cuando pueden existir varios contenedores simultáneamente (se puede implementar fácilmente en el mismo estilo usando tupla y opcional).
  
  La implementación de la función get <...> supone que el código de llamada tiene alguna idea de qué tipo de valor en caché quiere acceder (por ejemplo, entero o punto flotante).
  
  No menos común es la situación en la que el valor de tipo exacto no es importante para la persona que llama. En este caso, se reproduce el script select_value_type / apply_visitor del párrafo anterior (ajustado por la posible multiplicidad de valores, lo que implica ver los tipos en orden descendente de prioridad).
  
• Hasta ahora, prácticamente no se ha mencionado PBGL en este texto. Esto se explica por la pequeña y desaparecida experiencia del autor de trabajar con esta parte de la biblioteca (en relación con la cual el propio autor, con cierto escepticismo, se refiere a todo lo que se escribe a continuación en este párrafo, y llama a otros a lo mismo). De hecho, tal experimento se reduce a varios experimentos, en el mismo tipo de problemas de búsqueda que se demostraron en datos prácticos que perdieron una versión distribuida a una solución local 3-5 veces en la memoria y 15-20 veces en el rendimiento general (el origen de esta cifra aterradora se explica aquí y se comenta adicionalmente en los siguientes párrafos) . Dada la mayor complejidad de trabajar con estructuras distribuidas, la elección a favor de la versión local era evidente en tal situación.
  
  Expliquemos la mecánica de la operación PBGL utilizando un ejemplo típico del algoritmo de delta-walking. En esta versión paralela del algoritmo de Dijkstra, la cola de prioridad se reemplaza con una serie de "cubos". Los elementos que caen en un "cubo" se procesan en paralelo. En su forma original, el ritmo delta es un algoritmo típico para sistemas de memoria compartida.
  
  En la versión distribuida, sucede lo siguiente: en PBGL, cuando se carga, el gráfico se dispersa entre los procesos, y cada proceso tiene un rango continuo de números de vértices. Por lo tanto, por el número de vértice global, es fácil saber a qué proceso pertenece. En consecuencia, cada proceso en cada vuelta del algoritmo almacena una parte del "cubo" que contiene los vértices que pertenecen a este proceso. Todos los procesos seleccionan y procesan simultáneamente los vértices de sus partes de los "cubos" uno a la vez, mientras envían mensajes sobre la necesidad de actualizar los siguientes "cubos" a los procesos que poseen vértices vecinos. Es fácil ver que, ceteris paribus, un aumento en el número de procesos conduce a un aumento en el número de mensajes que envían. Como resultado, el tiempo de ejecución del algoritmo no solo no puede disminuir, sino incluso aumentar. En particular, el lanzamiento de varios procesos MPI para resolver este problema en una máquina física con una cierta probabilidad solo conducirá a un aumento en la carga total del procesador sin ganancia de tiempo.
  
  Cabe señalar que el ritmo delta es el algoritmo de búsqueda distribuido más rápido (de los tres admitidos por la biblioteca).
  
  Por lo tanto, si el gráfico no está preparado previamente, debe dividirse en bloques de tamaño máximo, un bloque por máquina física. Por preparación preliminar, nos referimos aquí a renumerar los vértices de la gráfica para que los rangos continuos de números utilizados por PBGL, si es posible, correspondan a subgrafías conectadas libremente. Para estos fines se utilizan paquetes como METIS, paraMETIS y Zoltan. Trabajar con gráficos dinámicos en este modo es difícil.
  
  En general, de acuerdo con los resultados de los experimentos descritos, el autor tuvo la impresión de que el funcionamiento normal del clúster PBGL solo es posible con un equipo de comunicación especial, y tiene sentido usar máquinas con un número mínimo de núcleos y una productividad máxima de hilo como nodos de dicho clúster. Los autores de Trinity en su artículo argumentan que su almacenamiento distribuido funciona de manera mucho más eficiente: al autor le resulta difícil comentar sobre esta declaración, pero, dadas las circunstancias anteriores, lo encuentra bastante posible: la arquitectura PBGL lleva un sello distintivo del tiempo en que las máquinas de múltiples núcleos aún no han recibido una distribución amplia.
  
  PBGL también comparte los problemas de la versión de subproceso único: algunos códigos de sincronización, documentación y ejemplos, agravados por la mayor complejidad del sistema y menos usuarios dispuestos a compartir experiencias útiles.
  

BGL y otros animales

Teniendo en cuenta una lista bastante larga de quejas específicas, no será inapropiado preguntar: ¿puede el autor recomendar BGL para nuevos proyectos en 2019? La respuesta es esta: el autor cree que las bibliotecas de este estilo y las aplicaciones basadas en ellas deben tener un futuro . En cuanto a la elección de una biblioteca de referencia para un proyecto en particular, debemos considerar seriamente la instrumentación, sin perder de vista los problemas enumerados anteriormente. La respuesta, obviamente, depende de muchas circunstancias, incluidas, entre otras, las enumeradas en los siguientes párrafos:

• Si trabajar con gráficos en un proyecto es la base de la funcionalidad o una tarea opcional;
• ¿Puede un proyecto obtener una ventaja mediante el uso de múltiples representaciones o es trabajar con algoritmos de tipo duro bastante suficiente para ello?
• El tipo de concurrencia más beneficioso para el proyecto;
• Matices organizacionales: el deseo de metaprogramación en C ++ entre los empleados (especialmente los programadores de matemáticas), etc.

Probablemente, ceteris paribus, el uso de BGL puede justificarse en el caso de un uso muy pequeño de una sola vez (para extruir o copiar un código de trabajo y olvidarlo), o para un sistema grande por el cual una mayor flexibilidad pagará la entrada pesada y otros costos a lo largo del tiempo. En otros casos, tiene sentido estudiar cuidadosamente otras opciones.

En cuanto a las posibles alternativas, su lista incluye al menos los siguientes elementos :

De particular interés general es la cuestión de la clasificación de varios productos de software orientados a trabajar con gráficos. Su diversidad, sin mencionar el número, es muy grande. Sin pretender completar (e incluso formalmente corregir) la clasificación, podemos intentar, sin embargo, resaltar las siguientes áreas importantes en el desarrollo de aplicaciones gráficas:

1. Gráfico DBMS (neo4j, etc.).
   
   Los sistemas de este tipo se centran en realizar operaciones transaccionales en gráficos grandes (disco distribuido). Aunque la API de un sistema de este tipo puede estar altamente desarrollada, la velocidad de ejecución de los algoritmos gráficos en sí mismos, por lo que se puede juzgar, no es la primera prioridad. Es posible que el sistema ni siquiera intente cargar todo el gráfico en la memoria. Para la modificación y el recorrido de gráficos, se admiten lenguajes declarativos (SPARQL, Cypher, Gremlin). Se concede gran importancia a garantizar la continuidad con los sistemas SQL tradicionales.
2. Extensiones de gráficos de sistemas de procesamiento de big data que trabajan en el paradigma de mapa / reducción (GraphX ​​en Spark, Pegasus y Giraph para Hadoop) y sistemas de clúster independientes ( MS Trinity / MS Graph Engine , GraphLab). Los primeros en realizar operaciones en el gráfico implementan el modelo Google Pregel (pero no solo él) y pueden configurarse para su uso, incluidos nodos informáticos paralelos masivos. Tanto esos como otros pueden usarse, entre otras cosas, como base para proyectos de software corporativo.
   
   Aunque la API de dichos sistemas puede estar bastante desarrollada (entre otras cosas, GraphX ​​admite SPARQL y Cypher), el enfoque principal cuando se trabaja con ellos es resolver problemas de infraestructura. GraphX ​​se caracteriza por la inmutabilidad de los datos y un sesgo en la canalización de todas las operaciones. MS Trinity actualmente no incluye métodos de alto nivel y proporciona solo un conjunto de primitivas para trabajar con nodos y bordes. Los sistemas que se ejecutan sobre Hadoop son, en principio, de poca utilidad para resolver problemas de gráficos arbitrarios.
   
3. Bibliotecas de herramientas realmente universales que implementan conjuntos de métodos más o menos amplios (BGL / PBGL, LEMON, etc.), incluidos los masivamente paralelos (nvGraph, Gunrock).
   
   En base a ellos, se pueden crear sistemas de aplicación que adapten algoritmos gráficos a áreas temáticas específicas.
4. Sistemas y bibliotecas especializadas en problemas complejos particulares de importancia universal (METIS, paraMETIS, Zoltran: partición de gráficos, GraphViz, Gephi: visualización, GraphBLAS: algoritmos algebraicos para trabajar con gráficos, etc.).
   
   Muchas aplicaciones de gráficos independientes se pueden asignar condicionalmente a esta categoría, cuyo análisis detallado requeriría demasiado tiempo. Este último contiene aplicaciones de todas las variedades imaginables: académicas y comerciales, de usuario único y multiusuario, recientemente aparecidas y existentes por más de una década, etc.

Una parte oscura pero significativa de las aplicaciones de gráficos se centra en las tareas de Análisis de redes y, ya, Análisis de redes sociales (Detección de la comunidad). Curiosamente, los sistemas de análisis de enlaces (utilizados, por regla general, por varios "luchadores contra el crimen") son mucho menos comunes, y tienen cierta similitud con el sistema que estamos desarrollando. En todos los casos, sin una verificación especial, es difícil determinar la naturaleza de los modelos de datos utilizados por varios sistemas y las limitaciones de rendimiento asociadas, volúmenes admitidos, conjuntos de operaciones, etc.

Notas

1. BGL no es una biblioteca puramente de encabezado, pero en este momento la única funcionalidad que necesita vinculación es (más bien opcional) trabajar con archivos GraphViz DOT. Por lo tanto, en la gran mayoría de los casos, no es necesario vincular y vincular automáticamente con la versión adecuada de libbost-graph para incluir encabezados BGL en la configuración de Boost. Por lo tanto, para mantener la coherencia con la biblioteca libboost-regex utilizada por las funciones BGL sin encabezado, es conveniente simplemente conectar el encabezado boost \ regex.hpp del código del proyecto, incluso si este último no utiliza expresiones regulares.
2. El caos adicional se introduce por la presencia de entidades cuya aparente equivalencia alienta la caza de gatos negros (posiblemente ausentes) en habitaciones oscuras .
3. Antes de continuar con su descripción (usando un ejemplo específico, donde se manifestó especialmente fuerte y desagradable), notamos que el autor se encuentra entre las relativamente pocas personas afortunadas que trabajan con un proyecto cargado en un poderoso sistema operativo Windows y la línea de compiladores MSVC guardados por Dios. Es posible que los problemas descritos a continuación sean artefactos de esta línea de compiladores: una variedad de circunstancias particulares hacen que sea difícil realizar un experimento comparativo con gcc / clang en el entorno * nix. Si es así, solo puede felicitar a los usuarios de otros compiladores.
4. Para suavizar lo que en algunos casos, el constexpr recientemente apareció si probablemente ayudará.
5. En nuestro caso, esto llevó a una atención especial a la función de ahorro de estado, que permite la depuración con comodidad, primero llevando el sistema al estado inicial deseado en un ensamblaje optimizado.
6. En mi práctica, por varias razones, era necesario convertir los parámetros de tiempo de ejecución en argumentos de plantilla, y muy a menudo tenía que recurrir a formas muy elaboradas y muy precisas (inspiradas en las implementaciones ahora desactualizadas de boost typeof y boost lambda para C ++ 98, que golpeó directamente el tratar la técnica de programación en C ++ como una solución al acertijo), entre los cuales la estrella destaca la selección del argumento dividiendo a la mitad , pero, en general, los principales problemas con tales operaciones siempre estuvieron asociados con la incapacidad de exportar tipo seleccionado fuera del alcance, lo que dio lugar a patrones exóticos.
7. ( — 80 4 50 200 , ) ( ) - . , . , 6-8 — , .
8. , . ( , - , . , , , , , , , ).
9. , , – , , «» (-- ..) . ( , ), , «» , — ( ). , , , - . , , : «» ( ) , «» ( ), , . . , - , « », . , « » ? , , , : – , , , , .
10. . , , .
11. «LIBNAME C++ graph» , stackoverflow. , BGL 500 [boost-graph].