Minha vida com a Boost Graph Library

O artigo, cuja primeira parte é apresentada aqui, contém várias considerações do autor, acumuladas durante o longo desenvolvimento de um sistema especializado para busca de conexões sociais, com base na Boost Graph Library (BGL). Esta seção (técnica) resume as impressões do autor de trabalhar com esta biblioteca, levanta questões de instrumentação ao criar aplicativos gráficos e aborda alguns problemas práticos da metaprogramação em C ++.

BGL e com o que é consumido

A biblioteca de modelos BGL provavelmente é conhecida por qualquer desenvolvedor que tenha encontrado tarefas gráficas. Aparecendo no Boost 1.18.1 em 2000, ela imediatamente ganhou críticas de aprovação de clássicos do gênero como Alexander Stepanov. O guia da biblioteca, compilado por Jeremy Sik, Lai-Kwan Lee e Andrew Lamsdane, foi publicado em russo em 2006 por Peter (original - Jeremy G. Siek, Lie-Quan Lee e Andrew Lumsdaine, “The Boost Graph Library”, 2001 Addison-Wesley). A biblioteca foi intensamente atualizada e desenvolvida quase até o final de 2013 (Boost 1.55.0). Em particular, em 2005, apareceu o anúncio de sua versão distribuída (PBGL), que foi incluída no Boost da versão 1.40 em 2009 e até hoje continua sendo uma espécie de padrão de fato para computação gráfica em clusters de alto desempenho, em qualquer caso, no mundo acadêmico. Tanto quanto a história dos commits pode ser julgada, até 2005, o principal desenvolvedor da biblioteca foi Jeremy Sik, depois de 2005 - Douglas Gregor, e em geral várias vezes uma quantidade considerável de diversas pessoas trabalhava na biblioteca. As publicações dedicadas a ele apareceram repetidamente no habr.com: em primeiro lugar, uma série de artigos de Vadim Androsov deve ser observada: [ 1 , 2 , 3 ]. Assim, em princípio, boa e diversa literatura é dedicada à biblioteca, mas sua própria documentação, também, de um modo geral, bastante extensa, sofre um pouco devido ao fato de que:

1. Seu índice e seções raiz, que pretendem fornecer uma lista exaustiva das principais entidades, não foram alterados desde 2001. Por exemplo, o autor dessas linhas, que ingenuamente acreditava que:

   Atualmente, o BGL fornece duas classes de gráficos e um adaptador de lista de arestas:
   
   adjacency_list
   adjacency_matrix
   edge_list

   , depois de algum tempo, fiquei surpreso ao encontrar a representação compressed_sparse_row_graph (matriz esparsa) implementada em 2005. Uma história semelhante ocorreu com o algoritmo Bron-Kerbosch. Não acredite no índice, use uma pesquisa direta nos arquivos de cabeçalho;
   
2. Não há uma única lista comentada das categorias internas da biblioteca (categoria_contêiner, características_alterna_ paralela, estabilidade_do_erador etc.) necessárias para implementar suas próprias visualizações. Os problemas de compreensão do que está acontecendo ultrapassam, aparentemente, todos os usuários da biblioteca que desejam ir mais fundo, o que leva à aparência de um "tipo de código funcional", que leva muito tempo e esforço para trazê-lo a um estado completo: veja, por exemplo, uma discussão típica .

O número de categorias e vários seletores, incluindo aqueles que são confusamente semelhantes, é tão grande que os próprios autores às vezes se confundem neles. Por exemplo, nos construtores do compressed_sparse_row_graph já mencionado acima, na versão atual, há um erro sistemático que causa falhas ao tentar copiar uma lista de adjacências não direcionadas:



Pode-se notar aqui ocasionalmente que o teste completo de um mecanismo tão flexível é um problema separado, uma vez que é acompanhado por uma explosão combinatória do número de possíveis substituições.

