CXXGraph
v4.1.0
CXXGraph é uma biblioteca C++ abrangente que gerencia algoritmos gráficos. Esta biblioteca somente de cabeçalho serve como uma alternativa à Boost Graph Library (BGL).
Estamos procurando:
Se você estiver interessado, entre em contato conosco pelo e-mail [email protected] ou contribua para este projeto. Estamos esperando por você!
| Concluído | Descrição | Data de conclusão |
|---|---|---|
| ✔️ | Versão 0.4.0 | 7 de outubro de 2022 |
| ✔️ | Versão 0.5.0 | 23 de março de 2023 |
| ✔️ | Primeira versão estável 1.0.0 | 28 de março de 2023 |
| ✔️ | Versão 1.0.1 | 7 de maio de 2023 |
| ✔️ | Versão 1.1.0 | 8 de maio de 2023 |
| ✔️ | Versão estável 2.0.0 | 1º de junho de 2023 |
| ✔️ | Versão estável 3.0.0 | 3 de novembro de 2023 |
| ✔️ | Versão 3.1.0 | 9 de janeiro de 2023 |
| Apresente o Hipergrafo #122 | A definir | |
| Versão estável 4.0.0 | A definir |
Para instalar em sistemas Unix/Linux, execute o seguinte na linha de comando:
$ sudo tar xjf CXXGraph-{version}.tar.bz2
Para desinstalar:
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
Para instalar em sistemas Fedora/CentOS/RedHat, execute o seguinte na linha de comando:
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
Para desinstalar:
$ sudo rpm -e CXXGraph-{version}
Para instalar em sistemas Debian/Ubuntu, execute o seguinte na linha de comando:
$ sudo dpkg -i CXXGraph_{version}.deb
Para desinstalar:
$ sudo apt-get remove CXXGraph
Para instalações autocompiladas usando CMake, execute o seguinte na linha de comando quando a compilação for concluída:
$ sudo make install
A explicação das classes pode ser encontrada na seção Classes da documentação do Doxygen
Para usar a biblioteca, basta colocar o arquivo de cabeçalho onde for necessário. É muito fácil!
Trabalho em andamento
O Unit-Test requer CMake 3.9 e posterior e a biblioteca GoogleTest .
GoogleTest
git clone https://github.com/google/googletest.git
cd googletest # Main directory of the cloned repository
mkdir -p build # Create a directory to hold the build output
cd build
cmake .. # Generate native build scripts for GoogleTest
make # Compile
sudo make install # Install in /usr/local/ by defaultDo diretório base:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DTEST=ON .. # Generate native build scripts for GoogleTest,
make # CompileApós a compilação ser compilada, execute o executável “test_exe” no diretório “build” com o seguinte comando:
./test_exe
O Benchmark requer CMake 3.9 e posterior, a biblioteca GoogleTest e a biblioteca Google Benchmark .
Comparativo de mercado do Google
# Check out the library
$ git clone https://github.com/google/benchmark.git
# Google Benchmark requires GoogleTest as a dependency. Add the source tree as a subdirectory
$ git clone https://github.com/google/googletest.git benchmark/googletest
# Go to the library's root directory
$ cd benchmark
# Make a build directory to place the build output
$ cmake -E make_directory " build "
# Generate the build system files with CMake
$ cmake -E chdir " build " cmake -DCMAKE_BUILD_TYPE=Release ../
# If starting with CMake 3.13, you can use the following:
# cmake -DCMAKE_BUILD_TYPE=Release -S . -B "build"
# Build the library
$ cmake --build " build " --config Release
# Install the library
$ sudo cmake --build " build " --config Release --target installDo diretório base:
mkdir -p build # Create a directory to hold the build output
cd build # Enter the build folder
cmake -DBENCHMARK=ON .. # Generate native build scripts for Google Benchmark
make # CompileApós a compilação ser compilada, execute o executável “benchmark” no diretório “build” com o seguinte comando:
./benchmark
Você pode verificar o resultado do benchmark usando este link.
Para criar um pacote tarball, execute o seguinte na linha de comando:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shPara criar um pacote RPM, execute o seguinte na linha de comando:
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shPara criar um pacote deb, execute o seguinte na linha de comando:
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shAlgoritmo de caminho mais curto de Dijkstras do gráfico (caminho mais curto de Dijkstra) [Algoritmo de Dijkstra] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) é usado para encontrar o caminho mais curto de um nó de origem para todos os outros nós acessíveis no gráfico. O algoritmo inicialmente assume que todos os nós são inacessíveis a partir de um determinado nó de origem, então marcamos as distâncias de todos os nós como infinito. (infinito) do nó de origem (INF/infinito denota incapacidade de alcançar).
Especialização de discagem do algoritmo de Dijkstra.
Quando os pesos das arestas são números inteiros pequenos (delimitados por um parâmetro C ), filas especializadas que aproveitam esse fato podem ser usadas para acelerar o algoritmo de Dijkstra. O primeiro algoritmo deste tipo foi o algoritmo de Dial (Dial 1969) para gráficos com pesos de borda inteiros positivos, que usa uma fila de balde para obter um tempo de execução O(|E|+|V|C) .(fonte wikipedia)
Abaixo está o algoritmo completo:
Neste link você encontra ilustrações passo a passo.
Algoritmo de Prim O Algoritmo de Prim é um algoritmo ganancioso que encontra uma árvore geradora mínima para um gráfico não direcionado ponderado. Isso significa que ele encontra um subconjunto de arestas que forma uma árvore que inclui todos os vértices, onde o peso total de todas as arestas da árvore é minimizado. O algoritmo opera construindo esta árvore, um vértice de cada vez, a partir de um vértice inicial arbitrário, adicionando a cada passo a conexão mais barata possível da árvore para outro vértice.
Passos:
(Breadth First Search) Algoritmo Breadth First Search (Breadth First Search) Breadth First Search , também citado como BFS , é um algoritmo de travessia de gráfico. Complexidade de tempo O(|V| + |E|) onde V é o número de vértices e E é o número de arestas no gráfico. As aplicações da primeira pesquisa ampla são:
E há muitos mais...
(Depth First Search) Algoritmo de profundidade de primeira pesquisa (Depth First Search) Depth First Search , também citado como DFS , é um algoritmo de travessia de gráfico. Complexidade de tempo O(|V| + |E|) onde V é o número de vértices e E é o número de arestas no gráfico. As aplicações da primeira pesquisa em profundidade são:
E há muitos mais...
Best First Search Best First Search é uma classe de algoritmos de busca que percorre o gráfico explorando o nó mais promissor escolhido de acordo com uma função de avaliação. A complexidade de tempo do pior caso é O(n * log n) onde n é o número de nós no gráfico.
Ciclo (teoria dos grafos)
A existência de um ciclo em grafos direcionados e não direcionados pode ser determinada se a pesquisa em profundidade (DFS) encontra uma aresta que aponta para um ancestral do vértice atual (ela contém uma aresta posterior). Todas as arestas posteriores que o DFS ignora fazem parte de ciclos. Em um gráfico não direcionado, a aresta para o pai de um nó não deve ser contada como uma aresta posterior, mas encontrar qualquer outro vértice já visitado indicará uma aresta posterior. No caso de grafos não direcionados, apenas O(n) tempo é necessário para encontrar um ciclo em um grafo de n vértices, uma vez que no máximo n − 1 arestas podem ser arestas de árvores.
Muitos algoritmos de classificação topológica também detectarão ciclos, uma vez que esses são obstáculos para a existência de ordem topológica. Além disso, se um gráfico direcionado foi dividido em componentes fortemente conectados, os ciclos só existem dentro dos componentes e não entre eles, uma vez que os ciclos estão fortemente conectados.
Para gráficos direcionados, algoritmos baseados em mensagens distribuídas podem ser usados. Esses algoritmos baseiam-se na ideia de que uma mensagem enviada por um vértice em um ciclo retornará a si mesma. Algoritmos de detecção de ciclo distribuído são úteis para processar gráficos de grande escala usando um sistema de processamento de gráfico distribuído em um cluster de computador (ou supercomputador).
As aplicações de detecção de ciclo incluem o uso de gráficos de espera para detectar impasses em sistemas simultâneos.
O algoritmo Bellman-Ford pode ser usado para encontrar a distância mais curta entre um nó de origem e um nó de destino. Complexidade de tempo O(|V| . |E|) onde V é o número de vértices e E é o número de arestas no gráfico que é maior que o algoritmo de caminho mais curto de Dijkstra. A complexidade de tempo do algoritmo de dijkstra é O(|E| + |V| log |v| ). A vantagem do bellman-ford sobre o dijkstra é que ele pode lidar com gráficos com pesos de aresta negativos. Além disso, se o gráfico contiver um ciclo de peso negativo, o algoritmo poderá detectar e relatar a presença de um ciclo negativo.
Este vídeo oferece uma boa visão geral da implementação do algoritmo. Esta palestra do MIT fornece uma prova da correção de Bellman-Ford e de sua capacidade de detectar ciclos negativos. Aplicações:
Algoritmo Floyd Warshall
Inicializamos a matriz de solução igual à matriz do gráfico de entrada como uma primeira etapa. Em seguida, atualizamos a matriz solução considerando todos os vértices como vértices intermediários. A ideia é escolher todos os vértices um por um e atualizar todos os caminhos mais curtos que incluem o vértice escolhido como um vértice intermediário no caminho mais curto. Quando escolhemos o número do vértice k como um vértice intermediário, já consideramos os vértices {0, 1, 2, .. k-1} como vértices intermediários. Para cada par (i, j) dos vértices de origem e destino respectivamente, existem dois casos possíveis.
Redução Transitiva
Este algoritmo é usado para construir um grafo direcionado com a mesma alcançabilidade e satisfaz fechamento transitivo, com o mínimo de arestas possível. Mais concretamente, ele cria um gráfico mínimo equivalente com o menor número possível de arestas, removendo caminhos de "curto-circuito" através do gráfico.
Isso é feito iterando cada par de nós, verificando se existem duas arestas que saem do primeiro nó OU do último nó, removendo a aresta do par de nós, se existir.
Em pseudocódigo: foreach x no gráfico.vértices foreach y no gráfico.vértices foreach z no gráfico.vértices exclua a aresta xz se as arestas xy e yz existirem
Nossa implementação tem portas if que fazem a verificação antecipada de arestas em vários lugares, o que proporciona um tempo de execução um pouco mais rápido do que o pseudocódigo cúbico aqui.
O algoritmo de Kruskal pode ser usado para encontrar a floresta de abrangência mínima de um gráfico não direcionado com ponderação de aresta. Complexidade de tempo O(E log E) = O(E log V) onde V é o número de vértices e E é o número de arestas no gráfico. A principal limitação de velocidade deste algoritmo é a classificação das arestas.
Para uma rápida compreensão do procedimento do algoritmo, confira este vídeo. Algumas das aplicações da vida real são:
Outros algoritmos para encontrar a floresta de abrangência mínima são o algoritmo de Prim ou o algoritmo de Borůvka.
O Algoritmo de Borůvka é um algoritmo ganancioso que pode ser usado para encontrar uma árvore geradora mínima em um grafo, ou uma floresta geradora mínima no caso de um grafo que não está conectado.
O algoritmo começa encontrando a aresta de peso mínimo incidente em cada vértice do gráfico e adicionando todas essas arestas à floresta. Em seguida, ele repete um processo semelhante de encontrar a aresta de peso mínimo de cada árvore construída até agora para uma árvore diferente e adicionar todas essas arestas à floresta. Cada repetição deste processo reduz o número de árvores, dentro de cada componente conectado do gráfico, para no máximo metade deste valor anterior, de modo que após muitas repetições logaritmicamente o processo termina. Quando isso acontece, o conjunto de arestas adicionado forma a floresta de abrangência mínima.
Pode-se mostrar que o algoritmo de Borůvka faz O (log V) iterações do loop externo até que ele termine e, portanto, é executado no tempo O (E log V), onde E é o número de arestas e V é o número de vértices em G (assumindo E ≥ V).
Definição matemática do problema: Seja G o conjunto de nós em um grafo e n um determinado nó nesse conjunto. Seja C o subconjunto não estrito de G contendo n e todos os nós acessíveis a partir de n, e seja C' seu complemento. Há um terceiro conjunto M, que é o subconjunto não estrito de C contendo todos os nós que são acessíveis a partir de qualquer nó em C'. O problema consiste em encontrar todos os nós que pertencem a C, mas não a M.
Algoritmo atualmente implementado:
Aplicativo:
Este algoritmo é usado em sistemas de coleta de lixo para decidir quais outros objetos precisam ser liberados, visto que um objeto está prestes a ser liberado.
O algoritmo Ford-Fulkerson é um algoritmo ganancioso para encontrar um fluxo máximo em uma rede de fluxo. A ideia por trás do algoritmo é a seguinte: desde que haja um caminho da origem (nó inicial) até o coletor (nó final), com capacidade disponível em todas as arestas do caminho, enviamos o fluxo por um dos caminhos. Então encontramos outro caminho e assim por diante. Um caminho com capacidade disponível é chamado de caminho aumentado.
O Algoritmo de Kosaraju é um algoritmo de tempo linear para encontrar os componentes fortemente conectados de um gráfico direcionado. Baseia-se na ideia de que se alguém é capaz de alcançar um vértice v a partir do vértice u, então deve ser capaz de alcançar o vértice u a partir do vértice v e se for esse o caso, pode-se dizer que os vértices u e v são fortemente conectados - eles estão em um subgráfico fortemente conectado. A seguir está um exemplo:
1). Crie uma pilha vazia 'S' e faça a travessia DFS de um gráfico. Na travessia DFS, depois de chamar o DFS recursivo para vértices adjacentes de um vértice, empurre o vértice para empilhar. 2). Inverta as direções de todos os arcos para obter o gráfico de transposição. 3). Um por um, retire um vértice de S enquanto S não está vazio. Deixe o vértice exibido ser 'v'. Tome v como fonte e faça DFS (chame DFSUtil(v)). O DFS começando em v imprime o componente fortemente conectado de v.
O algoritmo de Kahn encontra ordenação topológica removendo iterativamente nós no gráfico que não possuem arestas de entrada. Quando um nó é removido do gráfico, ele é adicionado à ordenação topológica e todas as suas arestas são removidas, permitindo que o próximo conjunto de nós sem arestas de entrada seja selecionado.
O algoritmo Welsh Powell Coloring é um algoritmo ganancioso de coloração de vértices. Este algoritmo também é usado para encontrar o número cromático de um gráfico.
O algoritmo Welsh Powell consiste nas seguintes etapas:
O algoritmo retorna um resultado std::map<Node, int> que atribui cada nó a uma cor ordenada por números inteiros. Os usuários também podem consultar a ordem cromática mínima do gráfico consultando o valor mais alto do mapa resultante.
std::map<Node, int > result = graph.welshPowellColoring();
auto chromatic_color = std::max_element(result.begin(), result.end(),
[]( const auto & lhs, const auto & rhs) {
return lhs. second < rhs. second ;
}A coloração mínima começa em 1 em vez de 0.
O algoritmo assume que o gráfico não é direcionado. Todas as fontes e inspirações estão vinculadas na declaração do algoritmo e nos casos de teste.
Um particionamento por corte de vértice divide as arestas de um gráfico em partições de tamanhos iguais. Os vértices que contêm as extremidades de uma aresta também são colocados na mesma partição que a própria aresta. No entanto, os vértices não são únicos entre partições e podem ter que ser replicados (cortados), devido à distribuição das suas arestas entre diferentes partições.
O fator de replicação quantifica quantos vértices são replicados em computadores em comparação com o número de vértices do gráfico de entrada original.
Este algoritmo é um corte de vértice simples no estilo Round-Robin. Ele pega as arestas originais do gráfico e as atribui às partições, dividindo-as em tamanhos iguais (ou semelhantes). Este algoritmo não cuida da otimização na replicação de vértices (Fator de Replicação), mas apenas equilibra as arestas nas partições.
Algoritmos de particionamento gananciosos usam todo o histórico de atribuições de borda para tomar a próxima decisão. O algoritmo armazena o conjunto de partições A(v) às quais cada vértice v já observado foi atribuído e os tamanhos atuais das partições. Ao processar a aresta e ∈ E conectando os vértices vi, vj ∈ V , o algoritmo ganancioso segue este conjunto simples de regras:
O algoritmo High Degree (are) Replicated First (HDRF) é um algoritmo ganancioso de corte de vértice, conforme descrito neste artigo. Este algoritmo tenta otimizar o Fator de Replicação usando o histórico das atribuições das arestas e o grau incremental do vértice. Com uma função que leva em consideração esses dois fatores calcula-se a melhor partição para atribuir a aresta analisada. As réplicas criadas são baseadas no grau dos vértices, e os vértices replicados são provavelmente os chamados "Hub-Node", que são os vértices com maior grau.
Corte de vértice eficiente e equilibrado (EBV) é um algoritmo de corte de vértice offline conforme descrito neste artigo. Este algoritmo tenta equilibrar as partições em relação ao número de arestas e vértices de cada partição e ao Fator de Replicação. Aplica uma fórmula para avaliar a partição na qual atribui a aresta que leva em consideração também o número total de arestas e vértices do grafo. A fórmula de avaliação é a seguinte:
O valor mais baixo é considerado o ID da partição.
A Matriz de Graus é uma matriz quadrada que fornece insights sobre a conectividade dos nós em um gráfico. Para grafos direcionados, reflete o número de arestas de entrada e saída de cada nó, enquanto para grafos não direcionados, representa o número de arestas incidentes em cada nó.
A Matriz Laplaciana é uma matriz quadrada derivada da matriz de adjacência e da matriz de graus de um gráfico. É fundamental na análise de várias propriedades do gráfico, como conectividade, contagem de árvores geradoras e outras características espectrais.
A Matriz de Transição é comumente usada no estudo de Cadeias de Markov e processos estocásticos. No contexto de um gráfico, denota as probabilidades de transição de um nó para outro, muitas vezes com base nos pesos das arestas ou critérios predeterminados. Esta matriz encontra aplicações em vários campos, como análise de rede, aprendizado de máquina e otimização.
Se quiser dar seu apoio, você pode criar uma solicitação pull ou relatar um problema . Se você deseja alterar o código, corrigir um problema ou implementar um novo recurso, leia nosso Guia de CONTRIBUIÇÃO.
Se você quiser discutir novos recursos ou tiver alguma dúvida ou sugestão sobre a biblioteca, abra uma discussão ou simplesmente converse no
Site CXXGraph
E-mail: [email protected]
Perfil GitHub
Para me apoiar, adicione uma estrela ao projeto ou siga-me
Para ficar atualizado, assista ao projeto
Somos referenciados por:
Obrigado à comunidade TheAlgorithms por alguma inspiração em algoritmos.
Obrigado a GeeksForGeeks por alguma inspiração em algoritmos.
Obrigado a todas as pessoas que já contribuíram para o CXXGraph!
Se você usar este software, siga as instruções de CITAÇÃO. Obrigado!
Participamos do Hacktoberfest 2021. Obrigado a todos os colaboradores!
Participamos do Hacktoberfest 2022. Obrigado a todos os colaboradores!
Participamos do Hacktoberfest 2023. Obrigado a todos os colaboradores!
Visualize o valor estimado do projeto
@ZigRazor |
|---|
