CXXGraph
v4.1.0
CXXGraph es una biblioteca completa de C++ que gestiona algoritmos de gráficos. Esta biblioteca de solo encabezado sirve como alternativa a la biblioteca Boost Graph (BGL).
Estamos buscando:
Si está interesado, contáctenos en [email protected] o contribuya a este proyecto. ¡Te estamos esperando!
| Terminado | Descripción | Fecha de finalización |
|---|---|---|
| ✔️ | Versión 0.4.0 | 7 de octubre de 2022 |
| ✔️ | Versión 0.5.0 | 23 de marzo de 2023 |
| ✔️ | Primera versión estable 1.0.0 | 28 de marzo de 2023 |
| ✔️ | Versión 1.0.1 | 7 de mayo de 2023 |
| ✔️ | Versión 1.1.0 | 8 de mayo de 2023 |
| ✔️ | Versión estable 2.0.0 | 1 de junio de 2023 |
| ✔️ | Versión estable 3.0.0 | 3 de noviembre de 2023 |
| ✔️ | Versión 3.1.0 | 9 de enero de 2023 |
| Presentar el hipergráfico n.° 122 | Por determinar | |
| Versión estable 4.0.0 | Por determinar |
Para instalar en sistemas Unix/Linux, ejecute lo siguiente desde la línea de comando:
$ sudo tar xjf CXXGraph-{version}.tar.bz2
Para desinstalar:
$ sudo rm -f /usr/include/Graph.hpp /usr/include/CXXGraph*
Para instalar en sistemas Fedora/CentOS/RedHat, ejecute lo siguiente desde la línea de comando:
$ sudo rpm -ivh CXXGraph-{version}.noarch.rpm
Para desinstalar:
$ sudo rpm -e CXXGraph-{version}
Para instalar en sistemas Debian/Ubuntu, ejecute lo siguiente desde la línea de comando:
$ sudo dpkg -i CXXGraph_{version}.deb
Para desinstalar:
$ sudo apt-get remove CXXGraph
Para instalaciones autocompiladas usando CMake, ejecute lo siguiente desde la línea de comando una vez que se complete la compilación:
$ sudo make install
La explicación de las clases se puede encontrar en la sección Clases de la documentación de Doxygen.
Para usar la biblioteca, simplemente coloque el archivo de encabezado donde lo necesite. ¡Es así de fácil!
Trabajo en progreso
La prueba unitaria requiere CMake 3.9 y posterior, y la biblioteca GoogleTest .
Prueba de Google
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 defaultDesde el directorio 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 # CompileUna vez compilada la compilación, ejecute el ejecutable "test_exe" en el directorio "build" con el siguiente comando:
./test_exe
Benchmark requiere CMake 3.9 y posterior, la biblioteca GoogleTest y la biblioteca Google Benchmark .
Punto de referencia de 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 installDesde el directorio 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 # CompileUna vez compilada la compilación, ejecute el ejecutable "benchmark" en el directorio "build" con el siguiente comando:
./benchmark
Puede consultar el resultado de la prueba comparativa utilizando este enlace.
Para crear un paquete tarball, ejecute lo siguiente desde la línea de comando:
# Enter Packaging Directory
$ cd packaging
# Execute the script to generate tarballs
$ ./tarballs.shPara crear un paquete RPM, ejecute lo siguiente desde la línea de comando:
# Enter Packaging Directory
$ cd packaging/rpm
# Execute the script to generate tarballs
$ ./make_rpm.shPara crear un paquete deb, ejecute lo siguiente desde la línea de comando:
# Enter Packaging Directory
$ cd packaging/deb
# Execute the script to generate tarballs
$ ./make_deb.shGráfico del algoritmo de ruta más corta de Dijkstra(La ruta más corta de Dijkstra) [Algoritmo de Dijkstra] (https://www.interviewbit.com/blog/find-shortest-path-dijkstras-algorithm/) se utiliza para encontrar la ruta más corta desde un nodo de origen hasta todos los demás nodos accesibles en el gráfico. Inicialmente, el algoritmo supone que todos los nodos son inalcanzables desde el nodo fuente dado, por lo que marcamos las distancias de todos los nodos como infinitas. (infinito) desde el nodo de origen (INF/infinito indica que no se puede alcanzar).
Especialización dial del algoritmo de dijkstra.
Cuando los pesos de los bordes son enteros pequeños (limitados por un parámetro C ), se pueden utilizar colas especializadas que aprovechan este hecho para acelerar el algoritmo de Dijkstra. El primer algoritmo de este tipo fue el algoritmo de Dial (Dial 1969) para gráficos con pesos de borde enteros positivos, que utiliza una cola de cubo para obtener un tiempo de ejecución O(|E|+|V|C) . (fuente wikipedia)
A continuación se muestra el algoritmo completo:
En este enlace puedes encontrar ilustraciones paso a paso.
Algoritmo de Prim El algoritmo de Prim es un algoritmo codicioso que encuentra un árbol de expansión mínimo para un gráfico no dirigido ponderado. Esto significa que encuentra un subconjunto de aristas que forma un árbol que incluye cada vértice, donde se minimiza el peso total de todas las aristas del árbol. El algoritmo opera construyendo este árbol un vértice a la vez, desde un vértice inicial arbitrario, agregando en cada paso la conexión más barata posible del árbol a otro vértice.
Pasos:
(Búsqueda de amplitud primero) Algoritmo de búsqueda de amplitud primero(Búsqueda de amplitud primero) Búsqueda de amplitud primero , también citado como BFS , es un algoritmo de recorrido de gráficos. Complejidad temporal O(|V| + |E|) donde V es el número de vértices y E es el número de aristas del gráfico. Las aplicaciones de Breadth First Search son:
Y hay muchos más...
(Búsqueda primero en profundidad) Algoritmo de búsqueda primero en profundidad (Búsqueda primero en profundidad) La búsqueda primero en profundidad , también citado como DFS , es un algoritmo de recorrido de gráficos. Complejidad temporal O(|V| + |E|) donde V es el número de vértices y E es el número de aristas en el gráfico. Las aplicaciones de Depth First Search son:
Y hay muchos más...
Best First Search Best First Search es una clase de algoritmos de búsqueda que atraviesa el gráfico explorando el nodo más prometedor elegido según una función de evaluación. La complejidad temporal del peor de los casos es O(n * log n) donde n es el número de nodos en el gráfico.
Ciclo (teoría de grafos)
La existencia de un ciclo en gráficos dirigidos y no dirigidos se puede determinar en función de si la búsqueda en profundidad (DFS) encuentra un borde que apunta a un antepasado del vértice actual (contiene un borde posterior). Todos los bordes posteriores que DFS omite son parte de ciclos. En un gráfico no dirigido, el borde del padre de un nodo no debe contarse como un borde posterior, pero encontrar cualquier otro vértice ya visitado indicará un borde posterior. En el caso de gráficos no dirigidos, solo se requiere tiempo O (n) para encontrar un ciclo en un gráfico de n-vértices, ya que como máximo n − 1 aristas pueden ser aristas de árbol.
Muchos algoritmos de clasificación topológica también detectarán ciclos, ya que esos son obstáculos para que exista el orden topológico. Además, si un grafo dirigido se ha dividido en componentes fuertemente conectados, los ciclos sólo existen dentro de los componentes y no entre ellos, ya que los ciclos están fuertemente conectados.
Para gráficos dirigidos, se pueden utilizar algoritmos basados en mensajes distribuidos. Estos algoritmos se basan en la idea de que un mensaje enviado por un vértice en un ciclo volverá a sí mismo. Los algoritmos de detección de ciclos distribuidos son útiles para procesar gráficos a gran escala utilizando un sistema de procesamiento de gráficos distribuido en un grupo de computadoras (o supercomputadora).
Las aplicaciones de la detección de ciclos incluyen el uso de gráficos de espera para detectar interbloqueos en sistemas concurrentes.
El algoritmo Bellman-Ford se puede utilizar para encontrar la distancia más corta entre un nodo de origen y un nodo de destino. Complejidad temporal O(|V| . |E|) donde V es el número de vértices y E es el número de aristas en el gráfico que es mayor que el algoritmo de ruta más corta de Dijkstra. La complejidad temporal del algoritmo de dijkstra es O(|E| + |V| log |v| ). La ventaja de bellman-ford sobre dijkstra es que puede manejar gráficos con pesos de borde negativos. Además, si el gráfico contiene un ciclo de peso negativo, entonces el algoritmo puede detectar e informar la presencia de un ciclo negativo.
Este vídeo ofrece una buena descripción general de la implementación del algoritmo. Esta conferencia del MIT da una prueba de la corrección de Bellman-Ford y su capacidad para detectar ciclos negativos. Aplicaciones:
Algoritmo de Floyd Warshall
Inicializamos la matriz de solución igual que la matriz del gráfico de entrada como primer paso. Luego actualizamos la matriz solución considerando todos los vértices como un vértice intermedio. La idea es seleccionar uno por uno todos los vértices y actualizar todos los caminos más cortos que incluyan el vértice elegido como vértice intermedio en el camino más corto. Cuando elegimos el vértice número k como vértice intermedio, ya hemos considerado los vértices {0, 1, 2, .. k-1} como vértices intermedios. Para cada par (i, j) de los vértices de origen y destino respectivamente, hay dos casos posibles.
Reducción transitiva
Este algoritmo se utiliza para construir un gráfico dirigido con la misma accesibilidad y satisface el cierre transitivo, con la menor cantidad de aristas posible. Más concretamente, crea un gráfico equivalente mínimo con la menor cantidad de aristas posible, eliminando rutas de "cortocircuito" a través del gráfico.
Esto se hace iterando a través de cada par de nodos, verificando si existen dos bordes que salen del primer nodo O del último nodo, eliminando el borde del par de nodos si existe.
En pseudocódigo: foreach x en Graph.vertices foreach y en Graph.vertices foreach z en Graph.vertices eliminar el borde xz si los bordes xy e yz existen
Nuestra implementación tiene puertas if que verifican tempranamente los bordes en múltiples lugares, lo que le da un tiempo de ejecución ligeramente más rápido que el pseudocódigo cúbico aquí.
El algoritmo de Kruskal se puede utilizar para encontrar el bosque de expansión mínima de un gráfico ponderado por bordes no dirigido. Complejidad del tiempo O (E log E) = O (E log V) donde V es el número de vértices y E es el número de aristas en el gráfico. La principal limitación de velocidad de este algoritmo es la clasificación de los bordes.
Para comprender rápidamente el procedimiento del algoritmo, consulte este video. Algunas de las aplicaciones de la vida real son:
Otros algoritmos para encontrar el bosque de expansión mínima son el algoritmo de Prim o el algoritmo de Borůvka.
El algoritmo de Borůvka es un algoritmo codicioso que se puede utilizar para encontrar un árbol de expansión mínimo en un gráfico, o un bosque de expansión mínimo en el caso de un gráfico que no está conectado.
El algoritmo comienza encontrando el borde de peso mínimo incidente en cada vértice del gráfico y agregando todos esos bordes al bosque. Luego, repite un proceso similar de encontrar el borde de peso mínimo de cada árbol construido hasta ahora en un árbol diferente y agregar todos esos bordes al bosque. Cada repetición de este proceso reduce el número de árboles, dentro de cada componente conectado del gráfico, a como máximo la mitad de este valor anterior, por lo que después de muchas repeticiones logarítmicas el proceso finaliza. Cuando lo hace, el conjunto de bordes que ha agregado forma el bosque de extensión mínima.
Se puede demostrar que el algoritmo de Borůvka toma O(log V) iteraciones del bucle externo hasta que termina y, por lo tanto, se ejecuta en el tiempo O(E log V), donde E es el número de aristas y V es el número de vértices en G (asumiendo E ≥ V).
Definición matemática del problema: Sea G el conjunto de nodos de un gráfico y n un nodo dado de ese conjunto. Sea C el subconjunto no estricto de G que contiene tanto n como todos los nodos alcanzables desde n, y sea C' su complemento. Hay un tercer conjunto M, que es el subconjunto no estricto de C que contiene todos los nodos a los que se puede acceder desde cualquier nodo en C'. El problema consiste en encontrar todos los nodos que pertenecen a C pero no a M.
Algoritmo actualmente implementado:
Solicitud:
Este algoritmo se utiliza en los sistemas de recolección de basura para decidir qué otros objetos deben liberarse, dado que un objeto está a punto de ser liberado.
El algoritmo Ford-Fulkerson es un algoritmo codicioso para encontrar un flujo máximo en una red de flujo. La idea detrás del algoritmo es la siguiente: siempre que haya una ruta desde la fuente (nodo inicial) hasta el sumidero (nodo final), con capacidad disponible en todos los bordes de la ruta, enviamos flujo a lo largo de una de las rutas. Luego encontramos otro camino, y así sucesivamente. Un camino con capacidad disponible se llama camino de aumento.
El algoritmo de Kosaraju es un algoritmo de tiempo lineal para encontrar los componentes fuertemente conectados de un gráfico dirigido. Se basa en la idea de que si uno es capaz de alcanzar un vértice v a partir del vértice u, entonces debería poder alcanzar el vértice u a partir del vértice v y si tal es el caso, se puede decir que los vértices u y v son fuertemente conectados: están en un subgrafo fuertemente conectado. A continuación se muestra un ejemplo:
1). Cree una pila vacía 'S' y realice un recorrido DFS de un gráfico. En el recorrido DFS, después de llamar a DFS recursivo para los vértices adyacentes de un vértice, empuje el vértice para apilarlo. 2). Invierta las direcciones de todos los arcos para obtener el gráfico de transposición. 3). Uno por uno, saque un vértice de S mientras S no esté vacío. Deje que el vértice reventado sea 'v'. Tome v como fuente y haga DFS (llame a DFSUtil(v)). El DFS a partir de v imprime el componente fuertemente conectado de v.
El algoritmo de Kahn encuentra el orden topológico eliminando iterativamente nodos en el gráfico que no tienen aristas entrantes. Cuando se elimina un nodo del gráfico, se agrega al ordenamiento topológico y se eliminan todos sus bordes, lo que permite seleccionar el siguiente conjunto de nodos sin bordes entrantes.
El algoritmo de coloración de Welsh Powell es un algoritmo de coloración de vértices codicioso. Este algoritmo también se utiliza para encontrar el número cromático de un gráfico.
El algoritmo Welsh Powell consta de los siguientes pasos:
El algoritmo devuelve un resultado std::map<Node, int> que asigna a cada nodo un color ordenado por números enteros. Los usuarios también pueden consultar el orden cromático mínimo del gráfico consultando el valor más alto del 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 ;
}La coloración mínima comienza desde 1 en lugar de 0.
El algoritmo supone que el gráfico no está dirigido. Todas las fuentes e inspiraciones están vinculadas en la declaración del algoritmo y los casos de prueba.
Una partición de corte de vértice divide los bordes de un gráfico en particiones del mismo tamaño. Los vértices que contienen los puntos finales de un borde también se colocan en la misma partición que el borde mismo. Sin embargo, los vértices no son únicos entre las particiones y es posible que deban replicarse (cortarse) debido a la distribución de sus bordes entre las diferentes particiones.
El factor de replicación cuantifica cuántos vértices se replican en las computadoras en comparación con el número de vértices del gráfico de entrada original.
Este algoritmo es un corte de vértice simple en forma de round-robin. Toma los bordes del gráfico original y los asigna a las particiones, dividiéndolos en tamaños iguales (o similares). Este algoritmo no se encarga de la optimización en la replicación de vértices (factor de replicación), sino que solo equilibra el borde en las particiones.
Los algoritmos de partición codiciosos utilizan el historial completo de las asignaciones de bordes para tomar la siguiente decisión. El algoritmo almacena el conjunto de particiones A(v) a las que se ha asignado cada vértice v ya observado y los tamaños de partición actuales. Al procesar el borde e ∈ E que conecta los vértices vi, vj ∈ V, el algoritmo codicioso sigue este simple conjunto de reglas:
El algoritmo de alto grado (son) replicado primero (HDRF) es un algoritmo codicioso de corte de vértices como se describe en este artículo. Este algoritmo intenta optimizar el factor de replicación utilizando el historial de asignaciones de bordes y el grado incremental de los vértices. Con una función que toma en consideración estos dos factores calcula la mejor partición para asignar el borde analizado. Las réplicas creadas se basan en el grado de los vértices, y los vértices replicados probablemente sean los llamados "Hub-Node", que son los vértices con mayor grado.
El corte de vértices eficiente y equilibrado (EBV) es un algoritmo de corte de vértices fuera de línea como se describe en este documento. Este algoritmo intenta equilibrar las particiones con respecto al número de aristas y vértices de cada partición y el factor de replicación. Aplica una fórmula para evaluar la partición en la que se asigna la arista que tiene en cuenta también el número total de aristas y vértices del gráfico. La fórmula de evaluación es la siguiente:
El valor más bajo se toma como ID de partición.
La matriz de grados es una matriz cuadrada que proporciona información sobre la conectividad de los nodos en un gráfico. Para gráficos dirigidos, refleja el número de aristas entrantes y salientes para cada nodo, mientras que para gráficos no dirigidos, representa el número de aristas incidentes en cada nodo.
La matriz laplaciana es una matriz cuadrada derivada de la matriz de adyacencia y la matriz de grados de un gráfico. Es fundamental para analizar diversas propiedades del gráfico, como la conectividad, el recuento de árboles de expansión y otras características espectrales.
La Matriz de Transición se utiliza comúnmente en el estudio de Cadenas de Markov y procesos estocásticos. Dentro del contexto de un gráfico, denota las probabilidades de transición de un nodo a otro, a menudo en función de los pesos de los bordes o criterios predeterminados. Esta matriz encuentra aplicaciones en diversos campos, como el análisis de redes, el aprendizaje automático y la optimización.
Si desea brindar su apoyo, puede crear una solicitud de extracción o informar un problema . Si desea cambiar el código, solucionar un problema o implementar una nueva función, lea nuestra Guía de CONTRIBUCIÓN.
Si desea analizar nuevas funciones o tiene alguna pregunta o sugerencia sobre la biblioteca, abra una discusión o simplemente charle en
Sitio CXXGraph
Correo electrónico: [email protected]
Perfil de GitHub
Para apoyarme, agrega una estrella al proyecto o sígueme
Para mantenerse actualizado, vea el proyecto.
Nos referencian:
Gracias a la comunidad de TheAlgorithms por inspirarme en los algoritmos.
Gracias a GeeksForGeeks por inspirarnos en un algoritmo.
¡Gracias a todas las personas que ya han contribuido a CXXGraph!
Si utiliza este software, siga las instrucciones de la CITACIÓN. ¡Gracias!
Participamos en Hacktoberfest 2021. ¡Gracias a todos los contribuyentes!
Participamos en Hacktoberfest 2022. ¡Gracias a todos los contribuyentes!
Participamos en Hacktoberfest 2023. ¡Gracias a todos los contribuyentes!
Ver el valor estimado del proyecto
@ZigRazor |
|---|