Deve-se notar com pesar que, atualmente, os principais desenvolvedores aparentemente tenham perdido o interesse em mais trabalhos na biblioteca e, nos últimos seis anos, ela, de maneira alguma esgotou seu potencial de desenvolvimento e nem mesmo se libertou completamente de inconsistências internas e erros diretos, está em voo livre. Os planos expressados ​​na região de 2011 para expandir significativamente o conjunto de métodos e abranger novas áreas da teoria dos grafos (incluindo a adição de suporte interno ao particionamento de gráficos à capacidade de ler o formato METIS) permaneceram por cumprir. Parece também que a biblioteca poderia se beneficiar muito (pelo menos em termos de legibilidade) com o amplo uso de novos produtos que se tornaram padrão após 2011.

Assim, as questões de escolher uma biblioteca de referência para aplicativos gráficos ao olhar para 2019 não parecem tão claras quanto gostaríamos, e nos últimos 5 anos, a incerteza aumentou e não diminuiu.

Essa situação causa tristeza, porque a criação de um mecanismo universal semelhante ao BGL é em si uma espécie de façanha intelectual, tanto em termos de poder da abordagem quanto da riqueza do arsenal de métodos universais implementados (uma boa e meia centena de thread único e duas dúzias distribuídas) a biblioteca, até onde o autor dessas linhas é conhecido, ainda não tem igual.

No momento, somente essa biblioteca permite, em princípio, sem perda de desempenho, impor acordos estritos sobre a apresentação de dados e perda de controle sobre os mecanismos internos da própria biblioteca, para separar completamente os algoritmos e representações gráficas, tornando a última completamente independente da apresentação de metadados associados a arestas e vértices ( que, em princípio, é obviamente a maneira mais correta de fazer as coisas).

A palavra "fundamentalmente" é usada aqui por uma razão. Considerando uma situação específica usando o exemplo da longa classe compressed_sparse_row_graph já mencionada acima, podemos observar, por exemplo, os seguintes desvios em relação aos altos padrões:

1. O operador [] para a lista de adjacência e a matriz esparsa lida com as propriedades internas e externas das arestas de maneira diferente (Propriedades Internas e Agrupadas): o primeiro retorna apenas propriedades externas (internas são acessíveis apenas com property_map), o segundo retorna uma propriedade de estrutura de estrutura que contém uma lista comum de propriedades.
2. A função get para obter o índice de borda usando boost :: property_map <compressed_sparse_row_graph, boost :: edge_index_t> :: type caiu em boost :: detail e não em boost, como em todos os outros casos.

Finalmente, no modelo compressed_sparse_row_graph, a especialização para o gráfico não direcionado (boost :: undirectedS) permaneceu não preenchida.

Nesse sentido, ao usar a propriedade edge_index (número de série da borda), surgem dificuldades adicionais devido ao fato de que, para a lista de adjacências, essa propriedade deve ser explicitamente definida como interna e, como tal, pode ser alterada arbitrariamente, mas para um gráfico não direcionado, seu valor não depende da direção onde a costela passa. Para uma matriz esparsa (sempre direcional), é uma constante constante property_map de uma forma especial (calculada como um índice em uma matriz de arestas). Consequentemente, os valores para as arestas próximas (representando um gráfico não direcionado) não podem ser alterados e sempre serão diferentes.

Todas essas discrepâncias levam à impossibilidade de "simplesmente substituir a representação gráfica por uma equivalente" ao chamar funções algorítmicas, o que prejudica significativamente a principal vantagem da biblioteca. Na prática, nesses casos, é necessária uma especialização excessiva de código ou seu processamento para excluir elementos com comportamentos diferentes, ou um ajuste de modelos de gráfico para que eles "se comportem de forma idêntica" com diferentes definições de atributo ou, finalmente, remoção de arquivos individuais da biblioteca e criação "Versão de reforço pessoal."

Além disso, os seguintes inconvenientes, não tão significativos, podem ser observados:

• As dimensões dos descritores internos das representações gráficas têm um impacto significativo no consumo de memória necessário para armazenar o gráfico e, algumas vezes, afetam o desempenho dos algoritmos.
  
  Algumas visualizações (a mesma compressed_sparse_row_graph) permitem controlar essas dimensões. Outros (adjacency_list) não possuem esses parâmetros e sempre usam números inteiros de 64 bits (geralmente redundantes), que não podem ser substituídos sem modificar o código;
  
• Apesar de os autores da biblioteca fornecerem muito, muito, algumas primitivas obviamente necessárias não foram incluídas na biblioteca. Por exemplo, não há função como reverse_edge que executa inversão de borda.
  
  A implementação de tais funções, é claro, depende da representação gráfica: nesse caso, pode ser implementada por uma troca trivial de elementos de um par, pesquisa mais ou menos eficiente por contêiner ou não. É difícil para o usuário final entender toda essa variedade de opções, principalmente porque, de acordo com a ideologia da biblioteca, os membros internos dos descritores não devem lhe interessar.
  
• Da mesma forma, alguns scripts longe de inúteis caíram da biblioteca. Por exemplo, você pode definir predicados de aresta que usam o filter_graph para transformar um gráfico não direcionado em um gráfico direcionado, mas não há como chamar essa transformação à atenção da biblioteca. Consequentemente, algoritmos regulares para gráficos direcionados não serão compilados com esse objeto, e algoritmos para gráficos não direcionados não funcionarão corretamente com ele.
  
  Em algum lugar da vizinhança, há o tópico de suporte para gráficos tecnicamente não direcionais que têm um marcador de direção de serviço nas bordas. No entanto, maior atenção a essa visão pode ser devida à natureza específica das tarefas que o autor resolve, e o amplo interesse em apoiar esses objetos não é óbvio.
  
• Quanto à função reverse_edge, tomada como exemplo acima, não existe uma opção incrível de que a função desejada esteja presente em algum lugar nas entranhas da biblioteca, mas por algum motivo recebeu um nome não óbvio. Isso leva ao seguinte problema, que à primeira vista não é sério, mas diminui significativamente o trabalho com bibliotecas de modelos complexas (não apenas o BGL, embora esteja claramente entre os líderes por esse critério): trabalhe com sistemas extensos de funções relacionadas implicitamente sem digitar explicitamente os parâmetros e com a semântica não óbvia do uso (geralmente a menos transparente que a mais bem pensada) é fisicamente difícil, e os ambientes de desenvolvimento existentes não fornecem suporte para isso no desenvolvedor:
  
  
  
  De fato, assistentes automáticos:
  
  
  1. Projetado principalmente para suporte a OOP, quando um conjunto de funções é vinculado ao objeto à direita, de acordo com seu tipo. Com funções globais que podem ficar à esquerda de um tipo (muito menos um conjunto de tipos), elas ajudam muito pior, mesmo que todos os tipos sejam conhecidos.
  2. Eles ridiculamente nem são capazes de trabalhar com modelos simples. A versão do assistente visual usada pelo autor, tendo à sua frente a definição de uma classe de modelo com parâmetros padrão, oferece a especificação de uma “substituição de teste” para poder gerar uma dica para a classe. Se você a conhecer, absolutamente nada acontece.
  3. Além disso, eles são menos capazes de entender qualificadores de metaprograma, mesmo os mais simples, como enable_if.
  4. Sobre um cenário típico: “estamos dentro de uma função de modelo chamada a partir de um número indefinido de cadeias de comprimento indefinido de outras funções, incluindo as de modelo”, é impossível falar sem lágrimas. Nesse caso, o vim realmente continua sendo o melhor amigo do programador.
  
  Outro aspecto da mesma situação pode ser ilustrado usando a primeira linha do fragmento de código mostrado na figura anterior. O leitor é convidado a concluir as consultas "aumentar a hora atual" versus "hora atual da CRT" e comparar os resultados. Sim, o boost :: date_time (agora parcialmente movido para std) torna possível fazer muitas coisas complexas corretamente, enquanto o CRT permite executar várias operações triviais incorretamente, mas em situações domésticas comuns, o CRT é mais conveniente de todos os pontos de vista e polinomiais construções do formato posix_time :: second_clock :: local_time (um exemplo simples) tendem a se transformar em hieróglifos vagando no programa. Privar o desenvolvedor de acesso à biblioteca pessoal de tais hieróglifos e a velocidade de desenvolvimento será zero .
  
  O Boost :: string_algo torna possível fazer qualquer coisa com strings, mas, honestamente, cada operação não muito trivial é acompanhada de uma sessão de releitura da documentação para atualizar a lógica geral da biblioteca, os nomes dos predicados e um exercício separado para descobrir a compatibilidade dos parâmetros. Uma situação semelhante ocorre com operações de tokenização no boost :: regexp, com lógica interna impecável do último.
  
  Se tal situação ocorrer com as bibliotecas mais usadas, não surpreende que o BGL, como uma biblioteca mais especializada, na qual, por exemplo, existam funções make_property_map_function e make_function_property_map que não estejam relacionadas entre si, assim como uma função get sacramental que seja recarregada para qualquer o número de argumentos de qualquer tipo gera os mesmos problemas, mas de forma hipertrofiada. Sim, qualquer tarefa pode ser resolvida pela cadeia de chamadas get, mas, infelizmente, nem toda cadeia get resolve esse problema.
  
  Ler um código como esse pode ser fácil e agradável, pode até parecer uma sinopse de um algoritmo formalmente escrito em uma linguagem natural, mas ao escrevê-lo, a impossibilidade de substituir palavras por sinônimos, etc. manifestações de rigidez, não é característica de um real.
  
• Em ordem geral, não se pode deixar de repetir a observação banal, mas não se tornando menos verdadeira, de que a metaprogramação em C ++ ainda é literalmente baseada em efeitos colaterais de ferramentas de linguagem cujo objetivo original era diferente e até nas idéias mais simples com base em Como resultado, é difícil expressar e ler a metalinguagem, e vincular o código do modelo ao sistema arcaico dos arquivos incluídos não facilita a vida do desenvolvedor e não reduz a quantidade de código processado pelo compilador.
  
  (Por outro lado, as atualizações periódicas de boost e std trazem muitas construções não muito triviais e muitas vezes extremamente úteis e soluções inesperadas, o que realmente permite escrever códigos mais claros e compactos a um custo menor. No entanto, o fluxo de novos produtos é tão amplo, desigual e mal estruturado que os mais importantes adições à biblioteca padrão, mesmo as mais óbvias, como as opções / apply_visitor ou qualquer outra mencionada abaixo, se as vantagens conceituais de sua aplicação no contexto de um projeto específico não forem relevantes Por óbvio, sem a ajuda de um evento feliz, eles podem ficar fora de foco por um longo tempo, se você não gastar uma parte significativa do tempo de trabalho rastreando cuidadosamente novos produtos, estudando exemplos não triviais de uso e tentativas mentais de aplicá-los a um código existente. para lidar com esse problema - manter para cada cinco programadores de C ++ em prática um C ++ - um teórico ocupado apenas com questões prioritárias de novos produtos, sua implementação ções no projeto e os profissionais da educação seletiva. Conclusão: não inicie projetos C ++ com menos desenvolvedores ).
  
• Por fim, objetivamente, o problema mais sério que ocorre ao trabalhar com o código padrão da BGL . Suponha que estamos usando algum algoritmo de gabarito que faz uma passagem através de um gráfico e toma uma representação do gráfico G como argumento. Em um caso típico, essa representação depende dos filtros sobrepostos nos vértices e nas arestas $$$F_v$, $$$F_e$e esquema de peso $$$W$. Para trabalhar com gráficos filtrados, o BGL oferece a classe de modelo filter_graph mencionada acima, a maneira de anexar o esquema de ponderação é a critério do usuário. Functors representando $$$F_v$, $$$F_e$e $$$W$pode incluir pelo menos as seguintes visualizações:
  
  
  • Diretamente um wrapper para uma função que representa um esquema de ponderação e predicados que representam filtros (lentamente, sem perda de inicialização);
  • Caches sobre esses wrappers, mapeando descritores de borda / nó para índices de borda / nó, abordando o bitmap e a matriz de valores (sem perdas de inicialização, com um aumento gradual na velocidade conforme usado);
  • Mapeamento direto de descritores de nó / borda para matrizes de valor preenchidas (requer inicialização, mas pode ser construído com base na representação anterior; a velocidade atinge o máximo).
  
  Portanto, se esse algoritmo fosse escrito em um estilo tradicional, três seletores com pelo menos três ramificações em cada apareceriam em seu corpo (e a necessidade de ajustar o corpo quando novas representações aparecerem). Como cada ramificação no corpo do algoritmo, que executa um grande número de vezes ao passar pelo gráfico, resulta em perda de tempo perceptível, o desejo de evitar essas perdas enquanto mantém o código do mesmo estilo tradicional pode levar a mais de 27 implementações do algoritmo para várias combinações de representações.
  
  O estilo do metaprograma deve salvá-lo desses problemas, permitindo que você suporte uma metafunção que descreve o algoritmo que gera implicitamente todas as implementações necessárias (e também, possivelmente, algumas e possivelmente uma quantidade considerável de desnecessária se as estruturas de código de tempo de execução não gerarem de fato algumas combinações de tipos, ), .
  
  , , 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 ... } 

  
  Ele pode ser reescrito de forma um pouco mais compacta usando a variante <...> aproximadamente da seguinte 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); } 

  
  A desvantagem dessa forma de escrita é a necessidade de enumeração explícita dos tipos type_1, type_2, ... na declaração da variante. Esses tipos podem ser complicados, a gravação usando declval / result_of_t não pode ser menos complicada.
  
  Ao usar qualquer, não há necessidade de listar tipos, mas não há como obter um apply_visitor analógico.
  
  O uso de alguma função de modelo make_variant, que permite escrever código do seguinte tipo, sugere-se:
  
  

    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, ...), ... ); 

  
  mas a cura não parece melhor que a doença.
  
  Em geral, existe uma situação típica para a metaprogramação em C ++, quando, para expressar uma idéia muito simples, é necessário usar todo um arsenal de ferramentas auxiliares com um resultado que não é muito satisfatório em termos de legibilidade e facilidade de gravação. Essencialmente, eu gostaria de poder escrever algo como o seguinte:
  
  

    //   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 ... } 

  
  ou até:
  
  

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

  
  A última opção, embora seja completamente eliminada do estilo C ++, parece mais prática, pois pode haver mais de uma variável arg para a qual o tipo é selecionado e não há motivo para antecipar a lógica de sua construção .
  
• O outro lado da mesma situação é o uso de estruturas auxiliares (por exemplo, armazenamento em cache) que implementam um script que merece o nome de uma "variável de modelo", mas difere da extensão padrão C ++ 14 com o mesmo nome.
  
  O código correspondente pode ser algo como isto:
  
  

    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); } }; 

  
  Aqui, como acima, construções longas expressam a idéia simples de acessar uma variável que representa o cache por um nome específico, independentemente da dimensão do valor em cache (passando de maneira transparente pelo código de chamada).
  
  Por uma questão de brevidade, o código é fornecido para o caso em que apenas um tipo pode estar ativo, mas na prática a situação é mais comum quando vários contêineres podem existir simultaneamente (ele pode ser facilmente implementado no mesmo estilo usando tupla e opcional).
  
  A implementação da função get <...> supõe que o código de chamada tenha alguma idéia de que tipo de valor em cache ele deseja acessar (por exemplo, número inteiro ou ponto flutuante).
  
  Não menos comum é a situação em que o valor exato do tipo não é importante para o chamador. Nesse caso, o script select_value_type / apply_visitor do parágrafo anterior é reproduzido (ajustado para a possível multiplicidade de valores, o que implica a visualização de tipos em ordem decrescente de prioridade).
  
• Até agora, praticamente não houve menção ao PBGL neste texto. Isso é explicado pela experiência cada vez menor do autor de trabalhar com essa parte da biblioteca (em relação à qual o próprio autor, com um certo ceticismo, se refere a tudo o que está escrito abaixo neste parágrafo e apela a outros para o mesmo). De fato, esse experimento se resume a vários experimentos, no mesmo tipo de problemas de pesquisa que demonstraram em dados práticos a perda de uma versão distribuída para uma solução local 3-5 vezes na memória e 15-20 vezes no desempenho geral (a origem dessa figura assustadora é explicada aqui e comentada adicionalmente nos parágrafos seguintes) . Dada a maior complexidade de trabalhar com estruturas distribuídas, a escolha a favor da versão local era evidente em tal situação.
  
  Vamos explicar a mecânica da operação PBGL usando um exemplo típico do algoritmo delta-walking. Nesta versão paralela do algoritmo de Dijkstra, a fila de prioridade é substituída por uma matriz de "buckets". Os elementos que se enquadram em um "bloco" são processados ​​em paralelo. Na sua forma original, o ritmo delta é um algoritmo típico para sistemas de memória compartilhada.
  
  Na versão distribuída, acontece o seguinte: no PBGL, ao carregar, o gráfico é espalhado entre os processos, e cada processo possui um intervalo contínuo de números de vértices. Assim, pelo número do vértice global, é fácil saber a qual processo ele pertence. Consequentemente, cada processo em cada turno do algoritmo armazena uma parte do "bucket" que contém os vértices pertencentes a esse processo. Todos os processos simultaneamente selecionam e processam os vértices de suas partes dos "buckets", um de cada vez, enquanto enviam mensagens sobre a necessidade de atualizar os seguintes "buckets" para processos que possuem os vértices vizinhos. É fácil ver que, ceteris paribus, um aumento no número de processos leva a um aumento no número de mensagens que eles enviam. Como resultado, o tempo de execução do algoritmo pode não apenas diminuir, mas até aumentar. Em particular, o lançamento de vários processos MPI para resolver esse problema em uma máquina física com uma certa probabilidade só levará a um aumento na carga total do processador sem nenhum ganho de tempo.
  
  Deve-se observar que o ritmo delta é o algoritmo de pesquisa distribuído mais rápido (dos três suportados pela biblioteca).
  
  Portanto, se o gráfico não for preparado anteriormente, ele deverá ser dividido em blocos de tamanho máximo, um bloco por máquina física. Por preparação preliminar, entendemos aqui a renumeração dos vértices do gráfico para que os intervalos contínuos de números usados ​​pelo PBGL, se possível, correspondam a subgráficos vagamente conectados. Pacotes como METIS, paraMETIS e Zoltan são usados ​​para esses fins. Trabalhar com gráficos dinâmicos nesse modo é difícil.
  
  Em geral, de acordo com os resultados dos experimentos descritos, o autor teve a impressão de que a operação normal do cluster PBGL é possível apenas com equipamentos de comunicação especiais, e faz sentido usar máquinas com um número mínimo de núcleos e desempenho máximo do encadeamento como nós desse cluster. Os autores do Trinity, em seu artigo, argumentam que o armazenamento distribuído funciona com muito mais eficiência - o autor acha difícil comentar sobre essa afirmação, mas, dadas as circunstâncias acima, considera bastante possível: a arquitetura PBGL tem um selo distinto do tempo em que as máquinas com vários núcleos ainda não receberam ampla distribuição.
  
  O PBGL também compartilha os problemas da versão single-threaded: alguma sincronização de código, documentação e exemplos, agravados pela maior complexidade do sistema e menos usuários dispostos a compartilhar experiências úteis.
  

BGL e outros animais

Levando em conta uma lista bastante longa de reclamações específicas, não será inapropriado perguntar: o autor pode recomendar a BGL para novos projetos em 2019. A resposta é a seguinte: o autor acredita que as bibliotecas desse estilo e aplicativos baseados neles devem ter um futuro . Quanto à escolha de uma biblioteca de referência para um projeto em particular, devemos considerar seriamente a instrumentação, sem perder de vista os problemas listados acima. A resposta, obviamente, depende de muitas circunstâncias, incluindo, entre outras, as listadas nos parágrafos seguintes:

• Se trabalhar com gráficos em um projeto é a base da funcionalidade ou uma tarefa opcional;
• Um projeto pode obter vantagem com o uso de várias representações ou trabalhar com algoritmos de tipo rígido o suficiente;
• O tipo mais benéfico de simultaneidade para o projeto;
• Nuanças organizacionais: o desejo de metaprogramação em C ++ entre funcionários (especialmente programadores de matemática), etc.

Provavelmente, ceteris paribus, o uso de BGL pode ser justificado no caso de um uso único muito pequeno (para extrudar ou copiar um código de trabalho e esquecer), ou para um sistema grande para o qual uma maior flexibilidade pagará entrada pesada e outros custos ao longo do tempo. Em outros casos, faz sentido estudar cuidadosamente outras opções.

Quanto às possíveis alternativas, sua lista inclui pelo menos os seguintes itens :

De particular interesse geral é a questão da classificação de vários produtos de software orientados para trabalhar com gráficos. Sua diversidade, para não mencionar o número, é muito grande. Sem pretender concluir (e até mesmo formalmente) a classificação, podemos tentar, no entanto, destacar as seguintes áreas importantes no desenvolvimento de aplicativos gráficos:

1. Gráfico de DBMS (neo4j, etc.).
   
   Sistemas desse tipo estão focados na execução de operações transacionais em gráficos grandes (disco distribuído). Embora a API desse sistema possa ser altamente desenvolvida, a velocidade de execução dos próprios algoritmos gráficos, até onde se pode julgar, não é a primeira prioridade. O sistema pode nem tentar carregar o gráfico inteiro na memória. Para modificação e passagem de gráfico, são suportadas linguagens declarativas (SPARQL, Cypher, Gremlin). É de grande importância garantir a continuidade dos sistemas SQL tradicionais.
2. Extensões gráficas de sistemas de processamento de big data que trabalham no paradigma mapear / reduzir (GraphX ​​no Spark, Pegasus e Giraph para Hadoop) e sistemas de cluster independentes ( MS Trinity / MS Graph Engine , GraphLab). Os primeiros a executar operações no gráfico implementam o modelo do Google Pregel (mas não apenas ele) e podem ser configurados para uso, incluindo nós de computação paralela em massa. Esses e outros podem ser usados, entre outras coisas, como base para projetos de software corporativo.
   
   Embora a API desses sistemas possa ser bastante desenvolvida (entre outras coisas, o GraphX ​​suporta SPARQL e Cypher), o foco principal ao trabalhar com eles é a solução de problemas de infraestrutura. O GraphX ​​é caracterizado pela imutabilidade dos dados e um viés no pipelining de todas as operações. Atualmente, o MS Trinity não inclui métodos de alto nível e fornece apenas um conjunto de primitivas para trabalhar com nós e arestas. Os sistemas executados no topo do Hadoop são, em princípio, de pouca utilidade para resolver problemas gráficos arbitrários.
   
3. Bibliotecas de ferramentas realmente universais que implementam conjuntos de métodos mais ou menos amplos (BGL / PBGL, LEMON etc.), incluindo os massivamente paralelos (nvGraph, Gunrock).
   
   Com base neles, podem ser criados sistemas de aplicativos que adaptam algoritmos gráficos a áreas específicas.
4. Sistemas e bibliotecas especializados em problemas complexos e de importância universal (METIS, paraMETIS, Zoltran: particionamento de gráficos, GraphViz, Gephi: visualização, GraphBLAS: algoritmos algébricos para trabalhar com gráficos, etc.).
   
   Muitos aplicativos gráficos independentes podem ser atribuídos condicionalmente a essa categoria, cuja análise detalhada exigiria muito tempo. Este último contém aplicações de todas as variedades possíveis: acadêmicas e comerciais, de usuário único e multiusuário, surgiram recentemente e existem há mais de uma década, etc.

Uma parte obscura, mas significativa, dos aplicativos gráficos é focada nas tarefas de Análise de Rede e, já, Análise de Rede Social (Detecção de Comunidade). Curiosamente, os sistemas de Análise de Link (usados, geralmente, por vários "combatentes do crime") são muito menos comuns, que têm uma certa semelhança com o sistema que estamos desenvolvendo. Em todos os casos, sem uma verificação especial, é difícil determinar a natureza dos modelos de dados usados ​​por vários sistemas e as limitações de desempenho associadas, volumes suportados, conjuntos de operações etc.

Anotações

1. O BGL não é uma biblioteca puramente de cabeçalho, mas, no momento, a única funcionalidade que precisa de vinculação é (bastante opcional) trabalhar com arquivos DOT do GraphViz. Portanto, na grande maioria dos casos, não há necessidade de vincular e vincular automaticamente a versão adequada do libbost-graph para incluir cabeçalhos BGL na configuração do Boost. Portanto, para obter consistência com a biblioteca libboost-regex usada por funções BGL sem cabeçalho, é conveniente simplesmente conectar o cabeçalho boost \ regex.hpp do código do projeto, mesmo que este último não use expressões regulares.
2. Caos adicional é introduzido pela presença de entidades cuja aparente equivalência incentiva a caça a (possivelmente ausentes) gatos pretos em salas escuras .
3. Antes de prosseguir com sua descrição (usando um exemplo específico, onde ele se manifestou de maneira especialmente forte e desagradável), observamos que o autor está entre as poucas pessoas de sorte que trabalham com um projeto carregado em um poderoso sistema operacional Windows e a linha salva de Deus de compiladores MSVC. É possível que os problemas descritos abaixo sejam artefatos dessa linha de compiladores: uma variedade de circunstâncias particulares dificulta a realização de um experimento comparativo com o gcc / clang no ambiente * nix. Nesse caso, você só pode parabenizar usuários de outros compiladores.
4. Para suavizar o que, em alguns casos, o recentemente apareceu constexpr if provavelmente ajudará.
5. No nosso caso, isso levou a uma atenção especial à função de economia de estado, que permite a depuração com conveniência, primeiro levando o sistema ao estado inicial desejado em uma montagem otimizada.
6. Na minha prática, por várias razões, havia a necessidade de converter parâmetros de tempo de execução em argumentos de modelo, e muitas vezes eu tive que recorrer a formas muito elaboradas (com muita precisão) (inspiradas nas implementações desatualizadas de boost typeof e boost lambda para C ++ 98, que atingiam diretamente o (tratar a técnica de programação em C ++ como uma solução para o rébus), entre as quais a estrela brilha na seleção do argumento dividindo-a ao meio , mas, em geral, os principais problemas com essas operações sempre foram associados à incapacidade de exportar tipo selecionado fora do escopo, que deu origem a padrões exóticos.
7. ( — 80 4 50 200 , ) ( ) - . , . , 6-8 — , .
8. , . ( , - , . , , , , , , , ).
9. , , – , , «» (-- ..) . ( , ), , «» , — ( ). , , , - . , , : «» ( ) , «» ( ), , . . , - , « », . , « » ? , , , : – , , , , .
10. . , , .
11. «LIBNAME C++ graph» , stackoverflow. , BGL 500 [boost-graph].